Bài giảng Lí thuyết Ngôn ngữ hình thức và ôtômat: Chương 3- Nguyễn Thị Minh Huyền

Bài giảng "Lí thuyết Ngôn ngữ hình thức và ôtômat - Chương 3: Ngôn ngữ phi ngữ cảnh" cung cấp cho người đọc các kiến thức về: Ngôn ngữ ε - tự do, văn phạm dạng chuẩn Chomsky, cây dẫn xuất, điều kiện cần của ngôn ngữ phi ngữ cảnh,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Lí thuyết Ngôn ngữ hình thức và ôtômat: Chương 3- Nguyễn Thị Minh HuyềnLí thuyết Ngôn ngữ hình thức vàÔtômat Giảng viên: Nguyễn Thị Minh Huyền Khoa Toán – Cơ – Tin học Trường ĐH Khoa học Tự nhiên Hà Nội Chương 3 Ngôn ngữ phi ngữ cảnhNgôn ngữ phi ngữ cảnh: Ngôn ngữ ε - tự do Văn phạm dạng chuẩn Chomsky Cây dẫn xuất Điều kiện cần của ngôn ngữ phi ngữ cảnh Tính đóng của ngôn ngữ phi ngữ cảnh Ôtômat đẩy xuống 2 Văn phạm/ngôn ngữ ε - tự do Định nghĩa:  ε – quy tắc, quy tắc rỗng: quy tắc có vế phải là từ rỗng  Văn phạm ε – tự do: Văn phạm phi 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 |  3 Vă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 4 Câ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 =  5 Câ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|. 6 Đ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 = uviwxiy  L Chứng minh: Ý tưởng:  Chọn l1 = 2|V|  h(T) ≥|V| + 1  l2 = 2|V| 7yĐ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} 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. 12 Ô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ăng vào … (vô hạn) a b b c Bộ nhớ B xếp chồng Bộ ĐK A B A 13Ôtômat đẩy xuống (2)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 (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 đ ...