Văn Phạm Chính Quy Và Automat Hữu Hạn

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. Nêu các phép toán trên xâu; cho ví dụ.

1.4. Nêu các khái niệm: *, +, ngôn ngữ; cho ví dụ.

1.5. Nêu các phép toán trên ngôn ngữ; cho ví dụ.

1.6. Nêu định nghĩa văn phạm; cho ví dụ.

1.7. Nêu khái niệm ngôn ngữ sinh bởi văn phạm; cho ví dụ.

1.8. Nêu cách phân loại và các loại văn phạm và ngôn ngữ; cho ví dụ.

1.9. Nêu khái niệm văn phạm tương đương; cho ví dụ.

1.10. Nêu các tính chất của ngôn ngữ.

1.11. Mô tả automat, cách phân loại và các loại automat.

1.12. Nêu các phương pháp biểu diễn ngôn ngữ; cho ví dụ.

1.13. Cho bảng chữ cái T = {0 ,1}. Ta ký hiệu T* là tập tất cả các xâu (kể cả xâu rỗng ).

1) Hãy biểu diễn T* dưới dạng liệt kê theo thứ tự độ dài tăng dần và trong các xâu có cùng độ dài thì theo thứ tự từ điển.

2) Chỉ ra một số ngôn ngữ trên bảng chữ cái T.

1.14. Cho bảng chữ cái T = {0 ,1}. L1 và L2 là hai ngôn ngữ trên bảng chữ cái T; với:

L1 = {0, 1};

L2 = {, 0, 1, 00, 11, 000, 001, 010, 011, 100}.

Hãy tính:

1) L1  L2

2) L1  L2

3) L1 - L2

4) L2 - L1

5) L1L2

1.15. Cho bảng chữ cái  = {a , b}. L là một ngôn ngữ trên bảng chữ cái ; với: L

= {, a, b}.

Hãy tính:

1) L

2) L0, L1, L2, L3

1.16. Tìm các biểu diễn hữu hạn cho các ngôn ngữ vô hạn sau:

1) L1 = {, ab, aabb, aaabbb, ...}

2) L2 = {, 0, 1, 00, 01, 000, 001, 011, 111, 0000, 0001, 0011, 0001, 1111, ...}

1.17. Cho các văn phạm sau đây:

1) G = (N, T, P, S) với tập quy tắc sinh là:

P ={S  ABC; AB aADb; Dab  bDb; DbC  BaC; aB Ba; AB ; C }.

2) G = (N, T, P, S) với tập quy tắc sinh là:

P = {S  ABaDF; BD DCB; BC  bB; AD AAE; EC AE; EB BE; EF BBDF; DF  B | }.

3) G = (N, T, P, S) với tập quy tắc sinh là:

P = {S  SS; S aSb; S bSa; S ab; S ba}.

4) G = (N, T, P, S) với tập quy tắc sinh là:

P = {S  aA; S a; A abB  B ; }.

a) Cho biết văn phạm nào là văn phạm chính quy, văn phạm nào là văn phạm phi ngữ cảnh, văn phạm nào là văn phạm ngữ cấu; Tại sao.

b) Viết lại mỗi văn phạm dưới dạng đầy đủ theo định nghĩa của văn phạm.

1.18. Hãy chỉ ra mỗi văn phạm sau đây thuộc loại nào?. Nêu các thành phần của mỗi văn phạm đó.

1) S Sab; Sb; S Aa; A  Sa; A Abbba; A  a; S.

2) S  AB; AB  BA; A  aA; B  Bb; A  a; B  b.

3) S  A; S  AAB; Aa  Aba; A aa; BbAbb; AB ABB; B b.

1.19. Cho văn phạm có tập các luật sinh: S Sa; S a; S.

1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên.

2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau:

- w = ;

- w = a;

- w = aa;

- w = ai ; với iN.

3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên.

1.20. Cho văn phạm có tập các luật sinh: S aA; A aA; A aB; B bB; Bb.

1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên.

2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau:

- w = aab;

- w = aaaaabb;

- w = ai bj; với i, jN+; i  2.

3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên.

1.21. Cho văn phạm có tập các luật sinh: S bSa; S.

1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên.

2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau:

- w = ;

- w = ba;

- w = bbbaaa;

- w = bi ai; với iN.

3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên.

1.22. Cho văn phạm có tập các luật sinh: S aAb; S; A aAb; A.

1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên.

2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau:

- w = ;

- w = ab;

- w = aaaabbbb;

- w = ai bi; với iN.

3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên.

1.23. Cho văn phạm có tập các luật sinh: S AB; A aA; A a; B aB; Bb.

1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên.

2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau:

- w = aab;

- w = aaaaabb;

- w = ai b; với iN+.

3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên.

1.24. Chỉ ra văn phạm G có tập T = a, b sao cho xâu L(G) có một trong các tính chất sau:

1) Bắt đầu bằng kí tự a.

2) Kết thúc bằng hai kí tự ab.

3) Kết thúc bằng hai kí tự ba.

4) Không kết thúc bằng ab.

1.25. Cho ngôn ngữ: L = {0i 1 | iN+ }

1) Chỉ ra văn phạm tuyến tính trái sinh ra ngôn ngữ trên.

