Giáo trình Ôtômát và ngôn ngữ hình thức (Phần 1)

 Ôtômát và ngôn ngữ hình thức 
 - 1 - 
 MỤC LỤC 
LỜI NÓI ĐẦU .......................................................................................................... 5 
Chƣơng I: Mở đầu ................................................................................................... 8 
1.1 Tập hợp và các cấu trúc đại số ......................................................................... 8 
1.1.1 Tập hợp và các tập con ............................................................................. 8 
1.1.2 Tập hợp và các phép toán hai ngôi .......................................................... 9 
1.3 Quan hệ và quan hệ tương đương .................................................................. 12 
1.4 Hàm số .......................................................................................................... 15 
1.5 Logic mệnh đề và tân từ .............................................................................. 16 
1.5.1 Logic mệnh đề ........................................................................................ 16 
1.6.2 Công thức mệnh đề ................................................................................. 18 
1.5.3 Dạng chuẩn của các công thức ............................................................... 20 
1.5.4 Các qui tắc suy diễn trong tính toán mệnh đề ........................................ 23 
1.6 Tân từ (vị từ) và các lượng tử ........................................................................ 25 
1.7 Các phương pháp chứng minh ...................................................................... 28 
Bài tập về logic và lập luận ................................................................................. 30 
Chƣơng II: Lý thuyết ôtômát ............................................................................... 35 
2.1 Ôtômát hữu hạn ............................................................................................. 35 
2.1.1 Các tính chất của hàm chuyển trạng thái ................................................ 38 
2.1.2 Các phương pháp biểu diễn ôtômát ........................................................ 39 
2.1.3 Ngôn ngữ đoán nhận được của ôtômát ................................................... 40 
2.2 Ôtômát hữu hạn không đơn định .................................................................. 41 
2.3 Sự tương đương của ôtômát đơn định và không đơn định ........................... 43 
2.4 Cực tiểu hoá ôtômát hữu hạn ........................................................................ 47 
Bài tập về ôtômát hữu hạn ................................................................................... 51 
Chƣơng III: Văn phạm và ngôn ngữ hình thức .................................................. 53 
3.1 Bảng chữ cái và các ngôn ngữ ...................................................................... 53 
3.2 Các dẫn xuất và và ngôn ngữ sinh bởi văn phạm .......................................... 55 
3.3 Phân loại các ngôn ngữ của Chomsky ........................................................... 62 
3.4 Tính đệ qui và các tập đệ qui ......................................................................... 70 
3.5 Các phép toán trên các ngôn ngữ ................................................................... 73 
3.6 Ngôn ngữ và ôtômát ...................................................................................... 76 
 Ôtômát và ngôn ngữ hình thức 
 - 2 - 
Bài tập về văn phạm và các ngôn ngữ sinh ......................................................... 77 
Chƣơng IV: Tập chính qui và văn phạm chính qui ........................................... 80 
4.1 Các biểu thức chính qui ................................................................................. 80 
4.2 Sự tương đương của các biểu thức chính qui ................................................ 82 
4.3 Ôtômát hữu hạn và biểu thức chính qui......................................................... 83 
4.3.1 Các hệ biến đổi và các biểu thức chính qui ............................................ 85 
4.3.2 Loại bỏ các - dịch chuyển trong các hệ thống biến đổi trạng thái ...... 87 
4.3.3 Chuyển các hệ chuyển trạng thái không đơn định về hệ thống đơn định
 ......................................................................................................................... 88 
4.3.4 Phương pháp đại số ứng dụng định lý Arden ......................................... 90 
4.3.5 Thiết lập ôtômát hữu hạn tương đương với biểu thức chính qui ............ 93 
4.3.6 Sự tương đương của hai biểu thức chính qui ......................................... 96 
4.4 Bổ đề Bơm đối với các tập chính qui ............................................................ 97 
4.5 Ứng dụng của bổ đề “Bơm” (điều kiện cần của ngôn ngữ chính qui) ......... 98 
4.6 Các tính chất đóng của các tập chính qui ...................................................... 99 
4.7 Các tập chính qui và văn phạm chính qui .................................................... 101 
4.7.1 Xây dựng văn phạm chính qui tương đương với ÔTĐĐ cho trước ........... 101 
4.7.2 Xây dựng ÔTĐĐ hữu hạn tương đương với văn phạm chính qui G .......... 102 
4.8 Điều kiện cần và đủ của ngôn ngữ chính qui............................................... 103 
4.8.1 Quan hệ tương đương bất biến phải ..................................................... 103 
4.8.2 Điều kiện cần và đủ: Định lý Myhill - Nerode .................................... 103 
Bài tập về biểu thức chính qui ........................................................................... 105 
Chƣơng V: Các ngôn ngữ phi ngữ cảnh ............................................................ 109 
5.1 Các ngôn ngữ phi ngữ cảnh và các cây dẫn xuất ......................................... 109 
5.2 Sự nhập nhằng trong văn phạm phi ngữ cảnh ............................................. 114 
5.3 Giản lược các văn phạm phi ngữ cảnh ........................................................ 115 
5.3.1 Lược giản các văn phạm phi ngữ cảnh ................................................. 115 
5.3.2 Loại bỏ các qui tắc rỗng ....................................................................... 118 
5.3.3 Loại bỏ các qui tắc đơn vị ..................................................................... 119 
5.4 Các dạng chuẩn của văn phạm phi ngữ cảnh ............................................... 120 
5.4.1 Dạng chuẩn Chomsky ........................................................................... 120 
5.4.2 Dạng chuẩn Greibach ........................................................................... 122 
5.5 Bổ đề Bơm cho ngôn ngữ phi ngữ cảnh ...................................................... 124 
 Ôtômát và ngôn ngữ hình thức 
 - 3 - 
