Lí thuyết Ngôn ngữ hình thức và Ôtômat

hi ngữ cảnh không chứa quy tắc rỗng  Ngôn ngữ ε – tự do L: tồn tại văn phạm ε – tự do sinh ra L  Tính chất:  Mọi văn phạm phi ngữ cảnh G = (, V, , P) đều đưa được về văn phạm phi ngữ cảnh G’ = (, V’, ’, P’) tương đương với nó sao cho nếu G’ chứa quy tắc rỗng thì vế trái của nó phải là tiên đề (’  ε).  Với mọi ngôn ngữ phi ngữ cảnh L, ngôn ngữ L \ {ε} luôn là ngôn ngữ ε – tự do.  VD: S SB | c A aA | B B b |  4Văn phạm dạng chuẩn Chomsky  Định nghĩa:  Văn phạm G = (, V, , P) được gọi là thuộc dạng chuẩn Chomsky nếu mỗi quy tắc của nó có 1 trong 2 dạng sau:  A  BC  A  a với A, B, C  V, a    Mọi văn phạm phi ngữ cảnh ε – tự do đều đưa được về dạng chuẩn Chomsky tương đương với nó  Thuật toán:  Loại bỏ quy tắc dạng A  B  Thay thế tất cả các kí hiệu cơ bản xuất hiện ở vế phải với độ dài >1 bằng một kí hiệu phụ mới  Rút ngắn độ dài vế phải xuống không vượt quá 2  Ví dụ S bA | aB; A a | aS | bAA | B ; B b | bS | aBB 5Cây dẫn xuất (1)  Khái niệm: Với mỗi văn phạm phi ngữ cảnh G = (, V, , P), mỗi quy tắc đều có vế trái là một kí hiệu phụ Mỗi dẫn xuất w = [w0, w1, , wn] với w0 = A  V có thể biểu diễn dưới dạng cây, gọi là cây dẫn xuất Chiều cao của cây T: Số cung trên đường đi dài nhất xuất phát từ đỉnh gốc đến đỉnh ra (lá), kí hiệu h(T) Cây dẫn xuất kết: Cây tương ứng với dẫn xuất [w0, w1, , wn] trong đó wn chỉ chứa các kí hiệu cơ bản Cây dẫn xuất đầy đủ: Cây dẫn xuất kết [w0, w1, , wn] với w0 =  6Cây dẫn xuất (2)  Tính chất: Trong cây dẫn xuất kết trong văn phạm dạng chuẩn Chomsky, các đỉnh không kề với đỉnh ra bao giờ cũng có 2 cung đi ra, các đỉnh kề với đỉnh ra bao giờ cũng có đúng 1 cung đi ra Nếu T là cây dẫn xuất trong văn phạm G mà vế phải các quy tắc đều có độ dài  m thì T có số đỉnh ra  mh(T). G là dạng chuẩn Chomsky thì mỗi cây dẫn xuất kết có số đỉnh ra  2h(T)-1 Nếu văn phạm G có cây dẫn xuất T với h(T) > |V| thì G cũng có cây dẫn xuất T’ với h(T’)  |V|. 7Điều kiện cần của ngôn ngữ phi ngữ cảnh Nếu L là ngôn ngữ phi ngữ cảnh thì luôn tồn tại 2 số nguyên dương l1, l2 sao cho z có |z|  l1 thì z phân tích được thành 5 từ u, x, w, y, v (z = uvwxy) và:  |vwx|  l2  |vx| > 0  i=0, 1, 2, zi = uv iwxiy  L  Chứng minh: Ý tưởng:  Chọn l1 = 2 |V|  h(T) ≥|V| + 1  l2 = 2 |V| y Điều kiện cần  Ứng dụng: Khẳng định một số ngôn ngữ không phải là ngôn ngữ phi ngữ cảnh  {ap | p là số nguyên tố}  {an bn cn |n > 0} 12 Tính đóng của ngôn ngữ phi ngữ cảnh  Lớp ngôn ngữ phi ngữ cảnh đóng với các phép toán hợp, tích ghép, soi gương, lặp, và lặp cắt  Chứng minh: Xây dựng các văn phạm phi ngữ cảnh sinh ngôn ngữ hợp, tích ghép, soi gương, lặp, lặp cắt của các ngôn ngữ phi ngữ cảnh  Lớp ngôn ngữ phi ngữ cảnh không đóng đối với các phép toán giao và lấy phần bù  Chứng minh:  Phép giao: Giao của {at bt cs} và {ap bq cq} không phải là ngôn ngữ phi ngữ cảnh  Phép lấy phần bù: Nếu lớp ngôn ngữ phi ngữ cảnh đóng với phép lấy phần bù thì cũng đóng với phép giao vì L1  L2 = C(C L1  C L2), mâu thuẫn với kết luận ở trên. 13 Ôtômat đẩy xuống (1)  Công cụ nhận biết ngôn ngữ phi ngữ cảnh  Khái niệm: Ôtômat hữu hạn + bộ nhớ “đẩy xuống” (pushdown automata - PDA) Bộ ĐK A B A B cbba Băng vào (vô hạn) Bộ nhớ xếp chồng Băng vào Trạng thái Bộ nhớ xếp chồng aaabbb s0 $ aabbb s0 Z$ abbb s0 ZZ$ bbb s0 ZZZ$ bb s1 ZZ$ b s1 Z$ s1 $ s2 Ôtômat đẩy xuống (2) 15 Ôtômat đẩy xuống (3) Định nghĩa: Ôtômat đẩy xuống không đơn định là bộ bảy M = (S, , V, s0, $, , F) S – tập trạng thái, trong đó s0 – trạng thái khởi đầu, F – tập trạng thái kết của ôtômat  - bảng chữ cái vào (hữu hạn) V – bảng chữ cái ngăn xếp (hữu hạn), trong đó chứa $ – kí hiệu khởi đầu của ngăn xếp Hàm chuyển trạng thái   : S x V x (  {ε})  2SxV*  (s’, )  (s, A, a): máy đang ở trạng thái s, ngăn xếp chứa kí hiệu A ở trên cùng, đọc được kí hiệu a ở băng vào thì chuyển sang trạng thái s’, xoá kí hiệu A khỏi ngăn xếp, thay vào đó xâu  16 Ôtômat đẩy xuống (4) Hình trạng C = (s, )  S x V* Hàm chuyển hình trạng  tM : (S x V*) x (  {ε})  2 SxV* Cho C = (s, A), a {  ε}  (s’, )  (s, A, a)  (s’, )  tM(C, a) Hàm chuyển mở rộng TM : (S x V*) x *  2 SxV*  (s’, ’)  TM((s, ), a1 a2 an) nếu s1=s, s2, , sn  S, 1=, 2, , n  V* : (si+1, i+1)  tM((si, i), ai) (1 i n-1), (s’, ’)  tM((sn, n), an) 17 Ôtômat đẩy xuống (5) Ngôn ngữ sinh/đoán nhận bởi ôtômat đẩy xuống  2 cách định nghĩa:  M chấp nhận từ x khi chuyển đến trạng thái kết L(M) = {x  * | TM((s0, $), x)  F x V*}  M chấp nhận từ x khi ngăn xếp rỗng L(M) = {x  * | TM((s0, $), x)  S x {ε}}  Khẳng định: Nếu M là ôtômat đẩy xuống chấp nhận bằng trạng thái kết thì từ M có thể xây dựng một ôtômát đẩy xuống M’ chấp nhận bằng ngăn xếp rỗng sao cho L(M) = L(M’) và ngược lại 18 Ôtômat đẩy xuống (6)  Cách xây dựng (): Cho M là ôtômát đẩy xuống chấp nhận bằng trạng thái kết. Xây dựng ôtômát đẩy xuống chấp nhận bằng ngăn xếp rỗng M’ tương đương với M (L(M) = L(M’)) M’ = (S’, , V’, s0’, , ’, F’) S’ = S  {s0’, s1’}, V’ = V  {}, F’ = {s1’} (F’ thực ra không cần)  ’ xây dựng dựa trên , bổ sung các quan hệ chuyển sau:  ’(s0’, , ε) = {(s0, $)}  ’(s, A, ε) = {(s1’, ε)} với mọi A  V’, s  F  ’(s1’, A, ε) = {(s1’, ε)} với mọi A  V’ 19 Ôtômat đẩy xuống (7)  Cách xây dựng (): Cho M là ôtômát đẩy xuống chấp nhận bằng ngăn xếp rỗng. Xây dựng ôtômát đẩy xuống chấp nhận bằng trạng thái kết M’ tương đương với M (L(M) = L(M’)) M’ = (S’, , V’, s0’, , ’, {sf}) S’ = S  {s0’sf}, V’ = V  {}  ’ xây dựng dựa trên , bổ sung các quan hệ chuyển sau:  ’(s0’, , ε) = {(s0, $)}  ’(s, , ε) = {(sf , ε)} với mỗi s  S 20 Ôtômat đẩy xuống (8)  Lớp ngôn ngữ sinh bởi văn phạm phi ngữ cảnh tương đương với lớp ngôn ngữ sinh bởi ôtômat đẩy xuống  () Cho văn phạm, xây dựng ôtômat đẩy xuống tương đương: G = (, V, , P) M = ({s0, s1, s2}, ,   V  $, s0, $, , {s2})  (s0, $, ε) = {(s1, $)}  (s1, A, ε) = {(s1, ) | A    P} với mọi A  V  (s1, a, a) = {(s1, ε) } với mọi a    (s1, $, ε) = {(s2, ε)} 21 Ôtômat đẩy xuống (8)  () Cho ôtômat đẩy xuống M chấp nhận bằng ngăn xếp rỗng, XD văn phạm phi ngữ cảnh tương đương M = (S, , V, s0, , , F) (có thể bỏ F) Xây dựng văn phạm phi ngữ cảnh G = (, VG, , P) trong đó Bảng chữ cái phụ VG chứa kí hiệu phụ đặc biệt  là tiên đề và tập các kí hiệu phụ t.ứ. với các bộ [pAq] trong đó p, q  S, A  V Tập quy tắc P gồm các quy tắc sau:    [s0 p]  p  S  Giả sử (r0, B1Bk)  (q, A, a) với a   {ε}, k ≥ 0, khi đó  dãy trạng thái r1 , , rk thêm quy tắc [qArk]  a [r0B1r1] [rk-1Bkrk] Tổng kết  Giới thiệu các khái niệm cơ bản về ngôn ngữ hình thức và văn phạm hình thức  Lớp ngôn ngữ chính quy (ôtômát, biểu thức chính quy, tính chất đóng, điều kiện cần, điều kiện cần và đủ)  Lớp ngôn ngữ phi ngữ cảnh (ôtômát đẩy xuống, tính chất đóng, điều kiện cần)