Giáo trình Ngôn ngữ hình thức

y dùng đặc tả 
cho tập hợp chính quy, do đó chỉ cần cung cấp thêm một cơ chế dịch từ dạng biểu 
thức này sang dạng automat hữu hạn. Một số định lý sau có thể xem là nền tảng cho 
việc chuyển đổi này. 
92 Phạm Hùng Phú 
 Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 
1) Định lý 1 
 Một ngôn ngữ chính quy đƣợc đoán nhận bởi một automat hữu hạn M có n 
trạng thái là: 
 1. Không rỗng nếu và chỉ nếu automat đoán nhận một chuỗi có độ dài < n. 
 2.Vô hạn nếu và chỉ nếu automat đoán nhận một chuỗi có độ dài l với n ≤ l < 2n. 
Chứng minh: 
 1. Phần đảo là hiển nhiên. 
 Ta chứng minh phần thuận: Giả sử M đoán nhận một tập không rỗng. Gọi w 
là chuỗi ngắn nhất đƣợc đoán nhận bởi M. Theo bổ đề bơm, ta có | w | < n vì nếu w 
là chuỗi ngắn nhất và | w | ≥ n thì ta có thể viết w = uvy, và uy là chuỗi ngắn hơn 
trong L hay | uy | < | w | Mâu thuẫn. 
 2. Nếu w L và n ≤ | w | < 2n thì theo bổ đề bơm ta có 
 i 
 w = w w w và w w w L với mọi i ≥ 0, suy ra L(M) vô hạn . 
 1 2 3 1 2 3 
 Ngƣợc lại, nếu L(M) vô hạn thì tồn tại w L(M) sao cho | w | ≥ n. 
 Nếu | w |< 2n thì xem nhƣ đã chứng minh xong. Nếu không có chuỗi nào có 
độ dài nằm giữa n và 2n-1 thì gọi w là chuỗi có độ dài ít nhất là 2n nhƣng ngắn hơn 
mọi chuỗi trong L(M), nghĩa là | w | ≥ 2n. Một lần nữa, cũng theo bổ đề bơm, ta có 
thể biểu diễn w = w w w , trong đó 1 ≤ | w | ≤ n và w w L(M). Ta có hoặc w 
 1 2 3 2 1 3 
không phải là chuỗi ngắn nhất có độ dài ≥ 2n, hoặc là n ≤ | w w | ≤ 2n-1 Mâu 
 1 3 
thuẫn. Vậy có tồn tại chuỗi có độ dài l sao cho n ≤ l < 2n. 
2) Định lý 2 
 Tồn tại giải thuật để xác định hai automat tƣơng đƣơng (đoán nhận cùng một 
ngôn ngữ). 
Chứng minh: 
 Đặt M , M là hai automat đoán nhận L , L . 
 1 2 1 2
 Ta có ( L ∩ L )  ( L ∩ L ) đƣợc đoán nhận bởi automat M nào đó. Dễ thấy 
 1 2 1 2 3 
M đoán nhận một xâu nếu và chỉ nếu L ≠ L . Theo định lý trên, ta thấy có giải 
 3 1 2
thuật để xác định xem liệu L = L hay không. 
 1 2 
Phạm Hùng Phú 93 
 Câu hỏi và bài tập chƣơng 2 
 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 
2.1. Nêu định nghĩa automat hữu hạn; cho ví dụ. 
2.2. Nêu các phƣơng pháp biểu diễn automat hữu hạn; cho ví dụ. 
2.3. - Nêu định nghĩa automat hữu hạn đơn định, cho ví dụ. 
 - Nêu ngôn ngữ đoán nhận bởi automat hữu hạn đơn định; cho ví dụ. 
 - Nêu hàm chuyển trạng thái mở rộng của automat hữu hạn đơn định và ý 
 nghĩa của nó. 
 - Nêu giải thuật mô phỏng sự hoạt động của automat hữu hạn đơn định để 
 đoán nhận một từ. 
2.4. - Nêu định nghĩa automat hữu hạn không đơn định, cho ví dụ. 
 - Nêu ngôn ngữ đoán nhận bởi automat hữu hạn không đơn định; cho ví dụ. 
 - Nêu hàm chuyển trạng thái mở rộng của automat hữu hạn không đơn định 
 và ý nghĩa của nó. 
 - Nêu giải thuật mô phỏng sự hoạt động của automat hữu hạn không đơn 
 định để đoán nhận một từ. 