5.6 Thuật toán quyết định được đối với các ngôn ngữ phi ngữ cảnh ................ 127 
Bài tập về ngôn ngữ phi cảnh ............................................................................ 128 
Chƣơng VI: Ôtômát đẩy xuống .......................................................................... 130 
6.1 Các định nghĩa cơ sở.................................................................................... 130 
6.2 Các kết quả đoán nhận bởi PDA .................................................................. 133 
6.3 Ôtômát đẩy xuống PDA và ngôn ngữ phi ngữ cảnh .................................... 136 
6.4 Phân tích cú pháp và ôtômát đẩy xuống ...................................................... 141 
6.4.1 Phân tích cú pháp trên / xuống ............................................................. 141 
6.4.2 Phân tích cú pháp dưới / lên ................................................................. 144 
Bài tập về ôtômát đẩy xuống ............................................................................. 147 
Chƣơng VII: Văn phạm LR(k) ........................................................................... 149 
7.1 Văn phạm LR(k) .......................................................................................... 149 
7.2 Một số tính chất của văn phạm LR(k) ......................................................... 152 
7.3 Các tính chất đóng của các ngôn ngữ .......................................................... 153 
Bài tập về văn phạm LR(K) ............................................................................... 155 
Chƣơng VIII: Máy Turing, ôtômát giới nội và những bài toán P, NP ........... 156 
8.1 Mô hình máy Turing .................................................................................... 156 
8.2 Biểu diễn máy Turing .................................................................................. 157 
8.2.1 Biểu diễn bằng các mô tả hiện thời ...................................................... 157 
8.2.2 Biểu diễn bằng đồ thị chuyển trạng thái ............................................... 159 
8.2.3 Biểu diễn bằng bảng chuyển trạng thái ................................................ 160 
8.3 Thiết kế máy Turing .................................................................................... 161 
8.4 Ngôn ngữ đoán nhận và “Hàm tính được” .................................................. 164 
8.4.1 Máy Turing như là một máy tính hàm số nguyên ................................ 164 
8.4.2 Các chương trình con ............................................................................ 166 
8.5 Máy Turing không đơn định ........................................................................ 167 
8.6 Luận đề Church ............................................................................................ 167 
8.7 Sự tương đương giữa văn phạm loại 0 và máy Turing ................................ 168 
8.8 Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh .............................. 171 
8.8.1 Ôtômát tuyến tính giới nội .................................................................... 171 
8.8.2 Văn phạm cảm ngữ cảnh (CSG) ........................................................... 172 
8.8.3 Sự tương đương giữa LBA và CSG ..................................................... 174 
8.9 Bài toán dừng của máy Turing .................................................................... 176 
 Ôtômát và ngôn ngữ hình thức 
 - 4 - 
8.9.1 Những bài toán không quyết định được ............................................... 176 
8.9.2 Bài toán về sự tương ứng của Post ....................................................... 178 
8.10 Lớp các bài toán NP đầy đủ ................................................................... 179 
8.10.1 Các lớp bài toán P và NP .................................................................... 179 
8.10.2 NP-đầy đủ ........................................................................................... 180 
Bài tập về các bài toán quyết định được và lớp bài toán P, NP-đầy đủ ............ 183 
Phụ lục: Hƣớng dẫn và lời giải các bài tập ....................................................... 185 
Danh sách các từ viết tắt và thuật ngữ .............................................................. 202 
Tài liệu tham khảo ............................................................................................... 206 
 Ôtômát và ngôn ngữ hình thức 
 - 5 - 
