Lý thuyết tính toán - Chương 3: Văn phạm và ôtômat đẩy xuống

DSĐX là  R/W Head 52/77 Định nghĩa hình thức ôđx  Một NSA là một bộ 7 : M  Q, , , , Z, q0, A, trong đó :  Q là tập hợp hữu hạn các trạng thái   là bảng chữ vào hữu hạn Input Alphabet   là bộ chữ đẩy xuống hữu hạn Stack Alphabet  Z   là ký tự đầu của DSĐX Initial Stack Symbol  q0  Q là trạng thái đầu  F  Q là tập các trạng thái cuối    ((Q  *  *)  (Q  *)) là quan hệ chuyển tiếp gồm một tập hợp hữu hạn các quan hệ ((p, u, ), (q, )) p, q  Q ; u  * ; ,   * Có thể viết gọn quan hệ thành puq 53/77 Mô tả  Bộ chữ đẩy xuống  của ôđx :  Chứa tập hợp các ký tự sẽ được đưa vào trong DSĐX  Không nhất thiết phân biệt  với  (có thể   )  Ký tự Z là ký tự đầu hay nội dung ban đầu của DSĐX  Các chuyển tiếp ((p, u, ), (q, )) trong  :  Tương tự một ôhh không đđ  Có thêm hoạt động chuyển tiếp của DSĐX :  Câu vào bắt đầu bởi tiền tố u : w = uw’  Ôtômat chuyển từ trạng thái p sang trạng thái q  Phần câu  đang nằm trên đỉnh của DSĐX  Đầu đọc đọc xong tiền tố u của câu vào  Thay thế  trên đỉnh DSĐX bởi câu phần  54/77 Các khái niệm  Người ta cũng định nghĩa một cách hình thức tương tự các ôhh, nhưng có mặt của DSĐX các khái niệm :  Cấu hình  Chuyển tiếp một bước  Chuyển tiếp nhiều bước  Ôđx đoán nhận câu vào  NN được thừa nhận bởi ôđx 10 55/77 Ôđx thừa nhận câu vào  Cho ôđx MQ, , , , Z, q0, F và một câu vào w*  Ôđx thừa nhận câu w nếu quá trình đoán nhận đạt đến một trong các trạng thái kết thúc :  Phần câu xử lí còn lại rỗng  (q0, w, Z) ├*M  p, ,   với p  F  Do ôđx M không đơn định, nên có thể có nhiều phép đoán nhận khác nhau trên cùng một câu vào 56/77 Biểu diễn ôtômat đẩy xuống  Cho ôtômat M  Q, , , , Z, q0, F  Có thể biểu diễn M tương tự các ôhh như sau :  Bằng cách liệt kê hết các thành phần của M  Dùng đồ thị  Thực tế, người ta thường dùng cách biểu diễn đồ thị khi số trạng thái của ôtômat không quá lớn 57/77 Dùng đồ thị biểu diễn ôđx  Cho ôđx M  Q, , , , Z, q0, F quy ước vẽ M như sau : q > p q u, | p p là trạng thái đầu, p = q0 (p, u, , q,    q là trạng thái cuối, q  F 58/77 Ví dụ 1 : ôđx đơn định  Ngôn ngữ { anbn | n  0 } được thừa nhận bởi ôđx M1 : Q  { s, p, q }   { a, b }   { A }, F  { q }  gồm các chuyển tiếp : s, a,    s, A s, b, A   p,  s, , Z   q,  p, b, A  p,  p, , Z  q,  p b, A| q> s a, |A b, A| , Z| , Z| Vừa đọc vừa ghi nhớ A vào DSĐX n con a đã đọc i Đọc từng con b và xoá đỉnh DSĐX là con A t ỉ l Xử lý câu rỗng   anbn l r 59/77 Ôđx M1 đoán nhận câu anbn  Cho câu vào a3b3, ôđx M1 thực hiện đoán nhận như sau : saaabbbZ ├M1 saabbbAZ ├M1 sabbbAAZ ├M1 sbbbAAAZ ghi nhớ a ├M1 pbbAAZ ├M1 pbAZ ├M1 pZ kiểm tra b q thừa nhận  Như vậy M1 thừa nhận các câu anbn, n0, ta viết L(M1) = anbn p b, A| q> s a, |A b, A| , Z| , Z| 60/77 Cách vẽ khác của ôđx M1 Có thể vẽ ôđx M1 theo cách khác như sau : p b, A| q> s a, Z|AZ b, A| , Z| , Z| a, A|AAZ 11 61/77 Ví dụ 2 : ôđx không đơn định  Ngôn ngữ {wwR} được thừa nhận bởi M2 như sau : Q  { s, p, q}   { a, b }   { A, B } F  { q }  chứa các chuyển tiếp : s, a,   s, A s, ,   p,  p, b, B  p,  s, b,   s, B p, a, A  p,  p, , z  q,  Vừa đọc vừa ghi nhớ A, B vào DSĐX các con a, b đã đọc i , , Đọc từng con a, b và xoá đỉnh DSĐX là con A, B t , ỉ l , p , | q> s a, |A a, A| , Z| , Z|Xử lý câu rỗng   wwR l r b, |B b, B| 62/77 Ôđx M2 thừa nhận câu abba  Cho câu vào abba, ôđx M2 thực hiện đoán nhận như sau : sabbaZ ├M1 sbbaAZ ├M2 sbaBAZ ghi nhớ a, b đã đọc ├M2 pbaBAZ chuyển dịch không đơn định ├M2 paAZ ├M2 pZ kiểm tra a, b để xoá A, B trên DSĐX q thừa nhận câu abba (thành công) p , | q> s a, |A a, A| , Z| , Z| Chuyển dịch không đơn định ị ị b, |A b, B| 63/77 Ôđx M2 đoán nhận câu abba thất bại  Vẫn câu vào abba, ôđx M2 thực hiện đoán nhận như sau : sabbaZ ├M1 sbbaAZ ├M2 sbaBAZ ghi nhớ a, b đã đọc ├M2 saBBAZ ├M2 sABBAZ hóc : không thể đọc tiếp a hay b ! ├M2 pABBAZ ??? cũng vẫn hóc : không thể đọc tiếp ôtômat không thừa nhận câu abba ! p , | q> s a, |A a, A| , Z| , Z| Chuyển dịch không đơn định ị ị b, |B b, B| 64/77 Ví dụ ôđx kđđ hai trạng thái  Có thể xây dựng ôđx M3 gồm chỉ hai trạng thái M3 thừa nhận ngôn ngữ wwR với DSĐX rỗng : Q  { s, p }   { a, b }   { A, B } F  { p }  gồm các chuyển tiếp : s, a,   s, A  s, ,   p,  p, b, B  p,  s, b,   s, B p, a, A  p,  p, , Z  p,  , | a, |A a, A| b, |B b, B| , Z| , Z| p> s 65/77 Văn phạm phi ngữ cảnh  Theo phân cấp VP của Chomsky, VP phi ngữ cảnh (PNC) : G   N, , R, S  gồm các sản xuất dạng A   với A  N,   (N)* = V*, không có hạn chế gì trên   Từ G, có thể định nghĩa NN PNC : L = L(G)  Một NN L là PNC nếu tồn tại một VP PNC sản sinh ra L 66/77 Ví dụ các VP2  Dưới đây làmột số VP PNC :  G1 { S  aSb |  } L(G1) = anbn, n0  G2 { S  aSa | bSb |  } L(G1) = wwR  G3 { S  aB | bA |  A  bAA | aS B  bS | aBB } L(G3) gồm các câu chứa cùng số chữ a và chữ b trong một thứ tự nào đó  G4 { S  aAS | a A  SbA | SS | ba } L(G4) = ? 12 67/77 Quan hệ giữa VP2 và ôđx  Các ngôn ngữ thừa nhận bởi các ôtômat đẩy xuống có thể được sinh bởi các văn phạm PNC và ngược lại  Định lý : Một ngôn ngữ là PNC nễu ngôn ngữ đó được thừa nhận bởi một ôtômat đẩy xuống L = L(M) = L(G) với G là VP2 và M là ôđx 68/77 Tính chất của các ngôn ngữ PNC  Cho L1 và L2 là hai NN PNC, ta có các tính chất sau :  Các ngôn ngữ sau là phi ngữ cảnh :  L1  L2 phép hợp của hai NN PNC  L1 . L2 phép ghép tiếp hai NN PNC  L1* lấy bao đóng của một NN PNC  Ngôn ngữ :  L1  L2 phép giao của hai NN PNC không hẳn là phi ngữ cảnh !  Tuy nhiên ngôn ngữ :  LR  L2 là PNC với LR là NNCQ và L2 là PNC 69/77 Vấn đề tạo sinh câu của VP PNC  Cho VP PNC G  (N, , R, S) có L = L(G)  Khi áp dụng các sản xuất để tạo sinh câu, thứ tự áp dụng là không quan trọng :  Xuất phát từ ký tự đầu S, có thể áp dụng tuỳ ý các sản xuất, hay dùng các dẫn xuất khác nhau trong G đều có thể tạo ra cùng một câu  Tính “phi ngữ cảnh” thể hiện ở chỗ : một ký tự không kết thúc AN có thể đựơc thay thế độc lập với các ký tự bao xung quanh (trước A và sau A), không phụ thuộc vào “ngữ cảnh”  Tính không quan trọng về thứ tự khi áp dụng các sản xuất là đặc trưng của các NN PNC 70/77 Ví dụ có nhiều cách suy dẫn  Cho văn phạm G : G { S  SS 1 | aSa 2 | bSb 3 |  4 } (đánh số các sản xuất)  Với câu w=aabaab, có thể có 10 cách suy dẫn khác nhau để sinh ra w : Cách 1 (dãy các SX là 124324) : S 1 SS 2 aSaS 4 aaS 3 aabSb 2 aabaSab 4 aabaab Cách 2 (dãy các SX là 132424) : S 1 SS 3 SbSb 2 SbaSab 4 Sbaab 2 aSabaab 4 aabaab V.v...  Sự khác nhau của các cách suy dẫn ra w là thứ tự áp dụng các sản xuất của G 71/77 Ví dụ hiện tượng nhập nhằng  Trong NN tự nhiên nói chung, tiếng Việt nói riêng, thường xuyên xảy ra các hiện tượng nhập nhằng  Nhập nhằng về từ loại :  Học sinh học sinh học  Nhập nhằng về nghĩa :  Ông già đi nhanh quá  Nhập nhằng về phát âm :  Bà Ba bốn bận bán bánh  Nhập nhằng về tiếng Việt không dấu :  Nha may Co khi Gia Lam 72/77 Văn phạm nhập nhằng  Cho VP PNC G :  VP G đgl nhập nhằng (Ambiguous Grammar) khĩ Có hai cây phân tích cùng suy dẫn cho một câu wL(G)  Cho L là NN PNC :  NN L đgl nhập nhằng cố hữu (Inherently Ambiguous Language) khĩ NN L được sinh bởi nhiều VP khác nhau L = L(G1) = L(G2) = ... và tất cả các văn phạm G1, G2 ... này đều nhập nhằng  Cho VP PNC G nhập nhằng :  Có thể biến đổi G về G’ tương đương, L(G’) = L(G), sao cho  G không còn là văn phạm nhập nhằng 13 73/77 Ví dụ văn phạm nhập nhằng  Cho VP PNC G có các SX : { E  E+E 1 | E*E 2 | a 3 }  VP G nhập nhằng vì có hai cây PT sinh ra câu w=a+a*a :  E 1 E+E 3 a+E 2 a+E*E 3 a+a*E 3 a+a*a  E 2 E*E 1 E+E*E 3 a+E*E 3 a+a*E 3 a+a*a E E E a*a a+ 1 3 2 E E E3 3 E E E a + aa * 1 2 E E3 3 3 E 74/77 Một số ví dụ khác về VP nhập nhằng  Các VP sau đây đều :  G1 { S  aSa | bSb | a | b |  }  G2 { S  aS | Sa | a }  Bài tập : Cho ví dụ minh họa tính nhập nhằng của G1 và G2 ? i í i í 75/77 Bài tập chương 4 1. Mô tả các ôhh đẩy xuống thừa nhận các NN sau đây : a) anbncm b) anbmcn 2. Tìm văn phạm PNC sản sinh các ngôn ngữ sau đây : a) anbncm b) anbmcn 3. Chứng minh rằng NN { aibjck | i  j hoặc i  k } là PNC Phần bù của ngôn ngữ này cũng là PNC ? Gợi ý : hội của các ngôn ngữ PNC cũng là PNC 4. Chứng minh rằng NN { an | n là số nguyên tố } không là PNC 76/77 Hướng dẫn 1  Mô tả các ôhh đẩy xuống thừa nhận NN L = anbncm  Vẽ Ođx thừa nhận anbn (đã biết cách vẽ)  Vẽ tiếp Ođx chỉ đọc cm (không cần ghi nhớ vào DSĐX) 77/77 Hướng dẫn 2 Tìm văn phạm PNC sản sinh ngôn ngữ anbncm Ý tưởng : vận dụng VP G’ mà L(G’) = anbn sau đó thêm cm  Xây dựng G’ { S  aSb |  } có L(G’) = anbn  Thêm cm để nhận được G như sau : G { S  AB A  aAb |  B  cB | }  Quả thật, L(G) = anbncm