2.5. Nêu định lý về sự tƣơng đƣơng giữa automat hữu hạn đơn định, automat 
 hữu hạn không đơn định. Phƣơng pháp xây dựng một DFA tƣơng đƣơng 
 với một NFA cho trƣớc; cho ví dụ. 
 2.6. - Nêu định nghĩa automat hữu hạn không đơn định có  -dịch chuyển, cho ví 
 dụ. 
 - Nêu ngôn ngữ đoán nhận bởi automat hữu hạn không đơn định có  -dịch 
 chuyển; cho ví dụ. 
 - Nêu hàm -CLOSURE(q), cho ví dụ. 
 - Nêu hàm chuyển trạng thái mở rộng của automat hữu hạn không đơn định 
 có  -dịch chuyển và ý nghĩa của nó. 
 - Nêu giải thuật mô phỏng sự hoạt động của automat hữu hạn không đơn 
 định có  -dịch chuyển để đoán nhận một từ. 
2.7. - So sánh sự khác nhau của (q,  ) và *(q,  ), cho ví dụ. 
 - So sánh sự khác nhau của (q, a ) và *(q, a ), cho ví dụ. 
94 Phạm Hùng Phú 
 Câu hỏi và bài tập chƣơng 2 
2.8. - So sánh DFA với NFA 
 - So sánh NFA với NFA 
 - Nêu sự tƣơng đƣơng giữa NFA và DFA. 
2.9. Nêu định lý về sự tƣơng đƣơng giữa NFA và NFA. Phƣơng pháp xây dựng 
 một NFA tƣơng đƣơng với một NFA cho trƣớc; cho ví dụ. 
2.10. - Nêu định nghĩa biểu thức chính quy; cho ví dụ. 
 - Nêu các tính chất của biểu thức chính quy. 
2.11. Nêu định lý về sự tƣơng đƣơng giữa biểu thức chính quy và NFA. Xây 
 dựng NFA đoán nhận ngôn ngữ đƣợc ký hiểu bởi biểu thức chính quy. 
2.12. Nêu định lý về sự tƣơng đƣơng giữa ngôn ngữ đƣợc đoán nhận bởi một 
 DFA và ngôn ngữ đƣợc biểu diễn bằng một biểu thức chính quy. Viết biểu 
 thức chính quy biểu diễn cho ngôn ngữ đƣợc đoán nhận bởi DFA. 
2.13. Nêu các khái niệm văn phạm tuyến tính trái, tuyến tính phải; cho ví dụ. Chỉ 
 ra văn phạm tuyến tính trái, tuyến tính phải đƣợc biểu diễn bằng một biểu 
 thức chính quy. 
2.14. Nêu các định lý về sự tƣơng đƣơng giữa văn phạm chính quy và FA. Xây 
 dựng FA biết văn phạm tuyến tính trái hoặc phải và ngƣợc lại. 
2.15. Nêu các tính chất của ngôn ngữ chính quy. 
2.16. Cho Automat hữu hạn: M = trong đó: 
 -q0 = A ;
 -  = a, b; 
 - Q = A, B, C, D, E; 
 - F = C, E; 
 - : 
 (A, a) = A; (A, b) = B; (B, a) = D; (B, b) = E;(C, a) = E; 
 (C, b)= D; (D, a) = C; (D, b) = E; (E, a) = E. 
 1) Biểu diễn M dƣới dạng: 
 - Bảng; 
 - Đồ thị. 
Phạm Hùng Phú 95 
Câu hỏi và bài tập chƣơng 2 
 2) Automat M thuộc dạng nào, vì sao?. 
 3) Tính: - (A, aaabbaaaa); 
 - (B, aaaabbaa); 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = aabaaaaa; 
 - w = aaaababbb. 
2.17. Cho Automat hữu hạn: M = trong đó: 
 -q0 = 0 ;
 -  = a, b, c; 
 - Q = 0, 1, 2, 3, 4; 
 - F = 3; 
 - : 
 (0, a) = 1; (0, b) = 1; (0, c) = 1; (1, a) = 1; (1, b) = 2; 
 (2, a) = 3; (2, b) = 4 ; (3, a) = 4 ; (4, a) = 2; (4, b) = 4; 
 (4, c) = 3. 
 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) Tính: - (1, aaabbaaaabc); 
 - (0, cabaabba); 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = caabaaabca; 
 - w = aaaabbbc. 
2.18. Cho Automat hữu hạn: M = trong đó: 
 -q0 = A ;
 -  = a, b; 
 - Q = A, B, C, D, E; 
 - F = E; 
