Bài giảng Ngôn ngữ hình thức - Chương 3: Văn phạm phi ngữ cảnh và Automat đẩy xuống - Phạm Hùng Phú

140 trang Gia Huy 16/05/2022 5260

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Ngôn ngữ hình thức - Chương 3: Văn phạm phi ngữ cảnh và Automat đẩy xuống - Phạm Hùng Phú", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_ngon_ngu_hinh_thuc_chuong_3_van_pham_phi_ngu_canh.pdf

Nội dung text: Bài giảng Ngôn ngữ hình thức - Chương 3: Văn phạm phi ngữ cảnh và Automat đẩy xuống - Phạm Hùng Phú

Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH VÀ AUTOMAT ĐẨY XUỐNG (Contexet free Grammar - CFG and push down Automata - PDA) Mục tiêu: Giúp sinh viên có khả năng: - Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một CFG. - Nhận dạng đƣợc lớp ngôn ngữ phi ngữ cảnh (CFL) do văn phạm CFG sinh ra và tính chất của CFL. - Xây dựng đƣợc các thành phần của CFG đặc tả một lớp CFL. - Hiểu và xây dựng đƣợc dẫn xuất và cây dẫn xuất. - Rút gọn và chuẩn hoá đƣợc CFG. - Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một PDA - Xây dựng đƣợc các thành phần của PDA đoán nhận ngôn ngữ sinh bởi CFG và xây dựng đƣợc CFG sinh ra ngôn ngữ đƣợc đoán nhận bởi PDA. Nội dung chính: - Văn phạm phi ngữ cảnh: định nghĩa, dẫn xuất và ngôn ngữ và cây dẫn xuất. - Rút gọn văn phạm phi ngữ cảnh. - Chuẩn hoá văn phạm phi ngữ cảnh. - Tính chất của CFL. - Automat đẩy xuống: định nghĩa, ngôn ngữ đoán nhận bởi PDA. - Quan hệ của PDA và CFG. 3.1. Văn phạm phi ngữ cảnh (CFG: Context Free Grammar) Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ nhƣ sau: → → → → 107 Phạm Hùng Phú
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống → An → sinh viên → là → giỏi Các từ trong cặp dấu nhƣ , , , là các phạm trù cú pháp, cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu đƣợ sinh ra qua các bƣớc triển khai dần dần theo các quy tắc cú pháp. Đây cũng chính là dạng của các luật sinh trong văn phạm phi ngữ cảnh. Nhƣ vậy, văn phạm phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự nhiên. Tuy nhiên, trong khoa học máy tính, với nhu cầu biểu diễn các ngôn ngữ lập trình, văn phạm phi ngữ cảnh CFG còn đƣợc thiết kế thành một dạng tƣơng đƣơng gọi là văn phạm BNF (Backus - Naur Form). Đây cũng là văn phạm CFG với những thay đổi nhỏ về dạng thức và một số ký hiệu viết tắt mà các nhà khoa học máy tính thƣờng ứng dụng trong việc diễn tả cú pháp của các ngôn ngữ lập trình cấp cao (nhƣ ALGOL, PASCAL, ). Trong dạng thức của văn phạm BNF, ký hiệu::= đƣợc dùng thay cho ký hiệu →. Chẳng hạn, để định nghĩa một biểu thức số học (expression) bao gồm các danh biểu (identifier) tham gia vào các phép toán +, * hoặc biểu thức con lồng trong dấu ngoặc đơn , ta viết: ::= + ::= * ::= ( ) ::= Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân tích cú pháp vận dụng trong chƣơng trình dịch và cho nhiều ứng dụng khác về xử lý xâu. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình có cấu trúc mà biểu thức chính quy không thể đặc tả đƣợc. Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ đƣợc biểu diễn bởi 108 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 các biến đƣợc mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là ký hiệu kết thúc. Quy tắc quan hệ giữa các biến và các ký hiệu kết thúc đƣợc gọi là luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một xâu có thể gồm các biến lẫn các ký hiệu kết thúc trong văn phạm. 3.1.1. Định nghĩa Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu là G = (N, T, P, S); trong đó: - N là tập hữu hạn các ký tự không kết thúc (hay các biến) ; - T là tập hữu hạn các ký tự kết thúc; N  T = ∅ ; - P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A → α với A N và α (N  T)*; - S là một ký tự không kết thúc đặc biệt gọi là ký tự bắt đầu văn phạm. Ví dụ: Văn phạm phi ngữ cảnh G = (N, T, P, S); trong đó: N = {S, A, B}; T = {a, b}; S = S; P gồm các luật sinh sau: S → AB; A → aA; A → a; B → bB; B → b. Quy ƣớc ký hiệu: - Các chữ in hoa A, B, C, D, E, đầu bảng chữ cái La tinh và S ký hiệu cho các ký tự không kết thúc (S thƣờng đƣợc dùng làm ký tự bắt đầu ). - Các chữ nhỏ a, b, c, d, e, , các chữ số và một số ký tự khác ký hiệu cho các ký tự kết thúc. - Các chữ in hoa X, Y, Z ký hiệu cho các ký tự có thể kết thúc hoặc không kết thúc. Phạm Hùng Phú 109
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống - Các chữ Hi-Lạp α, β, γ, ký hiệu cho các xâu gồm các ký tự kết thúc và không kết thúc. Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh của nó. Nếu A → α ; A → α ; ; A → α là các luật sinh của biến A trong văn 1 2 k phạm nào đó, ta sẽ ghi ngắn gọn là A → α | α | | α 1 2 k Ví dụ: Văn phạm cho trong ví dụ trên có thể viết gọn là: S → AB; A → aA | a; B → bB | b‟ 3.1.2. Dẫn xuất và ngôn ngữ 1) Dẫn xuất Cho văn phạm CFG: G = (N, T, P, S), giả sử luật sinh A → β P và xâu αAγ (N T)* với α , β, γ (N T)* . Nếu thay ký tự không kết thúc A trong xâu αAγ bằng xâu β để thu đƣợc xâu αβγ hay còn nói áp dụng luật sinh A → β vào xâu αAγ để thu đƣợc xâu αβγ; khi đó, ta nói rằng xâu αAγ dẫn xuất trực tiếp ra xâu αβγ hay xâu αβγ đƣợc dẫn xuất trực tiếp từ xâu αAγ trong văn phạm G và đƣợc ký hiệu là αAγ αβγ. G Giả sử α , α , , α là các xâu thuộc (N  T)* với m ≥ 1 và 1 2 m α α ; α α ; ; α α 1 G 2 2 G 3 m -1 G m thì ta ký hiệu là α * α và nói là α dẫn xuất (không, một hoặc nhiều bƣớc) ra α 1 G m 1 m hay α đƣợc dẫn xuất từ α trong văn phạm G. m 1 Nếu α dẫn xuất ra α bằng i bƣớc dẫn xuất thì ta ký hiệu là α i α . 1 m 1 G m Nếu α dẫn xuất ra α bằng một hoặc nhiều bƣớc dẫn xuất thì ta ký hiệu là 1 m α + α . 1 G m Chú ý rằng α * α với mọi xâu α. và nếu α * ;  *  thì α *  với G G G G mọi xâu α, , . 110 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Thông thƣờng, nếu không có nhầm lẫn, ta sẽ dùng các ký hiệu , * , + i thay cho ký hiệu tƣơng ứng , * , + , i . G G G G 2) Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh Cho văn phạm CFG: G = (N, T, P, S), Ngôn ngữ sinh bởi văn phạm phi ngữ * cảnh G là L(G) = {w | w T và S * w} và đƣợc gọi là ngôn ngữ phi ngữ cảnh. G Nghĩa là, một xâu thuộc L(G) nếu: 1. Xâu gồm toàn ký tự kết thúc. 2. Xâu đƣợc dẫn xuất ra từ ký tự bắt đầu S. Xâu α gồm các ký tự kết thúc và các ký tự không kết thúc, đƣợc gọi là một dạng câu sinh từ văn phạm G nếu S * α . G Hai văn phạm phi ngữ cảnh G , G đƣợc gọi là tƣơng đƣơng nếu L(G ) = L(G ). 1 2 1 2 Ví dụ: 1. Xét văn phạm CLG: G = (N, T, P, S), trong đó: N = {S}; T = {a, b}; P = {S → aSb, S → ab}. Bằng cách áp dụng luật sinh thứ nhất n-1 lần và luật sinh thứ hai 1 lần, ta có: 3 3 n-1 n-1 n n S aSb aaSbb a Sb a b a b n n n n Vậy, L(G) chứa các xâu có dạng a b với n ≥ 1; hay L(G) = {a b | n ≥ 1}. 2. Xét văn phạm CLG: G‟ = (N‟, T, P‟, S), trong đó: N‟ = {S, A}; T = {a, b}; P‟ = {S → aAb; A → aAb; A → }. Bằng cách áp dụng luật sinh thứ nhất 1 lần, luật sinh thứ hai n -1 lần và luật sinh thứ ba 1 lần , ta có: 3 3 n-1 n-1 n n n n S aAb aaAbb a Ab a Ab a Ab a b n n n n Vậy, L(G‟) chứa các xâu có dạng a b với n ≥ 1; hay L(G‟) = {a b | n ≥ 1}. Và ta có L(G) =L(G‟) nên hai văn phạm phi ngữ cảnh trên là tƣơng đƣơng. 3.1.3. Cây dẫn xuất Để hình dung một cách trực quan việc sinh ra các xâu trong văn phạm phi ngữ cảnh, ngƣời ta thƣờng diễn tả một dãy dẫn xuất qua hình ảnh một cây. Một cách hình thức, ta định nghĩa cây dẫn xuất nhƣ sau: 1) Định nghĩa Phạm Hùng Phú 111
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Cho văn phạm CFG: G = (N, T, P, S). Cây dẫn xuất (hay cây phân tích cú pháp) của G đƣợc định nghĩa nhƣ sau: 1. Mỗi nút có một nhãn, là một ký tự (N T{ε}). 2. Nút gốc có nhãn là ký tự bắt đầu S. 3. Nếu nút trong (trung gian) có nhãn A thì A N. 4. Nếu nút n có nhãn A và các nút n , n , , n là con của n theo thứ tự từ trái 1 2 k sang phải có nhãn lần lƣợt là X , X , , X thì A → X X X là một luật sinh 1 2 k 1 2 k trong tập luật sinh P. 5. Nếu nút n có nhãn là từ rỗng ε thì n phải là nút lá và là nút con duy nhất của nút cha của nó. 2) Ví dụ: a) Cho văn phạm G = ({S, A}, {a, b}, P, S), trong đó P gồm: S → aAS | a; A → SbA | SS | ba. Một cây dẫn xuất từ văn phạm có dạng nhƣ sau: S a S A a S b A a b a Hình 3.1. Cây dẫn xuất từ văn phạm Ta thấy, nút 1 có nhãn S và các con của nó lần lƣợt là a, A, S (chú ý S → aAS là một luật sinh). Tƣơng tự, nút 3 có nhãn A và các con của nó là S, b, A (từ luật sinh A → SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a (luật sinh S → a). Cuối cùng nút 7 có nhãn A và có các nút con b, a (luật sinh A → ba). Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có một dạng câu trong G. Ta gọi xâu này là xâu sinh bởi cây dẫn xuất. 112 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn đƣợc gọi là A-cây con (hoặc A-cây). Cây con cũng giống nhƣ cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký tự bắt đầu S. b) Xét văn phạm và cây dẫn xuất trên. Đọc các lá theo thứ tự từ trái sang phải ta có xâu aabbaa. Trong trƣờng hợp này, tất cả các lá đều là ký tự kết thúc. Tuy nhiên, nói chung cũng không bắt buộc nhƣ thế; lá có thể có nhãn là ε hoặc biến. Ta thấy dẫn xuất S * aabbaa bằng dãy dẫn xuất: S aAS aSbAS aabAS aabbaS aabbaa. A-cây (nút 3) nhãn của nút gốc là A tạo ra xâu con abba theo dãy dẫn xuất: A SbA abA abba. 3.1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất 1) Định lý Cho G = (N, T, P, S) là một văn phạm phi ngữ cảnh. S * α tồn tại cây dẫn xuất trong văn phạm G sinh ra α từ S. Chứng minh: Ta chứng minh rằng với biến A bất kỳ, A * α có một A-cây sinh ra α. - Đảo: Giả sử α đƣợc sinh bởi A-cây, ta chứng minh quy nạp theo số nút trong của cây dẫn xuất rằng A * α. Nếu A có số nút trong là 1 thì cây phải có dạng nhƣ hình sau: Khi đó X X X là xâu α và A → α là một luật sinh trong P theo định nghĩa cây 1 2 n dẫn xuất. S X1 X2 . . . Xn Hình 3.2(a). A-cây với một nút trong Giả sử kết quả đúng tới số nút trong là k -1 ( k > 1) Ta chứng minh kết quả cũng đúng với số nút trong là k. Phạm Hùng Phú 113
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Xét α đƣợc sinh ra bởi A-cây có số nút trong là k. Rõ ràng các nút con của nút gốc không phải tất cả đều là lá, ta gọi chúng từ trái sang phải là X , X , , X thì 1 2 n chắc chắn rằng A → X X X là một luật sinh. Xét nút X bất kỳ: 1 2 n i + Nếu X không là nút lá thì X phải là một biến và X - cây con sẽ sinh ra một i i i xâu α nào đó. i + Nếu X là nút lá, ta đặt α = X . Dễ thấy rằng nếu j < i thì các α ở bên trái α , do i i i j j vậy xâu đọc từ lá vẫn có dạng α = α α α . Mỗi X - cây con phải có ít nút trong hơn 1 2 n i cây ban đầu, vì thế theo giả thiết quy nạp, với mỗi đỉnh i không phải là lá thì X * α . i i Vậy A X X X * α X X * α α X X * * α α α = α 1 2 n 1 2 n 1 2 3 n 1 2 n Hay ta có A * α . Chú ý rằng đây chỉ là một trong nhiều cách dẫn xuất ra α. - Thuận: giả sử A * α , ta cần chỉ ra một A - cây sinh ra α. Nếu A * α bằng một bƣớc dẫn xuất thì A → α là một luật sinh trong P và có cây dẫn xuất sinh ra α nhƣ trong hình trên. Giả sử kết quả đúng tới k-1 bƣớc dẫn xuất Xét A * α bằng k bƣớc dẫn xuất, gọi bƣớc đầu tiên là A → X X X . 1 2 n Rõ ràng, một ký tự trong α phải đƣợc dẫn ra từ một biến X nào đó. Vì vậy, ta i có thể viết α = α α α , trong đó mỗi 1 ≤ i ≤ n thoả mãn: 1 2 n + α = X nếu X là ký tự kết thúc. i i i + X * α nếu X là một biến (ký tự không kết thúc). i i i Nếu X là biến thì dẫn xuất của α từ X phải có ít hơn k bƣớc. Vì vậy, theo giả i i i thiết quy nạp ta có X - cây sinh ra α , đặt cây này là T i i i Bây giờ ta dựng A - cây có n lá X X X . Mỗi X không là ký tự kết thúc ta 1 2 n i thay bằng cây T tƣơng ứng. Cuối cùng, ta có cây dẫn xuất sinh ra có dạng nhƣ sau: i 114 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 S X . . . Xn-1 X X2 3 Xn 1 T2 T3 Tn Hình 3.2(b). A-cây 2) Ví dụ: Xét dãy dẫn xuất S * aabbaa của văn phạm trên Bƣớc đầu tiên trong dẫn xuất đó là S aAS. Theo dõi các bƣớc suy dẫn sau đó, ta thấy biến A đƣợc thay bởi SbA, rồi trở thành abA và cuối cùng thành abba, đó chính là kết quả của cây T (A - cây). Còn biến S thì đƣợc thay bởi a và đó là kết 2 quả của cây T (S -cây). Ghép nối lại, ta đƣợc cây dẫn xuất mà kết quả là xâu 3 aabbaa. S S S a A S S b A a T T 2 3 b a Cây T2 Cây T3 Hình 3.3. Ghép nối các cây dẫn xuất 3.1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất 1) Định nghĩa Nếu tại mỗi bƣớc dẫn xuất, luật sinh đƣợc áp dụng vào biến bên trái nhất thì ta gọi đó là dẫn xuất trái nhất (leftmost - lm) hay dẫn xuất trái. Tƣơng tự, nếu biến bên phải nhất đƣợc thay thế ở mỗi bƣớc dẫn xuất thì đó là dẫn xuất phải nhất (rightmost - rm) hay dẫn xuất phải. Nếu xâu w L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và tƣơng ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất Phạm Hùng Phú 115
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó có thể có nhiều cây dẫn xuất. 2) Ví dụ: Xét cây dẫn xuất ở hình 3.1 - Dẫn xuất trái nhất của cây: S aAS aSbAS aabAS aabbaS aabbaa. -Dẫn xuất phải nhất tƣơng ứng là: S aAS aAa aSbAa aSbbaa aabbaa. 3.1.6. Văn phạm nhập nhằng (mơ hồ) 1) Định nghĩa Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất trái nhất hay phải nhất cho cùng một xâu w thì G đƣợc gọi là văn phạm nhập nhằng (ambiguity). Dĩ nhiên, cũng có thể nói rằng văn phạm G là nhập nhằng nếu có một xâu w đƣợc dẫn ra từ ký tự bắt đầu S với hai dẫn xuất trái nhất hoặc hai dẫn xuất phải nhất. 2) Ví dụ Xét văn phạm phi ngữ cảnh G với các luật sinh nhƣ sau: E → E + E | E * E | ( E ) | a Văn phạm này sinh ra các xâu biểu thức số học với 2 phép toán + và * . Xét xâu a + a * a , xâu này có hai dẫn xuất trái nhất là: 1. E E + E a + E a + E * E a + a * E a + a * a 2. E E * E E + E *E a + E * E a + a * E a + a * a Và có hai cây dẫn xuất trái nhất tƣơng ứng là: E E E + E E E * E E E a * E + a a a a a a) b) Hình 3.4. Hai cây dẫn xuất trái nhất cho cùng xâu 116 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Vậy văn phạm trên là văn phạm nhập nhằng. Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo hai cách khác nhau: thực hiện phép cộng trƣớc hay phép nhân trƣớc ? Để khắc phục sự nhập nhằng này, ta có thể: - Hoặc quy định rằng các phép cộng và nhân luôn luôn đƣợc thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G không mơ hồ 1 tƣơng đƣơng nhƣ sau: E → E + T | E * T | T ; T → ( E ) | a . - Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn luôn đƣợc ƣu tiên hơn phép cộng. Ta viết văn phạm G không mơ hồ tƣơng 2 đƣơng nhƣ sau: E → E + T | T; T → T * F | F; F → ( E ) | a. 3.2. Rút gọn văn phạm phi ngữ cảnh Thông thƣờng, một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài yếu tố thừa. Chẳng hạn nhƣ theo các đặc tính trên, có những ký tự không thực sự tham gia vào quá trình dẫn xuất ra xâu, hoặc sẽ có những luật sinh dạng A → B làm kéo dài dãy dẫn xuất một cách không cần thiết. Vì vậy, việc rút gọn văn phạm phi ngữ cảnh là nhằm loại bỏ những yếu tố thừa đó mà không làm giảm bớt khả năng sản sinh ngôn ngữ của văn phạm. Nếu L là một CFL, nó có thể tạo ra văn phạm CFG với các đặc tính sau: 1. Mỗi biến và mỗi ký tự kết thúc của G đều xuất hiện trong dẫn xuất của một số xâu trong L. 2. Không có luật sinh nào dạng A → B, mà trong đó A, B đều là biến. Hơn nữa, nếu ε ∉ L thì không cần luật sinh A → ε. Thực tế, nếu ε ∉ L, ta có mọi luật sinh trong G đều có một trong hai dạng: A → BC và A → a với A, B, C N; a T Phạm Hùng Phú 117
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống hoặc A → aα (α là xâu các biến hoặc ε). Hai dạng đặc biệt này gọi là dạng chuẩn Chomsky và dạng chuẩn Greibach. 3.2.1. Loại bỏ các ký tự thừa 1) Định nghĩa Một ký tự văn phạm X (X V = NT) gọi là không thừa nếu tồn tại một dẫn xuất S * αXβ * w với các xâu α, β bất kỳ V* và w T*. Ngƣợc lại X gọi là thừa. Vậy, ký tự không thừa có 2 đặc điểm: - X là biến thì X phải dẫn ra một xâu các ký tự kết thúc; - X phải nằm trong dẫn xuất từ S. 2) Bổ đề 1 (Dùng loại bỏ các biến không dẫn ra xâu ký tự kết thúc) Cho CFG G = (N, T, P, S) với L(G) ≠ ∅, có một CFG G‟= (N‟, T, P‟, S) tƣơng đƣơng sao cho mỗi A N‟ tồn tại w T* để A * w. Chứng minh: Với mỗi biến A N và với mỗi luật sinh A → w với w T* nằm trong P thì rõ ràng A N‟. Nếu A → X X X là một luật sinh, trong đó mỗi X hoặc là ký tự kết thúc 1 2 n i hoặc là một biến đã có sẵn trong N‟ thì một xâu các ký tự kết thúc có thể đƣợc dẫn ra từ A bằng dẫn xuất bắt đầu A X X X , vì vậy A N‟. 1 2 n Tập N‟ có thể tính đƣợc bằng cách lặp lại bƣớc trên cho đến khi không thêm đƣợc ký tự nào nữa vào N‟. P‟ là tập tất cả các luật sinh mà các ký tự của nó thuộc N‟  T. Giải thuật tìm N‟ nhƣ sau: Begin OLDN:= ∅; (1) NEWN:= {A N | A → w P và w T*}; (2) While OLDN <> NEWN do (3) begin OLDN:= NEWN; (4) 118 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 NEWN:= {A N | A → α với α (T  OLDN)*} (5) end; N‟:= NEWN; (6) end; Rõ ràng rằng nếu biến A đƣợc thêm vào N‟ tại bƣớc (2) hoặc (5) thì A sẽ dẫn ra đƣợc xâu ký tự kết thúc. Ta chứng minh rằng nếu A dẫn ra đƣợc một xâu ký tự kết thúc thì A đƣợc thêm vào tập NEWN. Dùng chứng minh quy nạp theo độ dài của dẫn xuất A * w. Nếu độ dài bằng 1 thì A → α là một luật sinh trong P. Vậy A đƣợc đƣa vào N‟ tại bƣớc (2). Giả sử kết quả đúng tới k -1 bƣớc dẫn xuất ( k >1) Nếu A X X X * w bằng k bƣớc thì ta có thể viết w = w w w , 1 2 n 1 2 n trong đó X * w , với 1 ≤ i ≤ n bằng ít hơn k bƣớc dẫn xuất. Theo giả thiết quy nạp i i thì các biến X này đƣợc thêm vào N‟. Khi X cuối cùng đƣợc thêm vào N‟ thì vòng i i lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ đƣợc thêm vào N‟ tại (5). Ta chứng minh L(G‟) = L(G): Chọn N‟ là tập hợp tại (6) và P‟ là tập tất cả các luật sinh mà các ký tự của nó thuộc (N‟T) thì chắc chắn rằng có tồn tại văn phạm G‟= (N‟, T, P‟, S) thoả mãn tính chất: nếu A N‟ thì A * w với w nào đó thuộc T*. Hơn nữa, mỗi luật sinh của P‟ đều là luật sinh của P nên ta có L(G‟)  L(G). Ngƣợc lại giả sử một từ w L(G) – L(G‟) thì một dẫn xuất bất kỳ của w phải liên quan đến các biến thuộc N – N‟ hoặc luật sinh thuộc P – P‟ (các dẫn xuất này đƣa ra các biến thuộc N – N‟), nhƣng do không có biến nào trong N – N‟ dẫn đến xâu các ký tự kết thúc, điều này dẫn đến mâu thuẫn. Vậy L(G‟) = L(G). Từ việc chứng minh bổ đề 1, ta có giải thuật sau. 3) Giải thuật loại bỏ biến không dẫn xuất ra xâu các ký tự kết thúc Input G = (N, T, P, S) - CFG Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi biến của nó đều sinh ra xâu ký tự kết thúc và L(G‟) = L(G) Phạm Hùng Phú 119
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Process Bước 1: khởi tạo S‟ = S; T‟ = T; N‟ = {A N  A → w P và w T*}; Bước 2: Xác định N‟ Với mỗi luật sinh A → X X X P kiểm tra 1 2 n Nếu X N‟ T‟ i thì N‟ = N‟{A}; i Bước 3: Quay lại bƣớc 2 cho đến khi gặp một lƣợt không thêm đƣợc biến nào vào N‟ nữa. Bước 4: xác định p’ P‟ ={ A → X X X P  A N‟ và X (N‟ T‟)* i} 1 2 n i Ví dụ: Xét văn phạm G = (N, T, P, S): N = S, A, B, C, D T = a, b, c, d S = S; P: có các luật sinh sau: S → AB | a; A → a ; C → b; D → bA. Áp dụng giải thuật trên, ta có: 1. G‟= (N‟, T‟, P‟, S‟): T‟ = a, b, c, d S‟ = S; 2. N‟: Bƣớc N‟ Giải thích KT {S, A, C} S → a; A → a; C → b 1 {S, A, C, D} D → bA; S → a; A → a; C → b 2 {S, A, C, D} D → bA; S → a; A → a; C → b 3. P‟ = {S → a; A → a; C → b; D → bA}. 4) Bổ đề 2 (Dùng loại bỏ các ký tự không nằm trong xâu đƣợc dẫn xuất ra từ ký tự bắt đầu văn phạm) 120 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Nếu G = (N, T, P, S) là CFG thì ta có thể tìm đƣợc CFG G‟ = (N‟, T‟, P‟, S) tƣơng đƣơng sao cho mỗi X N‟  T‟ tồn tại α, β (N‟  T‟)* để S * αXβ. Chứng minh: Tập N‟  T‟ gồm các ký tự xuất hiện trong dạng câu của G đƣợc xây dựng bởi giải thuật lặp nhƣ sau: Bước1: Đặt N‟ = {S}; T‟ = ∅; Bước2: Với mỗi A N‟ thực hiện - Tìm tất cả các luật sinh A → α | α | | α là các luật sinh trong P 1 2 n - Nếu có thì thêm tất cả các biến của α , α , , α vào N‟ và các ký tự 1 2 n kết thúc của α , α , , α vào T‟. 1 2 n Bước3: Lặp lại bƣớc 2 cho đến khi không còn biến hoặc ký tự kết thúc nào đƣợc thêm vào nữa. Dễ thấy, X N‟  T‟ thì tồn tại α, β (N‟  T‟)* để S * αXβ, trong đó P‟ là tập hợp tất cả các luật sinh của P chỉ chứa các ký tự thuộc (N‟  T‟). Ta dễ dàng chứng minh L(G‟) = L(G) . Từ việc chứng minh bổ đề 2, ta có giải thuật sau. 5) Giải thuật loại bỏ ký hiệu không được dẫn xuất ra từ ký hiệu bắt đầu Input G = (N, T, P, S) - CFG Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi ký hiệu của nó đều đƣợc dẫn xuất ra từ ký hiệu bắt đầu và L(G‟) = L(G) Process Bước1: Khởi tạo S‟ = S; N‟ = {S}; T‟ = ∅ Bước2: Xác định N‟, T‟ + Với mỗi A N‟ thực hiện - Tìm tất cả các luật sinh A → α | α | | α là các luật sinh trong P 1 2 n - Nếu có thì thêm tất cả các biến của α , α , , α vào N‟ và các ký tự 1 2 n kết thúc của α , α , , α vào T‟ ; 1 2 n Phạm Hùng Phú 121
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Bước3: Quay lại bƣớc 2 cho đến khi gặp một lƣợt không còn biến hoặc ký tự kết thúc nào đƣợc thêm vào N‟ và T‟ nữa. Bước 4: xác định p’ P‟ ={ A → X X X P  A N‟ và X (N‟ T‟)* i} 1 2 n i Ví dụ 1: Loại bỏ ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu trong văn phạm sau: G = (N, T, P, S): N = S, A, B, C, D T = a, b, c, d S = S; P: có các luật sinh sau: S → AB | a; A → a; C → b; D → bA. Áp dụng giải thuật trên, ta có: 1. G‟= (N‟, T‟, P‟, S‟): S‟ = S; 2. N‟, T‟: Bƣớc N‟ T‟ Giải thích KT {S}   1 {S, A, B} {a} S → AB a 2 {S, A, B} {a} A → a 3. P‟= {S → AB a; A → a}. Ví dụ2: Loại bỏ các ký thừa trong văn phạm trên - Theo ví dụ trên loại bỏ ký tự không đƣợc sinh ra từ ký hiệu bắt đầu ta có văn phạm với tập luật sinh: S → AB  a; A → a. - Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc, ta thu đƣợc văn phạm với tập luật sinh: S → a Nhƣ vậy, để loại bỏ các ký thừa trong văn phạm phi ngữ cảnh, ta chỉ việc thực hiện hai công việc: Loại bỏ các biến không sinh ra ký tự kết thúc và các ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu. Từ đó ta có định lý. 122 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 6) Định lý Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng đƣợc sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký tự thừa. Chứng minh: Đặt L = L(G) là CFL không rỗng. Đặt G là kết quả của việc áp dụng bổ đề 1 vào G và G là kết quả của việc áp 1 2 dụng bổ đề 2 vào G . 1 Giả sử G có ký tự thừa là X. Theo bổ đề 2 ta có S * αXβ. Vì tất cả các ký tự 2 G2 trong G đều có trong G nên theo bổ đề 1: S * αXβ * w với w là xâu ký tự kết 2 1 G1 G1 thúc. Vì vậy không có ký tự nào trong dẫn xuất αXβ * w bị loại bỏ bởi bổ đề 2, vậy X G1 dẫn ra ký tự kết thúc trong G . Suy ra X là ký tự không thừa (mâu thuẫn). 2 Vậy văn phạm G không có ký tự thừa nào. 2 Ví dụ: Cho văn phạm G = (N, T, P, S): N = S, , , C, D T = a, b, c S = S; P: S a;  a; S b;  b; D c; A BC; Hãy loại bỏ các ký tự thừa trong văn phạm trên. - Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc: 1. G‟= (N‟, T‟, P‟, S‟): T‟ = a, b, c S‟ = S; 2. N‟: Bƣớc N‟ Giải thích KT {A, B, D} B → a; A → b; D → c 1 {S, B, D, A} S a; S b; B → a; A → b; D → c 2 {S, A, B, D} S a; S b; B → a; A → b; D → c Phạm Hùng Phú 123
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 3. P‟= {S →Aa; S → Bb; B → a; A → b; D → c }. - Áp dụng giải thuật loại bỏ các ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu: 1. G” = (N”, T”, P”, S”): S” = S; 2. N” và T”: Bƣớc N” T” Giải thích KT {S}  1 {S , A, B} {a, b} S a; S b 2 {S, A, B} {a, b} S a; S b; A → b;  a 3. P” = {S → Aa; S → Bb; A → b; B → a}. Khi đó L(G) = L(G”) và G” không chứa ký hiệu thừa. 3.2.2. Luật sinh ε (ε quy tắc) 1) Định nghĩa - Một luật sinh có dạng A → ε đƣợc gọi là luật sinh ε (ε quy tắc). - Một biến A đƣợc gọi là biến rỗng (nullable) nếu A + ε Ta xét đến việc loại bỏ các luật sinh ε. Nếu ε L(G) thì không thể loại đƣợc tất cả các luật sinh ε, nhƣng nếu ε ∉ L(G) thì có thể. Phƣơng pháp loại bỏ dựa trên việc xác định liệu một biến A có là biến rỗng hay không ?. Ta có thể thay thế mỗi luật sinh B → X X X bằng tất cả các luật sinh đƣợc định dạng bởi việc xóa bỏ 1 2 n tập hợp con các biến X rỗng, nhƣng không bao gồm luật sinh B → ε, ngay cả khi tất i cả các X đều là biến rỗng. i 2) Bổ đề 3 (Dùng để loại bỏ luật sinh ε) Cho CFG G = (N, T, P, S) với ε L(G), có một CFG G‟= (N‟, T, P‟, S) tƣơng đƣơng sao cho G‟ không chứa luật sinh ε. Chứng minh: Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp nhƣ sau: - Bắt đầu, nếu A → ε là một luật sinh thì A là biến rỗng. 124 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 - Kế tiếp, nếu B → α, trong đó α gồm toàn các ký tự là các biến rỗng đã đƣợc tìm thấy trƣớc đó thì B cũng là biến rỗng. - Lặp lại cho đến khi không còn biến rỗng nào đƣợc tìm thấy nữa. Tập luật sinh P‟ đƣợc xây dựng nhƣ sau: Nếu A → X X X là một luật sinh trong 1 2 n P thì ta thêm tất cả các luật sinh A → α α α vào P‟ với điều kiện: 1 2 n 1. Nếu X không là biến rỗng thì α = X ; i i i 2. Nếu X là biến rỗng thì α là X hoặc ε; i i i 3. Không phải tất cả α đều bằng ε. i Đặt G‟ = (N, T, P‟, S). Ta sẽ chứng minh rằng với mọi A N và w T*; A * w nếu và chỉ nếu w ≠ ε và A * w. G‟ G - Thuận: i Đặt A w và w ≠ ε, ta chứng minh quy nạp rằng A * w. G G‟‟ Nếu i = 1 ta có A → w là một luật sinh trong P, và vì w ≠ ε nên luật sinh này cũng thuộc P‟. Giả sử kết quả đúng tới i - 1 (i >1) i -1 Xét A X X X w. Ta viết w = w w w sao cho với j, X * w . G 1 2 n G 1 2 n j j Nếu w ≠ ε và X là biến thì theo giả thiết quy nạp, ta có X * w (vì dẫn j j j G‟‟ j xuất X * w có ít hơn i bƣớc). Nếu w = ε thì X là biến rỗng, vậy A → β β β là j j j j 1 2 n một luật sinh trong P‟, trong đó β = X nếu w ≠ ε và β = ε nếu w = ε. j j j j j Vì w ≠ ε nên không phải tất cả β là ε. Vậy, ta có dẫn xuất: j A β β β * w β β * w w β β * * w w w = w trong G‟‟. 1 2 n 1 2 n 1 2 3 n 1 2 n - Đảo: i Giả sử A w. Chắc chắn rằng w ≠ ε vì G‟ không có luật sinh ε. Ta quy G‟ nạp theo i rằng A * w. G Nếu i = 1: Ta thấy A → w là một luật sinh trong P‟, do đó cũng phải có luật sinh A → w trong P sao cho bằng việc loại bỏ các ký tự rỗng trong α, ta có w. Vậy, Phạm Hùng Phú 125
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống có tồn tại dẫn xuất A α * w, trong đó α * w liên quan đến các dẫn xuất ε từ G G các biến rỗng của α mà chúng ta đã loại bỏ khỏi w. Giả sử kết quả đúng tới i - 1 (i >1) i - 1 Xét A X X X w. Phải có luật sinh A → β trong P sao cho G‟ 1 2 n G‟ X X X tìm đƣợc khi loại bỏ các biến rỗng của β. Vậy A * X X X (chứng 1 2 n G 1 2 n minh tƣơng tự nhƣ ở trên). Ta viết w = w w w sao cho với j ta có X * w 1 2 n j G‟ j (bằng ít hơn i bƣớc). Theo giả thiết quy nạp X * w nếu X là biến. Nếu X là ký j G‟ j j j tự kết thúc thì w = X và X * w là hiển nhiên. Vậy A * w. j j j G j G Hơn nữa S * w nếu và chỉ nếu S * w. Vậy L(G‟) = L(G) - {ε}. G‟ G Từ việc chứng minh bổ đề trên, ta có giải thuật sau. 3) Giải thuật loại bỏ luật sinh  Input G = (N, T, P, S) – CFG,  L(G) Output G‟= (N‟, T‟, P‟, S‟) – CFG, G‟ không chứa luật sinh  và L(G‟) = L(G) Process Bước1: Khởi tạo N‟ = N; T‟ = T; S‟ = S; P‟ = ; R = {A N‟  A →  P} Bước2: Tìm Tập các biến rỗng R Với mỗi luật sinh A → X X X P kiểm tra 1 2 n Nếu X R i thì R = R{A}; i Bước3: Quay lại bƣớc 2 cho đến khi không còn biến rỗng nào đƣợc thêm vào R nữa. Bước4: Xác định P‟ Với mỗi luật sinh A → X X X P không là luật sinh ε thực hiện 1 2 n Thêm tất cả các luật sinh A → α α α vào P‟ với điều kiện: 1 2 n 1. Nếu X không là biến rỗng thì α = X ; i i i 2. Nếu X là biến rỗng thì α là X hoặc ε; i i i 126 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 3. Không phải tất cả α đều bằng ε. i Chú ý: Trong trƣờng hợp  L(G), muốn có một văn phạm thực sự tƣơng đƣơng với văn phạm G thì sau khi loại bỏ các luật sinh , ta phải bổ sung thêm luật sinh S → ε vào tập luật sinh của G‟. Ví dụ: Loại bỏ luật sinh ε trong văn phạm sau: S → AB; A → aA | ε; B → bB | ε. - Áp dụng giải thuật trên, ta có tập các biến rỗng: Bƣớc R-Nullable Giải thích KT {A, B} A → ε; B → ε 1 {A, B, S} S → AB 2 {A, B, S} S → AB Tập biến rỗng Nullable = {A, B, S} - Tập luật sinh P‟: S → AB | A | B; A → aA | a; B → bB | b. Vì  L(G) nên phải bổ sung thêm luật sinh S → ε vào P‟. 4) Định lý Nếu L = L(G) với CFG G = (N, T, P, S) thì L - {ε} là L(G‟) với CFG G‟ không có ký tự thừa và không có luật sinh ε. Chứng minh: - Trƣớc hết, thực hiện loại bỏ luật sinh ε trong G để thu đƣợc G”. - Tiếp theo, thực hiện loại bỏ các ký hiệu thừa trong G” để thu đƣợc G‟. Vì thực hiện loại bỏ các ký hiệu thừa trong G” không đƣa ra thêm luật sinh mới nào nên G‟ không có chứa ký tự là biến rỗng hay ký tự thừa. Phạm Hùng Phú 127
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 3.2.3. Luật sinh đơn vị 1) Định nghĩa Một luật sinh có dạng A → B với A, B đều là biến (ký tự không kết thúc) gọi là luật sinh đơn vị. 2) Bổ đề 4 (Dùng để loại bỏ luật sinh đơn vị) Cho CFG G = (N, T, P, S) với ε L(G), có một CFG G‟= (N, T, P‟, S) tƣơng đƣơng sao cho G‟ không chứa luật sinh đơn vị. Chứng minh: Đặt L là CFL không chứa ε và L = L(G) với G = (N, T, P, S) là một CFG nào đó. Theo định lý trên, xây dựng tập hợp mới P‟ gồm các luật sinh từ P nhƣ sau: - Đầu tiên đƣa các luật sinh không là luật sinh đơn vị vào P‟. - Sau đó, nếu có suy dẫn dạng A + B với A, B N thì thêm vào P‟ tất cả các luật sinh dạng A → α, với B→ α không phải là luật sinh đơn vị của P. Chú ý rằng ta có thể dễ dàng kiểm tra có hay không A + B vì G không có G luật sinh ε và nếu A B B2 B (trong đó một vài biến nào đó có G 1 G G G thể xuất hiện 2 lần) thì ta có thể tìm một chuỗi rút ngắn hơn A + B. Vì vậy, ta chỉ G xét các luật sinh đơn vị không có biến lặp lại. Bây giờ ta sửa lại văn phạm G‟= (N, T, P‟, S). Chắc chắn rằng nếu A → α là một luật sinh trong P‟ thì A + α. Vậy nếu có dẫn xuất trong G‟ thì có dẫn xuất G trong G. Giả sử rằng w L(G). Xét dẫn xuất trái của w trong G: S α α α = w. G 0 G 1 G G n Nếu 0 ≤ i < n thì nếu trong G có α α bằng luật sinh không là luật sinh i G i+1 đơn vị thì trong G‟ cũng có α α không là luật sinh đơn vị. Giả sử α α i G‟ i+1 i G i+1 bằng luật sinh đơn vị, nhƣng bƣớc dẫn xuất trƣớc đó α α không phải bằng luật i - 1 i sinh đơn vị hoặc i = 0. Và chuỗi dẫn xuất trong G từ α α α tất i + 1 G i + 2 G G j cả đều bằng luật sinh đơn vị, còn từ α α không là luật sinh đơn vị thì ta thấy j G j+1 tất cả các α , α , , α sẽ có cùng độ dài và vì chuỗi dẫn xuất là dẫn xuất trái nên i i+1 j 128 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 các ký tự thay thế phải ở cùng một vị trí. Do vậy, tại vị trí này α α bằng một j G j+1 luật sinh nào đó thuộc P‟- P hay có nghĩa là một luật sinh không thuộc văn phạm G. Điều này sinh ra mâu thuẫn. Vậy L(G) = L(G‟). Ta còn có G‟ không có chứa luật sinh đơn vị (theo chứng minh trên) nên G cũng sẽ không chứa luật sinh đơn vị (do G G‟). Từ việc chứng minh bổ đề trên, ta có giải thuật sau. 3) Giải thuật loại bỏ luật sinh đơn vị Input G = (N, T, P, S) – CFG,  L(G) Output G‟= (N‟, T‟, P‟, S‟) – CFG, G‟ không chứa luật sinh  và L(G‟) = L(G) Process Bước1: Khởi tạo N‟ = N; T‟ = T; S‟ = S; P‟ = {A P A không là lật sinh đơn vị } Bước2: Xây dựng P‟ - Với mỗi biến A N‟ thực hiện: tìm Δ = {B N‟ | A + B} A - Với mỗi biến A N‟ và Δ  thực hiện: A Với mỗi B Δ thực hiện: A + Tìm các luật sinh B → α P‟; + Thêm vào P‟ tất cả các luật sinh dạng A → α. Ví dụ: Loại bỏ các luật sinh đơn vị trong văn phạm sau: E → E + T | T ; T → T * F | F; F → (E) | a. Áp dụng giải thuật trên, ta có G‟= (N‟, T‟, P‟, S‟): - N‟ = {E, T, F}; T‟ = {+, *, (, ), a} ; S‟ = E ; P‟ = {E → E + T ; T → T * F; F → (E) | a} - Δ = {T, F}; Δ = {F}; Δ =  E T F - Với biến E, phải thêm vào P‟ các luật sinh E → T * F | (E) | a; Phạm Hùng Phú 129
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống - Với biến T, phải thêm vào P‟ các luật sinh T → (E) | a; Vậy tập luật sinh P‟, theo giải thuật 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: E → E + T | T * F | (E) | a; T → T * F | (E) | a; F → (E) | a. 4) Định lý Mỗi CFL không chứa ε đƣợc sinh ra bởi CFG không có ký tự thừa, luật sinh ε hoặc luật sinh đơn vị . Chứng minh: Chỉ việc áp dụng các giải thuật trên để loại bỏ: các luật sinh đơn vị, luật sinh , các ký tự thừa sẽ thu đƣợc một văn phạm thỏa mãn điều kiện của định lý. 3.3. Chuẩn hóa văn phạm phi ngữ cảnh Phần trên ta đã xem xét vấn đề rút gọn văn phạm phi ngữ cảnh để nhận đƣợc văn phạm tối giản. Tuy nhiên chỉ nhƣ vậy thôi chƣa đủ. Khi viết các chƣơng trình dịch, chƣơng trình sẽ phức tạp lên rất nhiều nếu mỗi quy tắc sinh có nhiều dạng khác nhau. Vấn đề đặt ra là liệu có thể đƣa ra các quy tắc sinh của P về cùng một dạng nào đó đƣợc không. Việc đƣa các quy tắc sinh của văn phạm phi ngữ cảnh về các dạng chung đƣợc gọi là chuẩn hoá văn phạm phi ngữ cảnh. 3.3.1. Dạng chuẩn Chomsky - CNF (Chomsky Normal Form) 1) Định nghĩa Văn phạm phi ngữ cảnh G = (N, T, P, S) có  L(G) đƣợc gọi là ở dạng chuẩn Chomsky (CNF) nếu các luật sinh của nó chỉ có một trong hai dạng A → BC hoặc A → a, với A, B, C N và a T. 2) Định lý Một ngôn ngữ phi ngữ cảnh bất kỳ không chứa ε đều đƣợc sinh ra bằng một văn phạm ở dạng chuẩn Chomsky nào đó. Chứng minh: 130 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Đặt G là CFG sinh ra CFL không chứa ε. CFG tƣơng đƣơng có dạng chuẩn Chomsky có thể xây dựng từ G theo giải thuật sau: Bước 1: Khử luật sinh đơn vị dạng A → B, với A, B là biến (ký tự không kết thúc). Theo định lý ở phần trƣớc, ta có thể tìm đƣợc CFG tƣơng đƣơng G = (N, T, P1, S) 1 không có luật sinh đơn vị và luật sinh ε. Vậy nếu luật sinh mà vế phải chỉ có một ký tự thì đó phải là ký tự kết thúc và luật sinh này là luật sinh có dạng đúng trong định lý. Bước 2: Thay thế các luật sinh có độ dài vế phải >1 và có chứa ký tự kết thúc. Xét luật sinh trong P có dạng A → X X X (m >1). Nếu X là ký tự kết 1 2 m i thúc a thì ta đƣa thêm một biến (ký tự không kết thúc) mới C và luật sinh mới C → a a a. Thay thế X bởi C , gọi tập các biến (ký tự không kết thúc) mới là N‟ và tập luật i a sinh mới là P‟. Xét CFG G = (N‟, T, P‟, S). Nếu α β thì α * β. Vậy L(G )  L(G ). 2 G1 G2 1 2 Ta chứng minh quy nạp theo số bƣớc dẫn xuất rằng nếu A * w, với A N và w G2 * T thì A * w. G1 Kết quả hiển nhiên với 1 bƣớc dẫn xuất. Giả sử kết quả đúng tới k bƣớc dẫn xuất. Xét A * w bằng k +1 bƣớc dẫn xuất. G2 Bƣớc đầu tiên có dạng A → B B B (m > 1). Ta có thể viết w = w w 1 2 m 1 2 w trong đó B * w , 1 ≤ i ≤ m. Nếu B là ký tự kết thúc a nào đó thì w là a . m i G2 i i i i i Theo cách xây dựng P‟ ta có luật sinh A → X X X của P trong đó X = B nếu B 1 2 m i i i N và X = a nếu B N‟- N. Với B N, ta đã biết rằng có dẫn xuất B * w i i i i i G1 i bằng ít hơn k bƣớc, do vậy theo giả thiết quy nạp X * w . Vậy A * w. i G1 i G1 Ta đã có kết quả là một CFL bất kỳ đƣợc sinh ra từ một CFG mà mỗi luật sinh có dạng A → a hoặc A → B1B2 Bm với m 2 và A, B1, B2, , Bm là các biến (ký tự không kết thúc); a là ký tự kết thúc. Ta sửa G2 bằng cách thêm vào P‟ một số luật sinh. Phạm Hùng Phú 131
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Bước 3: Thay thế các luật sinh có độ dài vế phải > 2 ký tự chƣa kết thúc. Xét luật sinh trong P‟có dạng A → B B2 Bm (m 2). Ta bổ sung thêm m- 1 2 biến mới D , D , , D và thay nó bằng tập các luật sinh: 1 2 m - 2 A → B D ; 1 1 D → B D ; 1 2 2 D → B D ; m - 3 m - 2 m - 2 D → B B . m - 2 m - 1 m Đặt N” là tập các biến (ký tự không kết thúc) mới, P” là tập các luật sinh mới và văn phạm mới G = (N”, T, P”, S). Ta có G chứa các luật sinh thoả mãn định lý. 3 3 Hơn nữa, nếu A * β thì A * β, vậy L(G )  L(G ). Ngƣợc lại cũng G2 G3 2 3 đúng tức là, L(G )  L(G ). Chúng ta cũng đã có L(G )  L(G ) và L(G )  L(G ). 3 2 2 1 1 2 Vậy G là văn phạm thoả mãn dạng chuẩn CNF. 3 Từ việc chứng minh định lý, có thể rút ra giải thuật sau. 3) Giải thuật biến đổi văn phạm phi ngữ cảnh về dạng chuẩn Chomsky Input G = (N, T, P, S) – CFG,  L(G) Output G‟= (N‟, T‟, P‟, S) – ở dạng chuẩn Chomsky và L(G‟) = L(G) Process Bước1: Khử luật sinh đơn vị Bước 2: Thay thế các luật sinh có độ dài vế phải >1 và có chứa ký tự kết thúc. Với mỗi luật sinh trong P có dạng A → X X X (m >1) thực hiện 1 2 m Nếu X là ký tự kết thúc a thì i - Thêm vào một biến mới C a - Thêm vào một luật sinh mới C → a. a - Thay thế X bởi C i a (tập các biến mới là N‟ và tập luật sinh mới là P‟) Bước 3: Thay thế các luật sinh có độ dài vế phải > 2 ký tự chƣa kết thúc. 132 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Với mỗi luật sinh trong P‟có dạng A → B B2 Bm (m 2) thực hiện 1 - Thêm vào N‟ m-2 biến mới D , D , , D 1 2 m - 2 - Thay nó bằng tập các luật sinh: A → B D ; 1 1 D → B D ; 1 2 2 D → B D ; m - 3 m - 2 m - 2 D → B B . m - 2 m - 1 m Ví dụ: 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: Khử các luật sinh đơn vị Gọi tập Δ = {B | A * B }, xét các biến (ký tự không kết thúc) trong văn phạm, ta có: A Δ = {A, B }; S Δ = {B}; A Δ = {}. B Sau khi bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị ta có: 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ý tự 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 (ký tự không kết thúc) mới C , C và 2 luật sinh mới C → a và C → b. a b a b Văn phạm tƣơng đƣơng có tập luật sinh nhƣ sau: S → C A | a | C B | b | ABA; a b Phạm Hùng Phú 133
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống A → C A | a | C B | b; a b B → C B | b; b C → a; a C → b. 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 → C A | a | C B| b | AD1; a b A → C A | a | C B| b; a b B → C B| b; b C → a; 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. 3.3.2. Dạng chuẩn Greibach (Greibach Normal Form - GNF) 1) Các định nghĩa - Văn phạm phi ngữ cảnh G = (N, T, P, S) có  L(G) đƣợc gọi là ở dạng chuẩn Greibach (GNF) nếu các luật sinh của nó chỉ có một dạng A → aα với A N; * a T và α (N T) . * - Một luật sinh có dạng A → α (biến A ở bên trái) với A N, α (NT) đƣợc gọi là A – luật sinh. - Một văn phạm phi ngữ cảnh đƣợc gọi là đệ quy trái trực tiếp nếu tồn tại một * luật sinh có dạng A → Aα với A N, α (NT) . 2) Bổ đề 1 (Dùng thay thế các luật sinh trực tiếp) Cho G = (N, T, P, S) là một CFG, A → α Bα và các B - luật sinh B → β | β 1 2 1 2 | | β là các luật sinh trong P; văn phạm G = (N, T, P , S) thu đƣợc từ G bằng cách r 1 1 134 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 loại bỏ luật sinh A → α Bα và thêm vào các luật sinh A → α β α | α β α | | 1 2 1 1 2 1 2 2 α β α thì L(G) = L(G ). 1 r 2 1 Chứng minh: - Hiển nhiên L(G )  L(G) vì nếu A → α β α đƣợc dùng trong dẫn xuất của 1 1 i 2 G thì ta dùng A α Bα α β α . 1 G 1 2 G 1 i 2 - Để chỉ ra L(G)  L(G ) ta cần chú ý rằng A→α Bα là luật sinh trong P - P 1 1 2 1 (có trong G và không có trong G ). Bất cứ khi nào luật sinh A → α Bα đƣợc dùng 1 1 2 trong dẫn xuất của G thì phải viết lại tại bƣớc sau đó dùng luật sinh dạng B → β . i Hai bƣớc dẫn xuất này có thể đƣợc thay thế bằng một bƣớc dẫn xuất duy nhất, hay: A → α Bα và B → β A α β α 1 2 i G1 1 i 2 Vậy L(G) = L(G ) 1 3) Bổ đề 2 (Dùng loại bỏ luật sinh dạng đệ quy trái trực tiếp trong văn phạm) G = (N, T, P, S) là một CFG; A → Aα | Aα | | Aα | β | β | | β là tập 1 2 r 1 2 s các A - luật sinh; G = (N  {B}, T, P , S) là CFG đƣợc tạo ra từ G bằng cách thêm 1 1 vào N biến mới B và thay các A - luật sinh bằng tập các luật sinh dạng: 1. A → β B | β | β | | β với 1 ≤ i ≤ s i 1 2 s 2. B → α B | α với 1 ≤ i ≤ r i i thì L(G) = L(G ). 1 Chứng minh: Trong một dãy dẫn xuất trái, một chuỗi luật sinh dạng A → Aα phải kết thúc i bằng A → β . Tức là: j A Aα Aα α Aα α α β α α α i1 i2 i1 ip ip-1 i1 j ip ip-1 i1 Dãy dẫn xuất trong G có thể thay bằng dãy dẫn xuất trong G bởi: 1 A β B β α B β α α B β α α α B j j ip j ip ip-1 j ip ip-1 i2 β α α α . j ip ip-1 i1 Phạm Hùng Phú 135
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Sự chuyển đổi ngƣợc lại cũng có thể đƣợc. Vậy L(G) = L(G ). 1 4) Định lý (Dạng chuẩn Greibach - GNF) Mỗi CFL bất kỳ không chứa ε đƣợc sinh ra bởi một CFG ở dạng chuẩn Greibach – GNF. Chứng minh: Bước 1: Đặt G là CFG sinh ra CFL không chứa ε. Xây dựng văn phạm tƣơng đƣơng G‟ có dạng chuẩn Chomsky. Bước 2: Đổi tên các biến (ký tự không kết thúc) trong tập của G‟ thành A , 1 A , , A (m ≥ 1) với A là ký tự bắt đầu. Đặt N = {A , A , , A }. 2 m 1 1 2 m Bước 3: Thay thế các luật sinh sao cho nếu A → A γ là một luật sinh thì j > i i j bằng cách: Bắt đầu từ A và tiến tới A , thay thế các A - luật sinh: 1 m k Nếu A → A γ là luật sinh với j < k thì sinh ra một tập luật sinh mới bằng k j cách thay thế A bên vế phải bằng vế phải của mỗi A - luật sinh theo bổ đề 1. Lặp lại j j không quá k - 1 lần ta thu đƣợc tập luật sinh dạng A → A γ với l ≥ k. k l Sau đó, các luật sinh với l = k đƣợc thay thế theo bổ đề 2 bằng cách đƣa vào các biến (ký tự không kết thúc) mới B . k Giải thuật cụ thể nhƣ sau: Begin For k:= 1 to m do begin for j:= 1 to k-1 do for Mỗi luật sinh dạng A → A α do k j begin for Tất cả luật sinh A → β do Thêm luật sinh A → βα; j k Loại bỏ luật sinh A → A α k j end; 136 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 for Mỗi luật sinh dạng A → A α do k k begin Thêm các luật sinh B → α và B → αBk ; k k Loại bỏ luật sinh A → A α k k end; for Mỗi luật sinh A → β trong đó β không bắt đầu bằng A do k k Thêm luật sinh A → βBk k end; End; Bằng cách lặp lại bƣớc xử lý trên cho mỗi biến nguồn, trong P chỉ chứa các luật sinh có dạng nhƣ sau: 1. A → A γ với j > i; i j 2. A → aγ với a T; i * 3. B → γ với γ (N  {B , B , , B }) k 1 2 i - 1 Bước 4: Thay thế các A - luật sinh về đúng dạng. i Gọi N‟ là tập biến (ký tự không kết thúc) mới phát sinh sau bƣớc 3. Chú ý rằng ký tự trái nhất của vế phải trong một luật sinh bất kỳ đối với biến (ký tự không kết thúc) A phải là một ký tự kết thúc, vì A là biến (ký tự không kết m m thúc) có chỉ số cao nhất. Ký tự trái nhất của vế phải của một A - luật sinh bất kỳ m-1 phải là A hoặc một ký tự kết thúc. Nếu là A , ta tạo ra tập luật sinh mới bằng cách m m thay thế A bởi chuỗi vế phải của các A -luật sinh theo bổ đề 3. Tiếp tục quá trình m m này cho các luật sinh từ A , , A , A cho tới khi vế phải của tất cả các A - luật m-2 2 1 i sinh có dạng bắt đầu bằng một ký tự kết thúc. Bước 5: Thay thế các B -luật sinh về đúng dạng. k Bƣớc cuối cùng, ta khảo sát các luật sinh với tập các biến (ký tự không kết thúc) mới B , B , , B . 1 2 m Phạm Hùng Phú 137
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Vì ta bắt đầu từ văn phạm đã có dạng chuẩn Chomsky, nên dễ dàng chứng minh quy nạp theo số lần áp dụng bổ đề 1 và bổ đề 2 rằng vế phải của mỗi A -luật i sinh, với 1 ≤ i ≤ n, bắt đầu bằng ký tự kết thúc hoặc A A với j, k nào đó. Vậy α j k (trong bƣớc (7)) không khi nào có thể rỗng hoặc bắt đầu bằng một B khác, hay tất j cả B - luật sinh đều có vế phải bắt đầu bằng ký tự kết thúc hoặc A . Một lần nữa, lại i i áp dụng bổ đề 1 cho mỗi B - luật sinh. i Ta thu đƣợc tập luật sinh trong văn phạm sau cùng thỏa đúng dạng chuẩn Greibach. Từ việc chứng minh định lý, có thể rút ra giải thuật biến đổi văn phạm phi ngữ cảnh về dạng chuẩn Greibach. 3) Giải thuật biến đổi văn phạm phi ngữ cảnh về dạng chuẩn Greibach Input G = (N, T, P, S) – CFG,  L(G) Output G‟= (N‟, T‟, P‟, S) – ở dạng chuẩn Greibach và L(G‟) = L(G) Process Bước 1: Biến đổi văn phạm G về dạng chuẩn Chomsky. Bước 2: Đổi tên các biến của N = {A , A , , A } với A là ký tự bắt đầu. 1 2 m 1 Bước 3: Thay thế các luật sinh sao cho nếu A → A γ là một luật sinh thì j > i i j bằng cách thay thế các A - luật sinh với k = 1, 2, , m: k - Nếu A → A α là một luật sinh mà j < k thì k j + Tìm tất cả luật sinh A → β j + Thay A → A α bằng tập A → βα  β k j k - Nếu A → A α là một luật sinh thì k k + Thêm vào biến mới Bk + Thay A → A α bằng B → α và B → αBk k k k k - Nếu A → β là một luật sinh mà β không bắt đầu bằng A thì k k Thêm luật sinh A → βBk k Bước 4: Thay thế các A - luật sinh về đúng dạng chuẩn. i 138 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Thay thế các luật sinh các A - luật sinh với k = m-1, m- 2, , 1 bằng cách: k Nếu A → A α là một luật sinh thì k j + Tìm tất cả luật sinh A → β j + Thay A → A α bằng tập A → βα  β k j k Bước 5: Thay thế các B - luật sinh về đúng dạng chuẩn. k Với mỗi B - luật sinh bắt đầu bằng một biến thực hiện thay thế B - luật k k sinh này cách: - Tìm tất cả các luật sinh có vế trái là biến đó - Thay vế phải của các luật sinh tìm đƣợc vào biến đó ở vế phải của B - k luật sinh. Ví dụ: Tìm văn phạm có dạng GNF tƣơng đƣơng văn phạm G sau: A → A A | A A ; 1 2 1 2 3 A → A A | a; 2 3 1 A → A A | b. 3 2 2 Bước 1: G đã thỏa mãn dạng chuẩn CNF và sinh ra CFL không chứa ε Bước 2: Ta có N = {A , A , , A } 1 2 3 Bước 3: Thay thế các luật sinh sao cho nếu A → A γ là một luật sinh thì j > i. i j Trong tập luật sinh, các luật sinh cho A và A đã thỏa điều kiện j > i. Chỉ có 1 2 luật sinh A → A A cần sửa đổi. Ta lại có A → A A | a, nên ta thay luật sinh này 3 2 2 2 3 1 bằng A → A A A | aA A → A A A | aA | b. 3 3 1 2 2 3 3 1 2 2 Sau đó, loại bỏ đệ quy trái trực tiếp cho A luật sinh, ta đƣợc tập luật sinh 3 mới có dạng nhƣ sau: A → aA | b | aA B | bB ; 3 2 2 B → A A | A A B. 1 2 1 2 Do đó, văn phạm có tập luật sinh: Phạm Hùng Phú 139
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống A → A A | A A 1 2 1 2 3 ; A → A A | a ; 2 3 1 A → aA | b | aA B | bB ; 3 2 2 B → A A | A A B. 1 2 1 2 Bước 4: Thay thế các A -luật sinh về đúng dạng chuẩn. i Ta có, tất cả các A - luật sinh A → aA | b | aA B | bB đã có dạng chuẩn. 3 3 2 2 Thay thế các A rồi A - luật sinh ta thu đƣợc tập luật sinh mới nhƣ sau: 2 1 A → aA A | bA | aA BA | bBA | a; 2 2 1 1 2 1 1 A → aA A A | bA A | aA BA A | bBA A | aA | 1 2 1 1 1 1 2 1 1 1 1 1 aA A A | bA A | aA BA A | bBA A | aA 2 1 3 1 3 2 1 3 1 3 3 ; B → A A | A A B; 1 2 1 2 Bước 5: Thay thế các B - luật sinh về đúng dạng chuẩn. k B → aA A A A | bA A A | aA BA A A | bBA A A | aA A 2 1 1 2 1 1 2 2 1 1 2 1 1 2 1 2 | aA A A A | bA A A | aA BA A A | bBA A A | aA A 2 1 3 2 1 3 2 2 1 3 2 1 3 2 3 2 | aA A A A B | bA A A B | aA BA A A B | bBA A A B | aA A B 2 1 1 2 1 1 2 2 1 1 2 1 1 2 1 2 | aA A A A B | bA A A B | aA BA A A B | bBA A A B | aA A B 2 1 3 2 1 3 2 2 1 3 2 1 3 2 3 2 Cuối cùng, ta thu đƣợc văn phạm có dạng GNF với 39 luật sinh. 3.4. Tính chất của ngôn ngữ phi ngữ cảnh Tƣơng tự ngôn ngữ chính quy, có một số tính chất giúp xác định một ngôn ngữ có là ngôn ngữ phi ngữ cảnh hay không ? 3.4.1. Bổ đề bơm đối với CFL (Dùng để chứng minh một ngôn ngữ không là ngôn ngữ phi ngữ cảnh) 1) Bổ đề Cho L là một CFL bất kỳ, tồn tại một số n chỉ phụ thuộc vào L sao cho nếu z L và | z | ≥ n thì ta có thể viết z = uvwxy sao cho: 1. | vx | ≥ 1 2. | vwx | ≤ n và 140 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 3. i ≥ 0: uvi wxi y L Chứng minh: Đặt G là văn phạm có dạng chuẩn CHOMSKY sinh L - {ε}. Chú ý rằng nếu z L(G) và cây dẫn xuất không có đƣờng đi dài hơn i thì chuỗi sinh ra từ văn phạm i -1 có độ dài không dài hơn 2 . k Giả sử G có k biến (ký tự không kết thúc), ta đặt n = 2 . Nếu z L(G) và k-1 | z | ≥ n thì | z | > 2 , vậy có một đƣờng đi nào đó trên cây dẫn xuất có độ dài lớn hơn hoặc bằng k+1. Nhƣ vậy, đƣờng đi đó sẽ có ít nhất k+2 đỉnh, hay có ít nhất k+1 biến (ký tự không kết thúc) trên đƣờng đi (chỉ có nút lá mới có thể không là biến (ký tự không kết thúc)), suy ra phải có biến (ký tự không kết thúc) xuất hiện hai lần, hơn nữa ta phải có: 1. Có hai đỉnh v và v có cùng nhãn là A 1 2 2. Đỉnh v gần gốc hơn v 1 2 3. Phần đƣờng đi từ v tới lá có độ dài nhiều nhất là k+1 (đi từ lá lên tới gốc 1 theo đƣờng đi, chỉ có lá mới có thể là ký tự kết thúc vì vậy trong k+2 đỉnh đầu tiên phải có ít nhất k+1 biến (ký tự không kết thúc) và phải có ít nhất hai biến (ký tự không kết thúc) trùng nhau) Xét cây con T có đỉnh là v biểu diễn dẫn xuất của chuỗi con có độ dài 1 1 k không quá 2 (vì trong cây con T không có đƣờng đi nào có độ dài vƣợt quá k+1). 1 Đặt z là chuỗi sinh ra từ cây T . Ta gọi T là một cây con có nút gốc là v , rõ ràng 1 1 2 2 T là cây con của T . Giả sử T sinh ra chuỗi z thì ta có thể viết z = z z z . Hơn nữa 2 1 2 2 1 3 2 4 z và z không thể đồng thời bằng ε vì luật sinh đầu tiên trong cây dẫn xuất của T là 3 4 1 A → BC với biến (ký tự không kết thúc) B, C nào đó. Cây con T phải thuộc vào 2 cây con sinh bởi nút biến (ký tự không kết thúc) B hoặc cây con sinh bởi nút biến (ký tự không kết thúc) C. Ta có: k A * z Az và A * z trong đó | z z z | ≤ 2 = n. G 3 4 G 2 3 2 4 i i Vậy A * z z z , với i ≥ 0. G 3 2 4 Hiển nhiên chuỗi z = uz z z y, với các chuỗi u, y nào đó. 3 2 4 Phạm Hùng Phú 141
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Nếu đặt z = v, z = w và z = x, thì ta sẽ hoàn thành việc chứng minh. 3 2 4 2) Ứng dụng bổ đề bơm i i i Ví dụ 1: Chứng minh L = {a b c | i ≥ 1} không phải là ngôn ngữ phi ngữ cảnh. Chứng minh: Giả sử L là ngôn ngữ phi ngữ cảnh, khi đó có tồn tại số n (theo bổ đề bơm). n n n Xét chuỗi z = a b c với | z | ≥ n, ta có thể viết z = uvwxy thoả mãn bổ đề. n n n Ta thấy vx nằm trong a b c và | vwx | ≤ n, vậy vx không thể chứa cả ký tự a và ký tự c (do sau ký tự a bên phải nhất n+1 vị trí mới đến vị trí của c bên trái nhất). i i Nếu vx chỉ có chứa ký tự a, thì chuỗi uwy (trƣờng hợp uv wx y với i = 0) sẽ có chứa j j j số ký tự b và c ít hơn số ký tự a vì | vx | ≥ 1. Vậy uwy không có dạng a b c . Tƣơng tự cho các trƣờng hợp chuỗi vx chỉ chứa ký tự b hay c. Còn nếu trong vx có chứa ký tự a và b thì chuỗi uvy sẽ có chứa số ký tự c lớn hơn a và b, nên nó cũng không thể thuộc L. Cũng tƣơng tự cho trƣờng hợp vx chứa hai ký tự b và c. Cuối cùng, ta suy i i ra chuỗi uv wx y ∉ L, vì các ký tự a, b, c trong chúng không thể bằng nhau với mọi i. Mà theo giả thiết của bổ đề bơm, chuỗi này phải thuộc L, mâu thuẫn. Vậy L không thể là CFL. i j i j Ví dụ 2: Chứng minh L = {a b c d | i, j ≥ 1} không phải là ngôn ngữ phi ngữ cảnh. Chứng minh: Giả sử L là ngôn ngữ phi ngữ cảnh, khi đó có tồn tại số n (theo bổ đề bơm). n n n n Xét chuỗi z = a b c d với | z | ≥ n, ta có thể viết z = uvwxy thoả mãn bổ đề. n n n n Ta thấy vì vx nằm trong a b c d và | vwx | ≤ n, nên vx không thể chứa ít nhất hai ký tự khác nhau. Hơn nữa, nếu vx có chứa hai ký tự khác nhau, thì chúng phải là hai ký tự liên tiếp đứng cạnh nhau, chẳng hạn a và b. Nếu vx chỉ có chứa ký tự a, thì chuỗi uwy sẽ có số ký tự a ít hơn số ký tự c nên không thuộc L, mâu thuẫn. Tƣơng tự với trƣờng hợp chuỗi vx chỉ chứa ký tự b, c hoặc d. Bây giờ giả sử chuỗi vx có chứa a và b thì vwy vẫn có số ký tự a ít hơn c. Mâu thuẫn tƣơng tự cũng xuất hiện khi chuỗi vx có chứa b và c hoặc c và d. Vì chỉ có thể có một trong các trƣờng hợp này nên ta có thể kết luận rằng L không thể là CFL. 142 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 3.4.2. Tính chất đóng của CFL 1) Định lý 1 CFL đóng với phép hợp, phép nhân ghép và phép láybao đóng Kleene. Chứng minh: Đặt L và L là hai CFL sinh bởi các CFG G = (N , T , P , S ) 1 2 1 1 1 1 1 và G = (N , T , P , S ). 2 2 2 2 2 Vì các biến (ký tự không kết thúc) có thể đổi tên mà không ảnh hƣởng tới ngôn ngữ sinh ra nên ta có thể xem tập N và N là rời nhau. Ta cũng giả sử các biến 1 2 (ký tự không kết thúc) mới S , S , S ∉ N hoặc N 3 4 5 1 2 . Đối với L  L : Xây dựng văn phạm G (N  N  {S3}, T  T , P , S ), 1 2 3 1 2 1 2 3 3 trong đó P = P  P  {S → S | S }. 3 1 2 3 1 2 Nếu w L thì dẫn xuất S S * w là một dẫn xuất trong G (vì mỗi luật 1 3 G3 1 G1 3 sinh trong G cũng là luật sinh trong G ). Tƣơng tự mỗi chuỗi trong L có dẫn xuất 1 3 2 trong G bắt đầu bằng S S . Vậy L  L  L(G ). 3 3 2 1 2 3 Ngƣợc lại, nếu w L(G ) thì dẫn xuất S * w phải bắt đầu bằng S → S hoặc S 3 3 G3 3 1 3 → S . Tức là dẫn xuất có dạng S S * w hoặc S S * w. Trong 2 3 G3 1 G3 3 G3 2 G3 trƣờng hợp thứ nhất, do N và N rời nhau nên chỉ có các ký tự của G xuất hiện 1 2 1 trong dẫn xuất S * w. Vì trong các luật sinh của P chỉ có chứa các ký tự thuộc 1 G3 3 G và nằm trong tập luật sinh P , nên ta có thể kết luận chỉ có những luật sinh thuộc 1 1 P đƣợc dùng trong dẫn xuất S * w. Vì thế S * w và w L . Tƣơng tự cho 1 1 G3 1 G1 1 trƣờng hợp dẫn xuất S S , ta cũng có w L . Vậy L(G )  L  L , và vì thế 3 G3 2 2 3 1 2 L(G ) = L  L . 3 1 2 Vậy ta đã chứng minh xong L(G ) = L  L , hay L  L là CFL. 3 1 2 1 2 . Đối với L L Xây dựng văn phạm G = (N  N  {S }, T  T , P , S ) , 1 2: 4 1 2 4 1 2 4 4 trong đó P = P  P  {S → S S }. 4 1 2 4 1 2 Phạm Hùng Phú 143
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Chứng minh tƣơng tự nhƣ trên ta có L(G ) = L L , vậy L L cũng là CFL. 4 1 2 1 2 *: . Đối với L Xây dựng văn phạm G = (N  {S }, T , P , S ), 1 5 1 5 1 5 5 trong đó P = P  { S → S S | ε}. 5 1 5 1 5 * Ta cũng dễ dàng chứng minh đƣợc L(G ) = (L(G )) . 5 1 2) Định lý 2 CFL không đóng với phép giao Chứng minh: i i i Ta đã biết ngôn ngữ L = {a b c | i ≥ 1} không là CFL. Ta có thể chứng minh: 1 i i j - L = {a b c | i ≥ 1 và j ≥ 1} là CFL vì L đƣợc sinh bởi văn phạm: 2 2 S → AB A → aAb | ab B → cB | c i j j - L = {a b c | i ≥ 1 và j ≥ 1} cũng là CFL vì L đƣợc sinh từ văn phạm: 3 3 S → CD C → aC | a D → bDc | bc Tuy nhiên L ∩ L = L không phải là CFL. 2 3 1 Vậy CFL không đóng với phép giao. 3) Hệ quả CFL không đóng với phép lấy phần bù. Chứng minh: Giả sử CFL đóng với phép lấy phần bù, vậy với L , L là hai CFL bất kỳ, 1 2 theo quy luật DeMorgan ta có L ∩ L = L1  L nên L ∩ L là CFL hay CFL cũng 1 2 2 1 2 đóng với phép giao ( Điều này mâu thuẫn với định lý trên). 144 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 3.5. Automat đẩy xuống (Push down Automata) Nhƣ đã biết, ngôn ngữ chính quy đƣợc sinh từ văn phạm chính quy, đồng thời cũng đƣợc đoán nhận bởi các automat hữu hạn (đơn định hoặc không đơn định). Trong phần này sẽ biết thêm một điều tƣơng tự là ngôn ngữ phi ngữ cảnh đƣợc sinh ra từ văn phạm phi ngữ cảnh và đƣợc đoán nhận bởi một loại automat khác - gọi là automat đẩy xuống (PDA). Có một điều khác biệt là chỉ có dạng automat đẩy xuống không đơn định (NPDA) mới có thể đủ mạnh để đoán nhận lớp ngôn ngữ phi ngữ cảnh, còn dạng đơn định (DPDA) chỉ cho phép đoán nhận một tập con thực sự của lớp ngôn ngữ này. Tuy nhiên, tập con đó cũng đã bao gồm phần lớn các ngôn ngữ lập trình bậc cao. 3.5.1. Mô tả PDA Automat đẩy xuống thực chất là một automat với sự điều khiển cả hai: băng vào và Stack (bộ đẩy xuống).Về cơ bản, Automat đẩy xuống giữ tất cả các thành phần của một automat hữu hạn, với sự bổ sung thêm một ngăn xếp làm việc (Stack) đóng vai trò nhƣ một bộ nhớ phụ, nhờ đó mà khả năng ghi nhớ của automat đƣợc tăng thêm. Stack xem nhƣ là một chồng đĩa, vì vậy cái đặt vào sau sẽ lấy ra trƣớc (LIFO). Với sự mở rộng này automat đẩy xuống có thể đoán nhận cả các biểu thức R * R không chính quy. Chẳng hạn tập hợp L = {wcw | w (0+1) } (với w là xâu đảo ngƣợc của xâu w) là một ngôn ngữ phi ngữ cảnh sinh bởi văn phạm S → 0S0 | 1S1 | c và nó không thể đƣợc đoán nhận bởi bất kỳ một automat hữu hạn nào. Về mặt trực quan Automat Push down (Automat đẩy xuống) có thể coi là một hệ thống mô tả nhƣ sau: Có một băng vào (kênh vào), băng này gồm nhiều ô hay ngăn, mỗi ngăn chứa một ký tự của bảng chữ cái nào đó gọi là bảng chữ cái vào. Các ký tự vào đƣợc xếp bắt đầu từ ngăn bên trái nhất, băng vào đƣợc coi nhƣ dài vô hạn về bên phải. Có bộ điều khiển, gồm một số hữu hạn trạng thái. Có một đầu đọc, đầu đọc này dò đọc trên băng vào. Mỗi lần đầu đọc chỉ đọc một ký tự trong một ngăn của băng vào. Sau mỗi lần đọc một ký tự vào nó dịch chuyển sang bên phải một ngăn hoặc đứng yên. Phạm Hùng Phú 145
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Có một bộ nhớ phụ, gọi là băng đẩy xuống, còn gọi là Stack. Băng đẩy xuống cũng gồm nhiều ngăn, mỗi ngăn chứa một ký tự của bảng chữ cái nào đó gọi là bảng chữ cái đẩy xuống (Push down Alphabet). Băng đẩy xuống hoạt động theo nguyên tắc vào sau ra trƣớc (Last in First out). Ký tự đƣa vào hoặc lấy ra bao giờ cũng ở đỉnh của Stack. Hình 3.5 mô tả các bộ phận của Automat Pushdown. Hình 3.5 Mô tả một PDA 3.5.2. Định nghĩa Automat đẩy xuống Automat đẩy xuống có một bộ điều khiển hữu hạn và một Stack. Stack chứa một xâu các ký tự thuộc một bảng chữ cái nào đó. Ký tự bên trái nhất của xâu xem nhƣ ký tự tại đỉnh Stack. PDA đƣợc gọi là không đơn định nếu nhƣ có nhiều hơn một lựa chọn các phép chuyển trong một lần chuyển nào đó. Ngƣợc lại gọi là PDA đơn định. Phép chuyển sẽ có hai kiểu: - Kiểu thứ nhất phụ thuộc vào ký tự vào, tức là với một trạng thái, một ký tự tại đỉnh Stack và một ký tự vào; PDA sẽ lựa chọn trạng thái kế tiếp và một xâu các ký tự thay thế trên Stack, đầu đọc dịch đi sang phải một ký tự. - Kiểu thứ hai không phụ thuộc vào ký tự vào, gọi là ε - dịch chuyển: tƣơng tự nhƣ kiểu thứ nhất, chỉ khác là ký tự vào không đƣợc dùng và đầu đọc không dịch 146 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 chuyển sau khi chuyển trạng thái. Thực chất, bƣớc chuyển đặc biệt này là một sự tạm ngừng quan sát trên băng vào để sắp xếp lại các ký tự trong ngăn xếp. Có hai cách để định nghĩa ngôn ngữ đoán nhận bởi automat đẩy xuống: - Ngôn ngữ đƣợc đoán nhận bởi Stack rỗng: gồm tất cả các xâu vào mà sau một dãy các phép chuyển trạng thái làm cho automat dẫn tới Stack rỗng. - Ngôn ngữ đƣợc đoán nhận bởi trạng thái kết thúc: ta thiết kế một số trạng thái kết thúc, khi đó ngôn ngữ đoán nhận bởi automat có thể định nghĩa gồm tất cả các xâu vào mà có một dãy các phép chuyển làm cho automat dẫn tới một trong những trạng thái kết thúc. Ta có thể thấy hai cách định nghĩa cho sự đoán nhận xâu này là tƣơng đƣơng nhau trong mọi trƣờng hợp, có nghĩa là nếu một ngôn ngữ đƣợc đoán nhận bởi Stack rỗng của một PDA nào đó thì nó cũng sẽ đƣợc đoán nhận bằng trạng thái kết thúc trên một PDA khác, và ngƣợc lại. Thiết kế PDA đoán nhận xâu bằng trạng thái kết thúc thƣờng phổ biến hơn, nhƣng sẽ dễ dàng hơn để chứng minh nguyên lý cơ bản của PDA khi thiết kế PDA đoán nhận xâu bằng Stack rỗng. Nguyên lý này đƣợc phát biểu nhƣ sau: Một ngôn ngữ đƣợc đoán nhận bởi PDA khi và chỉ khi nó là một ngôn ngữ phi ngữ cảnh. Một cách hình thức, ta định nghĩa: 1) Định nghĩa Một automat đẩy xuống M là một hệ thống M = <Q, Σ, Γ, δ, q , Z , F). Trong đó: 0 0 1. Q là tập hữu hạn các trạng thái. 2. Σ là bảng chữ cái gọi là bảng chữ cái nhập (vào). 3. Γ là bảng chữ cái gọi là bảng chữ cái Stack. * 4. δ: hàm chuyển ánh xạ từ Q × (Σ {ε}) × Γ → Q × Γ . 5. q là trạng thái khởi đầu. 0 6. Z là một chữ cái riêng của Stack gọi là ký tự bắt đầu trên Stack. 0 7. F  Q là tập các trạng thái kết thúc. (Trong trƣờng hợp PDA đƣợc thiết kế đoán nhận ngôn ngữ bằng Stack rỗng thì tập hợp F = ∅) Phạm Hùng Phú 147
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Trừ khi ta dùng các ký tự khác, ta quy ƣớc dùng chữ cái nhỏ ở đầu bảng chữ cái để chỉ các ký tự vào, các chữ cái nhỏ cuối bảng chữ cái để chỉ các xâu vào. Các chữ cái in hoa và chữ Hy lạp chỉ ký tự và xâu ký tự trên Stack. 2) Sự dịch chuyển a) Hàm chuyển phụ thuộc ký tự vào δ(q, a, Z) = {(p , γ ), (p , γ ), , (p , γ )} 1 1 2 2 m m Trong đó: q và p với 1 ≤ i ≤ m, là các trạng thái thuộc tập Q, a Σ, Z là một i * ký trên đỉnh Stack và γ Γ với 1 ≤ i ≤ m. i Nghĩa là PDA đang ở trạng thái q nhìn thấy ký tự vào a và ký tự Z tại đỉnh Stack thì nó chuyển sang một trạng thái p nào đó, thay Z bằng γ và dịch chuyển đầu i i đọc đi một ký tự. Ta quy ƣớc rằng ký tự bên trái nhất của γ sẽ là ký tự đƣợc thay i cao nhất trên Stack (nghĩa là nó nằm tại đỉnh Stack mới) và ký tự bên phải nhất của γ là ký tự đƣợc thay thấp nhất trong Stack. Chú ý rằng không đƣợc phép chọn p và i i γ với i ≠ j tại một bƣớc chuyển nào đó. j b) Hàm chuyển không phụ thuộc ký tự vào δ(q, ε, Z) = {(p , γ ), (p , γ ), , (p , γ )} 1 1 2 2 m m Trong đó: q là trạng thái mà PDA đang giữ, độc lập với ký tự vào, PDA đi vào trạng thái p thay Z bởi γ với 1 ≤ i ≤ m. Trong trƣờng hợp này đầu đọc không i i dịch chuyển. R * Ví dụ: PDA đoán nhận ngôn ngữ {wcw |w (0+1) } bằng Stack rỗng. M = <Q, Σ, Γ, δ, q , Z , F). Trong đó: 0 0 Q = {q , q }; 1 2 Σ = {0, 1, c}; Γ = {R, B, Y}; q = q 0 1; Z = R; 0 F = ∅. 148 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 δ: 1. δ(q , 0, R) = {(q , BR)}; 1 1 2. δ(q , 1, R) = {(q , YR)}; 1 1 3. δ(q , 0, B) = {(q , BB)}; 1 1 4. δ(q , 1, B) = {(q , YB)}; 1 1 5. δ(q , 0, Y) = {(q , BY)}; 1 1 6. δ(q , 1, Y) = {(q , YY)}; 1 1 7. δ(q , c, R) = {(q , R)}; 1 2 8. δ(q , c, B) = {(q , B)}; 1 2 9. δ(q , c, Y) = {(q , Y)}; 1 2 10. δ(q , 0, B) = {(q , ε)}; 2 2 11. δ(q , 1, Y) = {(q , ε)}; 2 2 12. δ(q , ε, R) = {(q , ε)}. 2 2 3) Hình trạng (hình thái) (ID: Instantaneous Descriptions) Để hình thức hóa cấu hình của một PDA với một PDA cụ thể, ta định nghĩa một hình trạng. Hình trạng là một bộ ba (q, w, γ), trong đó q là trạng thái, w là xâu vào và γ là xâu các ký tự nằm trong Stack. Nếu M = là một PDA, ta nói: (q, aw, Zα) ⊢M (p, w, βα) nếu δ(q, a, Z) chứa (p, β) Ở đây, a có thể là một ký tự trong xâu vào hoặc ε. * * Ta dùng ký hiệu ⊢ M cho bao đóng phản xạ và bắc cầu của ⊢M, tức là: I ⊢ i * * K đối với mỗi ID I và I ⊢M J và J ⊢ M K thì I ⊢ M K. Ta viết I ⊢ K nếu ID I trở i thành K sau chính xác i bƣớc chuyển. Chữ chỉ số dƣới M trong các ký hiệu ⊢M, ⊢ M * và ⊢ M có thể đƣợc bỏ qua khi M đã đƣợc xác định. Phạm Hùng Phú 149
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Chẳng hạn, với PDA mô tả nhƣ trên, ta có (q , BY) δ(q , 0, Y), suy ra rằng 1 1 (q , 011, YYR) ⊢ (q , 11, BYYR). 1 1 3.5.3. Ngôn ngữ đoán nhận bởi PDA Cho PDA M = . - Ngôn ngữ đƣợc đoán nhận bởi PDA M bằng trạng thái kết thúc là: * L (M) = {w | (q , w, Z ) ⊢* (p, ε, γ) với p F và γ Γ } 0 0 - Ngôn ngữ đƣợc đoán nhận bởi PDA M bằng Stack rỗng là: L(M) = {w | (q , w, Z ) ⊢* (p, ε, ε) với p Q}. 0 0 Khi có sự đoán nhận ngôn ngữ bằng Stack rỗng thì tập trạng thái kết thúc là không còn cần thiết vì vậy ta ký hiệu tập trạng thái kết thúc F là ∅. Ví dụ: Các phép chuyển hình trạng của PDA M đơn định đƣợc cho trong ví dụ trên R * đoán nhận xâu 001c100 thuộc ngôn ngữ {wcw |w (0+1) } bằng Stack rỗng nhƣ sau: (q , 001c100, R) ⊢ (q , 01c110, BR) ⊢ (q , 1c110, BBR) ⊢ (q , c100, YBBR) 1 1 1 1 ⊢ (q , 100, YBBR) ⊢ (q , 00, BBR) ⊢ (q , 0, BR) ⊢ (q , ε, R) ⊢ (q , ε, ε): Đoán 2 2 2 2 2 nhận. Nhận xét: R * Trong ví dụ thiết kế PDA đoán nhận ngôn ngữ {wcw |w (0+1) } bằng Stack rỗng nhƣ trên, ta thấy các giá trị hàm chuyển của nó luôn là là đơn trị. Tại mỗi thời điểm từ một trạng thái trong bộ điều khiển, có thể đọc vào hoặc không đọc một ký tự trên băng vào, với một ký tự tại đỉnh Stack, chỉ có một giá trị xác định bƣớc chuyển kế tiếp. Vì thế, ta gọi dạng PDA này là automat đẩy xuống đơn định - DPDA. Ví dụ: R * PDA M không đơn định đoán nhận ngôn ngữ {ww |w (0+1) } bằng Stack rỗng. 150 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 M = : 1 2 1 1. δ(q , 0, R) = {(q , BR)}; 1 1 2. δ(q , 1, R) = {(q ,YR)}; 1 1 3. δ(q , 0, B) = {(q , BB), (q , ε)}; 1 1 2 4. δ(q , 0, Y) = {(q , BY)}; 1 1 5. δ(q , 1, B) = {(q , YB)}; 1 1 6. δ(q , 1, Y) = {(q , YY),(q , ε)}; 1 1 2 7. δ(q , 0, B) = {(q , ε)}; 2 2 8. δ(q , 1, Y) = {(q , ε)}; 2 2 9. δ(q , ε, R) = {(q , ε)}; 1 2 10. δ(q , ε, R) = {(q , ε)}. 2 2 Cũng nhƣ NFA, một PDA không đơn định (NPDA) M đoán nhận một xâu vào nếu có một dãy các lựa chọn mà M làm rỗng Stack của nó. Nghĩa là M luôn luôn "đoán đúng". Đoán sai không phải là nguyên nhân để loại bỏ xâu vào. Một xâu vào bị loại bỏ nếu và chỉ nếu không có sự lựa chọn nào để làm rỗng Stack (hay là không thể "đoán đúng" vì không tồn tại cách đúng). Ví dụ: Các phép chuyển hình trạng (hình thái) của PDA đoán nhận xâu 001100 R * thuộc ngôn ngữ {ww |w (0+1) } bằng Stack rỗng nhƣ sau: (q , 001100, R) ⊢ (q , 001100, ε): Không đoán nhận 1 2 ┬ (q , 01100, BR) ⊢ (q , 1100, R) ⊢ (q , 1100, ε): Không đoán nhận 1 2 2 ┬ (q , 1100, BBR) 1 ┬ (q ,100, YBBR) ⊢ (q ,00, BBR) ⊢ (q , 0, BR) ⊢ (q , ε, R) ⊢ (q , ε, ε): Đoán nhận 1 2 2 2 2 ┬ (q , 00, YYBBR) 1 Phạm Hùng Phú 151
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống ┬ (q , 0, BYYBBR) ⊢ (q , ε, YYBBR): Không đoán nhận 1 2 ┬ (q , ε, BBYYBBR): Không đoán nhận 1 R * Nhƣ vậy, để đoán nhận xâu 001100 thuộc ngôn ngữ {ww |w (0+1) } bằng Stack rỗng, PDA thực hiện dãy các phép chuyển hình trạng: (q , 001100, R) ⊢ (q , 01100, BR) ⊢ (q , 1100, BBR) ⊢ (q ,100, YBBR) ⊢ 1 1 1 1 (q ,00, BBR) ⊢ (q , 0, BR) ⊢ (q , ε, R) ⊢ (q , ε, ε): Đoán nhận 2 2 2 2 Một PDA M = đƣợc gọi là đơn định nếu: 1. Với q Q và Z Γ: nếu δ(q, ε, Z) ≠ ∅ thì δ(q, a, Z) = ∅ với a Σ 2. Không có q Q, Z Γ và a (Σ  {ε}) mà δ(q, a, Z) chứa nhiều hơn một phần tử. Điều kiện 1 không cho phép khả năng chọn lựa giữa phép chuyển không xác định ký tự vào (ε - dịch chuyển) và phép chuyển trên một ký tự của xâu vào. Điều kiện 2 không cho phép chọn lựa một vài phép chuyển nào đó (q, a, Z) hay (q, ε, Z). Không nhƣ automat hữu hạn FA, một PDA thì thông thƣờng đƣợc xét là không đơn định trừ khi ta có ghi chú cụ thể. Đối với automat hữu hạn, dạng đơn định và không đơn định là tƣơng đƣơng nhau về phƣơng diện đoán nhận ngôn ngữ. Tuy nhiên, điều này không đúng với automat đẩy xuống, PDA không đơn định và PDA đơn định là không tƣơng đƣơng R nhau. Thực tế ngôn ngữ ww đƣợc đoán nhận bởi một PDA không đơn định nhƣng không đƣợc đoán nhận bởi bất kỳ một PDA đơn định nào. Ví dụ: 1. Cho Automat pushdown M = ; Trong đó: Q = {q0, q1};  = {a, b};  = {Z0 , X}; F =  ; : (q0 , a, Z0 ) = {(q0, X)}; 152 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 (q0 , a, X ) = {(q0, XX)}; (q0 , b, X) = {(q1, )}; (q1 , b, X ) = {(q1, )}; (q1 , , X) = {(q1, )}. Automat pushdown đơn định đoán nhận đƣợc ngôn ngữ L = { ab, ambm-1 | m 1 } bằng xét rỗng stack Thật vậy: Với w L w = ab (q , ab, Z ) ⊢(q0, b, X) ⊢(q1, , ): đoán 0 0 nhận ab. Hoặc w = ambm-1 với m-n = 1 và n 1. Ta có: m n m-1 m-1 m-1 m-1 (q , a b , Z ) ⊢(q0, a b , X) ⊢ (q0, b , X X) (gồm m-1 ký tự X) 0 0 m-2 m-2 m m-1 ⊢(q1, b , X X) (gồm m-2 ký tự X) ⊢ (q1, , ): đoán nhận a b . 2. Cho automat push down M = ; Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0}; F = {q2}; : (q0 , a, Z0 ) = {(q0, Z0), (q1, Z0)}; (q0 , b , Z0 ) = {(q1, Z0), (q2, Z0)}; đoán nhận đƣợc ngôn ngữ L = { amb| m 0} bằng trạng thái kết thúc. Thật vậy: Với w L w = amb với m 0. Ta có: m m m (q , a b, Z ) ⊢ (q0, b, Z0) ⊢(q2, , Z0) mà q2 F: đoán nhận a b. 0 0 3.5.4. PDA và văn phạm phi ngữ cảnh 1) Sự tương đương của việc đoán nhận xâu bằng trạng thái kết thúc và bằng Stack rỗng a) Định lý 1 Nếu L là một ngôn ngữ phi ngữ cảnh đƣợc đoán nhận bởi một PDA M 2 bằng trạng thái kết thúc thì L đƣợc đoán nhận bởi một PDA M nào đó bằng 1 Phạm Hùng Phú 153
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Stack rỗng. Chứng minh: Ta sẽ xây dựng M tƣơng tự nhƣ M nhƣng M sẽ xóa rỗng Stack của nó khi 1 2 1 M đi vào trạng thái kết thúc. Ta dùng một trạng thái q của M để xóa Stack của nó 2 e 1 và dùng ký tự đánh dấu đáy Stack M bằng ký tự X , vì vậy M không thể làm rỗng 1 0 1 Stack của nó khi M chƣa đi vào trạng thái kết thúc. 2 Đặt M = là PDA sao cho L = L(M ). 2 0 0 2 Đặt M = trong đó δ‟ định nghĩa nhƣ sau: 1 e 0 0 0 1. δ‟(q‟ , ε, X ) = {(q , Z X )}; 0 0 0 0 0 2. δ‟(q, a, Z) chứa mọi phần tử của δ(q, a, Z) với q Q, a Σ hoặc a = ε và Z Γ; 3. δ‟(q, ε, Z) chứa (q , ε) với q F và Z Γ  {X }; e 0 4. δ‟(q‟ , ε, Z) chứa (q , ε) với  Z Γ {X }. 0 e 0 Quy tắc 1 làm cho PDA M đi vào trạng thái khởi đầu của M trừ việc thêm 1 2 X vào đáy Stack. Quy tắc 2 cho phép M chuyển tƣơng tự nhƣ M . Quy tắc 3 và 4 0 1 2 cho phép M chọn việc đi vào trạng thái q và xoá Stack hay là tiếp tục mô phỏng 1 e M . Chú ý rằng M có thể xóa rỗng Stack của nó khi chƣa tới trạng thái kết thúc vì 2 2 vậy M phải đƣợc đánh dấu đáy Stack bằng X . Vì nếu không làm nhƣ vậy thì khi 1 0 M chuyển tƣơng tự nhƣ M thì M sẽ xoá rỗng Stack và đoán nhận xâu vào trong 1 2 1 khi M chƣa đi vào trạng thái kết thúc nghĩa là xâu vào chƣa đƣợc đoán nhận. 2 * Đặt x L(M ) thì (q , x, Z ) ⊢ M2 (q, ε, γ) với q F. Ta xét M với xâu vào x. 2 0 0 1 * Theo quy tắc 1: (q‟ , x, X ) ⊢ M1 (q , x, Z X ) 0 0 0 0 0 Theo quy tắc 2 mỗi phép chuyển của M là một phép chuyển trong M , vậy: 2 1 * (q , x, Z ) ⊢ M1 (q, ε, γ) 0 0 Nếu một PDA có thể thực hiện một dãy các phép chuyển từ một ID đã cho thì nó có thể làm một dãy các phép chuyển đó từ một ID bất kỳ thu đƣợc từ ID đầu tiên bằng cách thêm các xâu ký tự Stack vào dƣới xâu Stack ban đầu (vì các ký tự ở phía dƣới của Stack không làm ảnh hƣởng gì). 154 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 * Vậy (q‟ , x, X ) ⊢M1 (q , x, Z X ) ⊢ M1 (q, ε, γX ). 0 0 0 0 0 0 * Theo quy tắc 3 và 4: (q, ε, γX ) ⊢ M1 (q , ε, ε). 0 e * Vì vậy (q‟ , x, X ) ⊢ M1 (q , ε, ε) và M đoán nhận xâu x bằng Stack rỗng. 0 0 e 1 Ngƣợc lại, nếu M đoán nhận x bằng Stack rỗng thì dễ dàng chỉ ra rằng dãy 1 các phép chuyển phải bắt đầu bằng một phép chuyển theo quy tắc 1, sau đó bằng một xâu phép chuyển theo quy tắc 2, trong khi thực hiện các phép chuyển này M 1 chuyển tƣơng tự nhƣ M , sau đó xóa Stack của M bằng quy tắc chuyển 3 và 4. 2 1 Vậy x L(M ). 2 b) Định lý 2 Nếu L là một ngôn ngữ phi ngữ cảnh đƣợc đoán nhận bởi một PDA M 1 bằng Stack rỗng thì L đƣợc đoán nhận bởi một PDA M nào đó bằng trạng thái 2 kết thúc. Chứng minh: Ta sẽ xây dựng M tƣơng tự M và M đi vào trạng thái kết thúc khi và chỉ 2 1 2 khi M làm rỗng Stack của nó. 1 Đặt M = là PDA sao cho L = N(M ). 1 0 0 1 Đặt M = trong đó δ‟ đƣợc định 2 0 f 0 0 0 f nghĩa nhƣ sau: 1. δ‟(q‟ , ε, X ) = {(q , Z X )}; 0 0 0 0 0 2. δ‟(q, a, Z) = δ(q, a, Z) với q Q, a Σ {ε}, và Z Γ; 3. δ‟(q, ε, X ) chứa (q , ε) với q Q. 0 f Quy tắc 1 cho phép M đi vào hình trạng (hình thái) khởi đầu ID của M , trừ 2 1 việc M sẽ có chứa ở dƣới đáy Stack của nó ký tự X , ký tự này sẽ nằm bên dƣới tất 2 0 cả các ký tự Stack của M . Quy tắc 2 cho phép M chuyển tƣơng tự nhƣ M . Khi M 1 2 1 1 làm rỗng Stack của nó, thì M khi chuyển tƣơng tự nhƣ M sẽ xóa toàn bộ Stack của 2 1 nó trừ ký tự X nằm dƣới đáy Stack. Quy tắc 3 làm cho M sau đó khi gặp X xuất 0 2 0 hiện thì đi vào trạng thái kết thúc và đoán nhận xâu vào x. Phạm Hùng Phú 155
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Chứng minh L(M ) = N(M ) cũng tƣơng tự nhƣ định lý 1. 2 1 2) Sự tương đương giữa PDA và CFL a) Định lý 1 Nếu L là ngôn ngữ phi ngữ cảnh đƣợc sinh ra bởi văn phạm phi ngữ cảnh G thì tồn tại PDA M sao cho L = N(M). Chứng minh: Giả sử ε không thuộc L(G) (có thể sửa đổi lập luận cho trƣờng hợp ngôn ngữ L(G) có chứa ε). Đặt G = (N, T, P, S) là văn phạm phi ngữ cảnh có dạng chuẩn Greibach sinh ra L. Đặt M = ; trong đó: δ(q, a, A) chứa (q, γ) khi và chỉ khi A → aγ là một luật sinh trong P. PDA M mô phỏng xâu dẫn xuất trái của G. Vì G là dạng chuẩn Greibach nên mỗi dạng câu trong dẫn xuất trái gồm một xâu các ký tự kết thúc x sau đó là một xâu các biến α. M lƣu trữ phần hậu tố α của dạng câu bên trái trên Stack của nó sau khi xử lý phần tiền tố x. Một cách hình thức ta chỉ ra rằng: * * S xα bằng dẫn xuất trái nhất khi và chỉ khi (q, x, S) ⊢ M (q, ε, α) (1) i Trƣớc tiên, chúng ta giả sử (q, x, S) ⊢ (q, ε, α) và sẽ chỉ ra bằng quy nạp theo số lần i rằng S * xα. Với i = 0, điều đó hiển nhiên đúng vì x = ε và α = S. Giả sử i ≥ 1 và đặt x = ya. Xét bƣớc chuyển hình trạng trƣớc bƣớc cuối: i -1 (q, ya, S) ⊢ (q, a, β) ⊢ (q, ε, α) (2) Nếu loại bỏ ký tự a ở cuối xâu vào trong hình trạng đầu tiên của (2), ta có: i -1 (q, y, S) ⊢ (q, ε, β) (vì a không ảnh hƣởng đến các phép chuyển của M). Theo giả thiết quy nạp S * yβ. Phép chuyển (q, a, β) ⊢ (q, ε, α) sẽ suy ra β = Aγ, với A V và A → aη là một luật sinh trong G và α = ηγ. Vậy S * yβ yaηγ = xα Ta đã chứng minh xong "nếu" của giả thiết (1) 156 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 i Ngƣợc lại, ta giả sử S xα bằng dẫn xuất trái. Ta sẽ chứng minh quy nạp * theo số bƣớc dẫn xuất i rằng: (q, x, S) ⊢ (q, ε, α) Với i = 0: phép chuyển hiển nhiên đúng i -1 Xét i ≥ 1 và giả sử S yAγ yaηγ, trong đó x = ya và α = ηγ. Theo giả * * thiết quy nạp: (q, y, S) ⊢ (q, ε, Aγ). Vậy (q, ya, S) ⊢ (q, a, Aγ) Vì A → aη là một luật sinh nên δ(q, a, A) chứa (q, η). Vậy: * * (q, x, S) ⊢ (q, a, Aγ) ⊢ (q, ε, α) Hay phần "chỉ nếu" của giả thiết (1) cũng đã đƣợc chứng minh xong. Để kết thúc việc chứng minh, ta chú ý rằng giả thiết (1) với α = ε thì S * x nếu và * chỉ nếu (q, x, S) ⊢ (q, ε, ε). Tức là x L(G) khi và chỉ khi x N(M). Từ chứng minh định lý, ta có giải thuật xây dựng PDA biết Văn phạm phi ngữ cảnh G. Input: G = (N, T, P, S) – CFG đã ở dạng chuẩn Greibach,  L(G) Output: M = - PDA sao cho L(M) = L(G) 0 0 Process: M = : 0 0 - Q = {q}; - Σ = T; - Γ = N; - q = q; 0 - Z = S; 0 - δ: δ(q, a, A) = {(q, γ)  A → aγ} với  a T, A N. Ví dụ: Xây dựng NPDA đoán nhận ngôn ngữ sinh bởi CFG G có các luật sinh nhƣ sau: S → aAA; A → aS | bS | a. Ta có: CFG G = ({S, A}, {a, b}, P, S) NPDA tƣơng đƣơng M = với δ nhƣ sau: 1. δ (q, a, S) = {(q, AA)}; Phạm Hùng Phú 157
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 2. δ (q, a, A) = {(q, S), (q, ε)}; 3. δ (q, b, A) = {(q, S)}. b) Định lý 2 Nếu L ngôn ngữ phi ngữ cảnh đƣợc đoán nhận bởi PDA M thì L là ngôn ngữ phi ngữ cảnh đƣợc sinh bởi van phạm G. Chứng minh: Gọi PDA M = . Đặt G = (N, Σ, P, S) là CFG, trong đó: 0 0 - N là tập các đối tƣợng dạng [q, A, p] với p, q Q; A Γ; - S là ký tự chƣa kết thúc mới thêm vào; - P là tập các luật sinh có dạng: 1. S → [q , Z , q] với q Q; 0 0 2. [q, A, q ] → a[q , B , q ][q , B , q ] [q , B , q ] m+1 1 1 2 2 2 3 m m m+1 với q, q , q , , q Q, a Σ {ε} và A, B , B , , B Γ sao cho δ(q, a, A) 1 2 m+1 1 2 m có chứa (q , B B2 Bm). 1 1 Nếu m = 0 thì luật sinh có dạng [q, A, q ] → a. 1 Để nắm đƣợc chứng minh, cần phải lƣu ý rằng các biến và luật sinh trong G đƣợc xác định sao cho dẫn xuất trái trong G của x mô phỏng bằng PDA khi cho x là xâu vào. Cụ thể hơn, các biến xuất hiện tại một bƣớc bất kỳ trong G tƣơng đƣơng với các ký tự trên Stack của M. Nói cách khác [q, A, p] dẫn ra x nếu và chỉ nếu x là nguyên nhân làm M xoá rỗng Stack của nó bằng dãy các phép chuyển từ trạng thái q đến trạng thái p. Để chứng minh L(G) = N(M), ta quy nạp theo số bƣớc dẫn xuất của G hoặc số bƣớc * * chuyển trạng thái của M rằng [q, A, p] x nếu và chỉ nếu (q, x, A) ⊢ M (p, ε, ε). G Từ chứng minh định lý, ta có giải thuật xây dựng văn phạm phi ngữ cảnh G biết PDA. Input: M = - PFD 0 0 Output: G = (N, T, P, S) – CFG, L(G) = L(M) Process: G = (N, T, P, S): - N = {[q, A, p]  p, q Q; A Γ }; - T = Σ; 158 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 - S = một ký tự chƣa kết thúc mới thêm vào; - P là tập các luật sinh có dạng: 1. S → [q , Z , q] với q Q; 0 0 2. [q, A, q ] → a[q , B , q ][q , B , q ] [q , B , q ] với q, q , q , m+1 1 1 2 2 2 3 m m m+1 1 2 , q Q, a Σ {ε} và A, B , B , , B Γ sao cho δ(q, a, A) có chứa m+1 1 2 m (q , B B2 Bm). 1 1 Nếu m = 0 thì luật sinh có dạng [q, A, q ] → a. 1 Ví dụ: Xây dựng CFG G tƣơng đƣơng sinh ra ngôn ngữ đƣợc đoán nhận bởi PDA M = với δ đƣợc cho nhƣ sau: 0 1 0 0 0 1. δ(q , 0, Z ) = {(q , XZ )}; 0 0 0 0 2. δ(q , 0, X) = {(q , XX)}; 0 0 3. δ(q , 1, X) = {(q , ε)}; 0 1 4. δ(q , 1, X) = {(q , ε)}; 1 1 5. δ(q , ε, X) = {(q , ε)}; 1 1 6. δ(q , ε, Z ) = {(q , ε)}. 1 0 1 Ta xây dựng CFG G = (N, {0, 1}, P, S) sinh ra L(M) với các thành phần nhƣ sau: N = { S, [q , X, q ], [q , X, q ], [q , X, q ], [q , X, q ], 0 0 0 1 1 0 1 1 [q , Z , q ], [q , Z , q ], [q , Z , q ], [q , Z , q ]} 0 0 0 0 0 1 1 0 0 1 0 1 Tập luật sinh P chứa các luật sinh có dạng: Các luật sinh cho ký tự bắt đầu S: S → [q , Z , q ] | [q , Z , q ] 0 0 0 0 0 1 Các luật sinh cho các biến khác trong N đƣợc xây dựng từ các hàm chuyển của PDA nhƣ sau: - Vì δ(q , 0, Z ) = {(q , XZ )} nên 0 0 0 0 + [q , Z , q ] → 0 [q , X, q ][q , Z , q ] | 0 [q , X, q ][q , Z , q ]; 0 0 0 0 0 0 0 0 0 1 1 0 0 + [q , Z , q ] → 0 [q , X, q ][q , Z , q ] | 0 [q , X, q ][q , Z , q ]. 0 0 1 0 0 0 0 1 0 1 1 0 1 - Vì δ(q , 0, X) = {(q , XX)} nên 0 0 + [q , X, q ] → 0 [q , X, q ][q , X, q ] | 0 [q , X, q ][q , X, q ]; 0 0 0 0 0 0 0 1 1 0 Phạm Hùng Phú 159
Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống + [q , X, q ] → 0 [q , X, q ][q , X, q ] | 0 [q , X, q ][q , X, q ]. 0 1 0 0 0 1 0 1 1 1 - Vì δ(q , 1, X) = {(q , ε)} nên [q , X, q ] → 1. 0 1 0 1 - Vì δ(q , 1, X) = {(q , ε)} nên [q , X, q ] → ε. 1 1 1 1 - Vì δ(q , ε, X) = {(q , ε)} nên [q , X, q ] → ε. 1 1 1 1 - Vì δ(q , ε, Z ) = {(q , ε)} nên [q , Z , q ] → ε. 1 0 1 1 0 1 Nhận xét rằng không có luật sinh nào cho các biến [q , X, q ] và [q , Z , q ]. 1 0 1 0 0 Vì tất cả các luật sinh cho biến [q , X, q ] và [q , Z , q ] đều có chứa [q , X, q ] hoặc 0 0 0 0 0 1 0 [q , Z , q ] ở vế phải, nên sẽ không thể có xâu ký tự kết thúc nào có thể đƣợc dẫn ra 0 0 0 từ các biến [q , X, q ] hoặc [q , Z , q ]. Loại bỏ 4 biến này ra khỏi tập biến N và xóa 0 0 0 0 0 các luật sinh có liên quan đến chúng trong tập P, ta thu đƣợc văn phạm có dạng nhƣ sau: S → [q , Z , q ]; 0 0 1 [q , Z , q ] → 0 [q , X, q ][q , Z , q ]; 0 0 1 0 1 1 0 1 [q , X, q ] → 0 [q , X, q ][q , X, q ]; 0 1 0 1 1 1 [q , X, q ] → 1; 0 1 [q , Z , q ] → ε; 1 0 1 [q , X, q ] → ε; 1 1 [q , X, q ] → 1. 1 1 160 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 3.1. Nêu định nghĩa văn phạm phi ngữ cảnh (CFG); cho ví dụ. 3.2. Nêu các khái niệm: dẫn xuất, ngôn ngữ sinh bởi CFG; cho ví dụ. 3.3. Nêu định nghĩa cây dẫn xuất; phƣơng pháp xây dựng cây dẫn xuất; cho ví dụ. 3.4. Nêu quan hệ giữa dẫn xuất và cây dẫn xuất. 3.5. Nêu định nghĩa dẫn xuất trái nhất, dẫn xuất phải nhất, văn phạm nhập nhằng; cho ví dụ. 3.6. Nêu khái niệm ký hiệu thừa, không thừa; cho ví dụ. 3.7. Nêu giải thuật loại bỏ các biến không dẫn ra xâu các ký hiệu kết thúc; cho ví dụ. 3.8. Nêu giải thuật loại bỏ các ký hiệu không đƣợc dẫn ra từ ký hiệu bắt đầu của văn phạm; cho ví dụ. 3.9. Nêu khái niệm luật sinh . Phƣơng pháp loại bỏ luật sinh ; cho ví dụ. 3.10. Nêu khái niệm luật sinh đơn vị. Phƣơng pháp loại bỏ luật sinh đơn vị; cho ví dụ. 3.11. Nêu dạng chuẩn Chomsky - CNF và phƣơng pháp đƣa một CFG về dạng chuẩn Chomsky; cho ví dụ. 3.12. Nêu dạng chuẩn Greibach - GNF và phƣơng pháp đƣa một CFG về dạng chuẩn Greibach; cho ví dụ. 3.13. Nêu tính chất của CFL. 3.14. Nêu các giải thuật quyết định CFL. Cho ví dụ. 3.15. Mô tả PDA và sự hoạt động của nó. 3.16. Nêu định nghĩa PDA; ngôn ngữ đoán nhận bởi PDA; cho ví dụ. 3.17. Nêu sự dịch chuyển của PDA và khái niệm hình trạng của PDA; cho ví dụ. 3.18. Nêu các định lý về sự tƣơng đƣơng giữa việc đoán nhận ngôn ngữ bởi trạng thái kết thúc và bởi stack rỗng; cho ví dụ. 3.19. Nêu phƣơng pháp xây dựng PDA tƣơng đƣơng với CFL; cho ví dụ. 3.20. Nêu phƣơng pháp xây dựng PDA tƣơng đƣơng với CFL; cho ví dụ. 3.21. Cho các văn phạm có tập các luật sinh tƣơng ứng: 161 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 1) S → aS | Sb | aSb | c 2) S → SS | a | b 3) S → SaS | b 4) S → aSS | b 5) S → aA | bB| c; A → Sa; B → Sb. 6) S → AB; A → Sc | a; B → dB | b. 7) S → TT; T → aTa | bTb | c. a) Nêu đầy đủ các thành phần của mỗi văn phạm. b) Mô tả ngôn ngữ sinh bởi mỗi văn phạm. 3.22. Hãy chỉ ra một văn phạm phi ngữ cảnh sinh ra tập hợp: 1) Tập hợp các xâu đọc xuôi đọc ngƣợc nhƣ nhau (đối xứng) trên bộ chữ cái Σ = {0,1}. 2) Tập hợp chuỗi các dấu ngoặc đúng trong biểu thức số học. i i j 3) Tập hợp {a b c | i, j ≥ 0} m n 4) Tập hợp {a b | m, n > 0} i j 5) Tập hợp {a ca | i , j ≥ 0} j j i i 6) Tập hợp {a b c d | i, j ≥ 1} 3.23. Chứng minh rằng văn phạm phi ngữ cảnh G với tập luật sinh: 1) P: S aAb | , A aAb |  sinh ra ngôn ngữ {anbn  n 0}; m n 2) P: S AB, A aA| a, B bB| b sinh ra ngôn ngữ {a b | m, n > 0}; i i j k 3) P: S ABC, A aAb|ab, B cB|c, C dC|d sinh ra ngôn ngữ {a b c d | i, j, k ≥ 1}. 3.24. Cho các văn phạm G có tập các luật sinh tƣơng ứng: 1) S abSba |  2) S 01S | A; A Aabc |  3) S Sabc | A; A 01A |  Hãy biểu diễn ngôn ngữ sinh bởi mỗi văn phạm trên dƣới dạng tập hợp. 3.25. Cho văn phạm G với các luật sinh sau: S → aB | bA; A → a | aS | bAA; B → b | bS | aBB và xâu w = aaabbabbba. 162 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 Hãy tìm: 1) Dẫn trái nhất xuất, dẫn xuất phải nhất ra xâu w. 2) Cây dẫn xuất trái nhất, cây dẫn xuất phải nhất ra xâu w. 3.26. Cho văn phạm G với các luật sinh sau: E → T | E + T | E - T; T → F | T × F | T / F; F → a | b | c | d | (E). 1) Nêu đầy đủ các thành phần của G. 2) Vẽ cây dẫn xuất sinh ra các xâu vào sau: a) (a + b) / c b) a × (b - c) c) a – (b × c / d) 3.27. Cho văn phạm: S → aSbS | bSaS | ε 1) Chứng tỏ văn phạm này là văn phạm nhập nhằng (mơ hồ). 2) Xây dựng dẫn xuất trái nhất, phải nhất và cây dẫn xuất tƣơng ứng cho xâu abab. 3.28. Cho văn phạm sinh ra câu lệnh rẽ nhánh trong ngôn ngữ lập trình Pascal: S → If b then S else S; S → If b then S; S → a; Trong đó a, b, if, then, else là các ký hiệu kết thúc và S là biến. 1) Chứng tỏ văn phạm trên là nhập nhằng (mơ hồ). 2) Hãy đƣa ra một văn phạm không nhập nhằng tƣơng đƣơng. 3.29. Cho văn phạm: S → S+S | S-S | S*S | S/S | (S) |a. 1) Chứng tỏ văn phạm là nhập nhằng (mơ hồ): 2) Hãy đƣa ra một văn phạm không nhập nhằng tƣơng đƣơng ? T → ( S ) | a . 3.30. Hãy loại bỏ các ký hiệu thừa trong mỗi văn phạm sau: 1) S → A | aSb | a; A → AB; B → b. 2) S → AB | CA; A → a; B → BC | AB; C → aB | b. 3.31. Tìm văn phạm chỉ có chứa một luật sinh ε duy nhất S → ε tƣơng đƣơng với văn phạm sau: S → AB; A → SA | BB | bB; B → b | aA | ε. 3.32. Cho văn phạm có tập luật sinh: Phạm Hùng Phú 163
Câu hỏi và bài tập chƣơng 3 S → AB | A | ; A → aBb | bS | b; B → AB | Ba |; C → Aa | D | . Hãy tìm văn phạm tƣơng đƣơng thỏa mãn một trong các điều kiện: 1) Không chứa ký hiệu thừa 2) Không chứa luật sinh  nào khác ngoài luật sinh S → ε 3.33. Cho văn phạm có tập luật sinh: S → AB | A | ; A → aBb | bS | b; B → AB | Ba |; C → Aa | D | . Hãy tìm văn phạm tƣơng đƣơng thỏa mãn các điều kiện: 1) Không chứa ký hiệu thừa. 2) Không chứa luật sinh  nào khác ngoài luật sinh S → ε. 3) Không chứa luật sinh đơn vị. 3.34. Tìm văn phạm không chứa ký hiệu thừa, luật sinh ε ngoại trừ luật sinh S → ε và luật sinh đơn vị tƣơng đƣơng với mỗi văn phạm sau: 1) S → aSbS | bSaS | ε 2) S → A | B; A → aB | bS | b; B → AB | Ba; C → AS | b. 3) S → ABC; A → BB | ε; B → CC | a; C → AA | b. 4) S → A | B; A → C | D; B → D | E; C → S | a | ε; D → S | b; E → S | c | ε. 3.35. Cho văn phạm với các luật sinh sau: S → A | aCA; A → D | a | ε; B → C | AbcB; C → aB | b | c | ε. 1) Nêu các thành phần của văn phạm trên. 2) Tìm văn phạm tƣơng đƣơng với văn phạm trên không chứa ký hiệu thừa, luật sinh ε và luật sinh đơn vị. 3.36. Cho văn phạm với các luật sinh sau: S → A| AcBC; A → B | ε; B → bCA | C |a; C → ABc | b| ε. 1) Nêu các thành phần của văn phạm trên. 2) Tìm văn phạm tƣơng đƣơng với văn phạm trên không chứa ký hiệu thừa, luật sinh ε và luật sinh đơn vị. 3.37. Biến đổi các văn phạm sau đây về dạng chuẩn CHOMSKY: 1) S → bA | aB; A → bAA | aS | a; B → aBB | bS | b. 2) S → 0S1 | 01. 3) S → aAB | BA; A → BBB| a; B → AS| b. 164 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 4) S → adAda | aSa | aca; A → bAb | bdSdb. 3.38. Biến đổi các văn phạm sau đây về dạng chuẩn GREIBACH: 1) G = ( {S, A}, {0, 1}, P, S) với các luật sinh P: S → AA | 0; A → SS | 1. 2) G = ( {A , A , A }, {a, b}, P, A ) với các luật sinh P: 1 2 3 1 A → A A ; A → A A | b; A → A A | a. 1 2 3 2 3 1 3 1 2 3) G = ( {A , A , A , A }, {a, b}, P, A ) với các luật sinh P: 1 2 3 4 1 A → A A | A A ; A → A A | a; A → A A | b; A → A A | a. 1 2 3 3 4 2 3 2 3 4 4 4 2 3 3.39. Cho văn phạm G với các luật sinh sau: S → BA | 0; A → SS | 1; B → AB | 0 | 1. 1) Xác định các thành phần và dạng chuẩn của văn phạm trên 2) Biến đổi văn phạm trên về dạng chuẩn GREIBACH 3.40. Cho Automat pushdown M = ; Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0 , X, Y}; F = ; : (q0 , a, Z0 ) = {(q0, XXX)}; (q0 , a, X ) = {(q0, XX)}; (q0 , b, X) = {(q1, )}; (q1 , b, X ) = {(q1, ), (q2, Y )}; (q2 , , Y) = {(q1, )}. Hãy kiểm tra xem M có đoán nhận đƣợc từ w bằng stack rỗng không: - w = aaaabbbbbb; - w = aabbb. 3.41. Cho Automat pushdown M = ; Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0 , X, Y}; F = {q2}; : (q0 , a, Z0 ) = {(q0, XXX)}; (q0 , a, X ) = {(q0, XX)}; (q0 , b, X ) = {(q1, )}; (q1 , b, X ) = {(q1, ), (q2, YX)}; (q2 , b,Y ) = {(q2, ), (q2, YX )}. Phạm Hùng Phú 165
Câu hỏi và bài tập chƣơng 3 Hãy kiểm tra xem M có đoán nhận đƣợc từ w bằng trạng thái kết thúc không: - w = aaaabbbbbb; - w = aabbbbb. 3.42. Chứng minh rằng các ngôn ngữ sau không phải là CFL: i j k 1) L = {a b c | i 0} i j 3) Tập hợp {a ca | i, j ≥ 0} m m n 4) {0 1 2 | m, n ≥ 1} m m n n 5) {a b c d | m, n ≥ 0} 3.49. Xây dựng văn phạm CFG tƣơng đƣơng với các PDA sau: 1) M = ; trong đó δ đƣợc cho nhƣ sau: 0 1 0 0 0 δ(q , 1, Z ) = {(q , XZ )} 0 0 0 0 δ(q , 0, X) = {(q , XX)} 0 0 δ(q , 1, X) = {(q , ε)} 0 1 δ(q , 1, X) = {(q , ε)} 1 1 δ(q , ε, X) = {(q , ε)} 1 1 166 Phạm Hùng Phú
Câu hỏi và bài tập chƣơng 3 δ(q , ε, Z ) = {(q , ε)} 1 0 1 2) M = ; trong đó δ đƣợc cho nhƣ sau: 0 1 0 0 0 δ(q , 1, Z ) = {(q , XZ )}; 0 0 0 0 δ(q , 1, X) = {(q , XX)}; 0 0 δ(q , 0, X) = {(q , X)}; 0 1 δ(q , ε, Z ) = {(q , ε)}; 0 0 0 δ(q , 1, X) = {(q , ε)}; 1 1 δ(q , 0, Z ) = {(q , Z )}. 1 0 0 0 3) M ({q , q }, {a, b, c}, {Z , X}, δ, q , Z , ∅), trong đó δ đƣợc cho nhƣ sau: 0 1 0 0 0 δ(q , a, Z ) = {(q , X)}; 0 0 0 δ(q , a, X) = {(q , XX)}; 0 0 δ(q , c, X) = {(q , X)}; 0 1 δ(q , b, Z ) = {(q , X)}; 0 0 0 δ(q , b, X) = {(q , XX)}; 0 0 δ(q , c, X) = {(q , ε)}. 1 1 3.50. Cho Automat pushdown M = ; Trong đó: Q = {q0, q1, q2};  = {a, b};  = {Z0 , X, Y}; F = {q2}; : (q0 , a, Z0 ) = {(q0, XXX)}; (q0 , a, X ) = {(q0, XX)}; (q0 , b, X ) = {(q1, )}; (q1 , b, X ) = {(q1, ), (q2, YX)}; (q2 , b,Y ) = {(q2, ), (q2, YX )}. Xây dựng văn phạm CFG tƣơng đƣơng với PDA trên. Phạm Hùng Phú 167
Lời giải tóm tắt hoặc hƣớng dẫn LỜI GIẢI TÓM TẮT HOẶC HƢỚNG DẪN 1. Bài tập chƣơng 1 1.13. 1) T* = {, 0, 1, 00, 11, 000, 001, 010, 011, 100, 101, 110, 111, } 2)  L  T* đều là ngôn ngữ trên bảng chữ cái T. Chẳng hạn: L1= ; * L2 = T = {, 0, 1, 00, 11, 000, 001, 010, 011, 100, 101, 110, 111, }; L3 = {}; L4 = {, 0, 1}; L5 = { 0, 11, 000, 111, 0110}; 1.14. 1) L1  L2 = {, 0, 1, 00, 11, 000, 001, 010, 011, 100}= L2 2) L1  L2 = {0, 1}= L1 3) L1 - L2 =  4) L2 - L1 = {, 00, 11, 000, 001, 010, 011, 100} 5) L1L2 = {0, 1, 00, 10, 01, 11, 000, 100, 011, 111, 0000, 1000, 0001, 1001, 0010, 1010, 0011, 1011, 0100, 1100}. 1.15. 1) * = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, }; L = * - L = {aa, ab, ba, bb, aaa, aab, aba, abb, }. 2) L0 = {}; L1 = {, a, b}; L2 = LL = {, a, b, aa, ab, ba, bb}; L3 = L2 L = {, a, b, aa, ab, ba, bb, aa, ba, aaa, aba, baa, bba, aab, abb, bab, bbb}; i i * 1.16. 1) L1 = {a b  i N } i j * 2) L2 = {0 1  i, j N } 1.17. 1a) - G không là văn phạm loại 3 vì luật sinh AB aADb vi phạm điều kiện của văn phạm loại 3; - G không là văn phạm loại 2 vì luật sinh AB aADb vi phạm điều kiện của văn phạm loại 2; 168 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn - G không là văn phạm loại 1 vì luật sinh C  vi phạm điều kiện của văn phạm loại 1. Vậy G là văn phạm loại 0 (văn phạm ngữ cấu). 1b) G = (N, T, P, S); trong đó: N = {S, A, B, C, D} ; T = {a, b}; P ={S ABC; AB aADb; Dab bDb; DbC BaC; aB Ba; AB ; C }; S = S. 2a) - G không là văn phạm loại 3 vì luật sinh DF B vi phạm điều kiện của văn phạm loại 3; - G không là văn phạm loại 2 vì luật sinh DF B vi phạm điều kiện của văn phạm loại 2; - G không là văn phạm loại 1 vì luật sinh DF B vi phạm điều kiện của văn phạm loại 1. Vậy G là văn phạm loại 0 (văn phạm ngữ cấu). 2b) G = (N, T, P, S); trong đó: N = {S, A, B, C, D, E, F} ; T = {a, b}; P = {S ABaDF; BD DCB; BC bB; AD AAE; EC AE; EB BE; EF BBDF; DF B | }; S = S. 3a) - G không là văn phạm loại 3 vì luật sinh S SS vi phạm điều kiện của văn phạm loại 3; - G là văn phạm loại 2 (văn phạm phi ngữ cảnh) vì tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm loại 2. 3b) G = (N, T, P, S) với: N = {S}; T = {a, b}; P = {S SS; S aSb; S bSa; S ab; S ba}. Phạm Hùng Phú 169
Lời giải tóm tắt hoặc hƣớng dẫn S = S. 4a) G là văn phạm loại 3 (văn phạm chính quy) vì tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm tuyến tính phải. 4b) G = (N, T, P, S) với: N = {S}; T = {a}; P = {S aS; S a; A abB | B|  }; S = S. 1.18. 1) - G là văn phạm loại 3 (văn phạm tuyến tính trái) vì tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm tuyến tính trái. - G = (N, T, P, S) với: N = {S, A}; T = {a, b}; P = {S Sab; S Aa; A Sa; A Abbba; A a; S }; S = S. 2) - G là văn phạm loại 1 (văn phạm cảm ngữ cảnh) vì: + G không là văn phạm loại 3 vì luật sinh AB BA vi phạm điều kiện của văn phạm loại 3; + G không là văn phạm loại 2 vì luật sinh AB BA vi phạm điều kiện của văn phạm loại 2; + Tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm loại 1. - G = (N, T, P, S) với: N = {S, A, B}; T = {a, b}; P = {S AB; AB BA; A aA; B Bb; A a; B b}; S = S. 3) - G là văn phạm loại 1 (văn phạm cảm ngữ cảnh) vì: + G không là văn phạm loại 3 vì luật sinh Bb Abb vi phạm điều kiện của văn phạm loại 3; 170 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn + G không là văn phạm loại 2 vì luật sinh Bb Abb vi phạm điều kiện của văn phạm loại 2; + Tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm loại 1. - G = (N, T, P, S) với: N = {S, A, B}; T = {a, b}; P = {S A; S AAB; Aa Aba; A aa; Bb Abb; AB ABB; B b}; S = S. 1.19. 1) - G là văn phạm loại 3 (văn phạm tuyến tính trái) vì tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm tuyến tính trái. - G = (N, T, P, S) với: N = {S}; T = {a}; P = {S Sa; S a; S }; S = S. 2) - w = . Áp dụng luật sinh S , ta có dẫn xuất một bƣớc S . - w = a. Áp dụng luật sinh S a, ta có dẫn xuất một bƣớc S a. Hoặc Áp dụng luật sinh S Sa, rồi áp dụng luật sinh S , ta có dẫn xuất hai bƣớc S Sa a. - w = aa. S Sa Saa aa hoặc S Sa aa. - w = ai ; với i N. Áp dụng i-1 lần luật sinh S Sa và một lần luật sinh S a, ta có S i ai. Hoặc áp dụng i lần luật sinh S Sa và một lần luật sinh S , ta có S i+1 ai. 3) L(G) = {ai  i N}. Phạm Hùng Phú 171
Lời giải tóm tắt hoặc hƣớng dẫn 1.20. 1) - G là văn phạm loại 3 (văn phạm tuyến tính phải) vì tất cả các luật sinh của nó đều thỏa mãn điều kiện của văn phạm tuyến tính phải. - G = (N, T, P, S) với: N = {S, A, B}; T = {a, b}; P = {S aA; A aA; A aB; B bB; B b}; S = S. 2) - w = aab. S aA aaB aab. - w = aaaaabb. S aA aaA aaaA aaaaA aaaaaB aaaaabB aaaaabb. - w = ai bj; với i, j N+; i 2. Áp dụng 1 lần luật sinh S aA Áp dụng i-2 lần luật sinh A aA và một lần luật sinh A aB, ta có S i aiB. Áp dụng j-1 lần luật sinh B bB và một lần luật sinh B b, ta có S i+j ai bj. 3) L(G) = {ai bj; với i, j N+; i 2}. 1.21. 1) - G là văn phạm loại 2. - G = (N, T, P, S) với: N = {S}; T = {a, b}; P = {S bSa; S }; S = S. 2) - w = . S . - w = ba. S bSa ba. - w = bi ai; với i N. Áp dụng i-1 lần luật sinh S bSa và một lần luật sinh S , ta có S i biai. 3) L(G) = {bi ai; với i N}. 172 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn 1.22. 1) - G là văn phạm loại 2. - G = (N, T, P, S) với: N = {S, A}; T = {a, b}; P = {S aAb; S ; A aAb; A }; S = S. 2) - w = . S . - w = ab. S aSb ab. - w = aaaabbbb. S aAb aaAbb aaaAbbb aaaaAbbbb aaaabbbb. - w = bi ai; với i N. Áp dụng 1 lần luật sinh S , ta có S . Áp dụng 1 lần luật sinh S aAb Áp dụng i -1 lần luật sinh A aAb và một lần luật sinh A , ta có S i+1 aibi với i N+. 3) L(G) = {ai bi ; với i N}. 1.23. 1) - G là văn phạm loại 2. - G = (N, T, P, S) với: N = {S, A, B}; T = {a, b}; P = {S AB; A aA; A a; B aB; B b}; S = S. 2) - w = aab. S AB aAB aaB aab. - w = aaaaab. S AB aAB aaAB aaaAB aaaaB aaaaaB aaaaab. - w = ai b; với i N+. Phạm Hùng Phú 173
Lời giải tóm tắt hoặc hƣớng dẫn Áp dụng 1 lần luật sinh S AB Áp dụng i-1 lần luật sinh A aA và một lần luật sinh B aB, ta có S i+1 aib. Áp dụng 1 lần B b, ta có S i+2 ai b. 3) L(G) = {ai b; với i N+}. 1.24. 1) S aA; A aA|b|c. 2) S Aab; A aA|b|c. 3) S Aba; A aA|b|c. 4) S Abcd; A aA|b|c. 1.25. 1) S A1; A A0|0. 2) S 0A; A 0A|1. 3) S 0A1; A 0A|0. Hoặc S AB; A 0A|0; B 1 1.26. 1) S A1; A A1|B; B C000; C . 2) S 000A; A 1A|1. 3) S 000AB; A 1A|1; B . Hoặc S AB; A 000; B 1B|1. 1.27. S AB; A 0A1|01; B 2B3|. 1.28. S AB; A aAb| ab; B cB|. 1.29. 1) S abA; A abA| B; B cB|c; 2) S Ac; A Ac| B; B Bab| ab; 3) S abAB; A abA| ; B cB|c. Hoặc S AB; A abA|ab; B cB|c. 1.30. 1) S A2; A A2|B; B B1|C; C 000. 2) S 000A; A 1A| B; B 2B| 2. 3) S 000AB; A 1A|1; B 2B|2. 1.31. 1) S S2| A; A A1|C; C C0|. 2) S 0S|A; A 1A|B; B 2B|. 3) S ABC; A 0A|; B 1B|; C 2C|. 1.32. 1) S S3|A; A A2|B; B B1|C; C C0|. 174 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn 2) S 0S|A; A 1A|B; B 2B|C;C 3C|. 3) S ABCD; A 0A|; B 1B|; C 2C|; D 1D|. 2. Bài tập chƣơng 2 2.16. 1) Biểu diễn M a) Dạng bảng: -q0 = A ; - F = C, E; - : Q  a b A A B B D E C E D D C E E E b) Dạng đồ thị: a a a b Start b b b A B C D E a a 2) Automat M là Automat hữu hạn đơn định; vì q Q và a , ta có:  (q, a)  1 3) - (A, aaabbaaaa) + (A, a) = A; (A, a) = A; (A, a) = A; + (A, b) = B; + (B, b) = E; + (E, a) = E;(E, a) = E; (E, a) = E; (E, a) = E (A, aaabbaaaa) = E. - (B, aaaabbaa); + (B, a) = D; Phạm Hùng Phú 175
Lời giải tóm tắt hoặc hƣớng dẫn + (D, a) = C; + (C, a) = E; + (E, a) = E; + (E, b) = ; + (, b) = ; + (, a) = . + (, a) = . (B, aaaabbaa) = . 4) - w = aabaaaaa$ Ta trình bày giải thuật sử dụng automat đơn định đoán nhận w bằng bảng sau: Bƣớc q c khởi tạo A a 1 A a 2 A b 3 B a 4 D a 5 C a 6 E a 7 E a 8 E $ Ta có q = E F. Vậy automat trên đoán nhận đƣợc từ w = aabaaaaa. - w = aaaababbb$ Bƣớc q c khởi tạo A a 1 A a 2 A a 3 A a 4 A b 5 B a 6 D b 7 E b 8  b 9  $ Ta có q =  F. Vậy automat trên không đoán nhận đƣợc từ w = aaaababbb. 176 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn 2.17. 1) Biểu diễn M a) Dạng bảng: -q0 = 0 ; - F = 3; - : Q  a b c 0 1 1 1 1 1 2 2 3 4 3 4 4 2 4 3 b) Dạng đồ thị: a a a b Start b b b c 0 1 2 4 3 c a a 2) Automat M là Automat hữu hạn đơn định; vì q Q và a , ta có:  (q, a)  1 3) - (1, aaabbaaaabc) + (1, a) = 1; (1, a) = 1; (1, a) = 1; + (1, b) = 2; + (2, b) = 4; + (4, a) = 2; + (2, a) = 3; + (3, a) = 4; + (4, a) = 2; + (2, b) = 4; + (4, c) = 3. Phạm Hùng Phú 177
Lời giải tóm tắt hoặc hƣớng dẫn (1, aaabbaaaabc) = 3. - (0, cabaabba); + (0, c) = 1; + (1, a) = 1; + (1, b) = 2; + (2, a) = 3; + (3, a) = 4; + (4, b) = 4; (4, b) = 4; + (4, a) = 2; (0, cabaabba)= 2. 4) - w = caabaaabca Bƣớc q c khởi tạo 0 c 1 1 a 2 1 a 3 1 b 4 2 a 5 3 a 6 4 a 7 2 b 8 4 c 9 3 a 10 4 $ Ta có q = 4 F. Vậy automat trên không đoán nhận đƣợc từ w = caabaaabca. - w = aaaabbbc. Bƣớc q c khởi tạo 0 a 1 1 a 2 1 a 3 1 a 4 1 b 5 2 b 6 4 b 7 4 c 8 3 $ Ta có q = 3 F. Vậy automat trên đoán nhận đƣợc từ w = aaaabbbc. 2.18. 1) Biểu diễn M a) Dạng bảng: -q0 = A ; 178 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn - F = E; - : Q  a b A {A, B} {B} B {D, E} {C, E} C {D, E} {D} D {C} {E} E {E} b) Dạng đồ thị: a a b a a a Start b b a b A B C D E b a a 2) Automat M là Automat hữu hạn không đơn định; vì A Q và a , ta có:  (A, a)  =  {A, B} = 2 1 3) - (A, aaabbaaaa) + (A, a) = {A, B}; + ({A, B}, a) = (A, a)  (B, a) = {A, B}{D, E}= {A, B, D, E}; + ({A, B, D, E}, a) = {A, B, C, D, E}; + ({A, B, C, D, E}, b) = {B, C, D, E}; + ({B, C, D, E}, b) = {C, D, E }; ({C, D, E}, a) = {C, D, E}; + ({C, D, E}, a) = {C, D, E}; + ({C, D, E}, a) = {C, D, E}; + ({C, D, E}, a) = {C, D, E}. Phạm Hùng Phú 179
Lời giải tóm tắt hoặc hƣớng dẫn (A, aaabbaaaa) = {C, D, E}. - (C, abaabbaa); + (C, a) = {D, E}; + ({D, E}, b) = {E}; + ({E}, a) = (E, a) = {E}; + ({E}, a) = {E}; + ({E}, b) = ; + (, b) = ; + (, a) = . (C, abaabbaa)= . 4) - w = aabaaaaa$ Ta trình bày giải thuật sử dụng automat không đơn định đoán nhận w bằng bảng sau: Bƣớc q = (q, c) c khởi tạo A a 1 {A, B} a 2 {A, B, D, E} b 3 {B, C, E} a 4 {D, E} a 5 {C, E} a 6 {D, E} a 7 {C, E} a 8 {D, E} $ Ta có q  F = {D, E}  {E} = {E} . Vậy automat trên đoán nhận đƣợc từ w = aabaaaaa. - w = aaaababbb$ 180 Phạm Hùng Phú
Lời giải tóm tắt hoặc hƣớng dẫn Bƣớc q = (q, c) c khởi tạo A a 1 {A, B} a 2 {A, B, D, E} a 3 {A, B,C, D, E} a 4 {A, B, C, D, E} b 5 {B, C, D, E} a 6 {C, D, E} b 7 {D, E} b 8 {E} b 9 {E} $ Ta có q  F = {E}  {E} = {E} . Vậy w = aaaababbb L(M). 2.19. 1) Biểu diễn M a) Dạng bảng: -q0 = 0 ; - F = 3; - : Q  a b c 0 {0,1} {2} {2} 1 {1, 2} {1, 2, 3} 2 {3} {2, 3} {3} 3 {3} {2} {3} b) Dạng đồ thị: b a a c b Start a a 0 1 a,b,c 3 a 2 b b b,c b Phạm Hùng Phú 181
Lời giải tóm tắt hoặc hƣớng dẫn 2) Automat M là Automat hữu hạn không đơn định; vì 1 Q và b , ta có:  (1, b)  =  {1, 2, 3} = 3 1 3) - (1, aaabbaaaabc) + (1, a) = {0,1} + ({0,1}, a) = {0, 1, 2}; + ({0,1,2}, a) = {0, 1, 2, 3}; + ({0,1,2,3}, b) = {1, 2, 3}; + ({1, 2, 3}, b) = {1, 2, 3}; + ({1, 2, 3}, a) = {1, 2, 3}; + ({1, 2, 3}, a) = {1, 2, 3}; + ({1, 2, 3}, a) = {1, 2, 3}; + ({1, 2, 3}, a) = {1, 2, 3}; + ({1, 2, 3}, b) = {1, 2, 3}; + ({1, 2, 3}, c) = {2, 3}; (1, aaabbaaaabc) = {2, 3}. - (0, cabaabba); + (0, c) = 2; + (2, a) = 3; + (3, b) = 2; + (2, a) = 3; + (3, a) = 3; + (3, b) = 2; + (2, b) = {2, 3}; + ({2, 3}, a) = 3; (0, cabaabba)= 3. 182 Phạm Hùng Phú