Tài liệu miễn phí Trang 6649 - Tài liệu tham khảo

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

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    ...

 (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ó ...

=  -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}; + ...

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) ...

- 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 ...

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í ...

 (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 ...

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 ...

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 ...

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‟ ...

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 ...