Ngôn ngữ hình thức - 26
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 ...
Tập Bài Giảng miễn phí, free không cần đăng nhập, download hay tải về Trang 95
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‟ ...
Trang 85, Trang 86, Trang 87, Trang 88, Trang 89, Trang 90, Trang 91, Trang 92, Trang 93, Trang 94,