LỜI NÓI ĐẦU 
Lý thuyết ôtômát ra đời xuất phát từ những nhu cầu của thực tiễn kỹ thuật, chủ 
yếu là từ những bài toán về cấu trúc của các hệ thống tính toán và các máy biến đổi 
thông tin tự động. Ngày nay, lý thuyết này đã có một cơ sở toán học vững chắc và 
những kết quả của nó đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau. 
Song song với lý thuyết ôtômát, các ngôn ngữ hình thức cũng được tập trung 
nghiên cứu nhiều từ những năm 50 của thế kỷ 20, khi các nhà khoa học máy tính 
muốn sử dụng máy tính để dịch từ một ngôn ngữ này sang ngôn ngữ khác. Các 
ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán cả 
cho dạng thông tin vào / ra, lẫn kiểu các thao tác. 
Ôtômát và văn phạm sinh ra các ngôn ngữ hình thức thực chất là một lĩnh vực liên 
ngành, góp phần rất quan trọng trong việc mô tả các dãy tính toán và điều khiển tự 
động, được phát sinh trong nhiều ngành khoa học khác nhau từ các hệ thống tính 
toán, ngôn ngữ học đến sinh học. Khi nghiên cứu với tư cách là các đối tượng toán 
học, lý thuyết này cũng đề cập đến những vấn đề cơ bản của khoa học máy tính, và 
các kết quả nghiên cứu đã có nhiều ứng dụng ngay đối với các ngành toán học trừu 
tượng. 
Ngày nay, các lý thuyết về ngôn ngữ hình thức, ôtômát và lý thuyết tính toán được 
hình thức hoá thành các mô hình toán học tương ứng cho các ngôn ngữ lập trình, 
cho các máy tính, cho các quá trình xử lý thông tin và các quá trình tính toán nói 
chung. Ôtômát và ngôn ngữ hình thức được áp dụng rộng rãi trong nhiều lĩnh vực 
khoa học và ứng dụng như: mô hình hoá, mô phỏng các hệ thống tính toán, các kỹ 
thuật dịch, thông dịch, trí tuệ nhân tạo, công nghệ tri thức, ... 
Nhằm đáp ứng nhu cầu giảng dạy, học tập và nghiên cứu của các sinh viên ngành 
Công nghệ thông tin, chúng tôi biên soạn giáo trình “Ôtômát và ngôn ngữ hình 
thức” theo hướng kết hợp ba lý thuyết chính: lý thuyết ôtômát, ngôn ngữ hình thức 
và lý thuyết tính toán với nhiều ví dụ minh hoạ phong phú. 
Giáo trình này giới thiệu một cách hệ thống những khái niệm cơ bản và các tính 
chất chung của ôtômát và ngôn ngữ hình thức. 
Chương mở đầu trình bày các khái niệm cơ bản, các tính chất quan trọng của các 
cấu trúc đại số, logic mệnh đề, logic tân từ và các phương pháp suy luận toán học 
làm cơ sở cho các chương sau. Chương II giới thiệu về lý thuyết ôtômát, những 
khái niệm cơ sở và các hoạt động của ôtômát. Văn phạm và các ngôn ngữ hình 
thức được đề cập đến ở chương III. Những vấn đề liên quan đến tập chính qui, 
ngôn ngữ chính qui và ôtômát hữu hạn được trình bày chi tiết ở chương IV. 
Chương V, VI nghiên cứu các khái niệm cơ sở, mối quan hệ giữa các lớp ngôn ngữ 
và các tính chất rất quan trọng của ngôn ngữ phi ngữ cảnh, ôtômát đẩy xuống. Lớp 
các ngôn ngữ phi ngữ cảnh loại LR(k) có nhiều ứng dụng trong chương trình dịch, 
chương trình phân tích cú pháp được trình bày trong chương VII. Mô hình tính 
toán máy Turing, mối quan hệ tương đương tính toán giữa các lớp ngôn ngữ được 
đề cập ở chương cuối. Trong đó chúng ta tìm hiểu về độ phức tạp tính toán của các 
hệ thống tính toán, những bài toán quyết định được và những bài toán thuộc lớp 
 Ôtômát và ngôn ngữ hình thức 
 - 6 - 
NP-đầy đủ. Sau mỗi chương có các bài tập hệ thống hoá lại kiến thức và thông qua 
môn học, học viên nắm bắt được các khái niệm cơ bản, nâng cao sự hiểu biết về 
ôtômát và ngôn ngữ hình thức, đồng thời phát triển khả năng ứng dụng chúng trong 
nghiên cứu và triển khai ứng dụng Công nghệ thông tin. Đặc biệt trong số các bài 
tập cuối chương có những bài được đánh dấu „*‟ là những bài khó, phần lớn là 
được trích từ các đề thi tuyển sinh sau đại học (đầu vào cao học) ngành công nghệ 
thông tin trong những năm gần đây. Hầu hết những bài tập khó đều có lời hướng 
dẫn hoặc giới thiệu cách giải ở phần phụ lục để người đọc có thể tham khảo và tự 
đánh giá được khả năng nắm bắt, giải quyết vấn đề của mình. 
Đây cũng là tài liệu tham khảo, học tập cho sinh viên, học viên cao học và nghiên 
cứu sinh cá ...  vào sự tương đương của ôtômát 
hữu hạn và biểu thức chính qui. 
Định lý 4.6 Nếu L là chính qui thì LT cũng là chính qui. 
 Ôtômát và ngôn ngữ hình thức 
 - 100 - 