96 Phạm Hùng Phú 
 Câu hỏi và bài tập chƣơng 2 
 - : 
 (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) Tính: - (A, aaabbaaaa); 
 - (C, abaabba); 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = aabaaaaa; 
 - w = aaaababbb. 
2.19. Cho Automat hữu hạn: M = trong đó: 
 -q0 = 0 ;
 -  = a, b, c; 
 - Q = 0, 1, 2, 3; 
 - F = 3; 
 - : 
 (0, a) = {0,1}; (0, b) = {2}; (0, c) = {2}; (1, a) = {1, 2}; 
 (1, b) = {1, 2, 3};(2, a) = {3}; (2, b) = {2, 3}; (2, c) = {3}; 
 (3, a) = {3}; (3, b) = {2}; (3, c) = {3}. 
 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) Tính: - (1, aaabbaaaabc); 
 - (0, cabaabba); 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = caabaaabca; 
Phạm Hùng Phú 97 
Câu hỏi và bài tập chƣơng 2 
 - w = aaaabbbc. 
2.20. Cho Automat hữu hạn: M = trong đó: 
 -q0 = A ;
 -  = a, b; 
 - Q = A, B, C, D, E; 
 - F = E; 
 - : 
 (A, a) = {A, B}; (A, b) = {B}; (A, ) = {B}; (B, a) = {D, E}; 
 (B, b) ={C, E};(C, a) = {D, E} ; (C, b) = {D}; (D, b) = {D, E}; 
 (E, a) = {E}; (E, ) = {A}. 
 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) Tính: 
 - -CLOSURE(A), -CLOSURE(E); 
 - (A, a) và *(A, a); 
 - (E, a) và *(E, a); 
 - *(E, aaabbaaaa). 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = aabaaaaa; 
 - w = aaaababbb. 
2.21. Cho Automat hữu hạn: M = trong đó: 
 -q0 = q0;
 -  = 0, 1; 
 - Q = q0; q1; q2; q3; 
 - F = q3; 
 - : 
 (q0,0) = {q0; q1}; ( q0, 1) = {q2}; (q0, ) = {q2}; 
98 Phạm Hùng Phú 
 Câu hỏi và bài tập chƣơng 2 
 (q1, 0) = {q2}; ( q1, 1) = {q1; q2; q3};(q2, 0) = {q2}; 
 (q2, 1) = {q3} ; (q2, ) = {q3}; ( q3, ) = {q0}. 
 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) Tính: 
 - -CLOSURE(q0), -CLOSURE(q3); 
 *
 - (q3, 0) và  (q3, 0); 
 *
 -  ( q3, 0101011). 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = 0001100; 
 - w = 1110010. 
2.22. Cho Automat hữu hạn: M = đƣợc biểu diễn dƣới dạng bảng 
 nhƣ sau: 
 -q0 = q0; 
 - F = q3; 
 - : 
 Q  0 1 
 q0 {q1; q2} {q1} 
 q1 {q1; q2; q3} {q3} 
 q2 {q1; q2} {q3} 
 q3 {q1} {q2; q3} 
 1) Nêu đầy đủ các thành phần của M. 
 2) Biểu diễn M dƣới dạng đồ thị. 
 3) Automat M thuộc dạng nào, vì sao?. 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
Phạm Hùng Phú 99 
Câu hỏi và bài tập chƣơng 2 
 - w = 0011111; 
 - w = 0000010. 
2.23. Cho Automat hữu hạn: M = đƣợc biểu diễn dƣới dạng đồ thị 
 nhƣ sau: 
 b a a a 
 Start a b b 
 0 1 2 3 
 b a 
 1) Nêu đầy đủ các thành phần của M. 
 2) Biểu diễn M dƣới dạng bảng. 
 3) Automat M thuộc dạng nào, vì sao?. 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = bbbbbbb; 
 - w = bbbaaab. 
2.24. Cho Automat hữu hạn: M = đƣợc biểu diễn dƣới dạng bảng 
 nhƣ sau: 
 -q0 = q0; 
 - F = q3; 
 - : 
 Q  0 1  
 q0 {q2; q3} {q1} {q2} 
 q1 {q1; q2} 
 q2 {q1; q2} {q2; q3} 
 q3 {q1} {q2; q3} {q0} 
 1) Nêu đầy đủ các thành phần của M. 
 2) Biểu diễn M dƣới dạng đồ thị. 
 3) Automat M thuộc dạng nào, vì sao?. 
