Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 4: Căn phạm phi ngữ cảnh và ôtômát đẩy xuống - Nguyễn Thị Thùy Linh

 và số b. 
 9 10 
 CÂY DẪN XUẤT VÀ SỰ NHẬP NHẰNG TRONG VPPNC CÂY DẪN XUẤT VÀ SỰ NHẬP NHẰNG TRONG VPPNC 
 (TT) (TT) 
 Ví dụ 4.3: Cho VPPNC G = ({a, b}, {S, A}, P, S), Trong đó: Các con của một nút là được xếp từ “trái qua phải”. Ta có thể mở 
 P= { S aAS | a rộng thứ tự “từ trái sang phải” đó cho các nút con của cây. 
 A SbA | SS | ba } Nếu ta đọc các nhãn của các lá, theo thứ tự từ “trái qua phải” ta có 
 S một dạng câu và gọi đó là kết quả của cây dẫn xuất. Chẳng hạn 
  Ta có một cây dẫn xuất như sau: 
 a A S aabbaa là kết quả của cây dẫn xuất ở hình trên. 
 Ta gọi cây con của một cây dẫn xuất là một nút nào đó cùng với các 
 S b A a nút con bên dưới của nó, các nhánh nối chúng và các nhãn kèm 
 theo. 
 a b a Nếu nhãn của của cây con là A, thì đó là cây con nhãn A còn gọi là 
 A-cây. 
 Kết quả của cây: w = aabbaa 
 11 12 
 3 
 MỐI LIÊN QUAN GIỮA 
 DẪN XUẤT VÀ CÂY DẪN XUẤT 
 Định lý 4.1: Cho G = (, , P, S) là một VPPNC, thế thì S * khi 
 S và chỉ khi có cây dẫn xuất trong G mà kết quả là . 
 a S Ta gọi dẫn xuất bên trái nhất (nói gọn là dẫn xuất trái), nếu ở mỗi 
 A bước dẫn xuất, biến được thay thế là biến nằm bên trái nhất trong 
 CÂY CON A (A-CÂY) dạng câu. 
 S b A 
 Tương tự ta gọi dẫn xuất bên phải nhất (nói gọn là dẫn xuất phải), 
 nếu ở mỗi bước dẫn xuất, biến được thay thế là biến nằm bên phải 
 a b a nhất trong dạng câu. 
 Mỗi cây dẫn xuất với kết quả tương ứng với nhiều dẫn xuất S * 
 . Các dẫn xuất này có cùng độ dài, chúng chỉ khác nhau ở thứ tự áp 
 dụng các sản xuất. Trong số các dẫn xuất này chỉ có một dẫn xuất bên 
 trái nhất và một dẫn xuất bên phải nhất. 
 13 14 
 MỐI LIÊN QUAN GIỮA MỐI LIÊN QUAN GIỮA 
 DẪN XUẤT VÀ CÂY DẪN XUẤT DẪN XUẤT VÀ CÂY DẪN XUẤT 
 Tuy nhiên với một xâu L(G), rất có thể có nhiều cây dẫn xuất với 
  Văn phạm này cho ta viết các biểu thức số học với các phép toán 
 kết quả chung . Điều đó có nghĩa là xâu có thể phân tích cú pháp + và *. Cây dẫn xuất sau cho kết quả là a + a * a. 
 theo nhiều cách khác nhau. 
  dẫn xuất trái nhất : 
 Ta nói một VPPNC G là nhập nhằng nếu có một xâu là kết quả của 
 hai cây dẫn xuất khác nhau trong G. Tuy nhiên cũng có thể nói rằng E E * E E + E * E a + E * E a + a * E a + a*a 
 văn phạm G là nhập nhằng nếu có một xâu với hai dẫn xuất bên trái  dẫn xuất phải nhất: 
 nhất (hay hai dẫn xuất bên phải nhất) S * . E E * E E * a E + E * a E + a * a a + a * a 
 Một ngôn ngữ PNC L được gọi là ngôn ngữ nhập nhằng cố hữu nếu E 
 mọi VPPNC sản sinh ra L đều nhập nhằng. 
 E * E 
 Ví dụ 4.4: Xét VPPNC G0 cho bởi các sản xuất sau: 
 E + E 
 E E + E | E * E | (E) | a a 
 a 
 a 
 15 16 
 4 
 MỐI LIÊN QUAN GIỮA DẪN XUẤT VÀ CÂY DẪN XUẤT MỐI LIÊN QUAN GIỮA 
 (TT) DẪN XUẤT VÀ CÂY DẪN XUẤT (TT) 
 Tuy nhiên ta còn thấy có một cây dẫn xuất khác với kết quả là a + a * a 
 Để khắc phục sự nhập nhằng của G đó, ta có thể: 
 như hình sau: 0
  Phép * được ưu tiên hơn phép +: 
 E E E + T | T 
 T T * F | F 
 E + E 
 F (E) | a 
  Phép cộng và phép nhân luôn thực hiện từ trái sang phải ( trừ khi gặp vòng 
 a E * E đơn) 
 E E + T | E * T | T 
 a a T (E) | a 
 Điều đó 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 cộng trước hay thực hiện phép nhân trước. 
 17 18 
 GIẢN LƢỢC CÁC VPPNC CÁC KÝ HIỆU VÔ ÍCH 
 Một VPPNC có thể còn chứa đựng nhiều yếu tố thừa vô ích, chẳng G = (, , P, S) là một VPPNC. Ta nói một ký hiệu X là có ích nếu 
 hạn có những ký hiệu không thật sự tham gia vào quá trình sinh sản có một dẫn xuất S * X * w, với ,  (  )* và w *. 
 xâu, hoặc có những sản xuất dạng A B làm kéo dài các dẫn xuất 
 Nếu không có thế thì X là vô ích. 
 một cách không cần thiết. 
 Như vậy có hai khía cạnh cần phải xem xét của ký hiệu có ích: 
 Vấn đề giản lược VPPNC: 
  Từ X có thể dẫn xuất ra một xâu các ký hiệu cuối nào đó (X là 
  Loại bỏ các kí hiệu không dẫn ra được kí hiệu kết thúc (bổ đề 4.1) 
 hữu sinh). 
  Loại bỏ các kí hiệu không được dẫn xuất từ S (bổ đề 4.2) 
  X phải xuất hiện trong một xâu dẫn xuất từ S (X là đến được). 
  Loại bỏ các dẫn xuất đơn dạng A B 
 Tuy nhiên hai điều kiện đó chưa đủ để đảm bảo rằng X là có ích. 
  Loại bỏ các qui tác rống dạng A  
 19 20 
 5 
 CÁC KÝ HIỆU VÔ ÍCH (TT) CÁC KÝ HIỆU VÔ ÍCH (TT) 
 *
 Bổ đề 4.1: (Loại bỏ các ký hiệu không dẫn xuất ra được ký hiệu kết P’ = {A | , (  ’) }  P ( P’ gồm mọi sản xuất 
 thúc): trong P mà các ký hiệu trong đó đều thuộc   ’ 
 Input: Cho một VPPNC G = (, , P, S) với L(G)  BEGIN 
 Output: VPPNC G’ = (, ’, P’, S) tương đương G sao cho với mọi A 
 cũ = ; 
 trong ’, có một w nào đó trong * để cho A * w (nghĩa là mọi biến 
 *
 ’ đều đến được đích). mới = {A | A w với w  }; 
  Giải thuật: Duyệt qua các sản xuất trong P và kết nạp dần các biến WHILE cũ mới DO 
 vào ’ như sau: BEGIN 
 *
 Nếu A w, với w  thì A đưa vào ’.  cũ = mới; 
 Nếu A X X X , trong đó các X là ký hiệu cuối hoặc là biến 
 1 2 n i  mới = cũ  {A | A với (  cũ)*}; 
 đã được kết nạp vào ’, thì A cũng được đưa vào ’. 
 END 
 Cứ thế, ’ được thành lập nhờ một giải thuật lặp ở phía sau. 
 Vòng lặp sẽ dừng vì P là hữu hạn. ’ = mới 
 21 END 22 
 CÁC KÝ HIỆU VÔ ÍCH (TT) CÁC KÝ HIỆU VÔ ÍCH (TT) 
 Bổ đề 4.2: (Loại bỏ các ký hiệu vô ích không được sinh ra từ S) Input Định lý 4.2: Mọi ngôn ngữ PNC không rỗng đều có thể được sản sinh từ 
 : Cho một VPPNC G = (, , P, S) một VPPNC không có ký hiệu vô ích. 
 Output: VPPNC G’ = (’, ’, P’, S) tương đương G sao cho với mọi Ví dụ 4.5: Xét văn phạm có tập luật sinh sau: 
 X trong ’  ’ tồn tại ,  trong ( ’  ’)* để cho S * X. 
 (nghĩa là mọi biến trong ’ đều xuất phát từ S) S AB | a 
  Giải thuật: Tập ’  ’ có thể được thành lập bởi giải thuật lặp A a 
 như sau: Áp dụng bổ đề 4.1, B bị loại cùng với sản xuất S AB 
 Cho S vào ’. Nếu một biến A đã được đưa vào ’ và A 1 | Áp dụng bổ đề 4.2 cho hai sản xuất còn lại 
 | | thì kết nạp mọi biến trong , , , vào ’ và mọi 
 2 n 1 2 n S a 
 ký hiệu kết thúc trong 1, 2, , n vào trong ’. 
 Thủ tục ngừng khi không còn bổ sung thêm được ký hiệu nào A a 
 mới cả. Ta thấy chỉ có S và a là đến được (A bị loại vì nó không được sinh ra từ S). 
 Khi đó lấy P’ là tập mọi sản xuất trong P chỉ chứa các ký hiệu Vậy văn phạm tương đương không có ký hiệu vô ích là G=({a}, {S}, (S 
 trong ’  ’ a), S). 
 23 24 
 6 
 LOẠI BỎ CÁC QUI TẮC RỖNG LOẠI BỎ CÁC QUI TẮC RỖNG (TT) 
 Ta tìm cách loại bỏ các sản xuất dạng A , gọi là các -dẫn xuất. Nếu A  thì A bỏ được, sau đó nếu B là một sản xuất mà 
 Đương nhiên nếu  L(G), ta không thể loại hết các -dẫn xuất được. mọi ký hiệu trong đều đã biết là bỏ được, thì B cũng bỏ được, 
 Trường hợp này -dẫn xuất vẫn còn và thường là S . lặp lại quá trình đó cho đến khi không bỏ được kí hiệu nào nữa. 
 Nhưng nếu  L(G) thì có thể loại hết  ra khỏi G.  Tập các sản xuất P’ được thành lập như sau: 
 Định lý 4.3: Nếu L = L(G) với một VPPNC G = (, , P, S), thì L – Nếu A X1X2Xn là một sản xuất trong P, thì ta đưa vào P’ các 
 {} là bằng L(G’) với một VPPNC G’ không chứa các ký hiệu vô ích sản xuất có dạng A 1 2 n, trong đó: 
 và các -dẫn xuất. 
 Nếu Xi là không triệt tiêu được, thì I = Xi 
  Giải thuật: xây dựng G’ = (, , P’, S) như sau: 
 Nếu Xi là triệt tiêu được thì i sẽ hoặc là Xi hoặc là . 
 *
 Gọi một biến A là triệt tiêu được, nếu A . Có thể xác định 
 Không cho tất cả các i đều . 
 các ký hiệu triệt tiêu được của G nhờ giải thuật lặp sau đây: 
 25 26 
 LOẠI BỎ CÁC QUI TẮC RỖNG (TT) CÁC SẢN XUẤT ĐƠN 
 Ví dụ 4.6: Loại - sản xuất trong văn phạm G sau đây: Ta tìm cách loại trừ các sản xuất dạng A B, trong đó A và B đều là 
 S AB biến; chúng được gọi là các sản xuất đơn. 
 A aA |  Chú ý A a, với a  không phải sx đơn. 
 B bB |  Định lý 4.4: Mọi NNPNC không chứa  đều có thể sinh ra từ một 
 Tập các ký hiệu triệt tiêu của G là {S, A, B} VPPNC không có ký hiệu vô ích, các  - sản xuất, và các sản xuất 
 Áp dụng cách thành lập P trong định lý 4.3: đơn. 
 Từ sản xuất S AB, ta có S AB | A | B  Giải thuật: Giả sử L = L(G) với một VPPNC G = (, , S, P) và  
 Từ sản xuất A aA, ta có A aA| a L. Bởi định lý 4.3 ta có thể giả thiết thêm là G không có các  - 
 Từ sản xuất B bB, ta có B bB | b sản xuất. Thành lập các sản xuất P’ từ P như sau: 
  Lưu ý rằng văn phạm mới G’ không sản sinh ra , trong khi G lại Đưa mọi sản xuất không đơn trong P vào P’ 
 *
 sản sinh ra . Vậy để G’ tương đương G, thì ta bổ sung thêm S  Nếu A B với A, B đưa vào P’ mọi sản xuất có dạng A 
 vào G’ nếu B là một sản xuất không đơn trong P. 
 27 28 
 7 
 CÁC SẢN XUẤT ĐƠN (TT) DẠNG CHUẨN CHOMSKY (CNF) 
 Ví dụ 4.7: Loại các sản xuất đơn trong văn phạm: Định lý 4.5 (Dạng chuẩn Chomsky): Mọi NNPNC không chứa  đều có thể 
 E E + T | T sinh ra từ một văn phạm trong đó mọi sản xuất đều có dạng A BC hoặc A 
 T T * F | F a, với A, B, C là biến và a là một ký hiệu kết thúc. 
 F (E) | a  Giải thuật: 
 *
 Gọi A = {B| A B}, dễ kiểm chứng rằng:  Input: G là VPPNC bất kỳ 
 E = {E, T, F}, T = {T, F}, F = {F}.  Output: G’ là VPPNC ở CNF sao cho L(G’) = L(G) 
 1. Các sản xuất không đơn trong P: 
 Cho NNPNC L. Bởi định lý 4.4, ta có thể tìm được một văn phạm G1 = 
 E E + T 
 (, , P, S) không có sản xuất đơn hoặc  - sản xuất và L = L(G1). 
 T T * F 
 B1:Trong P nếu có một sản xuất có vế phải là một ký hiệu duy nhất, thì 
 F (E) | a ký hiệu đó phải là ký hiệu cuối, và các sản xuất đó đã ở dạng CNF 
Các sản xuất mới thay cho các sản xuất đơn: 
 E T * F | (E) | a 
 T (E) | a 
 29 30 
 DẠNG CHUẨN CHOMSKY (TT) DẠNG CHUẨN CHOMSKY (TT) 
 B2:xét một sản xuất trong P có dạng A X1X2Xm với m 2. Nếu Như thế ta thu được một tập các biến mới ’’ và một tập các sản xuất 
 mới P’’. Cho G = (, ’’, P’’, S), G là VPPNC và ở dạng chuẩn 
 Xi là một ký hiệu cuối a, ta đưa thêm một biến mới Ca và một sản xuất 3 3
 Chomsky. 
 mới Ca a, sản xuất này đã ở dạng CNF. Sau đó thay Xi bởi Ca trong 
 sản xuất trên. Ví dụ 4.8: Tìm dạng chuẩn Chomsky cho văn phạm G({a, b}, {S, A, B}, P, 
 S) với P gồm các sản xuất: 
 Văn phạm G2 = (, ’, P’, S) chưa hẳn ở dạng Chomsky, song các dẫn 
 S bA | aB 
 xuất của nó đã ở dạng A a hoặc ở dạng A B1B2Bm với m 2 
 và Bi ’ (1 i m). A bAA | aS | a 
 B aBB | bS | b 
 B3:Bây giờ ta biến đổi G2 về dạng chuẩn Chomsky: mỗi sản xuất A 
 B1B2Bm trong P’ với m 3, ta thêm các biến mới D1, D2,, Dm-2 và -------Giải------ 
 thay sản xuất trên bởi tập các sản xuất: Bước 1: A a (thỏa CNF) 
{A B1D1, D1 B2D2 ,, Dm-3 Bm-2Dm-2, Dm-2 Bm-1Bm} B b (thỏa CNF) 
 31 32 
 8 
 DẠNG CHUẨN CHOMSKY (TT) 
 (1) A CbAA được thay bởi A CbD1 (thỏa CNF) 
Bước 2: Đặt Ca a D1 AA (thỏa CNF) 
 Cb b (2) B CaBB được thay bởi B CaD2 (thỏa CNF) 
 S bA | aB được thay bởi S CbA | CaB (thỏa CNF) D2 BB (thỏa CNF) 
A bAA được thay bởi A CbAA (1)  Vậy VPPNC ở dạng chuẩn CNF G’=(, ’ , P’ , s) 
A aS được thay bởi A CaS (thỏa CNF) ={a,b} 
B aBB được thay bởi B C BB (2) 
 a ’ = {S,A,B,C ,C ,D ,D } P’ = { S CbA | CaB 
 a b 1 2 A C S | C D | a 
B bS được thay bởi B CbS (thỏa CNF) S là kí hiệu bắt đầu a b 1
 B CbS | CaD2 | b 
Bước 3: Đặt D1 AA 
 D1 AA 
 D BB D BB 
 2 2
 Ca a 
 Cb b 
 33 34 
 DẠNG CHUẨN GREIBACH - GNF 
 VD 4.9. Cho VPPNC G({0,1},{A},P,A) Ta gọi luật sinh với biến A ở bên trái là A-luật sinh. 
 Với P = {A 0A1 | 01 } Bổ đề 4.3: Cho G = (, , P, S) là VPPNC. 
 Tìm VPPNC ở dạng CNF? Trong đó P = { A B là A-dẫn xuất 
 B 1 | 2 | | k 
 Khi đó G1 = (, , P1, S) là VPPNC tương đương với G. 
 Trong đó P1 = ({P – {A B})  {A i | 1 i k} 
 thật ra đây là phương pháp thế. 
 Bổ đề 4.3 được sử dụng để xóa biến B xuất hiện ở vị trí 
 đầu tiên của các A-dẫn xuất. 
 35 36 
 9 
 DẠNG CHUẨN GREIBACH – GNF (TT) 
  Tập các A-dẫn xuất trong P1 là A 1 | 2 || m và 
 Bổ đề 4.4: Cho G = (, , P, S) là VPPNC. Giả sử tập các A  Z |  Z||  Z 
 A-dẫn xuất là 1 2 m
  Tập các Z-dẫn xuất trong P1 là Z 1 | 2 || n và 
 A A | A | | A |  |  ||  , trong đó  không 
 1 2 n 1 2 m i Z 1 Z| 2 Z|| nZ 
 bắt đầu bằng A. 
  Các qui tắc đối với các biến khác cũng phụ thuộc P1. 
 Khi đó G’ = (,  {Z}, P1, S) là VPPNC tương đương với Bổ đề 4.4 được sử dụng để loại bỏ biến A khỏi vế phải của các quy 
 G có được bằng cách thêm biến mới Z và P1 được xác định tắc A . 
 như sau: Định nghĩa: VPPNC G ở dạng chuẩn Greibach (GNF) nếu các quy 
 tắc sản sinh đều có dạng: A a , trong đó * và a  
 37 38 
 DẠNG CHUẨN GREIBACH – GNF (TT) DẠNG CHUẨN GREIBACH – GNF (TT) 
  Bước 3: Chuyển A -dẫn xuất về dạng A a. Ở đây sử dụng bổ 
 Định lý 4.6: Mọi NNPNC L không chứa rỗng đều có thể được sinh n n
 đề 4.4 để loại bỏ quy tắc dạng A A . 
 bởi văn phạm phi ngữ cảnh G ở dạng chuẩn Greibach. n n
  Bước 4: Biến đổi A -dẫn xuất về dạng A a với i = 1,2,..,n-1 (sử 
 Giải thuật đưa VPPNC G về VPPNC G’ dạng chuẩn Greibach: i i
 dụng bổ đề 4.3). 
  Bước 1: Loại bỏ các quy tắc rỗng và sau đó xây dựng VPPNC G ở 
  Bước 5: Biến đổi các Z -dẫn xuất về dạng Z a (tƣơng tự bƣớc 
 dạng CNF để sinh ra L. Giả sử G = (, {A , A , , A }, P, A ) i i 
 1 2 n 1 4). 
  Bước 2: Để có được các quy tắc dạng Ai a hoặc Ai Aj  với 
 Sau bước 5 chúng ta có G1 là VPPNC dạng GNF 
 j>i thì phải chuyển Ai-dẫn xuất về dạng Ai Aj  sao cho j>i. Điều 
 này thực hiện được bằng phương pháp qui nạp theo i và sử dụng  Ví dụ 4.10: Tìm VPPNC ở dạng GNF tương đương với văn phạm 
 G có các qui tắc sản sinh sau: S AA |a, A SS |b 
 bổ đề 4.3 cuối cùng chúng ta có Ai Aj , với i = 1,2,..,n-1 và j>i 
 hoặc Ai a’. An-dẫn xuất sẽ có dạng An An hoặc An a’ 
 39 40 
 10 
 DẠNG CHUẨN GREIBACH – GNF (TT) DẠNG CHUẨN GREIBACH – GNF (TT) 
 Giải: A2 aA1, A2 b, A2 aA1Z2, A2 bZ2, Z2 A2 A1, Z2 A2 A1Z2 
 Bước 4: 
 Bước 1: Văn phạm G ở dạng CNF. Đặt A1 = S, A2 = A các quy tắc 
 trên chuyển thành A1 A2 A2 | a, A2 A1 A1 | b và không có quy  A2-dẫn xuất là A2 aA1| b| aA1Z2 | bZ2 
 tắc rỗng. 
  Trong các A1-dẫn xuất chỉ còn lại A1 a vì A1 A2A2 bị loại bỏ 
 Bước 2: theo bổ đề 4.3. Các A1 sau khi biến đổi là: 
  A1- dẫn xuất có đúng dạng theo yêu cầu: A1 A2 A2 | a A1 a| aA1A2| bA2| aA1Z2A2| bZ2A2 
  A2 b là thỏa mãn điều kiện bước 2 ở trên. Sử dụng bổ đề 4.3 Bước 5: Những Z2-dẫn xuất cần biến đổi là Z2 A2 A1, Z2 A2 A1Z2 
 để biến đổi A A A A , A a A Vậy A -dẫn xuất sẽ là: A 
 2 2 2 1 2 1 . 2 2 Áp dụng bổ đề 4.3 ta nhận được 
 A2 A2 A1, A2 a A1 , A2 b. 
 Z2 aA1A1| bA1| aA1Z2A1| bZ2A1 
 Bước 3: Áp dụng bổ đề 4.4 cho các A2-dẫn xuất. Thêm Z2 và biến 
 Z2 aA1A1Z2| bA1Z2| aA1Z2A1Z2 | bZ2A1Z2 
 đổi A2 A2 A2 A1 về dạng yêu cầu: 
 41 42 
 DẠNG CHUẨN GREIBACH – GNF (TT) 
 Cuối cùng văn phạm cần tìm ở dạng chuẩn GNF là 
 VD 4.11. Cho VPPNC G ({0,1}, {S,A,B},P,S) 
 G = ({a,b},{A1, A2, Z2},P1, A1) Với P = 
 trong đó { S AB 
 P1 = { A BS | 1 
 A a| aA A | bA | aA Z A | bZ A 
 1 1 2 2 1 2 2 2 2 B SA | 0 
 A aA | b| aA Z | bZ
 2 1 1 2 2 } 
 Z aA A | bA | aA Z A | bZ A
 2 1 1 1 1 2 1 2 1 Tìm VPPNC ở dạng chuẩn GNF? 
 Z2 aA1A1Z2| bA1Z2| aA1Z2A1Z2 | bZ2A1Z2 
 } 
 43 44 
 11