Chứng minh: Khi L là chính qui thì nó sẽ được đoán nhận bởi ôtômát hữu hạn 
M = (Q, , , q0, F), T(M) = L. 
Dựa vào đồ thị của ôtômát M chúng ta thiết lập hệ chuyển trạng thái S, trong đó 
các cung lấy chiều ngược lại của các cung tương ứng của M và F trở thành tập các 
trạng thái khởi đầu còn q0 lại trở thành trạng thái kết thúc duy nhất. Nghĩa là, 
S = (Q, ,  , F, {q0}). Nếu w T(M), tức chúng ta có một đường đi từ q0 đến một 
trạng thái kết thúc thuộc F với các nhãn tạo thành w. Bằng cách đi ngược lại đường 
đi đó thì chúng ta có đường đi trong đồ thị của S và có được wT L(S). 
Tương tự chiều ngược lại, nêu w L(S) thì wT T(M). Từ đó suy ra L(S) là chính 
qui và LT = L(S). 
Lưu ý: Trong chương 3 chúng ta đã nói văn phạm chính qui (theo định nghĩa 
Chomsky) là văn phạm tuyến tính phải. Từ định lý 4.6 suy ra, văn phạm tuyến tính 
trái (là đảo vị của văn phạm tuyến tính phải) có các qui tắc dạng A Ba | a có thể 
xem như là văn phạm chính qui và tất nhiên nó sinh ra tập chính qui. 
Ví dụ 4.15 Xét ôtômát M được cho như sau: 
Hình H4-16 Ôtômát M cho trước 
Áp dụng phương pháp giải hệ phương trình như đã thực hiện ở ví dụ 4.9, ta nhận 
được T(M) = {0i1j | i, j 0}. Ngôn ngữ này biểu diễn cho biểu thức chính qui 0*1*. 
Vậy, T(M)T = {1j0i | i, j 0}. Hệ chuyển trạng thái S được xây dựng bằng cách đảo 
chiều các cung trong đồ thị như sau: 
Hình H4-17 Hệ chuyển trạng thái S đoán nhận T(M)T 
Tương tự như trên, áp dụng thuật toán 4.2 để chuyển hệ chuyển trạng thái S về 
ôtômát đơn định cực tiểu M’ tương đương. 
Hình H4-18 Ôtômát cực tiểu M’ đoán nhận T(M)T 
Định lý 4.7 Nếu L là tập chính qui trên  thì * - L cũng tà tập chính qui. 
 q2 
 q0 q1 
1 
0 
0, 1 
0 
1 
 q2 
 q0 q1 
1 
0 
0, 1 
0 1 
 Q0 
 0 
 Q1 
 1 
1 
 Ôtômát và ngôn ngữ hình thức 
 - 101 - 
Chứng minh: Khi L là chính qui thì nó sẽ được đoán nhận bởi ôtômát hữu hạn 
M = (Q, , , q0, F), T(M) = L. 
Chúng ta thiết lập ôtômát M = (Q, , , q0, F ), với F = Q – F. Vậy M và M chỉ 
khác nhau ở các trạng thái kết thúc. Một trạn thái kết thúc của M thì lại không kết 
thúc của M và ngược lại. Đồ thị của hai ôtômát đó như nhau và chỉ khác ở các 
trạng thái kết thúc. 
 w T(M ) khi và chỉ khi (q0, w) F = Q – F, nghĩa là w L. Điều đó 
khẳng định rằng T(M ) =  - L là chính qui. 
Định lý 4.8 Nếu X, Y là chính qui trên  thì X  Y cũng tà tập chính qui trên . 
Chứng minh: Theo luật De Morgan trên các tập hợp, 
 X  Y = * - ((* - X)  (* - Y)). 
