Bài Giảng Automat_C3 - BG Automat - Chu Thị Thanh Xuân

Trang chủ » định Lý Kleene » Bài Giảng Automat_C3 - BG Automat - Chu Thị Thanh Xuân

Có thể bạn quan tâm

Đăng nhập / Đăng ký
  • Trang chủ
  • Thành viên
  • Trợ giúp
  • Liên hệ

Đăng nhập

Tên truy nhập Mật khẩu Ghi nhớ   Quên mật khẩu ĐK thành viên

Thông tin

  • Giới thiệu bản thân
  • Thành tích
  • Chia sẻ kinh nghiệm
  • Lưu giữ kỉ niệm
  • Hình ảnh hoạt động
  • Soạn bài trực tuyến

Tài nguyên dạy học

Các ý kiến mới nhất

Hỗ trợ trực tuyến

Điều tra ý kiến

Bạn thấy trang này như thế nào? Đẹp Đơn điệu Bình thường Ý kiến khác

Thống kê

  • 7084 truy cập (chi tiết) 2 trong hôm nay
  • 15064 lượt xem 2 trong hôm nay
  • 22 thành viên

    • Ảnh ngẫu nhiên

    Thành viên trực tuyến

    1 khách và 0 thành viên Đưa bài giảng lên Gốc > Bài giảng > BG Automat >
    • Bài giảng Automat_C3
    • Cùng tác giả
    • Lịch sử tải về

    Bài giảng Automat_C3 Download Edit-0 Delete-0

    Wait
    • Begin_button
    • Prev_button
    • Play_button
    • Stop_button
    • Next_button
    • End_button
    • 0 / 0
    • Loading_status
    Nhấn vào đây để tải về Báo tài liệu có sai sót Nhắn tin cho tác giả (Tài liệu chưa được thẩm định) Nguồn: Người gửi: Chu Thị Thanh Xuân (trang riêng) Ngày gửi: 10h:30' 23-03-2018 Dung lượng: 852.0 KB Số lượt tải: 7 Số lượt thích: 4 người (Đặng Xuân Phương, Phạm văn minh, Trương Đức Mạnh, ...) Chương 3AUTOMAT HỮU HẠN12 Định nghĩa ô tô mát hữu hạn Biểu diễn ô tô mát hữu hạn Hàm chuyển của xâu đầu vào. Ngôn ngữ được đoán nhận bởi ô tô mát hữu hạn Ô tô mát không đơn địnhSự tương đương ôtômát đơn địnhvà ôtômát không đơn địnhQuan hệ giữa NNCQ, ô tô mát và VPCQMột số ví dụ.Nội dung3 Một Automat hữu hạn M={Q, I, f, q0, F}: 1. tập hữu hạn Q các trạng thái, 2. một bộ các đầu vào I, 3. một hàm chuyển f : (trạng thái - đầu vào) trạng thái tiếp theo 4. trạng thái xuất phát q0, và 5. tập con F của Q, bao gồm các trạng thái kết thúc.Biểu diễn ôtômát hữu hạn: bằng bảng trạng thái hoặc đồ thị chuyển trạng thái.Ví dụ 1. Dựng đồ thị chuyển trạng thái của ôtômát hữu hạn M={Q,I,f, q0, F} với Q={q0, q1, q2, q3}, I={0,1}, F={q0, q3} còn hàm chuyển f được cho trong Bảng 1.1. Định nghĩa Automat hữu hạn4 q0q1q3q20011100,1Xuất phátq0,q3 – trạng thái kết thúcHai cách biểu diễn ôtômát2. Biểu diễn ôtômat hữu hạn5Định nghĩa hàm chuyển đối với một cặp trạng thái, xâu đầu vào f(q,x):Giả sử x= x1x2..xk là một xâu trong I. Khi đó f(q1, x) là một trạng thái nhận được bằng cách dùng tuần tự các ký hiệu của x từ trái sang phải làm đầu vào, bắt đầu với trạng thái q1. Từ q1  q2 =f(q1, x1) q3=f(q2, x2).. và qk+1= f(qk, xk). Vậy f(q1, x)=qk+1.Xâu x gọi là được đoán nhận bởi máy M={Q,I,f, q0, F } nếu nó đưa trạng thái xuất phát tới một trạng thái kết thúc, tức là f(q0, x)  F.3. Hàm chuyển của xâu đầu vàoMột ngôn ngữ được máy M đoán nhận, ký hiệu L(M) là tập tất cả các xâu được đoán nhận bởi M. Hai ôtômát hữu hạn là tương đương nếu đoán nhận cùng một ngôn ngữ. Ví dụ 2. Xác định ngôn ngữ đoán nhận bởi các ôtômát M1, M2, M3 trên Hình 2. Xuất phát L(M1)= {1n | n=0,1,2,.. } q0q100,114. Ngôn ngữ đoán nhận bởi ôtômát67Còn M2 0 1 và M3 0 0 0,1 1 1 0,1q0q1q2q3Xuất phát L(M2) = {1, 01}q1q2q0q3L(M3) = {0n, 0n10x | n=0,1,2,.., v x l xõu b?t k?}100,14. Ngôn ngữ đoán nhận bởi ôtômátVí dụ 3. Cho Ôtô mát đơn định M={Q, I, f, q0, F} với Q= {q0, q1, q2, q3}, I= {0,1 }, q0 trạng thái ban đầu, F= {q3 } trạng thái kết thúc, hàm chuyển f được cho như sau: Vậy M đoán nhận xâu 1 = 10110b) Với 2=110 4. Ngôn ngữ đoán nhận bởi ôtômát8 dãy trạng thái của M là: 2 = 1 1 0 $     q0  q2  q3q3F; M đoán nhận xâu 2 = 110c) Với xâu 3=10011 dãy trạng thái của M là: 3 = 1 0 0 1 1 $       q0 q2  q0 q1 q0q2 F nên máy M không đoán nhận xâu này.Quá trình đoán nhận một xâu đối với ôtômát đơn định là qt biến đổi từ trạng thái ban đầu đến trạng thái cuối cùng có phải là trạng thái kết thúc không.94. Ngôn ngữ đoán nhận bởi ôtômát10Định nghĩa: Một ôtômát hữu hạn không đơn định M={Q, I, f, q0, F} gồm: một tập hữu hạn Q các trạng thái, một bộ các đầu vào I, một hàm chuyển f gán cho mỗi cặp trạng thái- đầu vào, một tập các trạng thái, trạng thái xuất phát q0, và tập con F của Q, gồm các trạng thái kết thúc. Biểu diễn ôtômát hữu hạn không đơn định bằng bảng trạng thái hoặc đồ thị chuyển trạng thái.5. Ôtômát không đơn định11Ví dụ 4. Tìm đồ thị chuyển trạng thái cho ôtômát hữu hạn không đơn định với bảng trạng thái ở bên, các trạng thái kết thúc là q2 và q3.5. Ôtômát không đơn định1215. Ôtômát không đơn địnhÔtômat hữu hạn không đơn địnhNgôn ngữ được đoán nhận bởi ôtômát không đơn địnhVí dụ 5. Cho ôtômát không đơn định M= với I= {0, 1 }, Q= {q0, q1, q2, q3, q4}; q0 trạng thái ban đầu; F= { q2, q4 }- tập trạng thái kết thúc. Hàm chuyển như bên cạnh. Với ô tô mát không đơn định hàm chuyển f (q,a)  Q nên sẽ có rẽ nhánh. Lập dãy trạng thái của máy ứng với xâu đầu vào dưới dạng một cây gốc q0.135. Ôtômát không đơn địnhTrong cây này nếu có một đường đi từ gốc q0 tới một lá chứa trạng thái kết thúc, thì M đoán nhận xâu vào đang xét. Nếu không có một lá nào như vậy thì M không đoán nhận xâu này.Chẳng hạn với xâu vào 1=01001 đối với máy M trên cây đoán nhận xâu này;Xâu 2=010 không được đoán nhận14q0q3q0q3q1q3q1q0q0q0q0q4q40001110110000115. Ôtômát không đơn địnhTheo định nghĩa ô tô mát đơn định và ô tô mát không đơn định thì lớp ngôn ngữ đoán nhận bởi ô tô mát đơn định(M) nằm trong lớp ngôn ngữ đoán nhận bởi ô tô mát không đơn định (N). Và người ta cũng chứng minh điều ngược lại: lớp ngôn ngữ đoán nhận bởi ô tô mát không đơn định nằm trong lớp ngôn ngữ đoán nhận bởi ô tô mát đơn định. Hay:Định lý 1 . Lớp ngôn ngữ đoán nhận bởi ô tô mát đơn định trùng với lớp ngôn ngữ đoán nhận bởi ô tô mát không đơn định trên bảng ký tự I hay L(M)=L(N)6.Sự tương đương của Ô đơn định và không đơn định15Xây dựng ô tô mat đơn định tương đương theo cách sau:Cho ô tô mat không đơn định M=< Q,I,F,q0,f>. Xây dựng ô tô mat đơn định M’=< S,I’, F’,s0,f’> sao cho:I’=I của M;Tập trạng thái: =tập tất cả các tập con của Q, và s0 = {q0 }F’= {s | s  S và s  F   }f’ :S x I* S; xác định với mọi s S và mọi x  I* có: Khi đó M’ là ô tô mat đơn định và M’  M.166.Sự tương đương của Ô đơn định…Ví dụ 6. Cho ô tô mát không đơn định M={Q, I, f, q0, F} Hãy tìm L(M)=?Xây dựng ô tô mát đơn định M’ tương đương M?Bài giải. L(M)= {0n, 0m1k , 01l | n≥1, m≥1,k≥1, l≥0 Xây dựng M’ đơn định và tương đương với M 17q0q1q2110006.Sự tương đương của Ô đơn định…X. phátb) Xây dựng ô tô mát đơn định tương đương như sau:M’=< S, I’, f’, s0, F’ >; I’= I = {0,1 }S= {s0, s1, s2, s3, s4, s5, s6, s7} trong đós0=q0, s1=q1, s2=q2, s3= {q0, q1}, s4= {q0, q2}, s5= {q1, q2}, s6= {q0, q1,q2}, s7=  Hàm chuyển f’ như sau:s0=q0 là trạng thái ban đầu, F’= {s1, s2 ,s3, s4, s5,s6 }- tập trạng thái kết thúc.6.Sự tương đương của Ô đơn định…18Ví dụ 7. Cho ô tô mat không đơn định M=: a) Đưa M về dạng đồ thị chuyển b) Xây dựng ô tô mat đơn định M’=MBài giải: a) Đồ thi chuyển của M:19q0q1q2q310100,1110100q0 trạng thái ban đầu;F={q2, q3} - tập trạng thái kết thúc6.Sự tương đương của Ô đơn định…M’=< S, I, f’, s0, F’ >; I= {0,1 }S={s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, s13, s14, s15} trong đó: s0=q0, s1=q1, s2=q2, s3=q3; s4= {q0, q1}, s5= {q0, q2 }, s6= {q0, q3}, s7= {q1, q2}, s8= {q1, q3}, s9= {q2, q3}; s10= {q0, q1,q2}, s11= {q0, q1,q3}, s12={q0, q2,q3}; s13={q1,q2,q3}, s14= {q0, q1,q2, q3}; s15 =  ;s0 = {q0} - trạng thái ban đầu.F’= { s2 ,s3, s5, s6,s7 ,s8, s9 ,s10, s11, s12,s13, s14};Hàm chuyển f’ như sau: 6.Sự tương đương của Ô đơn định…20Hàm chuyển như bảng sau:216.Sự tương đương của Ô đơn định…Định lý 2 (Định lý Kleene). Tập A là NNCQ trên bảng I khi và chỉ khi nó được đoán nhận bởi ô tô mát M={S, I, f, s0, F} sao cho L(M)=A.Định lý 3 . Đối với VPCQ suy rộng bất kỳ G=(T,N,s0,P) bao giờ cũng xây dựng được ô tô mát hữu hạn M={S, I, f, q0, F} sao cho L(M)=L(G).Và ngược lại: Đối với ô tô mát hữu hạn bất kỳ M={S, I, f, q0, F} bao giờ cũng xây dựng được VPCQ suy rộng G=(T,N,s0,P) sao cho L(G)=L(M).7.Quan hệ giữa NNCQ, ô tô mát và VPCQ2223 BTCQ (suy rộng)VPCQ(suy rộng)NNCQ (suy rộng)Sinh raBiểu diễnAUTOMATHỮU HẠNĐoán nhận xây dựng xây dựng 7.Quan hệ giữa NNCQ, ô tô mát và VPCQVí dụ 1. Cho ô tô mát M= Bài giải. a) M không đơn định vì f(q0,a)={q0, q1}. Bảng 1. là bảng chuyển.q0q1q2q3aaabbbX.phátM đơn định hay không? Đưa về dạng bảng chuyển.Tìm L(M)=?Tìm BTCQ của L(M)Xây dựng VPCQ G sao cho L(G)=L(M)8. Một số ví dụ24Q={q0, q1, q2, q3};I= {a,b }; q0trạng thaí ban đầu,F= {q0, q3 }b)L(M)= {an,anb,am a(bb)ka| n,m,k≥0 },Chỉ ra các xâu được M đoán nhận;f(q0, )=q0, f(q0, aa)=f(q0, a)  f(q1, a)= {q0, q1}  {q3 }={q0, q1, q3};Do f(q0, aa)  F  nên aa được đoán nhận.f(q0, b)=q3 mà q3 F nên xâu b được đoán nhận.Tương tự cho các trường hợp còn lại.q0-trạng thái ban đầu; F= {q0, q3, }8. Một số ví dụ25c) BTCQ là a*a*b a*a(bb)*ad) Xây dựng VPCQ G=, T={a,b}, N={S, A,B} P={S,SaS, Sb, SaA, AaA, AbB, BbA, Aa}CM: L(G)= {,an,anb, am(bb)ka| n,k≥0 , m1}Vậy L(G)=L(M)Ví dụ 2 Cho L={ab(cdcd)nba,xmaba, b(xy)kxb| n,k≥0,m≥1}a) Xây dựng ô tô mat đơn định sao cho L(M)=L;b) Xây dựng VPCQ suy rộng sao cho L(G)=Lc) Chỉ ra BTCQ của L.Bài giải. 8. Một số ví dụ2627a) Sơ đồ của M:Dễ thấy L(M)={ab(cdcd)nba,xmaba, b(xy)kxb| n,k≥0,m≥1}Chứng minh? Nên L(M)=Ls0s6s5s4s3s2s1s7s10s8s11s9X.phátybbaxabdcdcbaxxb8. Một số ví dụ28b)VPCQ G= T= {a,b,c,d,x,y}, N= {S, … }P= {SaA, AbB, BcC,CdD, DcE, EdB, BbF, Fa, SxH, HxH, HaK, KbF, SbL, LxR, RyL,Rb};VP này sinh Ngôn ngữ L(G):CM L(G) ={ab(cdcd)nba,xmaba, b(xy)kxb| n,k≥0,m≥1}D(abba)=D(S,aA, abB, abbF, abba)D(xaba)=D(S,xH,xaK, xabF,xaba)D(bxb)=D(S,bL,bxR, bxb) …c) BTCQ biểu diễn NNCQ L là;BTCQ= ab(cdcd)*ba  xx*aba b(xy)*xb8. Một số ví dụ29Ví dụ 3.Cho BTCQ: 0(11)*000*1010*a) Tìm L là NNCQ biểu diễn bởi BTCQ trên . b) Xây dựng VPCQ suy rộng G sao cho L(G)=Lc) Xây dựng ô tô mat M sao cho L(M)=L(G).Bài giải. a) L={0(11)n0, 00m10, 10k, | n,m,k≥0}b) G=; T={1,0}, N={…}P={S , S0A, A1B, B1A, A0, S0C, C0C,C1D, D0, S1E, E0E, E };VPCQ suy rộng này sinh L tức là L(G)=L thật vậy:8. Một số ví dụ30D()=D(S,)D(0(11)n0)=D(S,0A,01B,011A,..,0(11)nA, 0(11)n0)D(00m10)=D(S,0C,0(0)m1D,0(0)m10)D(10k)=(S,1E,10E,…,10kE, 10k);Là các dẫn xuất đầy đủ trong L(G).c) Ô tô mát M mà L(M)=L(G)=L:q0q4q2q1q6q3q501000101108. Một số ví dụ31Ta thấy: f(s0,0(11)n0)=f(s4,(11)n0) f(s1,(11)n0)=f(s2, 1(11)n-10) = f(s1,(11)n-10)=…=f(s1,0)=s3F; f(s0,00m10)=f(s4,0m10) f(s1,0m10)=f(s4, 0m-110) = f(s4,10)=f(s5,0)=s3F; f(s0,10k)=f(s6,0k)= f(s6,0k-1)=…= f(s6,0)=s6 F; f(s0,)=q0 F; 8. Một số ví dụ3233Bài tập về nhà   ↓ ↓ Gửi ý kiến

    Chào mừng quý vị đến với website của Chu Thị Thanh Xuân

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tài liệu của Thư viện về máy tính của mình. Nếu chưa đăng ký, hãy nhấn vào chữ ĐK thành viên ở phía bên trái, hoặc xem phim hướng dẫn tại đây Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay phía bên trái. Website được thừa kế từ Violet.vn, người quản trị: Chu Thị Thanh Xuân

    Từ khóa » định Lý Kleene