Ngôn ngữ hình thức

Mục Lục Lời Nói Đầu 4 Chương 1. Tổng Quan Về Ngôn Ngữ Và Automat 6 1.1. Các Khái Niệm Cơ Bản 6 1.1.1. Khái Niệm Ngôn Ngữ Hình Thức 6 1.1.2. Bảng Chữ Cái (Alphabet) 8 1.1.3. Xâu Trên Bảng Chữ Cái 8 1.1.4. Các Phép Toán Trên Xâu 9 1.1.5. Ngôn ...

Xâu x   được gọi là xâu con của xâu w nếu x được tạo từ các ký tự nằm liền kề nhau trong xâu w. Tiền tố của xâu w là một xâu con bất kỳ nằm ở đầu xâu w. Hậu tố của xâu w là một xâu con bất kỳ nằm ở cuối xâu w. Ví ...

1.3.2. Văn phạm và ngôn ngữ loại 1 Văn phạm G được gọi là văn phạm loại 1 nếu các quy tắc sinh của nó có dạng:    , với điều kiện   (N  T) + và      Văn phạm loại 1 còn được gọi là văn phạm ...

Câu hỏi và bài tập chương 1 CÂU HỎI VÀ BÀI TẬP CHƯƠNG 1 1.1. Nêu khái niệm ngôn ngữ hình thức, công cụ và lĩnh vực nghiên cứu của nó. 1.2. Nêu các khái niệm: bảng chữ cái, xâu trên bảng chữ cái, tiền tố, hậu tố; cho ví dụ. 1.3. ...

- Q =  q 0 , q 1 , q 2 , q 3  ; - F =  q 0  ; -  :  (q 0 , 0) = q 2 ;  (q 0 , 1) = q 1 ;  (q 1 , 0) = q 3 ;  (q 1 , 1) = q 0 ;  (q 2 , 0) = q 0 ;  (q 2 , 1) = q 3 ;  (q 3 , 0) = q 1 ;  (q 3 , 1) = q 2 (Hàm chuyển thuộc dạng 1). 2) Cho automat hữu ...

Bước q c khởi tạo 0 b 1 0 b 2 0 a 3 1 a 4 1 a 5 1 b 6 2 b 7 3 $ Bảng 2.4. Quá trình Automat đoán nhận xâu Ta có q = 3  F. Vậy automat trên đoán nhận được từ w = bbaaabb. - w = bbaaaaab$ Ta trình bày giải thuật sử dụng automat đơn định đoán nhận w ...

2.1.4. Sự tương đương giữa DFA và NFA Mỗi DFA là một NFA đặc biệt, nên rò ràng lớp ngôn ngữ được đoán nhận bởi NFA cũng bao gồm các tập chính quy (đây chính là ngôn ngữ được đoán nhận bởi DFA ). Tuy nhiên, không có cơ sở để nói ...

Chuyển dịch (đường đi) từ trạng thái bắt đầu đến một trạng thái kết thúc khi nhận được xâu vào là w. Chẳng hạn, xâu 002 được đoán nhận bởi NFA trên bởi vì có đường đi q , q , q , q , q với các cung có nhãn tương ứng 0, 0, ε, ...

2.2.1. Định nghĩa Cho Σ là một bộ chữ cái. Biểu thức chính quy trên Σ và các tập hợp mà chúng mô tả được định nghĩa một cách đệ quy như sau: 1. ∅ là biểu thức chính quy ký hiệu cho tập rỗng 2. ε là biểu thức chính quy ký hiệu ...

Chứng minh của Định lý trên cũng chính là cơ sở của giải thuật chuyển một biểu thức chính quy r thành automat hữu hạn NFAε. Một điểm cần lưu ý là thứ tự ưu tiên của các phép toán được sử dụng trong biểu thức chính quy, điều ...

2) Nếu a thuộc T và α thuộc (N  T) * =V, thì δ([aα], a) = {[α]} Sau đó, có thể dễ dàng chứng minh quy nạp theo độ dài của dẫn xuất rằng δ([S], w) chứa [α] khi và chỉ khi có chuỗi dẫn xuất S *  xA  xyα với A → yα là một luật sinh ...

M 2 = <Q 2 ,  2 ,  2 , q 2 , F 2 > đoán nhận ngôn ngữ L 2 = T(M 2 ); Ta cần chứng minh L 1 L 2 =  uv  u  L 1 ; v  L 2 ) là ngôn ngữ loại 3. Không giảm tổng quát, ta giả sử Q 1  Q 2 =  và  1 =  2 =  . Ta xây dựng Automat M = ...

-  :  (A, a) = {A, B};  (A, b) = {B};  (B, a) = {D, E};  (B, b) ={C, E};  (C, a) = {D, E} ;  (C, b) = {D};  (D, a) = {C};  (D, b) = {E};  (E, a) = {E}. 1) Hãy biểu diễn M dưới dạng: - Bảng; - Đồ thị. 2) Automat M thuộc dạng nào, vì sao?. 3) ...

2.35. Cho NFA  được biểu diễn dưới dạng đồ thị như sau: Start A 1 B 0 C 1 D   1 1  1) Xây dựng văn phạm tuyến tính phải tương đương với NFA  trên. 2) Xây dựng văn phạm tuyến tính trái tương đương với NFA  trên. 3) Tìm biểu ...

Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn được gọi là A-cây con (hoặc A-cây). Cây con cũng giống như cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký tự bắt đầu S. b) Xét văn phạm và ...

Nếu G = (N, T, P, S) là CFG thì ta có thể tìm được CFG G‟ = (N‟, T‟, P‟, S) tương đương sao cho mỗi X  N‟  T‟ tồn tại α, β  (N‟  T‟) * để S *  αXβ. Chứng minh: Tập N‟  T‟ gồm các ký tự xuất hiện trong dạng câu ...