Theo định lý 4.7, * - X và * - Y là chính qui nên (* - X)  (* - Y) là chính qui. 
Một lần nữa áp dụng định lý 4.7 suy ra X  Y cũng là chính qui. 
4.7 Các tập chính qui và văn phạm chính qui 
Chúng ta đã chứng minh được rằng các tập chính qui chính xác là được đoán nhận 
được bởi ôtômát hữu hạn đơn định. Phần tiếp theo chúng ta chỉ ra rằng lớp các tập 
chính qui trên  cũng chính là các ngôn ngữ chính qui trên bảng chữ cái kết thúc . 
4.7.1 Xây dựng văn phạm chính qui tƣơng đƣơng với ÔTĐĐ cho trƣớc 
Cho trước M = (Q, , , q0, F) là ôtômát đơn định hữu hạn trạng thái. Vì Q là tập 
hữu hạn nên ta có thể viết Q = {q0, q1, q2 , . . ., qn}. Nếu w là một từ trong T(M) thì 
nó sẽ nhận được từ các phép ghép các nhãn của một số các phép chuyển trạng thái 
từ trạng thái q0 đến một trạng thái kết thúc nào đó trong F. Tương tự, một xâu được 
sinh ra trong một văn phạm cũng được xây dựng dựa trên các chữ cái và các qui tắc 
dẫn xuất liên tiếp từ ký tự bắt đầu. Do đó chúng ta có thể xây dựng văn phạm G để 
sinh ra T(M) như sau: 
 G = ({A0, A1, A2 , . . ., An}, , P, A0) 
Trong đó, P gồm các qui tắc: 
 (i) Ai aAj P nếu (qi, a) = qj F 
 (ii) Ai aAj và Ai a P nếu (qi, a) = qj F . 
Chúng ta có thể sử dụng cách thiết kế P để chỉ ra rằng L(G) = T(M). Theo cách 
thành lập P thì: 
 Ai aAj khi và chỉ khi (qi, a) = qj 
 Ai a khi và chỉ khi (qi, a) = qj F 
Do vậy, A0 a1A1 a1a2A2 . . . a1a2...ak-1Ak a1a2...ak-1ak khi và chỉ khi 
 (q0, a1) = q1 , (q1, a2) = q2, (q1, a3) = q3, ..., (q1, a3) F. 
 Ôtômát và ngôn ngữ hình thức 
 - 102 - 
Điều này khẳng định w = a1a2...ak L(G) khi và chỉ khi (q0, a1a2...ak) F, nghĩa 
là khi và chỉ khi w T(M). 
Ví dụ 4.16 Xây dựng văn phạm chính qui để sinh ra tập chính qui được biểu diễn 
bởi E = a*b(a+b)*. 
Giải: Trước tiên chúng ta xây dựng ôtômát hữu hạn M để đoán nhận E. 
Sau khi loại đi các - dịch chuyển, chúng ta được ôtômát đơn định hữu hạn như ở 
hình sau: 
Hình H4-19 Ôtômát hữu hạn M đoán nhận a*b(a+b)* 
Đặt G = ({A0, A1}, {a, b}, P, A0), trong đó P gồm: 
 A0 aA0, A0 bA1, A0 b, A1 aA1, A1 bA1, A1 a, A1 b 
Hiển nhiên, G là văn phạm chính qui, sinh ra ngôn ngữ chính qui và ngôn ngữ đó 
cũng chính là tập chính qui E. 
4.7.2 Xây dựng ÔTĐĐ hữu hạn tƣơng đƣơng với văn phạm chính qui G 
Cho trước văn phạm chính qui G = ({A0, A1, A2 , . . ., An}, , P, A0). Ôtômát hữu 
hạn M = ({q0, q1, q2 , . . ., qn, qf}, , , q0, {qf}) tương đương được xây dựng như sau: 
(i) Tập các trạng thái là tập các biến (ký hiệu chưa kết thúc), 
(ii) Trạng thái khởi đầu là A0, 
(iii) Ai aAj P thì (qi, a) = qj F và Ai a P thì (qi, a) = qf. 
Từ cách xây dựng như trên dễ nhận thấy: 
 A0 a1A1 a1a2A2 . . . a1a2...ak-1Ak a1a2...ak-1ak trong văn phạm G 
khi và chỉ khi tồn tại một đường dẫn trong đồ thị M đi từ A0 đến trạng thái kết thúc 
qf để có được a1a2...ak-1ak. Từ đó suy ra L(G) = T(M). 
Ví dụ 4.17 Cho trước G = ({A0, A1}, {a, b}, P, A0), trong đó 
 P = {A0 aA1, A1 bA1, A1 a, A1 bA0} 
Xây dựng ôtômát hữu hạn M để đoán nhận L(G). 
Giải: Đặt M = ({q0, q1, qf}, {a, b}, , q0, {qf}), trong đó q0, q1 là hai trạng thái 
tương ứng với các biến A0, A1 và qf là trạng thái kết thúc mới được bổ sung. Theo 
cách xây dựng như trên chúng ta có ôtômát M như sau: 
 
 
a, b
 a
b
a, b
a
q0 
b
qf 
 Ôtômát và ngôn ngữ hình thức 
 - 103 - 
