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

Chia sẻ: Đinh Y | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

40
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

Lí 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| 7
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}
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 đó xâu  15
Ô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 (  {ε})  2SxV*  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 *  2SxV*  (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) 16
Ô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 17
Ô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’ 18
Ô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 19
Ô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, ε)} 20