Hướng dẫn giải bài toán turning đoán nhận ngôn ngữ
- 1. niệm về ngôn ngữ, từ [chuỗi, xâu], một số phép toán cơ bản trên từ và trên ngôn ngữ. Các hình thức biểu diễn ngôn ngữ. Cho ví dụ minh họa...................................................3 Câu 2 : Định nghĩa văn phạm, dẫn xuất và ngôn ngữ sinh bởi văn phạm. Cho ví dụ minh họa. ...................................................................................................................................................4 Câu 3: Định nghĩa văn phạm, Phân loại văn phạm theo Chomsky, sự khác biệt giữa các loại văn phạm. Cho ví dụ minh họa..................................................................................................4 Câu 4: Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P >, hãy chỉ ra rằng xâu w khác rỗng nằm trong L[G] khi tồn tại cây dẫn xuất trong văn phạm G mà các nút lá của nó tạo nên xâu w....5 Câu 5: Chứng minh ngôn ngữ sinh ra bởi văn phạm là đóng với phép hợp..............................6 Câu 6: Chứng minh ngôn ngữ sinh ra bởi văn phạm là đóng với phép ghép [nối kết].............7 Câu 7: Cho G = < Σ, Δ, S, P > không phải là văn phạm loại 0 với ký tự xuất phát S có ở vế phải của quy tắc dẫn xuất, chỉ ra rằng tồn tại văn phạm G = < Σ’, Δ’, S’, P’ > cùng loại và tương đương với G không có ký tự xuất phát ở vế phải của quy tắc dẫn xuất..........................8 Câu 8: Khái niệm về văn phạm phi ngữ cảnh, khái niệm về dẫn xuất và cây dẫn xuất, sự nhập nhằng của văn phạm. Ví dụ minh họa.......................................................................................8 Câu 9: Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P > không chứa xâu rỗng, trình bày giải thuật loại bỏ các ký hiệu thừa, luật sinh ε, luật sinh đơn vị.......................................................9 Câu 10: Định nghĩa luật sinh . Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P > không chứa xâu rỗng, không chứa các ký hiệu thừa, trình bày giải thuật loại bỏ luật sinh .......................10 Câu 11:Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P > không chứa xâu rỗng, không chứa các ký hiệu thừa, không chứa luật sinh ε. Trình bày giải thuật loại bỏ luật sinh đơn vị. ..............10 Câu 12: Trình bày các bước chuẩn hóa văn phạm phi ngữ cảnh về dạng chuẩn Chomsky tương đương............................................................................................................................11 Câu 13: Cho ví dụ minh hoạ chuyển một văn phạm phi ngữ cảnh về dạng chuẩn Chomsky tương đương............................................................................................................................12 Câu 14:Trình bày các bước chuẩn hóa văn phạm phi ngữ cảnh về dạng chuẩn Greibach [không cần nêu ví dụ minh họa]..............................................................................................13 Câu 15: Trình bày khái niệm về automat hữu hạn. Phân biệt các dạng automata hữu hạn. Ngôn ngữ đoán nhận bởi automata hữu hạn. Ví dụ minh họa.................................................13 Câu 16: Khái niệm về Automata mealy, automata moore; phân biệt chúng với automat hữu hạn; lấy ví dụ minh hoạ...........................................................................................................14 Câu 17: Trình bày các phương pháp biểu diễn automata hữu hạn. Ví dụ minh họa...............16 Câu 18 : Trình bày thuật toán đoán nhận chuỗi bởi một âutomt hữu hạn cho trước. Ví dụ minh hoạ..................................................................................................................................17 Câu 19 :Trình bày phương pháp biến đổi từ automata không đơn định về automata đơn định [đưa NFA về DFA]..................................................................................................................18 Câu 20 : Trình bày phương pháp biến đổi từ automata không đơn định có dịch chuyển-ε về automata không đơn định và không có dịch chuyển-ε [đưa NFAε về NFA]. Dẫn ví dụ minh họa...........................................................................................................................................19 Câu 21: Trình bày phương pháp biến đổi từ automat ko đơn định có dịch chuyển về automat đơn định[đưa NFA về DFA].Dẫn VD minh họa.....................................................................20 Câu 22: Định nghĩa biểu thức chính quy. Thuật toán để xây dựng automata từ biểu thức chính quy gọi là thuật toán Thomson,trình bày thuật toán Thomson......................................21 Câu 23: Định nghĩa biểu thức chính quy, trình bày thuật toán xây dựng biểu thức chính quy từ một automata hữu hạn cho trước.........................................................................................22
- 2. niệm về văn phạm chính quy. Trình bày thuật toán xây dựng một automata hữu hạn từ một văn phạm chính quy tuyến tính phải.....................................................................23 Câu 25: Khái niệm về văn phạm chính quy. Trình bày thuật toán xây dựng một automata hữu hạn từ một văn phạm chính chinh quy tuyến tính trái.............................................................23 Câu 26: Khái niệm về văn phạm chính quy. Trình bày thuật toán xây dựng văn phạm chính chính quy tuyến tính phải từ một automata hữu hạn cho trước. Ví dụ minh hoạ....................24 Câu 27: Khái niệm về văn phạm chính quy. Trình bày thuật toán xây dựng một automata hữu hạn cho trước. Ví dụ minh hoạ................................................................................................24 Câu 28: Phát biểu bổ đề bơm[pumping lemma] cho tập hợp chính quy, giải thích, ý nghĩa bổ đề bơm.Lấy ví dụ minh họa.....................................................................................................25 Câu 29: Những phép toán nào là đóng với tập hợp chính quy?Lấy vd minh họa...................27 Câu 30: Những phép toán nào là đóng với văn phạm phi ngữ cảnh?Lấy vd minh họa..........28 Câu 31: Phát biểu bổ đề bơm[pumping lemma] cho tập hợp[ngôn ngữ] phi ngữ cảnh.Vd minh họa[ dùng để chứng minh cho 1 ngôn ngữ không là ngôn ngữ phi ngữ cảnh]..............30 Câu 32:Định nghĩa pushdown automata,giải thích các thành phần.Vd minh họa...................30 Câu 33: Phận biệt PDA đơn định và PDA không đơn định....................................................31 Câu 34: Nêu khái niệm máy Turing, các kỹ thuật xây dựng máy Turing, lớp ngôn ngữ đoán nhận bởi máy Turing...............................................................................................................31 Câu 35: Nêu khái niệm automata tuyến tính giới nội, lớp ngôn ngữ đoán nhận bởi automata tuyến tính giới nội...................................................................................................................32
- 3. niệm về ngôn ngữ, từ [chuỗi, xâu], một số phép toán cơ bản trên từ và trên ngôn ngữ. Các hình thức biểu diễn ngôn ngữ. Cho ví dụ minh họa. *Tập ∑ khác rỗng gồm hữu hạn hay vô hạn các ký hiệu được gọi là bảng chữ cái.Mỗi phần tử a Є ∑ được gọi là một chữ cái hay một kí hiệu. -Giả sử có bảng chữ cái ∑={ , ,…, }, một dãy các chữ cái α = , ,…, với Є ∑[1 ≤ j ≤ t] được gọi là một từ hay một xâu trên bảng chữ cái ∑. VD: Ta có ,0,01,101,1010,110011 là các từ trên bảng chữ cái ∑={0,1}. -Cho bảng chữ cái ∑,mỗi tập con L ∑* được gọi là một ngôn ngữ hình thức trên bảng chữ cái ∑.Ngôn ngữ rỗng là ngôn ngữ trên mọi bảng chữ cái. VD:L={ ,0,1,01,10,00,11,011,100} là một ngôn ngữ trên bảng chữ cái ∑={0,1}. *Một số phép toán cơ bản trên từ -Phép nối kết: Nối kết của 2 từ α = … và từ β = … trên bảng chữ cái ∑ là từ = … … trên bảng chữ cái ∑. Kí hiệu = α β = β α -Phép đảo ngược: Giả sử có từ khác rỗng ω = … trên bảng chữ cái Σ, khi đó từ … được gọi là từ ngược của từ ω, và được ký hiệu là hay . Khi = ta quy ước = . -Phép chia từ: là phép cắt bỏ phần đầu hay phần cuối của một từ.Phép cắt trái của từ α cho β là phần còn lại của từ α sau khi cắt bỏ phần đầu β trong từ α. Phép cắt phải của từ α cho β là phần còn lại của từ α sau khi cắt bỏ phần đuôi β trong từ α. *Phép toán trên ngôn ngữ:Vì mỗi ngôn ngữ là 1 tập hợp nên ta có các phép toán đại số tổ hợp trên các ngôn ngữ. -Phép hợp : ={ Є ∑*| Є or Є } -Phép giao : ={ Є ∑*| Є and Є } -Phép phần bù : [L] = ∑*L -Phép nhân ghép : = { | Є và Є } trên bộ chữ cái LLL…LL = kết nối i lần trên cùng ngôn ngữ L] ={ } -Phép lặp: L* = ={ } L … Ngôn ngữ lặp cắt: = = L … -Phép lấy ngôn ngữ ngược: = { | } -Ngôn ngữ cắt trái của ngôn ngữ X cho ngôn ngữ Y: Z = Y/X = {z Є | x Є X,y Є Y mà x=yz} -Ngôn ngữ cắt phải của ngôn ngữ X cho ngôn ngữ Y: Z = X/Y = {z Є ∑* | x Є X,y Є Y mà x=zy} *Các hình thức biểu diễn ngôn ngữ: Đối với các ngôn ngữ hữu hạn, để biểu diễn chúng một cách đơn giản ta chỉ cần liệt kê tất cả các chuỗi thuộc vào chúng. Chẳng hạn : L1 = {ε}
- 4. a, ba, aaba, bbbbb } Trong những trường hợp không phức tạp lắm, người ta thường xác định các chuỗi bằng cách chỉ rõ một đặc điểm chủ yếu chung cho các chuỗi đó. Đặc điểm này thường được mô tả qua một phát biểu hay một tân từ. Chẳng hạn : L3 = { ai | i là một số nguyên tố } L4 = { ai bj | i ≥ j ≥ 0 } L5 = { w ∈ { a, b}* | số a trong w = số b trong w } Câu 2 : Định nghĩa văn phạm, dẫn xuất và ngôn ngữ sinh bởi văn phạm. Cho ví dụ minh họa. *Theo từ điển, văn phạm là 1 tập hợp các quy tắc về cấu tạo từ và các quy tắc về cách thức liên kết từ lại thành câu. Văn phạm G là một bộ sắp thứ tự gồm 4 thành phần: G= Trong đó: -∑ là một bảng chữ cái cơ bản, mỗi phần tử của nó được gọi là 1 ký hiệu kết thúc[hay là ký hiệu cơ bản] là 1 bảng chữ cái, , gọi là bảng ký hiệu phụ S Є được gọi là ký hiệu xuất phát hay tiên đề P là tập hợp các quy tắc sinh có dạng , Є [∑ ]*, trong chứa ít nhất 1 ký tự không kết thúc. P = { | = A , với A , , [∑ ] *} VD: G = là một văn phạm. *Dẫn xuất: -Dẫn xuất trực tiếp: nếu là một luật sinh thì -Dẫn xuất gián tiếp: nếu các chuỗi , ,…, Є ∑* và , , …, thì có thể được dẫn xuất gián tiếp từ : *Ngôn ngữ L sinh bởi văn phạm G: L[G] = {w | w và S } VD: G = L[G] = { | n 0}. Câu 3: Định nghĩa văn phạm, Phân loại văn phạm theo Chomsky, sự khác biệt giữa các loại văn phạm. Cho ví dụ minh họa. *Theo từ điển, văn phạm là 1 tập hợp các quy tắc về cấu tạo từ và các quy tắc về cách thức liên kết từ lại thành câu. Văn phạm G là một bộ sắp thứ tự gồm 4 thành phần: G = Trong đó: -∑ là một bảng chữ cái cơ bản, mỗi phần tử của nó được gọi là 1 ký hiệu kết thúc[hay là ký hiệu cơ bản]
- 5. chữ cái, , gọi là bảng ký hiệu phụ S Є được gọi là ký hiệu xuất phát hay tiên đề P là tập hợp các quy tắc sinh có dạng , Є [∑ ]*, trong chứa ít nhất 1 ký tự không kết thúc. P = { | = A , với A , , [∑ ] *} VD: G = là một văn phạm. *Phân loại văn phạm theo Chomsky: dựa vào tính chất các luật sinh -Văn phạm loại 0[văn phạm ko hạn chế-Unrestricted Grammar]: ko cần thỏa mãn điều kiện ràng buộc nào trên tập các luật sinh. -Văn phạm loại 1[văn phạm cảm ngữ cảnh-Context Sensitive Grammar]: nếu văn phạm G có các luật sinh dạng và = A , với A , , [∑ ] *, | | ≥ | |. VD: G[{a,b,c},{S,B,C},P,S],P={S S CB BC, aB ab, bB bb, bC bc, cC cc}. Đây là văn phạm loại 1. -Văn phạm loại 2[văn phạm phi ngữ cảnh-Context Free Grammar] có luật sinh dạng A với A là một biến đơn và là chuỗi các ký hiệu thuộc [∑ ] *. VD: G = [{a,b}, {S}, S, P], P = {S aSb, S ab} đây là văn phạm loại 2 dạng A . -Văn phạm loại 3[văn phạm chính quy RG] có mọi luật sinh dạng tuyến tính phải hoặc tuyến tính trái. Tuyến tính phải: A wB hoặc A w Tuyến tính trái: A [với A,B là các biến đơn,w là chuỗi ký hiệu kết thúc,có thể là rỗng]. VD:G = [{a,b}, {S,A},S,P] trong đó P={S b}. sssĐây là văn phạm loại 3 dạng tuyến tính phải. *Nếu ký hiệu , , , là lớp các ngôn ngữ được sinh ra bởi các loại văn phạm loại 0,1,2,3 tương ứng thì ta có . Câu 4: Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P >, hãy chỉ ra rằng xâu w khác rỗng nằm trong L[G] khi tồn tại cây dẫn xuất trong văn phạm G mà các nút lá của nó tạo nên xâu w. Cho văn phạm: S→aAS; A→SbA ; A→SS; S→a; A→ba Xét chuỗi: S → aAS → aSbAS → aabAS → aabbaS → aabbaa sHiển nhiên xâu w khác rỗng nằm trong L[G] khi tồn tại cây dẫn xuất trong văn phạm G mà các nút lá của nó tạo nên xâu w.
- 6. minh ngôn ngữ sinh ra bởi văn phạm là đóng với phép hợp. Cách 1: Giả sử , là các ngôn ngữ được sinh bởi văn phạm =< >, =< >, tức là =L[ ], =L[ ]. Ta chứng minh tồn tại văn phạm G sao cho L[G] = . Xây dựng văn phạm G sinh ra ngôn ngữ như sau: G = với ∑ = , = {S}, P = {S S } Ta sẽ chứng minh L[G] = bằng cách chứng minh hai bao hàm thức: a.Chứng minh L[G] : Giả sử L[G], khi đó tồn tại một suy dẫn trong văn phạm G: S| , trong đó =[ *. Do cách xây dựng tập quy tắc P, nên trong suy dẫn S|= có hai khả năng: +hoặc S| | , vậy là kết quả của suy dẫn |= trong , do đó L[ ].[#] +hoặc S| | , vậy là kết quả của suy dẫn |= trong , do đó L[ ].[$] Từ [#] và [$], ta thấy , hay L[G] b.Chứng minh L[G]:Giả sử , khi đó ta cũng có hai khả năng: hoặc : +Nếu =L[ ], khi đó ta có suy dẫn | trong , do đó ta cũng có suy dẫn S| | là một suy dẫn trong G[vì theo cách xây dựng G, mọi quy tắc và mọi ký hiệu trong cũng đều thuộc G ], như vậy L[G] +Nếu =L[ ], khi đó ta có suy dẫn | trong , do đó ta cũng có suy dẫn S| | là một suy dẫn trong G[vì theo cách xây dựng G, mọi quy tắc và mọi ký hiệu trong cũng đều thuộc G ], như vậy L[G] Vậy ta luôn luôn có L[G], do đó L[G].Tức là ta đã c/m được L[G] =
- 7. hoặc gặp Phổ> ThËt vËy,gi¶ sö G1=[N1,T,S1,P1], G2=[N2,T,S2,P2] lµ 2 v¨n ph¹m cïng lo¹i vµ L1, L2 lµ c¸c ng«n ng÷ t¬ng øng. Gäi L= L1 ∪ L2 ta chøng minh tån t¹i v¨n ph¹m G cïng lo¹i víi G1, G2 sinh ra L. Ta x©y dung V¨n ph¹m G nh sau: 1. N:= N1∪ N2∪{S}, 2. S kh«ng thuéc N1, N2 3. T:=T 4. TËp luËt sinh P ®îc x¸c ®Þnh: P:= P1∪P2 ∪{S → S1, S → S2} Khi ®ã: - V¨n ph¹m võa nhËn ®îc cïng lo¹i víi víi 2 lo¹i v¨n ph¹m trªn do 2 luËt sinh võa thªm. - Ta chøng minh L[G]= L1 ∪ L2. Gi¶ sö w ∈ L, khi ®ã S*→w trong G, theo c¸ch x©y dùng P th× S→S1 hoÆc S→S2 v× vËy hoÆc S1*→w hoÆc S2*→w nghÜa lµ w∈L1 hoÆc w∈L2 tóc lµ w ∈ L1 ∪ L2. Câu 6: Chứng minh ngôn ngữ sinh ra bởi văn phạm là đóng với phép ghép [nối kết]. Giả sử là các ngôn ngữ được sinh bởi văn phạm , hay =L[ ], =L[ ]. Ta Chứng minh: tồn tại văn phạm G sao cho L[G]= . Giả sử = < , > và =< >. Không mất tính tổng quát, ta giả thiết rằng = . Lấy S . Xét văn phạm G = < , >,trong đó: P=[ { }] [ { }] {S | } {S | } {S | và } {S }. Khi đó ta có L[G] và . Khi và là hai văn phạm chính quy thì ta có thể xây dựng văn phạm chính quy G’ sao cho L[G’]= a] và [tức là và ]. Văn phạm chính quy G’ cần tìm là G’=< >, trong đó P’=[ {A }] {A a |A } b] : Đặt ’= { } thì ta xây dựng được văn phạm chính quy ’ sao cho L[ ’]= ’. Khi đó theo a] ta có văn phạm G’ sao cho L[G’]= . Từ =[ ’ {
- 8. từ cách xây dựng văn phạm ta tìm được văn phạm chính quy G’’ sao cho L[G’’]= Tương tự cho 2 trường hợp còn lại Vậy L[G]=L[ ].L[ ] Câu 7: Cho G = < Σ, Δ, S, P > không phải là văn phạm loại 0 với ký tự xuất phát S có ở vế phải của quy tắc dẫn xuất, chỉ ra rằng tồn tại văn phạm G = < Σ’, Δ’, S’, P’ > cùng loại và tương đương với G không có ký tự xuất phát ở vế phải của quy tắc dẫn xuất. Chøng minh. X©y dùng G’=[N’,T,S’,P’] nh sau: - N’:=N∪{S’}, ë ®©y S’ lµ ký hiÖu míi cha cã trong N vµ T P’:=P∪{ S’→α/S→α∈P, α∈[N∪T]+}, nghÜa lµ P’ gåm c¸c quy t¾c cña G bæ sung thªm c¸c quy t¾c d¹ng S’→α nÕu trong P cã quy t¾c S→α. Víi quy íc trªn ta thÊy - Kh«ng cã quy t¾c nµo mµ ký tù xuÊt ph¸t xuÊt hiÖn ë vÕ ph¶i cña dÉn xuÊt. Gi¶ sö w∈L[G] khi ®ã tån t¹i d·y dÉn xu©t S*→ w vµ tån t¹i α∈[N∪T]* sao cho S→α*→ w. Theo c¸ch x©y dùng dÉn xuÊt v× trong G cã S→α nªn trong G’ cã S’→α v× vËy dÉn xuÊt S’→α*→ w lµ dÉn xuÊt trong G’ vËy nªn w∈L[G] do ®ã L[G] ⊆L[G’]. Ngîc l¹i nÕu w∈L[G’] nghÜa lµ S’*→w tån t¹i α∈[N∪T]* S’→α*→ w mµ S’→α* cã t¬ng øng S→α trong G vËy nªn S→α*→w lµ dÉn xuÊt trong G cho nªn L[G’] ⊆L[G]. Câu 8: Khái niệm về văn phạm phi ngữ cảnh, khái niệm về dẫn xuất và cây dẫn xuất, sự nhập nhằng của văn phạm. Ví dụ minh họa. *Văn phạm loại 2[văn phạm phi ngữ cảnh-Context Free Grammar] có luật sinh dạng A với A là một biến đơn và là chuỗi các ký hiệu thuộc [∑ ] *. *Khái niệm dẫn xuất: Cho văn phạm G= và , [ ]*. Ta nói được suy dẫn từ trong G,ký hiệu |= , nếu = hoặc tồn tại 1 dãy * sao cho = , = và | với i=1,2,…,k.Khi đó dãy , ,…, được gọi là 1 dẫn xuất của từ trong G. *Khái niệm cây dẫn xuất: Cây dẫn xuất của văn phạm G= có đặc điểm -Mỗi nút có một nhãn,là một ký hiệu }] -Nút gốc có nhãn là S -Nếu nút trung gian có nhãn A thì A -Nếu nút n có nhãn là A và các đỉnh , ,…, là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là , ,…, thì A … là một luật sinh trong P. -Nếu nút n có nhãn là thì n phải là nút lá và là nút con duy nhất của nút cha của nó. *Sự nhập nhằng của văn phạm: một văn phạm phi ngữ cảnh G được gọi là văn phạm nhập nhằng nếu nó có nhiều hơn một cây dẫn xuất cho cùng 1 chuỗi w. *Ví dụ minh hoạ:
- 9. phi ng÷ c¶nh G=[N, T, s, P] trong ®ã N={s} T={+, a,*}, P={s s+s, s s*s, s a}, trong ®ã + lµ phÐp céng, * lµ phÐp nh©n. X©u a+a*a lµ kÕt qu¶ cña c©y suy dÉn ®Çy ®ñ sau ssss * + + * a a a a a a H×nh 1 H×nh 2 H×nh 1 nÕu thùc hiÖn phÐp nh©n tríc vµ c©y suy dÉn ®Çy ®ñ h×nh 2 nÕu thùc hiÖn phÐp céng tríc Râ rµng x©u trªn lµ kÕt qu¶ cña 2 c©y suy dÉn kh¸c nhau. Câu 9: Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P > không chứa xâu rỗng, trình bày giải thuật loại bỏ các ký hiệu thừa, luật sinh ε, luật sinh đơn vị. *Giải thuật loại bỏ các ký hiệu thừa: -Loại bỏ biến k dẫn ra ký hiệu kết thúc:Cho CONTEXT FREE GRAMMAR G= với L[G] # , có một CONTEXT FREE GRAMMAR G’[∑’, ’,S, P’] tương đương sao cho mỗi A G’ tồn tại w * để A *w. -Loại bỏ các biến k được dẫn ra từ ký hiệu bắt đầu: Cho CONTEXT FREE GRAMMAR G[ , , S, P], ta có thể tìm được CONTEXT FREE GRAMMAR G’[∑’, , S, P’] tương đương sao cho mỗi X [ ’ ∑’] tồn tại [ ’ ∑’]* để S * Cách tìm: - Đặt ’={S} -Nếu A ’ và A là các luật sinh trong P thì thêm các biến của vào V’. -Lặp lại cho đến khi không còn biến nào được thêm vào nữa. *Loại bỏ luật sinh Cho CONTEXT FREE GRAMMAR G=< , ,S, P > và L là ngôn ngữ sinh bởi G. Khi đó L-{ } là ngôn ngữ sinh ra bởi CONTEXT FREE GRAMMAR G’= k có ký hiệu thừa và ko có luật sinh . Cách tìm: - xác định tập biến rỗng Nullable A suy ra A Nullable B Nullable suy ra B thuộc Nullable -Xây dựng tập luật sinh P’: Với mỗi luật sinh A trong P ta xây dựng luật sinh A với điều kiện: -nếu Nullable thì -nếu Nullable thì | -Ko phải tất cả đều bằng ss ss ssss ss ss ss ss ss ss ss ss
- 10. sinh đơn vị[A B]: Mỗi CFL ko chứa được sinh ra bởi CONTEXT FREE GRAMMAR ko có ký hiệu thừa, k có luật sinh hoặc luật sinh đơn vị. Cách tìm: - Đặt L=L[G] và CFL ko chứa và được sinh ra bởi văn phạm G=< , ,S, P >. Theo định lý 3, ta có thể loại bỏ tất cả luật sinh ε trong G. Để loại bỏ luật sinh đơn vị, ta xây dựng tập P' mới theo giải thuật: For [mỗi biến A V] do Begin Tính ΔA = { B|B V và A * B} ; For [mỗi biến B ΔA] do For [mỗi luật sinh B thuộc P] do If [B không là luật sinh đơn vị] then Thêm luật sinh A a vào P' End ; Câu 10: Định nghĩa luật sinh . Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P > không chứa xâu rỗng, không chứa các ký hiệu thừa, trình bày giải thuật loại bỏ luật sinh . - Mọi luật sinh có dạng A → gọi là luật sinh - Giải thuật loại bỏ luật sinh dạng A → ε: Xét G = < Σ, Δ, S, P >, G’ = < Σ, Δ, S, P’ > không chứa luật sinh ε. + Bước 1: Ω := Ø; Nếu luật sinh A → ε thì thêm A vào Ω; Nếu B → X1X2...Xn, Xi ∈ Ω => thêm B vào Ω; + Bước 2: Xây dựng P’. Với mỗi luật A → X1X2...Xn , Xi ∈ [Σ+Δ] trong P, ta xây dựng luật sinh A → α1 α 2... α n trong P’ với điều kiện: Nếu Xi ∉ Ω thì α i = Xi Nếu Xi ∈ Ω thì α i = Xi | ε Không gán đồng thời tất cả ai đều bằng ε Câu 11:Cho văn phạm phi ngữ cảnh G = < Σ, Δ, S, P > không chứa xâu rỗng, không chứa các ký hiệu thừa, không chứa luật sinh ε. Trình bày giải thuật loại bỏ luật sinh đơn vị. *Luật loại bỏ luật sinh đơn vị không chứa các xâu rỗng, không chứa các ký hiệu thừa, không chứa luật sinh ε ta trải qua các bước sau: - A→B là các luật sinh đơn vị trong đó A,B là các biến. - Đưa các luật sinh không phải là luật sinh đơn vị vào P’ - Xác định các cặp biến[A,B] mà A→B chỉ sử dụng các luật sinh đơn vị. Để xác định các cặp biến này ta sử dụng các bước sau - [A,A] là cặp cần xác định với mọi biến A vì A→A bởi 0 bước - Nếu [A,B] là cặp thỏa mãn A→B và B→C là luát sinh, C là biến thì [A,c] là cặp thỏa mãn A→C
- 11. mỗi cặp biến [A,B] được xác định ở trên, thêm vào P’ các luật sinh A→α không là luật sinh đơn vị trong P. Ví dụ: S →aA|A A →B|a B →A|ab|bb Xây dựng tập luật sinh P’ bằng cách loại bỏ các luật sinh sinh đơn vị trong P Đặt các luật sinh không phải là luật sinh đơn vị vào P’ S→aA A→a B→ab|bb Xét các cặp luật sinh đơn vị S→A, S→B, A→B, B→A lần lượt thay thế các luật sinh này bằng các dẫn xuất , ta được S→a S→ab|bb A→ab|bb B→a Vậy cuối cùng ta được các luật sinh trong P’ như sau S→a|aA|ab|bb A→a|ab|bb B→a|ab|bb Câu 12: Trình bày các bước chuẩn hóa văn phạm phi ngữ cảnh về dạng chuẩn Chomsky tương đương. Dạng chuẩn Chomsky : nếu mọi luật sinh của nó có 1 trong 2 dạng đơn giản sau A→a, trong đó A là biến, a là kí hiệu kết thúc A→BC trong đó A,B,C là các biến Cho văn phạm phi ngữ cảnh [Σ,Δ,S,P] với L[G] không rỗng và không chứa ε. Không mất tính tổng quát chúng ta giả sử văn phạm G không chứa các biến vô ích, các luật sinh ε và các luật sinh đơn vị. Ta xây dựng văn phạm G’=[Σ,Δ,S,P’] tương đương ở dạng chuẩn Chomsky từ G như sau: [ giải thuật chuẩn hóa văn phạm phi ngữ cảnh về dạng chuẩn Chomsky tương đương] Đặt các luật sinh A→a vào P’[ đã thỏa mãn dạng chuẩn Chomsky] Đối với các luật sinh dạng A→x1x2…xn [ n >=2] xi ∈ [Δ∈Σ] nếu iss = 1,2,…,n Nếu xi là 1 kí hiệu kết thúc thì thay thế xi bởi 1 biến đại diện mới Bi. Khi đó luật sinh A→x1,x2,…,xn có dạng A→B1B2…Bn .Ứng với mỗi đại diện Bi thêm vào ta thêm vào luật sinh Bi→a. Nếu xi không phải là kí hiệu kết thúc thì giữ nguyên Ứng với mỗi luật sinh A→B1B2…Bn n=2 ta đặt vào P’ vì đã thỏa mãn dạng chuẩn Chomsky n>2 ta đưa vao các biến mới C1,C2,…,Cn và đưa vào P’ các luật sinh sau: A→B1C1 C1→ B2C2 …. Cn-2→ Bn-1Bn
- 12. ví dụ minh hoạ chuyển một văn phạm phi ngữ cảnh về dạng chuẩn Chomsky tương đương. Tìm văn phạm có dạng CNF tương đương văn phạm sau : S → A | ABA A → aA | a | B B → bB | b Bước 1 : Thay thế các luật sinh có độ dài vế phải = 1 [luật sinh đơn vị] Gọi tập ΔA = {B | A ⇒ * B }, xét các biến trong văn phạm, ta có : ΔS = { S, A, B } ΔA = { A, B} ΔB = { B } Vậy tập luật sinh mới, theo định lý sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau : S → aA | a | bB | b | ABA A → aA | a | bB | b B → bB | b Bước 2 : Thay thế các luật sinh có độ dài vế phải > 1 và có chứa ký hiệu kết thúc. Ta thấy, a và b đều xuất hiện ở vế phải một số luật sinh, do đó ta tạo thêm 2 biến mới Ca, Cb và 2 luật sinh mới Ca → a và Cb → b. Văn phạm tương đương có tập luật sinh như sau : S → CaA | a | CbB | b | ABA A → CaA | a | CbB | b B → CbB | b Ca → a Cb → b Bước 3 : Thay thế các luật sinh có độ dài vế phải > 2 Chỉ còn duy nhất một luật sinh cần xét ở bước này : S → ABA và tập luật sinh mới được thay thế có dạng như sau : S → CaA | a | CbB| b | AD1 A → CaA | a | CbB| b B → CbB| b Ca → a Cb → b D1 → BA Cuối cùng, ta sẽ thu được văn phạm có dạng chuẩn Chomsky như trên tương đương với văn phạm đã cho.
- 13. các bước chuẩn hóa văn phạm phi ngữ cảnh về dạng chuẩn Greibach [không cần nêu ví dụ minh họa]. - Dạng chuẩn Greibach[GNF]: văn phạm CONTEXT FREE GRAMMAR G[Σ, Δ, S, P] có dạng chuẩn Greibach nếu: + G không chứa các kí hiệu thừa + G không xuất hiện các luật sinh đơn vị + Các luật sinh của nó có dạng A→aα[α là chuỗi các kí hiệu phụ thuộc hoặc ε nếu ε không thuộc L; ngược lại thêm vào luật sinh S→ε] - Bổ đề thay thế Cho G[Σ, Δ, S, P] là một văn phạm phi ngữ cảnh. Giả sử P có chứa luật sinh A→x1Bx2. Trong đó A,B là các biến khác nhau và B→y1|y2|...| là tập các luật sinh trong P mà có B ở về trái. Cho G1[Σ, Δ1, S, P1] thu được từ G bằng cách loại bỏ luật sinh A→x1Bx2 thêm vào đó A→x1y1x2 | x1y2x2 |...| x1ynx2 th ì L[G] = L[G1] ví dụ: xét văn phạm G=[ {A,B }, {a,b },A,P] với luật sinh A→a| aA|bBc, B→abA| b sau khi thay biến B ta nhận được văn phạm tương đương như sau A→a|aA|babAc|bbc, B→abA|b - Bổ đề loại bỏ đệ qui trái Cho G[Σ, Δ, S, P] là văn phạm phi ngữ cảnh ; A→Ax1| Ax2|...| Axn và A→ y1| y2|... | ym| với xi,yi thuộc [V hợp T]* Xét G1[Σ, Δ hợp {B}, S, P1] là CONTEXT FREE GRAMMAR được tạo thành bằng cách thêm biến mới B và thay các A - luật sinh bằng các luật dạng: A→ yi|yiB , i = 1,..m B→xi|xiB , i=1,...,n Ví dụ : để loại bỏ các luật sinh đệ qui trái khỏi văn phạm A→Aa|aEc|ε E→Ee|ea Áp dụng định lí cho biến A ta được tập luật sinh mới như sau A→aEc|ε|aEcB|B E→Ee|ea B→a|aB Áp dụng cho biến E ta được tập luật sinh cuối cùng như sau A→aEc|ε|aEcB|B E→Ee|eaH B→a|aB H→e|eH Đưa về sạng chuẩn Greibach[GNF] Đặt lại tên cho các biến bằng A1,A2,...An với A1 là trạng thái ban đầu Thay thế các luật sinh dạng Ai→Ajγ [j>i] Nếu ji] Ai→aγ, Bk →γ với [γ thuộc Σ hợp{B1,...,Bi-1] Thay thế Ai Thay thế Bk Câu 15: Trình bày khái niệm về automat hữu hạn. Phân biệt các dạng automata hữu hạn. Ngôn ngữ đoán nhận bởi automata hữu hạn. Ví dụ minh họa. *Khái niệm automat hữu hạn: Một automat hữu hạn[FA] là 1 mô hình toán học hay máy trừu tượng có cơ cấu và hoạt động đơn giản và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ.
- 14. 1 mô hình tính toán hữu hạn, mọi cái liên quan tới nó đều có kích thước hữu hạn cố định và không thể mở rộng trong suốt quá trình tính toán. Một FA làm việc theo thời gian rời rạc Thông tin ra sản sinh bởi một FA phụ thuộc vào cả thông tin vào hiện tại lẫn các thông tin vào trước đó. Nếu sử dụng bộ nhớ, giả sử có ít nhất 1 bộ nhớ vô hạn về tiềm năng Sự phân biệt giữa các loại FA khác nhau chủ yếu dựa trên việc thông tin có được đưa vào bộ nhớ hay không Đoán nhận ngôn ngữ : đoán nhận các chuỗi của nó Hoạt động của automat bắt đầu từ 1 trạng thái đặc biệt, trạng thái đầu tiên Giả sử tại mỗi thời điểm, automata đang ở 1 trạng thái nào đó, đầu vào của aitomata đón nhận 1 kí tự của chuỗi cần xử lí, dưới tác động của kí tự đó automata chuyển sang 1 trạng thái kế tiếp Như vậy số bước để xử lý 1 chuỗi ứng với độ dài chuỗi Chuỗi được đoán nhận nếu trạng thái cuối cùng với độ dài chuỗi. Chuỗi được đoán nhận nếu trạng thái cuối cùng của automata rơi vào 1 trong các trạng thái kết thúc *Phân loại automat hữu hạn Automata đơn định: tại 1 thời điểm với 1 trạng thái và 1 kí tự nhập vào thì máy chỉ có thể chuyển đến không nhiều hơn 1 trạng thái Automata đa định: ứng với 1 trạng thái và 1 kí tự nhập vào, nó có khả năng chọn để di chuyển Ví dụ: automata đa định sau nhận dạng các xâu kết thúc bằn 01 Câu 16: Khái niệm về Automata mealy, automata moore; phân biệt chúng với automat hữu hạn; lấy ví dụ minh hoạ. Automat Mealy: là bộ 5 A=[S,X,Y,delta,F] X-tập hữu hạn các kí hiệu vào Y-tập hữu hạn các kí hiệu ra S-tập hữu hạn các trạng thái delta-ánh xạ từ tập SxX->S[hàm chuyển trạng thái] F-ánh từ tập SxX->Y[hàm ra]
- 15. bộ 5 A=[S,X,Y,delta,F] X-tập hữu hạn các kí hiệu vào Y-tập hữu hạn các kí hiệu ra S-tập hữu hạn các trạng thái delta-ánh xạ từ tập SxX->S[hàm chuyển trạng thái] F-ánh từ tập S->Y[hàm ra] Automat hữu hạn FA là 1 bộ 5 : M=[S, xichma, delta, q0, F] S-tập hữu hạn các trạng thái xichma-tập các tín hiệu vào delta-hàm chuyển trạng thái q0-trạng thái bắt đầu F-tập trạng thái kết thúc q0 thuộc S và F là tập con của S Hàm chuyển delta mở rộng: delta[q,epsilon]=q && delta[q,xa]=delta[delta[q,x],a] với mọi x thuộc xichma, a thuộc xichma* và q thuộc S
- 16. bày các phương pháp biểu diễn automata hữu hạn. Ví dụ minh họa. *Automata hữu hạn đơn định[DFA]: - Định nghĩa : một DFA là 1 bộ gồm 5 phần tử A=[Q, Σ, δ, q0, F] trong đó Q là tập rỗng, tập hữu hạn các trạng thái [p,q…] Σ là bộ chữ cái nhập vào [a,b,c...] δ : Q x Σ → Q là hàm dịch chuyển , δ có thể được viết dưới dạng δ[q,a] = q’ . Nghĩa là automata đang ở trạng thái q và đọc kí hiệu a thì nó sẽ chuyển sang trạng thái q’. q0 ∈ Q là trạng thái xuất phát F là trạng thái kết thúc - Biểu diễn automata hữu hạn đơn định: có 2 các mô tả đơn giản 1 DFA là bằng biểu đồ dịch chuyển và bảng dịch chuyển + Biểu đồ dịch chuyển Mỗi trạng thái trong Q là 1 nút Với mỗi trạng thái q∈Q và mỗi kí hiệu a∈Σ, có δ[q,a] = p∈Q. Như thế biểu đồ dịch chuyển có 1 cũng đi từ nút p tới nút q mang nhãn a, nếu có nhiều kí hiệu tạo ra dịch chuyển từ q đến p thì chỉ cần biểu diễn 1 cung mang nhãn là sanh sách các kí hiệu đó. Có 1 mũi tên đi vào nút q0 để kí hiệu trạng thái đầu Các trạng thái kết thúc F là các nút được biểu diễn bới 2 vòng tròn Các trạng thái k thuộc F được biểu diễn bằng 1 vòng tròn + Bảng dịch chuyển cho 1 DFA là 1 quy ước các biểu diễn dạng bảng của 1 hàm, mà ở đây là dịch chuyển với 2 tham số: các trạng thái và các kí hiệu vào. Trạng thái đầu được đánh dấu bởi dấu →, các trạng thái cuối sẽ được đánh dấu bởi dấu * Ví dụ : xây dựng DFA thừa nhận các xâu chỉ gồm các kí hiệu 0,1 chứa ít nhất 1 lần xâu 01, nghĩa là chúng ta có thể mô tả ngôn ngữ L này như sau: L={x01y| x và y gồm các kí hiệu 0 và 1 bất kì} biểu đồ dịch chuyển bảng trạng thái Ngôn ngữ được đoán nhận với automata A : L ={1*0*01x : x∈ {0,1}*} *Automata đa định[NFA]: - Định nghĩa : một DFA là 1 bộ gồm 5 phần tử A=[Q, Σ, δ, q0, F] trong đó Q là tập hữu hạn các trạng thái Q={q0,q1,…,qn} Σ là bộ chữ cái nhập vào [a,b,c...]
- 17. ánh xạ chuyển trạng thái δ: Q× Σ → 2Q q0 ∈ Q là trạng thái xuất phát F ⊆ Q là tập các trạng thái thừa nhận hay trạng thái kết thúc - Để biểu diễn NFA ta cũng sử dụng 2 cách là biểu đồ dịch chuyển và bảng trạng thái giống như DFA *NFA và DFA có sự khác biệt cơ bản là : - giá trị của hàm dịch chuyển:DFA chỉ trả về 1 trạng thái thuộc tập Q, trong khi NFA trả về 1 tập các trạng thái là tập con của Q - Một NFA có thể dịch chuyển đọc ε, tức là đọc xâu rỗng, trong khi DFA không đọc xâu rỗng. Như vậy, NFA cho phép thực hiện chuyển trạng thái mà không đọc kí hiệu nào cả. Câu 18 : Trình bày thuật toán đoán nhận chuỗi bởi một âutomt hữu hạn cho trước. Ví dụ minh hoạ. *Thuật toán đoán nhận chuỗi: q:= q0; c:= ký hiệu tiếp theo của chuỗi; while [C < > ε] do { q:= δ[q, c]; c:= ký hiệu tiếp theo của chuỗi; }; if [q in F] return [true]; else ssreturn [false]; *Ví dụ: Cho automat đơn định sau: M = [X,S,s0,δ,F] X = {0,1}; S = {s0, s1,s2,s3}; F = { s2,s4}; Trạng thái Ký tự vào 0 1 s0 { s0,s3} { s0,s1} s1 e s2 s2 s2 s2 s3 s4 e s4 s4 s3 Đối với Automat không đơn định trên thì hàm chuyển trạng thái δ khi máy ở trạng thái s và tín hiệu vào là a được δ [s,a] ⊆ S Vì vậy xuất hiện tình trạng rẽ nhánh, ta xây dựng cây đoán nhận xâu như sau: Cho xâu vào w = w1w2…wk. Gốc là s0 Các đỉnh con của gốc s0 là các trạng thái trong S[s0, w1] trong đó w1 là kí tự đầu tiên của xâu w
- 18. s* ⊆ δ[ s0, w1] ta xây dựng các đỉnh con của nó là các đỉnh thuộc tập δ[ s*, w2] và cứ tiếp tục cho đến ký tự cuối cùng của xâu Trong cây này nếu có một đường đi từ s0 đến một lá chứa trạng thái kết thúc thì ta nói máy M đoán nhận được xâu vào đang xét, ngược lại ta nói M không đoán nhận được xâu vào đó Với xâu vào có dạng w = 01001 máy M có cây đoán nhận đi từ s0 đến s4 ⊆ F nên máy M đoán nhận xâu trên. Cây có dạng sau: Câu 19 :Trình bày phương pháp biến đổi từ automata không đơn định về automata đơn định [đưa NFA về DFA]. *Nhận xét: Sự tương đương giữa 2 automata : 2 automata được gọi là tương đương nếu chúng cùng chấp nhận 1 ngôn ngữ như nhau. DFA về bản chất là 1 giới hạn của NFA, nên lớp các DFA là 1 lớp con của NFA. 2 lớp này là tương đương nhau, tức là với 1 NFA thì sẽ có 1 DFA tương đương với nó. Chú ý: 1 trạng thái của NFA là 1 tập trạng thái của DFA. Tập trạng thái kết thúc của NFA là trạng thái mà có chứa trạng thái kết thúc của DFA. L là ngôn ngữ được chấp nhận bới 1 NFA thì tồn tại 1 DFA chấp nhận L. *Thuật toán chuyển đổi tương đương: Xác định tất cả các tập con Q’ của tập Q. Nếu tập Q có n trạng thái thì sẽ có 2n trạng thái của tập con nhưng trên thực tế thường có các trạng thái không đạt đến được trong Q nên các trạng thái này có thể coi như bỏ. Vì vậy Q’ thường có số trạng thái aA| a| b. - Giải thuật + Xây dựng tập Q gồm các trạng thái có dạng [α] với α là S hoặc chuỗi hậu tố của vế phải một luật sinh nào đó trong P. + Nếu A là một biến và [A ® a] Î P: δ[[A], ε] = {[a]} + Nếu a là một ký hiệu kết thúc: δ[[aa], a] = {[a]} + Trạng thái bắt đầu [S], trạng thái kết thúc [ε] Câu 25: Khái niệm về văn phạm chính quy. Trình bày thuật toán xây dựng một automata hữu hạn từ một văn phạm chính chinh quy tuyến tính trái. - Văn phạm chính quy [Regular Grammar] là văn phạm mà tất cả các luật sinh của nó đều có dạng tuyến tính trái [hoặc tuyến tính phải]: + Tuyến tính trái: dạng A → Bw hoặc A → w + Tuyến tính phải: dạng A → wB hoặc A → w - Thuật toán xây dựng FA cho văn phạm tuyến tính trái được xây dựng dựa trên tính chất sau: + Cho văn phạm G = < Σ, Δ, S, P >, và G’ = < Σ, Δ, S, P’ >, trong đó nếu:
- 24. A → α | A → αR ∈ P } , thì L[G’]R = L[G]. + Như vậy ta có thể xây dựng giải thuật theo 3 bước: + Xác định văn phạm tuyến tính phải G’ = < Σ, Δ, S, P’ > + Xây dựng NFA cho G’; + Đảo ngược chiều các cạnh của NFA này, vị trí kết thúc trở thành vị trí bắt đầu và ngược lại. Câu 26: Khái niệm về văn phạm chính quy. Trình bày thuật toán xây dựng văn phạm chính chính quy tuyến tính phải từ một automata hữu hạn cho trước. Ví dụ minh hoạ. - Văn phạm chính quy [RG] là văn phạm mà tất cả các luật sinh của nó đều có dạng tuyến tính trái [hoặc tuyến tính phải]: + Tuyến tính trái: dạng A → Bw hoặc A → w + Tuyến tính phải: dạng A → wB hoặc A → w - Giải thuật xây dựng văn phạm tuyến tính phải cho FA: xét hàm chuyển trạng thái δ: + Nếu δ[p, a] = q, ta có luật sinh: p → aq + Nếu q là trạng thái kết thúc, ta có luật sinh p → a + Nếu q0 là trạng thái kết thúc, thêm vào: S → q0 | ε Ví dụ: xét DFA cho 0[10]* sau: Văn phạm tuyến tính phải cho FA trên là: A → 0B | 1D | 0 B →0D | 1C C → 0B | 1D | 0 D → 0D | 1D Câu 27: Khái niệm về văn phạm chính quy. Trình bày thuật toán xây dựng một automata hữu hạn cho trước. Ví dụ minh hoạ. - Văn phạm chính quy [RG] là văn phạm mà tất cả các luật sinh của nó đều có dạng tuyến tính trái [hoặc tuyến tính phải]: + Tuyến tính trái: dạng A → Bw hoặc A → w + Tuyến tính phải: dạng A → wB hoặc A → w - Giải thuật xây dựng RG tuyến tính trái cho FA: + Bắt đầu với một NFA cho LR + Đảo ngược chuỗi vế phải cho tất cả mọi luật sinh của văn phạm vừa thu được Ví dụ: xét DFA của LR : 0[10]* :
- 25. tính trái cho FA trên là: A → B0 | D1 | 0 B →D0 | C1 C → B0 | D1 | 0 D → D0 | D1 Câu 28: Phát biểu bổ đề bơm[pumping lemma] cho tập hợp chính quy, giải thích, ý nghĩa bổ đề bơm.Lấy ví dụ minh họa. Nếu L là tập hợp chính quy[RS] thì có tồn tại hằng số n sao cho nếu z là một từ bất kì thuộc L và |z| =n thì ta có thể viết z=uvwxy sắp cho: | vx | ≥ 1 | vwx | ≤ n và ∀i ≥ 0 : uv^i w x^i y ∈ L Ví dụ: chứng minh L = {aibici | i ≥ 1} không là CFL Giả sử L là CFL, khi đó tồn tại số n theo bổ đề bơm Xét chuỗi z = anbncn, |z| ≥ n, ta có thể viết z=uvwxy thỏa bổ đề bơm. Ta có: vwx ∈ anbncn, |vwx| ≤ n nên vwx không thể đồng thời chứa cả ký hiệu a và c [vì giữa a và c có n ký hiệu b] → vx cũng không thể chứa cả ký hiệu a và c. Do |vx| ≥ 1 và trong uvwxy chứa số ký hiệu a, b, c bằng nhau: - Nếu vx có chứa ký hiệu a [nên không thể chứa ký hiệu c] thì khi bơm chuỗi vx, số ký hiệu c sẽ không đổi [luôn là n], nhưng số ký hiệu a sẽ thay đổi. Ví dụ: chuỗi uv0wx0y ∉ L vì có số ký hiệu a [ít hơn n] số ký hiệu c [luôn là n] không bằng nhau. - Nếu vx không chứa ký hiệu a thì khi bơm chuỗi vx, số ký hiệu a không đổi, nhưng số ký hiệu b [hoặc c] sẽ thay đổi. Câu 32:Định nghĩa pushdown automata,giải thích các thành phần.Vd minh họa. PDA là một FA với sự bổ xung thêm một ngăn xếp [stack] đóng vai trò bộ nhớ, do vậy khả năng ghi nhớ của FA được tăng lên, dẫn đến PDA có khả năng đoán nhận lớp ngôn ngữ rộng hơn là RL [RG, RE]; Stack hoạt động theo nguyên lý FILO [LIFO], do đó FA sử dụng bộ nhớ có tên gọi là Pushdown automata;
- 31. điểm, PDA điều khiển đồng thời cả dòng dữ liệu nhập vào [băng nhập- tape] và bộ nhớ - bộ đẩy xuống [stack]. Khi đọc một tín hiệu vào, PDA có thể chuyển sang một trạng thái mới, hoặc thêm, xóa đi dữ liệu từ stack, hoặc đồng thời cả hai; Lớp PDA có khả năng đoán nhận lớp CFL, trong đó bao gồm các ngôn ngữ lập trình hiện đại; Một PDA A là 1 hệ thống gồm 7 thành phần: Q: tập hữu hạn các trạng thái Σ : bộ chữ cái nhập [tape or input alphabet]; Γ : bộ chữ cái stack [stack alphabet]; δ : hàm chuyển Q x [Σ {ε}] x Γ → tập con của Q x Γ*; q0 : trạng thái khởi đầu; Z0 : ký hiệu bắt đầu trên stack; F ⊆ Q : tập các trạng thái kết thúc [nếu PDA chấp nhận chuỗi bằng Stack rỗng thì F = Ø]. VÝ dô: Cho M:=[{q1,q2},{0,1},{Z,0,1},δ, Z, ∅}, víi c¸c hµm chuyÓn nh sau: 1. δ[q1,0,Z]={[q1,0]}, 2. δ[q1,1,Z]={[q1,1]}, 3. δ[q1,0,0]={[q1,00],[q2,e]} 4. δ[q1,0,1]={[q1,10]}, 5. δ[q1,1,0]={[q1,01]}, 6.δ[q1,1,1]={[q1,11],[q2,e]} 7. δ[q2,0,0]={[q2,e]}, 8. δ[q2,1,1]={[q2,e]}, 9. δ[q1,1,Z]={[q2,e]} 10. δ[q2,e,Z]={[q2,e]}. Câu 33: Phận biệt PDA đơn định và PDA không đơn định. Một PDA A[Q, Σ, Γ, δ, q0, Z0, F] được gọi là đơn định nếu: ∀q ∈Q và Z ∈Γ: nếu δ[q, e, Z] ≠ Ø thì δ[q, a, Z] = Ø, ∀a∈Σ Không có q ∈ Q, Z ∈ Γ và a ∈ [Σ ∪ {e}] mà | δ[q, a, Z] | chứa nhiều hơn một phần tử. Nếu không thỏa mãn một trong hai yêu cầu trên thì PDA A[Q, Σ, Γ, δ, q0, Z0, F] được gọi là đa định. Câu 34: Nêu khái niệm máy Turing, các kỹ thuật xây dựng máy Turing, lớp ngôn ngữ đoán nhận bởi máy Turing. Máy Turing có một băng nhớ, dùng để ghi mọi loại dữ liệu [dữ liệu nhập, dữ liệu dùng cho việc điều khiển tương tự như một chương trình máy tính và các kết quả trung gian khi làm việc]. Với một bộ điều khiển chứa một số hữu hạn trạng thái, TM cũng như các ôtômát khác, làm việc theo lối "ngắt quãng" theo từng bước chuyển. mô hình cơ bản của một máy Turing gồm : Một bộ điều khiển hữu hạn. Một băng được chia thành các ô. Một đầu đọc-viết, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc hay viết ký hiệu. →Định nghĩa: TM là một hệ thống M [Q, ∑, Γ, δ, q0, B, F], trong đó:
- 32. tập hữu hạn các trạng thái. . ∑: bộ ký hiệu nhập. . Γ : tập hữu hạn các ký tự được phép viết trên băng. . B : ký hiệu thuộc Γ dùng chỉ khoảng trống trên băng [Blank]. . δ : hàm chuyển ánh xạ : Q × Γ → Q × Γ × {L, R, ∅} [δ có thể không xác định với một vài đối số] . q0 ∈ Q là trạng thái bắt đầu . F ⊆ Q là tập các trạng thái kết thúc Các kĩ thuật xây dựng máy turing: Lưu trữ trong bộ điều khiển Nhiều rãnh trên băng Đánh dấu ký hiệu Dịch qua Chương trình con Lớp ngôn ngữ mà được chấp nhận bởi 1 máy Turing được gọi là ngôn ngữ đệ quy kiệt kê Đó là một lớp ngôn ngữ rất rộng, nó thực sự chứa ngôn ngữ phi ngữ cảnh CFL và một số ngôn ngữ mà không thể xác định các thành phần một cách máy móc. Nếu L[M] là một ngôn ngữ như vậy thì bất kỳ một máy Turing nào nhận diện L[M] cũng sẽ không dừng trên một số input không thuộc L[M]. Câu 35: Nêu khái niệm automata tuyến tính giới nội, lớp ngôn ngữ đoán nhận bởi automata tuyến tính giới nội. Ôtômát tuyến tính giới nội [Linear Bounded Automata - LBA] Khái niệm LBA Một cách hình thức, LBA là một hệ thống M[Q, Σ, Γ,δ,qo,⊄, $, F], trong đó các thành phần Q, Σ, Γ, qo, F vẫn như đã định nghĩa ở máy Turing, còn ⊄, $ ∈ Σ và hàm chuyển :
- 33. Γ → [Q × Γ × { L, R}] phải thỏa mãn điều kiện: - Nếu [p, Y, E] ∈ δ[q, ⊄] thì Y = ⊄ và E = R - Nếu [p, Y, E] ∈ δ[q, $] thì Y = $ và E = L Ngôn ngữ được chấp nhận bởi LBA Ta định nghĩa ngôn ngữ L[M] được đoán nhận bởi LBA M là tập hợp : L[M] = { w | w ∈ [Σ - {⊄, $}]* và qo⊄w$ ⊢M* αqβ với q ∈ F và αβ ∈ Γ* } Các dạng bài tập ôn thi Biến đổi tương đương giữa các dạng automata hữu hạn; NFA→DFA NFAε→DFA NFAε→NFA Biến đổi tương đương giữa automata hữu hạn với biểu thức chính quy và văn phạm chính quy; Văn phạm chính quy và automata hữu hạn RG→FA[automata hữu hạn] VĂN PHạMTT Trái VĂN PHạM TT Phải FA→RG Xây dựng RG tuyến tính phải cho FA Xây dựng RG tuyến tính trái cho FA Biểu thức chính quy và automata hữu hạn FA→RE [ xây dựng NFAε thỏa mãn RE] DFA tương đương RE [ viết RE cho DFA] Rút gọn, chuẩn hóa văn phạm phi ngữ cảnh. Rút gọn NNPNC Loại bỏ kí hiệu thừa Loại bỏ luật sinh ε Loại bỏ luật sinh đơn vị Chuẩn hóa VĂN PHạM PNC Dạng chuẩn hóa Chomsky Dạng chuẩn hóa Greibach Biến đổi tương đương giữa automata đẩy xuống và văn phạm phi ngữ cảnh; Sự tương đương giữa 2 automata đẩy xuống [PDA]
- 34. đẩy xuống đa định sang đơn định] DPDA→NPDA[ automata đẩy xuống đơn định sang đa định] Sự tương đương giữa automata đẩy xuống và văn phạm phi ngữ cảnh CONTEXT FREE GRAMMAR→PDA PDA→CONTEXT FREE GRAMMAR