Hình H4-20 Ôtômát đoán nhận L(G) 
Dễ nhận ra L(G) = (ab)*b*a. 
4.8 Điều kiện cần và đủ của ngôn ngữ chính qui 
Trong phần này chúng ta xét các điều kiện cần và đủ của ngôn ngữ chính qui (tập 
chính qui). 
4.8.1 Quan hệ tƣơng đƣơng bất biến phải 
Giả sử tập X . 
Định nghĩa 4.4 Quan hệ nhị nguyên R trên tập X, R  X X, được gọi là quan hệ 
bất biến phải nếu: 
 x, y, z X, xRy xz R yz 
Định nghĩa 4.5 Quan hệ nhị nguyên R trên tập X được gọi là quan hệ tương 
đương bất biến phải nếu R là quan hệ tương đương và là bất biến phải. 
Trong chương I (định lý 1.1) đã khẳng định là các lớp tương đương của một quan 
hệ tương đương sẽ tạo ra một phân hoạch của tập X. 
Định nghĩa 4.6 Số các lớp tương đương của quan hệ tương R được gọi là chỉ số 
tương đương của R trên tập X. 
4.8.2 Điều kiện cần và đủ: Định lý Myhill - Nerode 
Định lý 4.9 (Định lý Myhill – Nerode) 
Ngôn ngữ L là chính qui khi và chỉ khi nó là hợp của một số lớp tương đương bất 
biến phải với chỉ số tương đương là hữu hạn. 
Chứng minh: 
a/ Điều kiện cần 
Giả sử L là ngôn ngữ chính qui. Khi đó tồn tại một ôtômát đơn định đầy đủ (hàm chuyển 
trạng thái xác định đối với mọi phần tử của Q) M = (Q, , , q0, F) đoán nhận L, T(M) = L. 
(i) Xây dựng quan hệ tương đương bất biến phải với chỉ số hữu hạn. 
 a/ Trên tập * xác định quan hệ R như sau: 
 x, y *, x R y (q0, x) = (q0, y) 
 b/ Quan hệ R được định nghĩa như trên là tương đương. Tính phản xạ, đối xứng và 
bắc cầu là hiển nhiên (suy trực tiếp từ các định nghĩa). 
a
b
 a
q0 q1 
qf 
b
 Ôtômát và ngôn ngữ hình thức 
 - 104 - 
 c/ R là bất biến phải. Thật vậy, 
 x, y, z *, x R y (q0, x) = (q0, y) 
 (q0, xz) = ( (q0, x), z) = ( (q0, y), z) = (q0, xz) 
 xz R yz 
 Vậy R là bất biến phải. 
 d/ R có chỉ số tương đương hữu hạn. 
 Giả sử tập X được phân hoạch thành X1, X2, . . ., Xm các lớp tương đương của R. 
 Với mỗi trạng thái q Q, xác định tập 
 D(q) = { x * | (q0, x) = q} 
 Xét Xi, với i = 1, 2, , m. Do Xi  nên y Xi. Vì ôtômát M là đầy đủ nên 
q Q để (q0, y) = q . Khi đó x Xi, ta có (q0, x) = (q0, y) = q , nghĩa là x D(q ). 
T ừ đ ó suy ra Xi  D(q ). 
 Như vậy, mọi lớp tương đương trong phân hoạch trên đều chứa trong một tập D(q) 
với q là trạng thái nào đó của Q. Mà ta biết rằng tập các trạng thái là hữu hạn, vậy suy ra 
m |Q|, nghĩa là chỉ số tương đương của R là hữu hạn. 
(ii) L là hợp của một số lớp tương đương. 
 Vì L  * và 
m
i
iX
1 
= * nên L phải chứa trong hợp của một số lớp tương đương 
trong phân hoạch trên. 
 Giả sử 
1t
X , 
2t
X ,  
kt
X là những lớp tương đương trong các lớp phân hoạch của 
* mà có giao với L khác trống. Khi đó hiển nhiên là: 
 
k
n
tn
X
1 
 L 
 Chúng ta cần chứng minh chiều ngược lại 
k
n
tn
X
1 
 L. (4.10) 
 Thật vậy, vì 
nt
X  L , với 1 n k, nên x (
nt
X  L). Suy ra 
 x 
nt
X  L , với 1 n k, (4.11) 
 Vì x L nên ta có: (q0, x) F. (4.12) 
 Giả sử y 
nt
X , với 1 n k . Khi đó theo (4.11) và (4.12) ta có: 
 (q0, x) = (q0, y) F 
nên y T(M). Do đó y L. Bởi vậy, 
nt
X  L, n = 1, 2, , k. Từ đó ta suy ra (4.10). 
b/ Điều kiện đủ 
 Giả sử R là quan hệ tương đương trên * và L là hợp của các lớp tương đương 
 X1, X2, . . ., Xn (4.13) 
 Ôtômát và ngôn ngữ hình thức 
 - 105 - 
 Theo ký hiệu của các lớp tương, nếu x Xi, i = 1, 2, , n, thì Xi = [x]. 
 (i) Xây dựng ôtômát hữu hạn trạng thái: 
 M = (Q, , , q0, F) 