2) Chỉ ra văn phạm tuyến tính phải sinh ra ngôn ngữ trên.

3) Chỉ ra văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên.

1.26. Cho ngôn ngữ: L = {03 1i| iN+ }

1) Chỉ ra văn phạm tuyến tính trái sinh ra ngôn ngữ trên.

2) Chỉ ra văn phạm tuyến tính phải sinh ra ngôn ngữ trên.

3) Chỉ ra văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên.

1.27. Cho ngôn ngữ: L = {0i1i 2j 3j | iN+, jN }. Xây dựng văn phạm phi ngữ cảnh sinh ra ngôn ngữ trên.

1.28. Cho ngôn ngữ L = {an bn cm | nN+, mN}. Hãy chỉ ra văn phạm phi ngữ cảnh G sao cho L(G) = L.

1.29. Cho ngôn ngữ L = {(ab)n cm | n, mN+}. Hãy chỉ ra:

1) Văn phạm tuyến tính phải sinh ra ngôn ngữ trên.

2) Văn phạm tuyến tính trái sinh ra ngôn ngữ trên.

3) Văn phạm phi ngữ cảnh sinh ra ngôn ngữ trên.

1.30. Cho ngôn ngữ: L = {031i 2j | i, jN+}

1) Xây dựng văn phạm tuyến tính trái sinh ra ngôn ngữ trên.

2) Xây dựng văn phạm tuyến tính phải sinh ra ngôn ngữ trên.

3) Xây dựng văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên.

1.31. Cho ngôn ngữ: L = {0i1j 2k | i, j, kN }

1) Xây dựng văn phạm tuyến tính trái sinh ra ngôn ngữ trên.

2) Xây dựng văn phạm tuyến tính phải sinh ra ngôn ngữ trên.

3) Xây dựng văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên.

1.32. Cho ngôn ngữ: L = {0i1j 2k 3m| i, j, k, mN }

1) Xây dựng văn phạm tuyến tính trái sinh ra ngôn ngữ trên.

2) Xây dựng văn phạm tuyến tính phải sinh ra ngôn ngữ trên.

3) Xây dựng văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên.

Chương 2. Ngôn ngữ chính quy và Automat hữu hạn

Chương 2. VĂN PHẠM CHÍNH QUY VÀ AUTOMAT HỮU HẠN

(Regular Grammar -RG and Finite Automata -FA)

Mục tiêu:

Giúp sinh viên có khả năng:

- Trình bày được khái niệm và xác định được các thành phần của một FA và phân loại được FA.

- Biết cách chuyển từ NFA sang NFA và từ NFA sang DFA.

- Viết được biểu thức chính quy ký hiệu cho ngôn ngữ chính quy.

- Hiểu được mối liên hệ giữa FA và biểu thức chính quy và xây dựng được NFA từ một biểu thức chính quy và ngược lại.

- Nhận dạng được lớp ngôn chính quy do văn phạm chính quy (RG) sinh ra.

- Xây dựng được văn phạm chính quy sinh ra ngôn ngữ được đoán nhận FA và ngược lại.

Nội dung chính:

- Automat hữu hạn (FA): định nghĩa, ngôn ngữ đoán nhận bởi FA.

- Automat hữu hạn đơn định (DFA) và Automat hữu hạn không đơn định (NFA) .

- Sự tương đương giữa DFA và NFA.

- Biểu thức chính quy: định nghĩa và tính chất.

- Sự tương đương giưa FA và biểu thức chính quy

- Văn phạm chính quy: văn phạm tuyến tính, sự tương đương giữa văn phạm chính quy và FA

- Tính chất của RL (Regular Languages ).

2.1. Automat hữu hạn (FINITE AUTOMAT - FA)

Automat hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các thông tin vào (input) và các thông tin ra (output). Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn các cấu hình nội bộ gọi là các trạng thái (states). Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liên quan đến những input đã chuyển qua và xác định các phép chuyển tiếp theo trên dãy input tiếp theo.

Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự nhiên của khái niệm và khả năng ứng dụng đa dạng trong nhiều lĩnh vực thực tế. Automat hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA). Cả hai loại automat hữu hạn đều có khả năng nhận dạng chính xác tập chính quy. Automat hữu hạn đơn định có khả năng nhận dạng ngôn ngữ dễ dàng hơn automat hữu hạn không đơn định, nhưng thay vào đó thông thường kích thước của nó lại lớn hơn so với automat hữu hạn không đơn định tương đương.

Automat hữu hạn được coi là một công cụ hữu hiệu để nghiên cứu một lớp các ngôn ngữ quan trọng, đó là ngôn ngữ chính quy. Trước hết, ta đưa ra định nghĩa về Automat hữu hạn.

2.1.1. Định nghĩa Automat hữu hạn

Một cách hình thức ta coi Automat hữu hạn là một hệ thống gồm 5 thành phần, ký hiệu là M = <Q, , , q0, F> trong đó:

Q - Tập hữu hạn khác rỗng các trạng thái.

 - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).

 - Ánh xạ còn gọi là hàm chuyển trạng thái và có một trong hai dạng sau: 1) : Q  Q

(q, a) p 2) : Q  2Q

(q, a) p

q0 - Là trạng thái bắt đầu; q0 Q.

F  tập các trạng thái kết thúc; F  Q .