Ngôn ngữ hình thức - 16
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 ...
Tập Bài Giảng miễn phí, free không cần đăng nhập, download hay tải về Trang 96
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 ...
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à ...
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 ...
- : (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) ...
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 = ...
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 ...
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.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 ...
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.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 ...
Trang 64, Trang 65, Trang 66, Trang 67, Trang 68, Trang 69, Trang 70, Trang 71, Trang 72, Trang 73,