Trong đó: 
 Q = 
 q0 = [] 
 F = {[x] Q | x L} và hàm chuyển trạng thái được định nghĩa như 
sau: 
 ([x], a) = [xa] với a  và x *. (4.14) 
 (ii) Chứng minh M đoán nhận L 
 a/ Qui nạp theo độ dài của y, chúng ta có thể chứng được rằng 
 ([x], y) = [xy] với y + và x *. (4.15) 
 Thật vậy, nếu |y| = 1, nghĩa là y = a . Theo (4.14) ta có 
 ([x], y) = ([x], a) = [xa] = [xy] 
 Giả sử (4.15) đúng với mọi từ y có độ dài |y| k. Xét y = y a, trong đ ó |y | = k. 
 ([x], y) = ([x], y a) = ( ([x], y ), a) (theo tính chất của hàm ) 
 = ([xy ], a) (theo giả thiết qui nạp) 
 = [xy a] = [xy ] 
 Tất nhiên khi x = , thì từ (4.15) suy ra (q0, y) = [y], với mọi từ y 
+
. (4.16) 
 b/ Chứng minh rằng T(M) = L. 
 Giả sử x là từ bất kỳ thuộc *. 
 + Nếu |x| = 0, nghĩa là x = . Do  L q0 = [] F nên ta có  T(M)  L. 
 + Nếu |x| > 1 thì từ (7) ta suy ra x T(M) (q0, x) = [x] F x L. Do đó, 
T(M) = L, nghĩa là L là ngôn ngữ chính qui. 
Bài tập về biểu thức chính qui 
4.1 Biểu diễn các tập sau bằng các biểu thức chính qui 
(i) {0, 1, 2} 
(ii) {w {a, b}* | w chỉ chứa một lần xuất hiện a} 
(iii) {a2, a5, a8, ...} 
(iv) {an | n chia hết cho 2, 3 hoặc n = 5} 
(v) Tập tất cả các xâu trên {a, b} mà bắt đầu và kết thúc bằng a. 
{X1, X2, , Xn }, nếu  L 
{[], X1, X2, , Xn }, nếu  L 
 Ôtômát và ngôn ngữ hình thức 
 - 106 - 
4.2 Tìm tất cả các xâu có độ dài bằng hoặc nhỏ hơn 5 trong tập chính qui được biểu 
diễn bằng: 
(i) (ab + a)*(aa + b) 
(ii) (a*b + b*a)*a 
(iii) a* + (ab + a)* 
4.3 Chứng minh đẳng thức sau: 
 (a
*
ab + ba)
*
a
* 
= (a + ab + ba)
*
4.4 Xây dựng ôtômát hữu hạn tương ứng với các biểu thức chính qui sau: 
(i) (ab + c*)*b 
(ii) a + bb + bab*a 
(iii) (a + b)*abb 
4.5 Tìm các hệ chuyển đổi (hoặc ôtômát hữu hạn) tương đương với các biểu thức 
ở bài tập 4.2. 
4.6 Tìm các biểu thức chính qui biểu diễn cho các tập sau: 
(a) Tập tất cả các xâu trên {0, 1} có nhiều nhất một cặp số 0 hoặc nhiều nhất 
một cặp số 1. 
(b) Tập tất cả các xâu trên {a, b}, trong đó số các lần xuất hiện của a chia hết 
cho 3. 
(c) Tập tất cả các xâu trên {a, b}, trong đó có ít nhất hai lần xuất hiện của b 
giữa hai ký tự a. 
(d) Tập tất cả các xâu trên {a, b} kết thúc bằng 00 và bắt đầu bằng 1. 
4.7 Hãy chỉ ra rằng không tồn tại một ôtômát hữu hạn để đoán nận tất cả các từ 
Palindromes trên tập {a, b}. 
Lưu ý: Palindrome là một xâu mà viết xuôi và viết theo thứ tự ngược lại đều như 
nhau, ví dụ “malam”. Nếu một palindrome có độ dài chẵn thì có thể nhận được từ 
phép ghép của một xâu với đảo vị của xâu đó. 
4.8 Tìm biểu thức chính qui tương ứng với đồ thị trạng thái sau 
4.9 Loại bỏ - dịch chuyển trong ôtômát hữu hạn sau: 
0 
 q1 1 
0 
1 
0 
 1 q2 
q4 
0 
1 
q3 
 Ôtômát và ngôn ngữ hình thức 
 - 107 - 