Các ký tự thay thế phải ở cùng một vị trí. Do vậy, tại vị trí này α j  G α j+1 bằng một luật sinh nào đó thuộc P‟- P hay có nghĩa là một luật sinh không thuộc văn phạm G. Điều này sinh ra mâu thuẫn. Vậy L(G) = L(G‟). Ta còn có G‟ ...

For Mỗi luật sinh dạng A → A α do k k begin Thêm các luật sinh B → α và B → αB k ; k k Loại bỏ luật sinh A → A α k k end; for Mỗi luật sinh A → β trong đó β không bắt đầu bằng A do k k Thêm luật sinh A → βB k k end; End; Bằng cách lặp lại ...

3.5. Automat đẩy xuống (Push down Automata) Như đã biết, ngôn ngữ chính quy được sinh từ văn phạm chính quy, đồng thời cũng được đoán nhận bởi các automat hữu hạn (đơn định hoặc không đơn định). Trong phần này sẽ biết thêm một ...

 (q 0 , a, X ) = {(q 0 , XX)};  (q 0 , b, X) = {(q 1 ,  )};  (q 1 , b, X ) = {(q 1 ,  )};  (q 1 ,  , X) = {(q 1 ,  )}. Automat pushdown đơn định đoán nhận được ngôn ngữ L = { ab, a m b m-1 | m  1 } bằng xét rỗng stack Thật vậy: Với w  L  w ...

CÂU HỎI VÀ BÀI TẬP CHƯƠNG 3 3.1. Nêu định nghĩa văn phạm phi ngữ cảnh (CFG); cho ví dụ. 3.2. Nêu các khái niệm: dẫn xuất, ngôn ngữ sinh bởi CFG; cho ví dụ. 3.3. Nêu định nghĩa cây dẫn xuất; phương pháp xây dựng cây dẫn xuất; cho ví ...

- G không là văn phạm loại 1 vì luật sinh C   vi phạm điều kiện của văn phạm loại 1. Vậy G là văn phạm loại 0 (văn phạm ngữ cấu). 1b) G = (N, T, P, S); trong đó: N = {S, A, B, C, D} ; T = {a, b}; P ={S  ABC; AB  aADb; Dab  bDb; DbC  BaC; aB ...

2.17. 1) Biểu diễn M a) Dạng bảng: - q 0 = 0 ; - F =  3  ; -  : Q  a b c 0 1 1 1 1 1 2 2 3 4 3 4 4 2 4 3 b) Dạng đồ thị: a a Start 0 b 1 b c a b 2 b 4 c 3 a a 2) Automat M là Automat hữu hạn đơn định; vì  q  Q và  a   , ta có:   (q, a) ...

=  -CLOSURE({A, B, D, E}) = {A, B, D, E}; -  * (E, aaabbaaaa). Áp dụng công thức δ * (q, wa) = ε-CLOSURE(δ(δ * (q, w), a)), ta có: +  -CLOSURE(E) = δ * (E, ε) = {E, A, B}; +  -CLOSURE(δ({E, A, B}, a)) = {A, B, D, E}; +  -CLOSURE(δ({A, B, D, E}, a)) = {A, B, D, E}; + ...

 (1, a) = {1, 2};  (3,  ) = {4};  (4, b) = {4}; 2) Biểu diễn M dưới dạng bảng M = <Q,  ,  , q 0 , F> trong đó: - q 0 = 0 ; - F =  2, 4  ; -  : Q  a b  0 {3} {0} {1} 1 {1, 2} 2 3 {4} 4 {4} 3) Automat M thuộc dạng NFA  vì  3  Q, ta có ...

A) - Xây dựng NFA tương đương với NFA  NFA  M = <Q,  ,  , q 0 , F>: + Q = {A, B, C}; +  = {0, 1}; + q 0 = A ; + F = {B, C}; +  :         C       C    ...

- q 0 = 0 ; - F = {2, 4}; -  :  a     b    3        1  a     b    2   a    2   b    3, 4  b) ...

4) Viết biểu thức chính quy biểu diễn cho L(G). Từ đồ thị của M, sử dụng giải thuật heuritic suy ra: r = 0 * (   (1  0(10) * 0(00) * )1 * (0  1) 2.38. 1) G = (N, T, P, S): - N= {S, A, B, C}; - T = {a, b, c}; - P = {S → aA | bB| aC | b| c; A → aA | b; B ...

2) Văn phạm không nhập nhằng tương đương. S → S + T | S - T | S * T | S / T | T ; T → ( S ) | a . 3.30. 1) S → A | aSb | a; A → AB; B → b a) Loại bỏ biến không sinh ra xâu các ký tự kết thúc Áp dụng giải thuật loại bỏ biến không sinh ra xâu ký ...

A → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b; B → bCA | bA | bC | b | a | ABc | Bc | Ac | c | b; C → ABc | Bc | Ac | c | b. 3.37. 1) S → bA | aB; A → bAA | aS | a; B → aBB | bS | b. 1. Văn phạm không có luật sinh đơn vị 2. Thay thế các luật sinh có độ dài vế ...

PDA tương đương M = <Q, Σ, Γ, δ, q , Z ,  >: 0 0 - Q = {q}; - Σ = {+, * , a}; - Γ = {S}; - q = q; 0 - Z = S; 0 - δ: 1. δ (q, +, S) = (q, SS) vì S → +SS; 2. δ (q, * , S) = (q, SS) vì S → * SS; 3. δ (q, a, S) = (q,  ) vì S → a. 2) S → aS | bS | aA; A → bB| b; B ...