100 Phạm Hùng Phú 
 Câu hỏi và bài tập chƣơng 2 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = 0000000; 
 - w = 11100111. 
2.25. Cho Automat hữu hạn: M = đƣợc biểu diễn dƣới dạng đồ thị 
 nhƣ sau: a 
 b a 
 1 2
  
 Start 
 0 
 a 
 3  4 b 
 1) Nêu đầy đủ các thành phần của M. 
 2) Biểu diễn M dƣới dạng bảng. 
 3) Automat M thuộc dạng nào, vì sao?. 
 4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?: 
 - w = bbbbabb; 
 - w = abababa. 
2.26. Cho Automat NFA M: 
 1 0 1 
 0 
 Start 0 
 q1 q2 q3 
 0 
 1) Chuyển M về dạng DFA D tƣơng đƣơng. 
 2) Biểu diễn D dƣới dạng đồ thị. 
2.27. Cho Automat NFA M: 
 1 
 0 0 1 
 Start q q q
 1 2 3 q4 
 0 
 0 
Phạm Hùng Phú 101 
Câu hỏi và bài tập chƣơng 2 
 1) Chuyển M về dạng DFA D tƣơng đƣơng. 
 2) Biểu diễn D dƣới dạng bảng. 
2.28. Cho Automat NFA M. 
  
  
 Start 0 0 1 
 q1 q2 q3 q4 
  
 0 
 1) Hãy chuyển NFA M về dạng NFA M‟ tƣơng đƣơng và biểu diễn M‟ dƣới dạng 
bảng. 
 2) Hãy chuyển NFA M‟ về dạng DFA D tƣơng đƣơng và biểu diễn D dƣới dạng đồ 
thị. 
2.29. Cho Automat NFA M. 
  
 1 
 0 1 
 Start 0 
 q1 q2 q3 q4 
  
  
 0 0 
 1) Hãy chuyển NFA M về dạng NFA M‟ tƣơng đƣơng và biểu diễn M‟ dƣới dạng 
bảng. 
 2) Hãy chuyển NFA M‟ về dạng DFA D tƣơng đƣơng và biểu diễn D dƣới dạng đồ 
thị. 
2.30. Cho các Automat có sơ đồ chuyển trạng thái nhƣ sau: 
 0 1 
 0 
 Start A B Start 1 
 0 A B 
 1 
 1 0 
  
 0 
 C
 C 
 a) b) 
102 Phạm Hùng Phú 
 Câu hỏi và bài tập chƣơng 2 
 1) Cho biết biểu thức chính quy tƣơng ứng với mỗi sơ đồ. 
 2) Các Automat trên thuộc loại nào. 
 3) Xây dựng DFA tƣơng ứng với mỗi sơ đồ. 
2.31. Cho Σ = {0, 1, 2, 3}. Viết biểu thức chính quy của các ngôn ngữ trên Σ sau: 
 1) Tập hợp các xâu: Mở đầu bằng một ký tự 0, tiếp theo là một ký tự 1 hoặc 2, 
 cuối cùng là dãy một hoặc nhiều ký tự 3. 
 2) Tập hợp các xâu: Mở đầu bằng một dãy ký tự 3, tiếp theo là dãy các ký tự 0 
 hoặc 1 hoặc 2. 
 3) Tập hợp các xâu: Mở đầu là dãy các ký tự 0 hoặc 1, kết thúc là dãy các ký 
tự 2 hoặc 3. 
2.32. Cho các biểu thức chính quy: 
 a) 0(0 + 1)* 0+ 
 *
 b) ((0+ 1) 0(0 + 1))+ 
 c) (1+ 0)00 (0* + 1+) 
 *
 d) (a + ba + aab) (ε + a)+ 
 1) Mô tả (bằng lời) ngôn ngữ đƣợc biểu diễn bằng mỗi biểu thức trên. 
 2) Xây dựng NFAε tƣơng đƣơng với mỗi biểu thức trên. 
2.33. Cho các FA đƣợc biểu diễn dƣới dạng đồ thị nhƣ sau: 
 1) 
 b a 
 M1 
 Start a b b 
 0 1 2 3 
  
 a 
 b a 
 2) M2 
 a a 
  1 2 
 Start b 
 0 
  
 b 
 3 4 
 b 