4.10 Chứng minh rằng L = {ww | w {a, b}*} không phải là tập chính qui. 
4.11 Chứng minh rằng các tập sau không phải là tập chính qui 
(i) {anb2n | n > 0} 
(ii) {anbm | 0 < n < m} 
(iii) {anbn | n > 0} 
(iv) {anbm | n, m là nguyên tố cùng nhau, UCLN(m, n) = 1} 
4.12 Cho trước văn phạm G có các qui tắc dẫn xuất S aS | a, tìm ôttomát M để 
 đoán nhận L(G). 
4.13 Xây dựng một ôtômát hữu hạn để đoán nhận L(G), khi G có các qui tắc dẫn 
 xuất: S aS | bA | b,  aA | bS | a và A aA | bS | a 
4.14 Xây dựng ôtômát đơn định hữu hạn tương đương với văn phạm có các qui tắc 
sau: S aS | aA , A bB, B aC, C  
4.15 Những khẳng định sau đúng hay sai, nếu đúng thì chứng minh, còn sai thì cho 
ví dụ, 
(i) Nếu L1  L2 là chính qui và L1 chính qui thì L2 là chính qui, 
(ii) Nếu L1L2 là chính qui và L1 chính qui thì L2 là chính qui, 
(iii) Nếu L* là chính qui thì L chính qui. 
4.16 Cho ngôn ngữ chính qui trên bảng chữ cái {0, 1}, gồm tất cả các từ chứa hai 
 ký hiệu 0 đứng liền nhau. 
 (i) Hãy biểu diễn ngôn ngữ đó bởi biểu thức chính qui 
 (ii) Hãy tìm văn phạm chính qui sinh ra ngôn ngữ đó 
 (iii) Hãy xây dựng ôtômát hữu hạn đoán nhận cùng ngôn ngữ trên. 
4.17 Xây dựng ôtômát hữu hạn đơn định tương đương với biểu thức chính qui 
 10+(0+11)
*
1. 
4.18 Cho ngôn ngữ L trên bảng chữ {0, 1} có các từ chứa chẵn lần số 0 và chẵn 
 lần số 1. 
 (i) Tìm biểu thức chính qui biểu diễn cho L. 
 (ii) Xây dựng văn phạm sinh ra ngôn ngữ L. 
0 
q2 
0 
 
1 1 0 
q4 q2 q0 
1 
q1 
1 
q3 
q4 
 Ôtômát và ngôn ngữ hình thức 
 - 108 - 
4.19* (Đề thi cao học năm 2002, câu 3 môn thi cơ bản: “Toán học rời rạc”) 
Cho ngôn ngữ L = {xn(10)myk | n, k 1, m 0} 
 (i) Hãy tìm văn phạm chính qui G sinh ra L (L(G) = L). 
 (ii) Xây dựng ôtômát hữu hạn trạng thái M sao cho T(M) = L(G). 
 (iii) Hãy kiểm tra xem các xâu xx10y, x101 có được sinh ra bởi văn phạm G 
 và được đoán nhận bởi ôtômát M ở trong câu (i), (ii)? 
4.20* (Đề thi cao học năm 2002, câu 3 môn thi cơ bản: “Toán học rời rạc”) 
Cho văn phạm chính qui G = (VN, , P, S), với tập các qui tắc 
 P = {S aA | bE, A xB | b, B yC, C zA, E aF, F b} 
 (i) Tìm ngôn ngữ L(G) sinh ra bởi G. 
 (ii) Xây dựng ôtômát hữu hạn trạng thái M sao cho T(M) = L(G). 
 (iii) Cho xâu w = axyzb. Hãy chỉ ra G sinh ra xâu w và w còn được đoán 
 nhận bởi M. 
4.21* (Đề thi cao học năm 2003, câu 3 môn thi cơ bản: “Toán học rời rạc”) 
 Cho ôtômát hữu hạn M với hàm chuyển trạng thái được cho như hình sau: 
 (i) Xây dựng văn phạm chính qui G để L(G) = L(M). 
(ii) Hãy chỉ ra G sinh ra w1 = 1xyyx, w2 = 0yx và M cũng đoán nhận được w1, 
w2. 
4.22* (Đề thi cao học năm 2005, câu 3 môn thi cơ bản: “Toán học rời rạc”) 
Cho trước bảng chữ cái  = {a, b}. 
(i) Xây dựng ôtômát hữu hạn trạng thái M trên  để đoán nhận tất cả các xâu 
có các chữ a là số chẵn và lớn hơn 0. 
 (ii) Xây dựng văn phạm chính qui tương đương với M mà anh (chị) đã chỉ ra. 
 (iii) Xác định biểu thức chính qui tương đương với ngôn ngữ sinh bởi G. 
 q0 
1 y 
y 
 x 
q1 
q4 
0 
x 
q3 
q2