Phạm Hùng Phú 103 
Câu hỏi và bài tập chƣơng 2 
 a) Xác định các thành phần của mỗi FA trên. 
 b) Hãy biểu diễn mỗi FA trên dƣới dạng bảng. 
 c) Xây dựng văn phạm tuyến tính phải tƣơng đƣơng với mỗi FA trên. 
 d) Xây dựng văn phạm tuyến tính trái tƣơng đƣơng với mỗi FA trên. 
 e) Tìm biểu thức chính quy tƣơng đƣơng với mỗi FA. 
2.34. Cho các NFA đƣợc biểu diễn dƣới dạng bảng nhƣ sau: 
 a) - : 
 Q  a b  
 0 {0, 1} {1} 
 1 {2} {2} 
 2 {2, 3} 
 3 {3} {3} {0} 
 - q0 = 0; 
 - F = {3}. 
 b) - : 
 Q  a b  
 0 {1, 3} {1} {1} 
 1 {2} {1, 2} 
 2 {3} {3} 
 3 
 - q0 = 0; 
 - F = { 3}. 
 1) Xây dựng văn phạm tuyến tính phải tƣơng đƣơng với mỗi FA trên. 
 2) Xây dựng văn phạm tuyến tính trái tƣơng đƣơng với mỗi FA trên. 
 3) Tìm biểu thức chính quy tƣơng đƣơng với mỗi NFA trên. 
104 Phạm Hùng Phú 
 Câu hỏi và bài tập chƣơng 2 
2.35. Cho NFA đƣợc biểu diễn dƣới dạng đồ thị nhƣ sau: 
 1 1  
 Start 1 0 1 
 A B C D 
  
  
 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 thức chính quy tƣơng đƣơng với NFA trên. 
2.36. Cho các biểu thức chính quy: 
 a) 0 (1 + 2) 3* 
 b) 0 (1+ 2 + 3)+ 
 c) (0 + 1)* + (23)+
 1) Xây dựng các NFA đoán nhận các ngôn ngữ đƣợc biểu diễn bởi mỗi biểu 
thức trên. 
 2) Xây dựng văn phạm chính quy cho các ngôn ngữ đƣợc biểu diễn bởi mỗi 
biểu thức trên. 
2.37. Cho văn phạm tuyến tính phải G: 
 A → 0A| 0B| 1C | ε ; 
 B → 0C| 1A ; 
 C → 0B| 1C| 0 | 1. 
 1) Xác định các thành phần của G. 
 2) Xây dựng automat hữu hạn M: L(G) = L(M). 
 3) Biểu diễn M dƣới dạng đồ thị. 
 4) Viết biểu thức chính quy biểu diễn cho L(G). 
2.38. Cho văn phạm chính quy G: 
 S → aA | bB| aC | b| c; 
 A → aA | b; 
 B → aC | aA | a | b | ε; 
Phạm Hùng Phú 105 
Câu hỏi và bài tập chƣơng 2 
 C → bC| bB | a | b. 
 1) Xác định các thành phần của G. 
 2) Xây dựng automat hữu hạn M: L(G) = L(M). 
 3) Biểu diễn M dƣới dạng bảng và dƣới dạng đồ thị. 
 4) Viết biểu thức chính quy biểu diễn cho L(G). 
2.39. Cho văn phạm chính quy G: 
 S → Aa | B| Ca | b| ; 
 B → Cb | Aa | a | b; 
 C → Cb| B | b. 
 1) Xác định các thành phần của G. 
 2) Xây dựng automat hữu hạn M: L(G) = L(M). 
 3) Biểu diễn M dƣới dạng đồ thị. 
 4) Viết biểu thức chính quy biểu diễn cho L(G). 
2.40. Cho văn phạm tuyến tính trái G: 
 A → A0| B| C1 | ε ; 
 B → C0| A1 ; 
 C → B0| C1| 0 | A. 
 1) Xác định các thành phần của G. 
 2) Xây dựng automat hữu hạn M: L(G) = L(M). 
 3) Biểu diễn M dƣới dạng đồ thị. 
 4) Viết biểu thức chính quy biểu diễn cho L(G). 
 n n 
2.41. Chứng tỏ rằng ngôn ngữ L = {0 1 | n là số nguyên dƣơng} không chính quy. 
2.42. Ngôn ngữ nào trong các ngôn ngữ sau không là ngôn ngữ chính quy?. Chứng 
minh. 
 2n 
 a) L = {0 | n là số nguyên dƣơng}. 
 n m n+m 
 b) L = {0 1 0 | m, n là số nguyên dƣơng}. 
 n 
 c) L = {0 | n là số nguyên tố}. 
106 Phạm Hùng Phú