-Tập tất cả các xâu trên V là V * , {}V * V + = V * -{} V *: tập vô hạn đếm được Ví dụ: V={a,b}V *={ ,a,b,aa,bb,ab,ba,…} -Các phép toán trên xâu • Ghép tiếp: cho 2 xâu x,y. Ghép tiếp của x, y là x.y hay xy là 1 xâu viết x trước, rồi đến y sau chứ không có dấu cách. Ví dụ: x=01 y=0110 xy=010110 • Đảo ngược xâu x (x r ): xâu được viết theo thứ tự ngược lại của xâu x Ví dụ: x=0101 x r =1010 Chú ý: r = , 1 r =1 -Xâu x mà x=x r thì x là xâu hình tháp (xâu đối xứng) Ví dụ: x=0110 x r =0110, x: xâu hình tháp • Lũy thừa xâu x (x n ): xâu nhận được bằng cách ghép tiếp chính xâu x n lần. - 1. NÓI ĐẦU Môn học “Automat hữu hạn” được đưa vào chương trình đào tạo đại học ngành Công nghệ thông tin từ khóa 505, là khóa đầu tiên đào tạo theo tín chỉ. Bài giảng môn học này được biên soạn lần đầu vào năm 2007 và được sử dụng làm tài liệu học tập cho các sinh viên từ khóa 505 trở đi. Sau 5 năm sử dụng, tài liệu này đã đáp ứng được nhu cầu dạy và học môn học này trong khoa Công nghệ thông tin. Mỗi năm học, bài giảng lại được bổ sung thêm những ý mới, những bài tập mới đáp ứng yêu cầu nâng cao chất lượng đào tạo đại học, tiếp thu được những thay đổi, những tài liệu mới được công bố trên mạng. Trong lần tái bản này, mỗi chương đều được xem xét lại về nội dung, cập nhật những kiến thức mới, chỉnh sửa những chỗ sai sót, bổ sung thêm kiến thức cần thiết, bổ sung thêm những bài tập, những câu hỏi trắc nghiệm, cách giải các bài tập, giúp cho sinh viên nắm được nội dung bài giảng tốt hơn. Chúng tôi đã cố gắng trình bày bài giảng sao cho dễ đọc, dễ hiểu hơn, tuy nhiên nhiều vấn đề khi trình bày vẫn còn nặng về lý thuyết, trừu tượng. Mặc dù đã dành nhiều thời gian, chú trọng đến cả nội dung và hình thức, tuy nhiên trong quá trình biên soạn khó tránh khỏi những sai sót, rất mong được sự góp ý kiến của đồng nghiệp và các bạn sinh viên để bài giảng được tốt hơn. Biên soạn: ThS Trần Văn Lộc
- 2. 1 NHẬP MÔN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC 1. Các khái niệm cơ bản Ngôn ngữ tự nhiên: Ngôn ngữ là phương tiện giao tiếp hàng ngày giữa con người với nhau, được hình thành và phát triển song song với sự phát triển của xã hội loài người. Ngôn ngữ cũng còn là phương tiện giao tiếp giữa con người với máy tính hoặc giữa các máy tính với nhau. Ngôn ngữ giao tiếp giữa người với người gọi là ngôn ngữ tự nhiên, ví dụ như ngôn ngữ tiếng Việt, tiếng Anh, … Các quy tắc cú pháp của ngôn ngữ tự nhiên rất phong phú, đa dạng và phức tạp. Tuy nhiên các yêu cầu nghiêm ngặt về ngữ nghĩa trong các ngôn ngữ tự nhiên chưa cao, thể hiện ở chỗ một từ có thể được hiểu theo nhiều nghĩa khác nhau tùy theo ngữ cảnh cụ thể. Vì lẽ đó, ngôn ngữ tự nhiên không thể dùng để giao tiếp giữa người với máy hoặc giữa các máy với nhau. Ngôn ngữ hình thức (Formal Language): Ngôn ngữ được sử dụng để giao tiếp giữa người với máy hoặc giữa máy với máy phải có các quy tắc cú pháp chặt chẽ hơn sao cho mỗi từ, mỗi câu chỉ được hiểu theo một cách duy nhất. Những ngôn ngữ như vậy được gọi là ngôn ngữ hình thức (Formal Language). Ngôn ngữ hình thức là một loại ngôn ngữ đặc biệt được tạo ra để làm công cụ giao tiếp giữ người và máy hoặc giữa máy với máy. Bộ chữ cái (Alphabet): Giả sử là 1 tập hợp hữu hạn khác rỗng các phần tử nào đó được dùng để tạo ra các từ của ngôn ngữ, thì được gọi là bảng chữ cái. Như vậy, bảng chữ cái của ngôn ngữ tiếng Anh là tập hợp 26 chữ cái Latinh từ a đến z. Mỗi phần tử trong được gọi là 1 ký tự. Ví dụ: Để có các xâu nhị phân thì phải dùng 2 ký tự 0 và 1, như vậy, bảng chữ cái của ngôn ngữ các xâu nhị phân là ={0, 1}. Xâu ký tự (String): Một dãy hữu hạn các ký tự của được viết liền nhau được gọi là 1 xâu ký tự, hay là 1 từ trên . Trong xâu ký tự, 1 ký tự có thể xuất hiện nhiều lần. Số lượng ký tự trong xâu ký tự gọi là độ dài của xâu ký tự đó. Ví dụ 01001011 là 1 xâu ký tự trên bảng chữ cái {0, 1}, có độ dài 8. Giả sử là xâu ký tự, sử dụng ký hiệu || hoặc l() để chỉ độ dài của xâu .
- 3. rỗng (emty string) là xâu đặc biệt không chứa ký tự nào cả và xâu rỗng có độ dài là 0. Ký hiệu xâu rỗng là (có tài liệu ký hiệu là hoặc là ^). Lũy thừa của bộ chữ cái: Ký hiệu k là tập tất cả các xâu ký tự trên có độ dài bằng k, với k>0. Còn với k=0 thì 0 là tập hợp chỉ có 1 xâu rỗng : 0 ={}. Ví dụ với ={a, b, c}, thì 2 ={aa, ab, ac, ba, bb, bc, ca, cb, cc} Ký hiệu * là tập tất cả các xâu ký tự (kể cả xâu rỗng) trên , như vậy thì: *=0 1 2 … Ký hiệu + là tập tất cả các xâu ký tự khác rỗng trên , như vậy thì: + =1 2 … Như vậy + =* - {}, hoặc *=+ {}. Ngôn ngữ (Language): Một tập hợp các xâu ký tự (từ) trên bảng chữ cái gọi là một ngôn ngữ trên bảng chữ cái đó. Như vậy một ngôn ngữ có thể có hữu hạn và cũng có thể có vô hạn từ, và người ta gọi là ngôn ngữ hữu hạn hoặc ngôn ngữ vô hạn. Ký hiệu là ngôn ngữ rỗng, tức là ngôn ngữ không chứ từ nào cả. Chú ý phân biệt ngôn ngữ rỗng với ngôn ngữ có 1 từ rỗng {}. Ví dụ + , * là các ngôn ngữ vô hạn, còn k với số k cụ thể nào đó là ngôn ngữ hữu hạn. Có thể coi là ngôn ngữ hữu hạn. Mọi ngôn ngữ trên đều là ngôn ngữ con của ngôn ngữ *. Đối với một ngôn ngữ hình thức L *người ta quan tâm đến 1 số vấn đề sau: Với xâu bất kỳ cho trước không biết có thuộc L hay không ? Với xâu của L làm thế nào để tạo ra ? 2. Văn phạm và ngôn ngữ sinh bởi văn phạm 2.1. Định nghĩa văn phạm Trước khi đưa ra định nghĩa văn phạm, ta có thể hình dung văn phạm như là một “thiết bị tự động” có khả năng sinh ra 1 tập hợp các từ trên 1 bảng chữ cái cho trước nào đó. Mỗi từ được sinh ra sau 1 số hữu hạn bước thực hiện các quy tắc của
- 4. phạm. Việc xác định 1 ngôn ngữ trên bảng chữ cái cho trước có thể thực hiện theo 1 trong các cách thức sau: Cách 1: Đối với mỗi xâu thuộc ngôn ngữ đã cho, có thể chọn 1 quy cách hoạt động của “thiết bị tự động” để sau 1 số hữu hạn bước làm việc nó dừng lại và sinh ra chính xâu đó. Cách 2: “Thiết bị tự động” có khả năng lần lượt sinh ra tất cả các xâu trong ngôn ngữ đã cho. Cách 3: Với mỗi xâu cho trước, “Thiết bị tự động” có thể cho biết xâu đó có thuộc ngôn ngữ đã cho hay không. Việc thực hiện theo các cách trên là như nhau, hay nói cách khác, văn phạm làm việc theo các cách trên là tương đương nhau. Định nghĩa: Văn phạm G là 1 bộ sắp thứ tự gồm 4 thành phần G=<, , I, R>, trong đó: , là các tập hữu hạn, khác rỗng, không giao nhau. Tập được gọi là từ điển cơ bản, mỗi phần tử của gọi là ký hiệu cơ bản hay gọi là ký hiệu kết thúc (terminal). Tập được gọi là từ điển hỗ trợ, mỗi phần tử của gọi là ký hiệu hỗ trợ hay gọi là ký hiệu không kết thúc (nonterminal). Đặt V= , tập V gọi là từ điển đầy đủ. Ký hiệu I là 1 phần tử của được gọi là ký hiệu ban đầu R là tập các quy tắc mà mỗi quy tắc có dạng , với , là các từ trên từ điển đầy đủ V, còn ký hiệu thì không thuộc V. Chú ý: Để phân biệt giữa 2 loại ký hiệu kết thúc và không kết thúc, người ta quy ước sử dụng các chữ cái in thường hoặc các chữ số để chỉ ký hiệu kết thúc còn chữ cái in hoa để chỉ ký hiệu không kết thúc. Dẫn được trực tiếp: Cho văn phạm G=<, , I, R> và 1 quy tắc r= R. Xét các xâu =xy và =xy đều là xâu trên từ điển đầy đủ V. Ta thấy rằng nếu áp dụng quy tắc r thì từ xâu ta sẽ được xâu . Khi đó là xâu dẫn được trực tiếp từ xâu trong văn phạm G, và ký hiệu là: ╞ .
- 5. vậy khi áp dụng 1 quy tắc nào đó trong tập quy tắc R để chuyển 1 xâu thành 1 xâu khác tức là đã dẫn trực tiếp từ xâu đến xâu . Dẫn xuất: Dãy các xâu D=(0, 1, … , k) được gọi là 1 dẫn xuất của xâu k từ xâu 0 trong văn phạm G=<, , I, R>, và ký hiệu là 0├ k , nếu i-1╞ i, với i=1, 2, …, k. Số k được gọi là độ dài của dẫn xuất D. Như vậy dẫn được trực tiếp là trường hợp riêng của dẫn xuất với độ dài dẫn xuất bằng k=1. Ví dụ: Cho văn phạm G=<, , I, R>, với ={a, b}; ={I, A}; R={I I a, I A, A aAb, A ab}; Xét các xâu x=Ia, y=Aa, =aabbaaa Ta thấy, nếu áp dụng quy tắc I A thì từ x sẽ được y , vì vậy x ╞ y Xét dãy các xâu D=(Ia, Iaa, Iaaa, Aaaa, aAbaaa, aabbaaa) thỏa mãn điều kiện xâu đứng sau dẫn được trực tiếp từ xâu đứng trước, vậy ta có dẫn xuất x├ với độ dài dẫn xuất bằng 5. 2.2. Ngôn ngữ của văn phạm Định nghĩa: Cho văn phạm G=<, , I, R> và D=(0, 1, … , k) là 1 dẫn xuất của xâu k từ xâu 0 trong văn phạm G. Nếu 0=I và k * thì k được gọi là một xâu (từ) sinh bởi văn phạm G và dẫn xuất D được gọi là dẫn xuất đầy đủ trong G. Tập hợp tất cả các xâu (từ) sinh bởi văn phạm G được gọi là ngôn ngữ sinh bởi văn phạm G và ký hiệu là L(G), được định nghĩa như sau: L(G)={ * và I ├ } Ví dụ: Cho văn phạm G=<, , I, R>, với ={a, b}; ={I}; R={I a I b, I ab}; R chỉ có 2 quy tắc, quy tắc thứ nhất I a I b mỗi lần áp dụng sẽ tạo ra 1 cặp a b với I ở giữa. Như vậy nếu xuất phát từ I, áp dụng quy tắc thứ nhất n lần ta sẽ được xâu có dạng a..aIb..b với n ký tự a ở đầu và n ký tự b ở cuối, và có thể viết gọn lại là an Ibn . Còn quy tắc thứ 2 của R có tác dụng kết thúc quá trình sinh, vì vế phải của quy tắc này chỉ chứa các ký hiệu kết thúc. Như vậy xâu do văn phạm G
- 6. ra sẽ có dạng an bn với n là 1 số nguyên dương, hay viết đơn giản là n>0. Ngược lại, một xâu bất kỳ có dạng an bn với n>0 đều do G sinh ra bằng cách áp dụng n-1 lần quy tắc thứ nhất và sau đó 1 lần áp dụng quy tắc thứ 2, dẫn xuất đầy đủ là D=(I, aIb, … , an-1 Ibn-1 , an bn ). Do vậy có thể kết luận ngôn ngữ do văn phạm G sinh ra là: L(G)={an bn n>0}. Định nghĩa văn phạm tương đương: Hai văn phạm G và G’ được gọi là tương đương nhau nếu chúng cùng sinh ra 1 ngôn ngữ, tức là L(G)=L(G’). Ví dụ: Cho văn phạm G=<, , I, R> và G’=<, , I, R’> với ={a, b}; ={I}; R={I a I b, I ab}; R’={I a I b, I aabb, I ab}; Dễ dàng thấy rằng 2 văn phạm này đều sinh ra 1 ngôn ngữ, vì vậy chúng tương đương với nhau. 2.3. Một số tính chất của văn phạm Hai dẫn xuất đồng lực: Cho văn phạm G=<, , I, R> và 2 dẫn xuất trong G là D=(0, 1, … , k), E=(0, 1, … , m). D và E được gọi là đồng lực nếu 0=0 và k=m. Dẫn xuất không lặp: Cho văn phạm G=<, , I, R> và dẫn xuất trong G là D=(0, 1, … , k). D được gọi là dẫn xuất không lặp nếu không tồn tại cặp i, p khác nhau mà i=p. Tính chất 1: Với mỗi dẫn xuất trong văn phạm tùy ý luôn tồn tại 1 dẫn xuất không lặp đồng lực với nó. Tính chất 2: Với mỗi văn phạm G bất kỳ luôn tồn tại 1 văn phạm G’ tương đương với G, tức là L(G)=L(G’). Các phép toán trên ngôn ngữ : Ngôn ngữ là 1 tập hợp nên có thể áp dụng các phép toán tập hợp là phép hợp , phép giao giữa 2 ngôn ngữ, cụ thể như sau: Giả sử L và M là 2 ngôn ngữ, hợp của L và M là 1 ngôn ngữ, ký hiệu là L M, được định nghĩa như sau: L M={ L hoặc M}.
- 7. của L và M là 1 ngôn ngữ, ký hiệu là L M, được định nghĩa như sau: L M={ L và M}. Ngoài 2 phép toán trên, với ngôn ngữ người ta còn xét phép nhân 2 ngôn ngữ L và M, ký hiệu là L.M, là 1 ngôn ngữ được định nghĩa như sau: L.M={ L và M}, trong đó là xâu ghép nối của 2 xâu và . Nhận xét: Các phép hợp và giao có tính chất giao hoán còn phép nhân không có tính giao hoán. Cả 3 phép toán đều có tính chất kết hợp. Tính chất 3: Lớp các ngôn ngữ sinh bởi văn phạm đóng đối với các phép hợp, phép giao và phép nhân ngôn ngữ. Tính chất đóng của lớp ngôn ngữ sinh bởi văn phạm cho phép thực hiện các phép hợp, phép giao và phép nhân giữa các ngôn ngữ, kết quả sẽ cho ngôn ngữ cũng được sinh bởi 1 văn phạm nào đó. 3. Phân loại văn phạm của Chomsky Chomsky là nhà bác học người Mỹ có nhiều đóng góp quan trọng trong lĩnh vực ngôn ngữ học và văn phạm, ông đưa ra cách phân loại văn phạm và ngôn ngữ hình thức và được coi là cơ sở cho việc nghiên cứu và phát triển ngôn ngữ hình thức. Theo Chomsky, văn phạm được phân thành 4 loại: Loại 0 (Type 0): Văn phạm ngữ cấu (Phrase-structure Grammar) Loại 1 (Type 1): Văn phạm cảm ngữ cảnh (Context-sensitive Grammar) Loại 2 (Type 2): Văn phạm phi ngữ cảnh (Context-free Grammar) Loại 3 (Type3): Văn phạm chính quy (Regular Grammar). 3.1. Văn phạm ngữ cấu Văn phạm G=<, , I, R> được gọi là văn phạm ngữ cấu nếu mọi quy tắc thuộc R đều có dạng , với V+ và V*. Ngôn ngữ do văn phạm ngữ cấu sinh ra gọi là ngôn ngữ ngữ cấu. Nhận xét: Trong định nghĩa văn phạm ngữ cấu không có yêu cầu nào khác biệt so với định nghĩa văn phạm ở trên, có chăng là đòi hỏi V+ , thì cũng là lẽ
- 8. nhiên, vì không thể có quy tắc nào mà vế trái lại là 1 xâu rỗng. Như vậy văn phạm ngữ cấu là loại văn phạm chung nhất. 3.2. Văn phạm cảm ngữ cảnh Văn phạm G=<, , I, R> được gọi là văn phạm cảm ngữ cảnh nếu G là văn phạm ngữ cấu và mọi quy tắc thuộc R đều có dạng , với l() l() hoặc có dạng . Ngôn ngữ do văn phạm cảm ngữ cảnh sinh ra gọi là ngôn ngữ cảm ngữ cảnh. Nhận xét: Trong định nghĩa văn phạm cảm ngữ cảnh có bổ sung thêm các yêu cầu với các quy tắc của R: nếu xâu ở vế phải của quy tắc khác rỗng thì độ dài phải không nhỏ hơn độ dài xâu ở vế trái của quy tắc. Ví dụ: Xét các văn phạm sau: G1=<1, 1, I, R1> có 1={a, b}; 1={I, A, B}; R1={I AB, A aA, A a, B bB, B b}; G2=<2, 2, I, R2> có 2={a, b}; 2={I, A, B, C}; R2={I ACB, A aA, AC a, B bB, B b}; Văn phạm G1 là văn phạm cảm ngữ cảnh, văn phạm G2 không phải là văn phạm cảm ngữ cảnh mà là văn phạm ngữ cấu, vì trong G2 có quy tắc AC a vế trái có độ dài 2 còn vế phải có độ dài 1, không thỏa mãn điều kiện của văn phạm cảm ngữ cảnh. Nhưng 2 văn phạm này lại tương đương vì cùng sinh ra ngôn ngữ L={am bn | m>0, n>0}. Ví dụ này chứng tỏ rằng 1 ngôn ngữ là cảm ngữ cảnh thì đồng thời cũng là ngôn ngữ ngữ cấu, tuy nhiên điều ngược lại không đúng. Có ngôn ngữ ngữ cấu không thể có văn phạm cảm ngữ cảnh nào sinh ra được. 3.3. Văn phạm phi ngữ cảnh Văn phạm G=<, , I, R> được gọi là văn phạm phi ngữ cảnh nếu mọi quy tắc thuộc R đều có dạng A với A , V*. Ngôn ngữ do văn phạm phi ngữ cảnh sinh ra gọi là ngôn ngữ phi ngữ cảnh.
- 9. xét: Trong định nghĩa văn phạm phi ngữ cảnh yêu cầu với các quy tắc của R đều có vế trái là 1 ký hiệu không kết thúc, còn vế phải là xâu tùy ý thuộc V*. Yêu cầu này rõ ràng là cũng thỏa mãn điều kiện của văn phạm cảm ngữ cảnh, vì vậy văn phạm phi ngữ cảnh là trường hợp riêng của văn phạm cảm ngữ cảnh. Ví dụ: Xét các văn phạm sau: G1=<1, 1, I, R1> có 1={a, b}; 1={I}; R1={I aIb, I ab}; G2=<2, 2, I, R2> có 2={a, b}; 2={I, A, B, C}; R2={I AC, A aB, BC ACb, AC ab}; Rõ ràng G1 là văn phạm phi ngữ cảnh, còn G2 không phải là văn phạm phi ngữ cảnh mà là văn phạm cảm ngữ cảnh, vì trong G2 có các quy tắc BC ACb và AC ab có vế trái không phải là 1 ký hiệu, không thỏa mãn điều kiện của văn phạm phi ngữ cảnh. Nhưng 2 văn phạm này lại tương đương vì cùng sinh ra ngôn ngữ L={an bn | n>0}. Ví dụ này chứng tỏ rằng 1 ngôn ngữ là phi ngữ cảnh thì đồng thời cũng là ngôn ngữ cảm ngữ cảnh, tuy nhiên điều ngược lại không đúng. Có ngôn ngữ cảm ngữ cảnh không thể có văn phạm phi ngữ cảnh nào sinh ra được. 3.4. Văn phạm chính quy Văn phạm G=<, , I, R> được gọi là văn phạm chính quy nếu mọi quy tắc thuộc R có dạng A aB, A a hoặc có dạng A Ba, A a với A, B , a . Ngôn ngữ do văn phạm chính quy sinh ra gọi là ngôn ngữ chính quy. Nhận xét: Trong định nghĩa văn phạm chính quy yêu cầu các quy tắc của R đều có vế trái là 1 ký hiệu không kết thúc, còn vế phải có thể là 1 ký hiệu kết thúc hoặc có thể là xâu gồm 2 ký hiệu dạng aB, gọi là đệ quy phải, hoặc là có dạng Ba thì gọi là đệ quy trái và trong R chỉ được phép có 1 loại đệ quy (trái hoặc phải). Yêu cầu này rõ ràng là cũng thỏa mãn điều kiện của văn phạm phi ngữ cảnh, vì vậy văn phạm chính quy là trường hợp riêng của văn phạm phi ngữ cảnh. Ví dụ: Xét các văn phạm sau:
- 10. 1, I, R1> có 1={a, b}; 1={I, A}; R1={I aI, I aA, A bA, A b,}; G2=<2, 2, I, R2> có 2={a, b}; 2={I, A, B}; R2={I AabB, A aA, B bB, A , B }; Rõ ràng G1 là văn phạm chính quy, còn G2 không phải là văn phạm chính quy mà là văn phạm phi ngữ cảnh, vì trong G2 có các quy tắc I AabB có vế phải là xâu gồm 4 ký hiệu, không thỏa mãn điều kiện của văn phạm chính quy. Nhưng G1 và G2 lại tương đương vì cùng sinh ra ngôn ngữ L={am bn | m>0, n>0}. Ví dụ này chứng tỏ rằng 1 ngôn ngữ là chính quy thì đồng thời cũng là ngôn ngữ phi ngữ cảnh, tuy nhiên điều ngược lại không đúng. Có ngôn ngữ phi ngữ cảnh không thể có văn phạm chính quy nào sinh ra được. Nhận xét: Loại của ngôn ngữ trùng với loại của văn phạm sinh ra ngôn ngữ đó. Từ các định nghĩa của các loại văn phạm ta thấy khái niệm văn phạm ngữ cấu rộng nhất, nó bao hàm các loại văn phạm còn lại, văn phạm chính quy là hẹp nhất, nó chứa trong tất cả các loại văn phạm khác. Nếu gọi L0 , L1 , L2 , L3 theo thứ tự là lớp ngôn ngữ ngữ cấu, lớp ngôn ngữ cảm ngữ cảnh, lớp ngôn ngữ phi ngữ cảnh và lớp ngôn ngữ chính quy là tập tất cả các văn phạm của mỗi loại tương ứng sinh ra, sẽ có dãy bao hàm thức sau: L3 L2 L1 L0 Có thể chỉ ra rằng tồn tại ngôn ngữ chỉ thuộc L0 mà không thuộc L1, tồn tại ngôn ngữ chỉ thuộc L1 mà không thuộc L2, tồn tại ngôn ngữ chỉ thuộc L2 mà không thuộc L3, tức là các bao hàm thức đều là thực sự, nghĩa là không xảy ra đẳng thức. Biểu đồ Ven sau đây biểu diễn một cách trực quan các bao hàm thức này: L3L2L1L0
- 11. Các dạng bài toán về văn phạm 4.1. Bài toán xác định ngôn ngữ của văn phạm Dạng tổng quát của bài toán này là cho trước 1 văn phạm yêu cầu xác định ngôn ngữ sinh bởi văn phạm đó. Phương pháp chung để giải bài toán này là phân tích các quy tắc của văn phạm đã cho để tìm ra được tất cả các dạng từ có thể tạo được bằng cách áp dụng các quy tắc này. Trong số các quy tắc của văn phạm cần tìm ra những quy tắc mà vế phải chỉ gồm những ký hiệu kết thúc hoặc là xâu rỗng, những quy tắc này có tên gọi là quy tắc kết thúc vì chúng có vai trò kết thúc quá trình sinh các từ của ngôn ngữ. Như vậy, nếu trong văn phạm đã cho không có quy tắc kết thúc thì có thể kết luận ngay văn phạm đã cho sinh ra ngôn ngữ rỗng . Một điểm cần lưu ý là trong văn phạm phải có ít nhất 1 quy tắc có vế trái là I, nếu ngược lại thì cũng khẳng định ngay là văn phạm đã cho sinh ngôn ngữ rỗng . Ví dụ: Hãy xác định ngôn ngữ do văn phạm sau đây sinh ra: Cho văn phạm G=<, , I, R> với: ={a, b}; ={I, A, B}; R={I aA, I bB, A aA, A , B bB, B }; Giải: Để thuận tiện cho trình bày, ta đánh số các quy tắc của R theo thứ tự từ trái qua phải là (1), (2), (3), (4), (5), (6). Xét tất cả những dẫn xuất đầy đủ có thể có trong văn phạm G có dạng D=(I, 1, … , k). Trong R chỉ có 2 quy tắc có vế trái là I là (1) và (2). Nếu D bắt đầu bởi (1) tức là 1=aA, tiếp theo chỉ có thể áp dụng quy tắc (3) hoặc (4). Quy tắc (3) sẽ sinh thêm 1 ký tự kết thúc a và giữ nguyên A, vì vậy áp dụng bao nhiêu lần quy tắc (3) sẽ sinh ra bấy nhiêu a. Quy tắc (4) sẽ triệt tiêu A và kết thúc dẫn xuất đầy đủ. Như vậy nếu D áp dụng (1) đầu tiên thì sẽ sinh ra từ có dạng aa…a với k ký tự a, k>0. Lập luận tương tự, nếu D áp dụng (2) đầu tiên thì sẽ sinh ra từ có dạng bb…b với k ký tự b, k>0. Ngoài 2 dạng từ nêu trên, các dẫn xuất đầy đủ trong G không sinh ra dạng từ nào khác. Từ đó kết luận L(G)={am , bn | m>0, n>0}. 4.2. Bài toán xác định văn phạm sinh ngôn ngữ Dạng tổng quát của bài toán này là cho trước 1 ngôn ngữ, yêu cầu xác định văn phạm sinh ra ngôn ngữ đó. Phương pháp chung để giải bài toán này là phân tích tìm ra những đặc trưng, quy luật của các từ trong ngôn ngữ đã cho, từ đó xây
- 12. các quy tắc để sinh ra các từ đó. Cần lưu ý là khi tạo ra các quy tắc sinh ra các từ cần thiết phải bảo đảm rằng những quy tắc này không sinh ra những từ ngoại lai không thuộc ngôn ngữ đã cho, nghĩa là văn phạm cần tìm phải sinh ra tất cả các từ của ngôn ngữ đã cho và đồng thời không sinh ra bất kỳ một từ nào không thuộc ngôn ngữ đã chỉ định. Ví dụ: Hãy tìm văn phạm sinh ra ngôn ngữ L={am bn m n 0} Giải: Ngôn ngữ đã cho chỉ có 1 dạng từ bắt đầu là 1 dãy a, tiếp theo là 1 dãy b với điều kiện số ký tự a không ít hơn số ký tự b và số lượng b có thể là 0. Trong quá trình tạo ra các từ có dạng này cần chú ý để số lượng a không được ít hơn số lượng b. Như vậy phải có quy tắc sinh ra đồng thời a và b ở 2 phía, là quy tắc I aIb và phải có quy tắc chỉ sinh riêng ra a mà không có b, là quy tắc I aI. Vì số lương b có thể là 0 và khi đó số lượng a cũng có thể là 0 tức là từ rỗng cũng thuộc ngôn ngữ đã cho, vì vậy phải có quy tắc sinh ra từ rỗng I , và đây cũng chính là quy tắc kết thúc. Như vậy chỉ cần 3 quy tắc này có thể tạo tất cả các từ của ngôn ngữ đã cho. Dễ dàng thấy rằng chúng không tạo ra từ ngoại lai nào. Vậy văn phạm cần tìm là G=<, , I, R> với: ={a, b}; ={I}; R={I aIb, I aI, I }; 4.3. Một số ví dụ về văn phạm. Ví dụ 1: Cho văn phạm G=<, , I, R> với: ={a, b}; ={I, A}; R={I I a, I A, A aAb, A ab}; Xác định L(G). Giải: Dẫn xuất đầy đủ trong G chỉ có dạng như sau: D=(I, Ia, … , Iam , Aam , aAbam , … , an Abn am , an+1 bn+1 am ) với m 0, n 0. Từ đây suy ra ngôn ngữ sinh bởi G là L(G)={an bn am | n>0, m 0). Ví dụ 2: Cho văn phạm G=<, , I, R> với: ={a, b}; ={I, A, B}; R={I a I Ba, I A, aB Ba, AB bA, AB A, A };
- 13. định L(G). Giải: Đánh số thứ tự các quy tắc trong R từ (1) đến (6). Để có được dẫn xuất đầy đủ trong G, đoạn đầu phải áp dụng n lần quy tắc (1), sau đó phải áp dụng (2) để triệt tiêu I, thu được xâu có dạng an A(Ba)n với n 0. Ta thấy rằng muốn triệt tiêu B thì phải áp dụng (4) hoặc (5), mà 2 quy tắc này đều có vế trái là AB. Như vậy, muốn triệt tiêu B thì phải áp dụng (3) để chuyển B từ phải sang trái sát A. Ký tự A không sinh ra ký tự nào, chỉ dùng để chuyển B thành b hoặc thành rỗng. Sau khi đã triệt tiêu hết B thì áp dụng (6) để biến A thành rỗng và thu được một từ của ngôn ngữ cần tìm. Từ đây suy ra dạng tổng quát của các từ do văn phạm G sinh ra là: an bm an với n 0 và n m, và ngôn ngữ cần tìm là: L(G)={an bm an n m 0). Ví dụ 3: Cho văn phạm G=<, , I, R> với: ={a, b}; ={I}; R={I II, I aIb, I bIa, I }; Xác định L(G). Giải: Đánh số thứ tự các quy tắc trong R từ (1) đến (4). Các quy tắc (2), (3) và (4) đều tạo ra các xâu có số lượng a và b như nhau, còn quy tắc (1) được dùng để kết hợp với các quy tắc (2), (3) và (4) tạo ra 2 xâu cạnh nhau, mỗi xâu có số lượng a và b như nhau. Từ đây suy ra L(G) là ngôn ngữ gồm những từ có số lượng a và b như nhau, kể cả từ rỗng. L(G)={ {a, b}* trong số lượng ký tự a và b như nhau}. Ví dụ 4: Hãy xác định văn phạm sinh ra ngôn ngữ L={am bn ak m 0, n 0, k 0, m=n+k} Giải: Quá trình tạo ra các từ của ngôn ngữ đã cho thực hiện như sau: phần đầu của dẫn xuất sẽ tạo ra xâu có dạng ak Aak , tức là có dẫn xuất I├ ak Aak với k 0, phần tiếp theo sẽ dùng A tạo ra từ có dạng an bn , tức là có dẫn xuất A├ an bn với n 0. Từ đây suy ra văn phạm cần tìm là: G=<, , I, R> với: ={a, b}; ={I, A}; R={I aIa, I A, A aAb, A };
- 14. dụ 5: Hãy xác định văn phạm sinh ra ngôn ngữ L={ {a, b}* có số lượng ký tự a và số lượng ký tự b đều chẵn} Giải: Quá trình tạo ra các từ của ngôn ngữ đã cho cần chú ý nếu đã tạo ra 1 ký tự a thì phải tạo thêm 1 ký tự a nữa mới được kết thúc, tương tự như vậy đối với ký tự b. Để làm được như vậy thường sử dụng kỹ thuật ghi nhớ bởi ký hiệu không kết thúc. Trong quá trình tạo ra các từ của ngôn ngữ đã cho, vế phải chỉ chứa 1 ký hiệu không kết thúc và chỉ khi nào ký hiệu đó là I thì mới có thể dừng lại bằng cách cho I thành rỗng. Khi trong xâu tạo ra chứa I tức là số lượng a và b đều chẵn, còn nếu chứa A thì số lượng a lẻ và số lượng b chẵn, nếu chứa B thì số lượng b lẻ và số lượng a chẵn, còn nếu chứa C thì số lượng a và b đều lẻ. Từ A muốn chuyển sang I thì phải tạo thêm một ký tự a nữa, từ B muốn chuyển sang I thì phải tạo thêm một b nữa, từ C chỉ có thể chuyển sang A nếu tạo thêm b hoặc chuyển sang B nếu tạo thêm a mà không thể sang I được. Văn phạm cần tìm là: G=<, , I, R> với: ={a, b}; ={I, A, B, C}; R={IaA, IbB, AaI, AbC, BbI, BaC, CaB, CbA, I}; Dễ dàng chứng tỏ rằng G chính là văn phạm cần tìm. Có thể chỉ ra cách tạo một từ bất kỳ có số lượng a và b đều chẵn theo cách lập luận trên. Chẳng hạn, từ abab có dẫn xuất đầy đủ như sau: D=(I, aA, abC, abaB, ababI, abab) 5. Bài tập chƣơng 1 1) Cho văn phạm G = < , , I, R > với: = { 0, 1 }; = { I }; R = { I01I, I }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a. L = { 0n 1n n 0 } b. L = { 0n 1n n 1 } c. L = { (01)n n 0 } d. L = { (01)n n 1 } 2) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I, A, B }; R = { I IAb, I B, bA Ab, B , B aB, BA aB}; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a. L = { am bn m 0, n 0 } b. L = { am bn m n 0 } c. L = { am bn n m 0 } d. L = { am bn m > n 0 } 3) Cho văn phạm G = < , , I, R > với:
- 15. = { a, b }; = { I, A }; R = { I I a, I A, A aAb, A }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a. L = { am bm an m 0, n 0 } b. L = { am bm an m n 0 } c. L = { am bm an m 1, n 1 } d. L = { am bm an m n 1 } 4) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I, A, B }; R = { IAB, AaAb, BbBa, A, B}; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a.L = { am bn ak m n k 0, n = m+k } b.L = { am bn ak m 0, n 0, k 0, m = n+k } c.L = { am bn ak m 0, n 0, k 0, k = m+n } d.L = { am bn ak m 0, n 0, k 0, n = m+k } 5) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I, A, B }; R = { IaIB, IaI, IaabA, ABbAa, ABbA, aBBa, A,B}; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a. L = { am bn ak m n k 0 } b. L = { am bn ak m > n k 0 } c. L = { am bn ak m > n > k 0 } d. L = { am bn ak m > n > k > 0 } 6) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I }; R = { I I I, I a I b, I b I a, I }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a.L = { * có ký tự a và ký tự b xen kẽ nhau} b.L = { * có số lượng ký tự a bằng số lượng ký tự b} c.L = { * có số lượng ký tự a và số lượng ký tự b đều chẵn} d.L = { * } 7) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I }; R = { I a I a, I b I b, I }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a.L = { * chỉ bao gồm 1 loại ký tự a hoặc 1 loại ký tự b} b.L = { * có số lượng ký tự a bằng số lượng ký tự b và đều chẵn} c.L = { * có các ký tự đối xứng nhau} d.L = { * , * , là từ gương của } 8) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I, A, B, C, D }; R = { I AD, A aAa, A , A bB, Ba aB, BD CDb, aC Ca, bC bbB, C , D };
- 16. cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a. L = { am bn am bn m 0, n 0 } b. L = { am bn am bn m 0, n 1 } c. L = { am bn am bn m 1, n 0 } d. L = { am bn am bn m 1, n 1 } 9) Cho văn phạm G = < , , I, R > với: = { a, b }; = { I, A, B, C, D }; R = { I AD, A , A aAaaa, A bbB, Ba aB, BD CDb, aC Ca, bC bbbB, C , D }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a. L = { am bn a2m bn m 0, n 0 } b. L = { am bn a3m b2n m 0, n 0 } c. L = { am b2n a3m bn m 0, n 0 } d. L = { a3m b2n am bn m 0, n 0 } 10) Cho văn phạm G = < , , I, R > với: = { 0, 1 }; = { I, A}; R = { I A0A, A 0A, A 1A, A }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a.L = { * bắt đầu bởi ký tự 0} b.L = { * có số lượng ký tự 0 lớn hơn số lượng ký tự 1} c.L = { * có ít nhất 1 ký tự 1} d.L = { * có ít nhất 1 ký tự 0} 11) Cho văn phạm G = < , , I, R > với: = { 0, 1 }; = { I, A, B}; R = { I 0A, I 1A, A 0B, A 1B, B 0I, B 1I, I }; Hãy cho biết văn phạm G sinh ra ngôn ngữ nào trong số các ngôn ngữ sau: a.L = { * có số lượng ký tự là số chẵn} b.L = { * có số lượng ký tự là số lẻ} c.L = { * có số lượng ký tự là bội số của 3} d.L = { * có đúng 3 ký tự} 12) Cho ngôn ngữ L = { 0n 1n n 0 } sinh bởi văn phạm G = < , , I, R > có = { 0, 1 }; = { I }; Hãy cho biết tập quy tắc R của G là tập nào trong số các tập sau: a. R = { I 0 I 1, I 01 }; b. R = { I 0 I 1, I }; c. R = { I 0 I, I I 1, I }; d. R = { I 0 I, I I 1, I 01 }; 13) Cho ngôn ngữ L={ am bn m 0, n 0} sinh bởi văn phạm G=<, , I, R > có = { a, b }; = { I, A, B }; Hãy cho biết tập quy tắc R của G là tập nào trong số các tập sau: a.R = { I AB, A aA, A , B bB, B }; b.R = { I AB, A aA, A a, B bB, B };
- 17. = { I AB, A aA, A , B bB, B b}; d.R = { I AB, A aA, A a, B bB, B b}; 14) Cho ngôn ngữ L={ am bn m n 0} sinh bởi văn phạm G=< , , I, R > có = { a, b }; = { I, A }; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I aIA, A b, A , I }; b.R = { I aIA, A b, I a, A }; c.R = { I aI, I aIA, I , A b}; d.R = { I aIA, A b, I a, A , I }; 15) Cho ngôn ngữ L={am bm an m 0, n 0} sinh bởi văn phạm G=<, , I, R> có = { a, b }; = { I, A }; Hãy cho biết tập quy tắc R của G là tập nào trong số các tập sau: a.R = { I I a, I A, A aAb, A }; b.R = { I I a, I aAb, A }; c.R = { I I a, I , I aAb, A }; d.R = { I a I, I , I aAb, A }; 16) Cho ngôn ngữ L={am bm an m>0, n>0} sinh bởi văn phạm G=<, , I, R> có = { a, b }; = { I, A }; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I I a, I aAba, A aAb, A }; b.R = { I I a, I Aa, A aAb, A ab}; c.R = { I I a, I aba, I aAba, A aAb, A }; d.R = { I I a, I ab, I Aa, A aAb, A ab}; 17) Cho ngôn ngữ L = { am bn ak m 0, n 0, k 0, n = m+k } sinh bởi văn phạm G = < , , I, R > có = { a, b }; = { I, A, B }; Hãy cho biết tập quy tắc R của G là tập nào trong số các tập sau: a.R = { I AB, A aAb, B bBa, A , B }; b.R = { I AB, A aAb, B Ba, A , B }; c.R = { I AB, A aA, B bBa, A , B }; d.R = { I AB, A aA, B bB, A , B }; 18) Cho ngôn ngữ L = { am bn ak m n k 0 } sinh bởi văn phạm G = < , , I, R > có = { a, b }; = { I, A, B }; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R={IaIB, IaI, IA, ABbAa, ABbA, aBBa, Aa, A, B}; b.R={IaIB, IaI, IA, ABbAa, ABbA, aBBa, A, B};
- 18. IaI, IA, ABbAa, ABbA, aBBa, Aa, B}; d.R={IaIB, IaI, IA, ABbAa, ABbA, aBBa, I, A, B}; 19) Cho ngôn ngữ L ={* có số lượng ký tự a và số lượng ký tự b bằng nhau} sinh bởi văn phạm G = < , , I, R > có = { a, b }; = { I }; Hãy cho biết tập quy tắc R của G là tập nào trong số các tập sau: a.R = { I a I b, I b I a, I }; b.R = { I a I b, I b I a, I ab, I ba}; c.R = { I I I, I a I b, I b I a, I }; d.R = { I I I, I ab, I ba, I }; 20) Cho ngôn ngữ L ={{ a, b }* có số lượng ký tự a và số lượng ký tự b bằng nhau}sinh bởi văn phạm G = < , , I, R > có = { a, b }; = { I }; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I I I, I a I b, I b I a, I }; b.R = { I I I, I a I b, I b I a, I , I ab}; c.R = { I I I, I a I b, I b I a, I , I ba}; d.R = { I I I, I ab, I ba, I ab, I ba}; 21) Cho ngôn ngữ L={am bn am m n 0} sinh bởi văn phạm G=< , , I, R > có = { a, b }; = { I, A }; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I a I Ba, I A, aB Ba, AB bA, AB A, A }; b.R = { I a I Ba, I A, aB Ba, AB bA, AB A, A a}; c.R = { I a I Ba, I A, aB Ba, AB bA, AB A, A , I }; d.R = { I a I Ba, I A, aB Ba, AB bA, AB A, A , B }; 22) Cho ngôn ngữ L = { am bn an bm m 0, n 0 } sinh bởi văn phạm G = < , , I, R > có = { a, b }; = { I, A }; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I a I b, I A, A bAa, A }; b.R = { I a I b, I bAa, A bAa, A }; c.R = { I a I b, I A, I ba, A bAa, A }; d.R = { I a I b, I A, I ab, A bAa, A }; 23) Cho ngôn ngữ L = { am bn an bm m n 0 } sinh bởi văn phạm G = < , , I, R > có = { a, b }; = { I, A, B}; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I a I B b, I A, I ab, AB bAa, aB Ba, A , B }; b.R = { I a I B b, I A, I ba, AB bAa, aB Ba, A , B };
- 19. = { I a I B b, I A, I , AB bAa, aB Ba, A , B }; d.R = { I a I B b, I A, AB bAa, aB Ba, A , B }; 24) Cho ngôn ngữ L = { {0, 1}* có ít nhất 1 ký tự 1} sinh bởi văn phạm G = < , , I, R > có = { 0, 1 }; = { I, A}; Hãy cho biết tập quy tắc R của G không thể là tập nào trong số các tập sau: a.R = { I A1A, A 0A, A 1A, A }; b.R = { I A1A, I 1A, A 0A, A 1A, A }; c.R = { I A1A, I 1, A 0A, A 1A, A }; d.R = { I A1, I 1A, A 0A, A 1A, A }; 25) Cho ngôn ngữ L = {am bn ck m 0, n 0, k 0} sinh bởi văn phạm G = < , , I, R > có = { a, b,c }; = {I, A, B}; Hãy xác định R: a.R = { I aI, I A, A bA, A B, B cB, A }; b.R = { I aI, I A, A bA, A B, B cB, B }; c.R = { I aI, I A, A bA, A cB, B cB, A }; d.R = { I aI, I A, A bA, A cB, B cB, B }; 26) Cho ngôn ngữ L={am b2m c3m m 0} sinh bởi văn phạm G = < , , I, R > có: = { a, b,c }; = {I, A, B}; Hãy xác định R: a.R = { I AB, A aAbbC, Cb bC, CB Bccc, A , B }; b.R = { I AB, A aAbbCC, Cb bC, CB Bccc, A , B }; c.R = { I AB, A aAbbC, Cb bC, CB Bcc, A , B }; d.R = { I AB, A aAbbCC, Cb bC, CB Bcc, A , B }; 27) Cho ngôn ngữ L = {{a,b}* có số lượng ký tự a và số lượng ký tự b khác nhau} sinh bởi văn phạm G = < , , I, R > có: = {a, b}; = {I, A}; Hãy xác định R: a.R = {I aA, I bA, A aAb, A bAa, A AA, A ab}; b.R = {I aA, I bA, A aAb, A bAa, A AA, A }; c.R = {I aAb, I bAa, A aAb, A bAa, A AA, A ba}; d.R = {I aAb, I bAa, A aAb, A bAa, A AA, A }; 28) Hai văn phạm G1, G2 có cùng , còn tập quy tắc sinh tương ứng là R1 và R2: R1 = {I aA, I bB, A aI, A bB, B bI, B aA, I }; R2 = { I bA, I aB, A bI, A aB, B aI, B bA, I }; Tìm phát biểu sai: a. L(G1) = L(G2)
- 20. L(G1) và L(G2) đều có từ abababab c. L(G1) và L(G2) đều có từ rỗng d. L(G1) và L(G2) đều có từ bbbaaa 29)Cho văn phạm G1=<, , I, R1>, G2=<, , I, R2>, với: ={a, b}; ={I, A}; R1={IIa, IbA, AbA, Ab}; R2=R1{IbI} L1, L2 là ngôn ngữ do G1, G2 sinh ra. Tìm nhận xét đúng nhất: a. L1=L2 b. L1L2 c. L2=L1{bn |n>0} d. L2=L1{b} 30)Cho văn phạm G1=<, , I, R1>, G2=<, , I, R2>; ={a, b}; ={I, A, B}; R1={IAB, AaA, Aa, BbB, Bb}; Hãy chọn R2 để G1G2: a. R2={IaIb, Iab} b. R2={IaI, IIb, Iab } c. R2=R1{Ia} d. R2=R1{Ib} 31) Tìm văn phạm sinh ra ngôn ngữ L={ {a, b}* có số lượng ký tự a là số chẵn còn số lượng ký tự b là số lẻ} 32) Tìm văn phạm sinh ra ngôn ngữ L={ {a, b}* có số lượng ký tự a lớn hơn số lượng ký tự b} 33) Tìm văn phạm sinh ra ngôn ngữ L={ {a, b, c}* có số lượng ký tự a là số chẵn, số lượng ký tự b là số lẻ, số lượng ký tự b là số chẵn} 34) Tìm văn phạm sinh ra ngôn ngữ L={am bn ak bt m n k t 0} 35) Tìm văn phạm sinh ra ngôn ngữ L=={am bn a3m b2n m 0, n 0}
- 21. 2 AUTOMAT HỮU HẠN (FINITE AUTOMATA) 1. Định nghĩa Automat hữu hạn (Finite Automata FA) 1.1. Giới thiệu chung Lý thuyết Automat nghiên cứu về các thiết bị, máy tính toán trừu tượng. Vào khoảng năm 1936, khi máy tính chưa ra đời, A. Turing, nhà khoa học người Anh đã nghiên cứu một loại máy trừu tượng có đủ khả năng tính toán như của 1 máy tính như hiện nay, được gọi là máy Turing. Với mục đích mô tả chính xác giới hạn giữa những điều máy tính có thể và không thể làm được, máy Turing đã đặt nền tảng cho khoa học tính toán, khoa học máy tính và là công cụ nghiên cứu về lý thuyết độ phức tạp tính toán. Trong các thập niên 1940 và 1950, các loại máy trừu tượng đơn giản hơn, mà người ta gọi là “Automat hữu hạn” (Finite Automata) đã được nhiều nhà khoa học nghiên cứu, tìm hiểu để mô hình hóa chức năng, hoạt động của não bộ, của các thiết bị tự động, máy tính, … Cũng vào giai đoạn này, N. Chomsky đã nghiên cứu về văn phạm và ngôn ngữ hình thức, có mối quan hệ mật thiết với các automat trừu tượng, làm cơ sở cho một số phần mềm quan trọng, ví dụ như chương trình biên dịch cho máy tính. Để lấy ví dụ đơn giản nhất về FA là ta xét 1 loại công tắc bật/tắt (on/off). Thiết bị này ghi nhớ xem nó đang ở trạng thái “on” (bật) hay là “off” (tắt) và cho phép người sử dụng nhấn 1 nút, gây ra các tác dụng khác nhau tùy thuộc vào trạng thái hiện tại của công tắc. Công tắc này được mô hình hóa bởi một automat hữu hạn có sơ đồ như sau: 1.2. Định nghĩa FA đơn định (DFA)và không đơn định (NFA) Automat hữu hạn là 1 bộ có thứ tự M=<, Q, , q0, F>, trong đó: là tập hợp hữu hạn khác rỗng các ký hiệu vào off on push push start
- 22. Q là tập hợp hữu hạn khác rỗng các các trạng thái q0 là 1 trạng thái thuộc Q gọi là trạng thái ban đầu F là 1 tập con của Q gọi là tập các trạng thái kết thúc gọi là hàm chuyển, có thể là 1 trong 2 dạng sau: Dạng 1: là ánh xạ từ tích Đề các Q x vào Q, : Q x Q, cho tương ứng mỗi cặp (q, a) với q Q và a vào 1 trạng thái xác định q’ thuộc Q: (q, a)=q’. Nếu hàm chuyển có dạng này thì ta gọi là automat hữu hạn đơn định (Deterministic Finite Automata, viết tắt là DFA). Dạng 2: là ánh xạ từ tích Đề các Q x vào tập hợp các tập con của Q (ký hiệu là 2Q ), : Q x 2Q , cho tương ứng mỗi cặp (q, a) với q Q và a vào 1 tập con các trạng thái xác định Q’ thuộc 2Q (Q’ Q): (q, a)=Q’. Nếu hàm chuyển có dạng này thì ta gọi là automat hữu hạn không đơn định (Nondeterministic Finite Automata, viết tắt là NFA). Tập các trạng thái Q của automat M được sử dụng để ghi nhớ trạng thái của M trong quá trình hoạt động. Vì Q là hữu hạn nên M được gọi là automat hữu hạn. FA đoán nhận ngôn ngữ bằng cách đoán nhận từng từ thuộc ngôn ngữ đó. Automat M=<, Q, , q0, F> hoạt động theo cách sau: khi cho xâu vào =x1x2x3 … xn *, M sẽ đoán nhận bằng cách đọc từng ký tự từ trái sang phải, xuất phát từ trạng thái ban đầu q0 và đầu đọc đang ở vị trí có ký hiệu x1. Bước tiếp theo M sẽ chuyển từ trạng thái q0 sang trạng thái mới q1 nào đó được xác định bởi hàm chuyển và đầu đọc dịch chuyển sang phải 1 vị trí tới ký hiệu tiếp theo x2: Trường hợp M là DFA thì q1=(q0 , x1), còn trường hợp M là NFA thì (q0 , x1) là 1 tập hợp con của Q nên q1 (q0 , x1) nếu như (q0,x1), còn nếu như (q0, x1)= thì M sẽ không đọc tiếp được (trường hợp này gọi là “treo máy”) và xâu không đoán nhận được bởi M này. Một cách tổng quát: khi M ở trạng thái qk và đầu đọc đang ở vị trí có ký hiệu xk+1 thì sang bước tiếp theo M sẽ chuyển sang trạng thái mới xác định bởi hàm chuyển và đầu đọc dịch chuyển sang phải 1 vị trí tới ký hiệu tiếp theo nếu vẫn còn ký hiệu để đọc (đối với NFA, có thể xảy ra tình trạng treo máy). Quá trình cứ tiếp tục cho đến khi M đọc xong xâu và khi đó M ở trạng thái p nào đó. Nếu như trạng thái p này thuộc tập trạng thái kết thúc F thì kết luận M đoán nhận được , còn ngược lại (p F hoặc xảy ra treo máy đối với NFA) thì kết luận
- 23. cách đọc này M không đoán nhận được . Sự hoạt động của M đoán nhận xâu vào có thể mô tả bởi sơ đồ như sau: Xâu vào : x1 x2 … xk xk+1 … xn M: q0 q1 … qk-1 qk … qn-1 p Chú ý: Đối với automat M là DFA, giá trị của hàm chuyển (q, a) là 1 trạng thái xác định thuộc Q, tức là khi M ở trạng thái q, đọc ký hiệu a thì M chuyển sang trạng thái do (q, a) xác định, nên với mỗi xâu vào , M chỉ có 1 cách đọc duy nhất; còn đối với automat M là NFA, giá trị của hàm chuyển (q, a) là 1 tập hợp con của Q, tức là khi M ở trạng thái q, đọc ký a thì M có thể chuyển sang 1 trong các trạng thái thuộc tập hợp con này, nên với mỗi xâu vào , M có thể đọc theo nhiều cách khác nhau, nhưng nếu như có 1 cách đọc nào đó để M đoán nhận được xâu vào thì kết luận M đoán nhận được xâu , còn với tất cả các cách có thể đọc được mà M đều không đoán nhận được thì mới kết luận M không đoán nhận được . Để đơn giản cho việc trình bày, có thể viết (q0, )=p, nghĩa là xuất phát từ trạng thái ban đầu q0 với hàm chuyển , sau khi đọc song xâu , automat M ở vào trạng thái p. Ngôn ngữ đoán nhận được bởi automat M, ký hiệu là L(M), là tập hợp tất cả các xâu thuộc * đoán nhận được bởi M: L(M)={ * (q0, ) F} 1.3. Các phương pháp biểu diễn FA Theo định nghĩa và cách thức hoạt động của FA, hàm chuyển là nội dung cốt lõi của 1 FA. Việc biểu diễn FA cần phải thể hiện được hàm chuyển của nó. Vì lẽ đó, người ta có thể biểu diễn FA theo cách chỉ ra bảng chuyển (bảng chứa các giá trị của hàm chuyển) hoặc theo cách vẽ đồ thị biểu diễn quá trình chuyển trạng thái của FA. Phương pháp biểu diễn FA bằng bảng chuyển
- 24. FA M=<, Q, , q0, F> biểu diễn theo cách này cần phải chỉ rõ các thành phần , Q, F, còn hàm chuyển được cho bởi 1 bảng gồm Q hàng cột, có cấu trúc như sau: Đầu mỗi hàng ghi mỗi trạng thái của Q Đầu mỗi cột ghi mỗi ký hiệu của Mỗi ô của bảng tương ứng với hàng chứa trạng thái q và cột chứa ký hiệu a, ghi giá trị của hàm chuyển ứng với cặp (q, a), tức là giá trị (q, a) (giá trị này là 1 trạng thái đối với DFA, là 1 tập hợp con của Q đối với NFA, trường hợp là tập rỗng thì ghi ký hiệu của tập rỗng ). Giả sử cho M=<, Q, , q0, F>, với ={a1, a2, … , an} Q={q0, q1, … , qm} F là 1 tập con nào đó của Q Hàm chuyển được cho bởi bảng chuyển có cấu trúc như sau: a1 a2 … ak … an q0 (q0,a1) (q0,a2) … (q0,ak) … (q0,an) q1 (q1,a1) (q1,a2) … (q1,ak) … (q1,an) … … … … … … … qi (qi,a1) (qi,a2) … (qi,ak) … (qi,an) … … … … … … … qm (qm,a1) (qm,a2) … (qm,ak) … (qm,an) Ví dụ 1: Cho DFA M=<, Q, , q0, F>, với ={0, 1}; Q={q0, q1, q2, q3}; F={q0} Hàm chuyển được cho bởi bảng chuyển như sau:
- 25. 1 q0 q2 q1 q1 q3 q0 q2 q0 q3 q3 q1 q2 Xét xâu vào =110101, quá trình hoạt động của M đọc và đoán nhận như sau: (q0, 1)=q1, (q1, 1)=q0, (q0, 0)=q2, (q2, 1)=q3, (q3, 0)=q1, (q1, 1)=q0 hay viết gọn lại: (q0, 110101)=q0. Sơ đồ biểu diễn qua trình hoạt động của M: Xâu vào : 1 1 0 1 0 1 M: q0 q1 q0 q2 q3 q1 q0 Mà q0 F, chứng tỏ M đoán nhận được xâu , và kết luận L(M). Xét xâu vào =00110, quá trình hoạt động của M đọc và đoán nhận như sau: (q0, 0)=q2, (q2, 0)=q0, (q0, 1)=q1, (q1, 1)=q3, (q3, 0)=q1, hay viết gọn lại: (q0, 00110)=q1. Sơ đồ biểu diễn qua trình hoạt động của M: Xâu vào : 0 0 1 1 0 M: q0 q2 q0 q1 q3 q1 Mà q0 F, chứng tỏ M không đoán nhận được xâu , và kết luận L(M). Ví dụ 2: Cho NFA M=<, Q, , q0, F>, với ={0, 1} Q={q0, q1, q2}
- 26. chuyển được cho bởi bảng chuyển như sau: 0 1 q0 {q0} {q0, q1} q1 {q2} q2 {q2} Lưu ý: M đã cho là NFA, mỗi giá trị của hàm chuyển là 1 tập hợp con của Q, nên việc chọn trạng thái chuyển của M tại mỗi bước có thể khác nhau và dẫn đến các cách đọc khác nhau của M đối với cúng 1 xâu vào. Nói cách khác, với cùng một xâu vào có thể có nhiều cách đọc khác nhau, nhưng trong tất cả các cách đọc đó chỉ cần có 1 cách đọc làm cho M đoán nhận được thì kết luận M đoán nhận được , ngược lại, trong tất cả các cách đọc đó không có cách đọc nào làm cho M đoán nhận được thì kết luận M không đoán nhận được . Như vậy, để chứng tỏ L(M), chỉ cần chỉ ra 1 cách đọc của M sao cho được đoán nhận, còn để chứng tỏ L(M), thì phải xét tất cả các cách đọc có thể có của M đố với và chỉ ra với tất cả cách đọc đó M đều không đoán nhận được . Cho xâu vào =1011, quá trình hoạt động của M đọc và đoán nhận như sau: (q0, 1)=q0, (q0, 0)=q0, (q0, 1)=q1, (q1, 1)=q2, hay viết gọn lại: (q0, 1011)=q2. Sơ đồ biểu diễn qua trình hoạt động của M: Xâu vào : 1 0 1 1 M: q0 q0 q0 q1 q2 Mà q2 F, chứng tỏ M đoán nhận được xâu , và kết luận L(M). Chú ý: Khi ở trạng thái ban đầu q0, đọc ký hiệu vào 1, vì hàm chuyển (q0, 1)={q0, q1} nên có thể cho M chuyển sang trạng thái q0 như cách đọc ở trên hoặc có thể chuyển sang trạng thái q1, khi đó có cách đọc khác như sau: (q0, 1)=q1, (q1, 0)= hay viết gọn lại: (q0, 1011)=.
- 27. đồ biểu diễn qua trình hoạt động của M: Xâu vào : 1 0 1 1 M: q0 q1 Với cách đọc này, M không thể đọc hết được xâu , hay ta gọi là M bị “treo”, nghĩa là M không đoán nhận được xâu theo cách đọc này. Vấn đề đặt ra là làm thế nào để có thể xét hết tất cả các cách đọc khác nhau của NFA đối với một xâu vào cho trước nào đó. Cách thường sử dụng nhất là dùng mô hình cây, gọi là cây đoán nhận của NFA. Đối với mỗi xâu vào =x1x2…xn, cây đoán nhận của NFA M=<, Q, , q0, F> cho được xây dựng như sau: Đỉnh gốc ở mức 0 của cây là trạng thái ban đầu q0, các đỉnh con của q0 thuộc mức 1 của cây là các trạng thái thái thuộc tập con (q0, x1), … , một cách tổng quát, các đỉnh thuộc cùng 1 mức thứ k trong cây là những trạng thái có thể của M sau khi đọc xong ký tự thứ k của xâu vào . Như vậy nếu M đọc hết xâu thì cây đoán nhận sẽ có k+1 mức. Một đường đi trong cây từ gốc đến 1 đỉnh lá nào đó sẽ tương ứng với 1 cách đọc xâu của. Nếu độ dài đường đi bằng n (số ký tự của xâu vào ) chứng tỏ M đọc hết được xâu , còn trường hợp không đọc hết được xâu thì độ dài đường đi nhỏ hơn n. Nếu trong cây đoán nhận lập được tồn tại đường đi độ dài n từ gốc đến 1 đỉnh lá nào đó là 1 trạng thái thuộc F thì kết luận M đoán nhận được xâu còn ngược lại thì kết luận không đoán nhận được. Áp dụng cho ví dụ 2 ở trên, cây đoán nhận của xâu vào =1011 là: q0 q1q0 q0 q1q0 q1q0 q2
- 28. cây đoán nhận tạo được, ta thấy M có thể đọc xâu vào =1011 theo 4 cách khác nhau, trong số đó có 1 cách dẫn đến “treo máy”, 3 cách đọc hết được xâu , nhưng chỉ có 1 cách đoán nhận được xâu đã cho, đó là cách đọc ứng với đường đi từ gốc q0 tới đỉnh là q2 F. Phương pháp biểu diễn FA bằng đồ thị chuyển Một FA M=<, Q, , q0, F> biểu diễn theo cách này không cần phải chỉ rõ các thành phần, mà trong đồ thị chuyển có thể diễn đạt toàn bộ các thành phần của nó. Đồ thị chuyển của M là 1 đồ thị có hướng, mỗi đỉnh là 1 trạng thái của Q chứa trong 1 vòng tròn nhỏ, những đỉnh ứng với các trạng thái thuộc F được chứa trong 1 vòng tròn kép (2 vòng tròn nhỏ lồng nhau). Để chỉ trạng thái ban đầu q0 của M, có mũi tên trỏ vào đỉnh chứa q0 kèm theo chữ start hoặc không. Đỉnh chứa trạng thái ban đầu: Đỉnh chứa trạng thái q thuộc Q, đỉnh chứa trạng thái p thuộc F: Hàm chuyển được biểu diễn bởi các cung của đồ thị theo quy tắc sau: Nếu (q, a)=p, thì sẽ tương ứng với 1 cung đi từ đỉnh chứa trạng thái q đến đỉnh chứa trạng thái p và trên cung này sẽ ghi ký hiệu a: Như vậy đối với DFA thì từ mỗi đỉnh của đồ thị ứng với mỗi ký hiệu của sẽ có đúng 1 cung đi ra, nghĩa là số lượng cung đi ra từ mỗi đỉnh của đồ thị là như nhau và đều bằng lực lượng của . Còn đối với NFA thì từ mỗi đỉnh q của đồ thị ứng với mỗi ký hiệu a của có số cung đi ra đúng bằng số phần tử của tập con (q, a), số lượng này có thể là 0, 1, 2, … , nghĩa là số lượng cung đi ra từ mỗi đỉnh của đồ thị có thể rất khác nhau. Xét FA trong ví dụ 1 ở trên, là DFA, biểu diễn bởi đồ thị chuyển như sau q0 start q0 q p q a p 1 q1 q3 q2 1 1 1 0 0 0 0 q0 1 q1 q3 q2 1 1 1 0 0 0 0 q0 1 q1 q3 q2 1 1 1 0 0 0 0 q0 h.1
- 29. FA trong ví dụ 2 ở trên, là NFA, biểu diễn bởi đồ thị chuyển như sau Nhận xét: Hoạt động của FA M=<, Q, , q0, F> đọc và đoán nhận xâu vào =x1x2x3 … xn * trong trường hợp M biểu diễn bởi đồ thị chuyển như sau: Xuất phát từ đỉnh q0 theo cung chứa ký hiệu x1 đi đến đỉnh q1 xác định bởi hàm chuyển (q0, x1), tiếp theo từ đỉnh q1 đi theo cung chứa ký hiệu x2 đi đến đỉnh q2 xác định bởi hàm chuyển (q1,x2), … , quá trình tiếp tục cho đến khi đọc hết xâu hoặc buộc phải dừng lại không thể đi tiếp được (trường hợp đối với NFA). Giả sử sau khi đọc xong xâu , M ở trạng thái ứng với đỉnh p của đồ thị chuyển, tức là (q0, )=p, quá trình đọc xâu tương ứng với 1 đường đi trong đồ thị xuất phát từ đỉnh q0 đi qua n cung (n là số ký tự của xâu vào ), mỗi cung ứng với 1 ký tự cần đọc, đỉnh kết thúc của đường đi là đỉnh p. Như vậy việc đoán nhận được xâu vào của M tương đương với sự tồn tại 1 đường đi trong đồ thị xuất phát từ đỉnh q0 qua các cung tương ứng từng ký tự của và kết thúc tại 1 đỉnh nào đó thuộc F (đỉnh ký hiệu bởi đường tròn kép). Từ nhận xét này có thể áp dụng đồ thị chuyển để xác định ngôn ngữ đoán nhận được bởi FA. Ngôn ngữ đoán nhậnđược bởi FA M=<, Q, , q0, F> có đồ thị chuyển biểu diễn bởi h.1 ở trên (FA trong ví dụ 1) xác định như sau: Xuất phát từ q0, đường đi qua các cung và lại trở về q0 thì phải qua số lượng cung 0 là 1 số chẵn, phải qua số lượng cung 1 cũng là 1 số chẵn. đường đi dừng ở đỉnh q1 khi số cung 1 là số lẻ, dừng ở đỉnh q2 khi số cung 0 là số lẻ, dừng ở đỉnh q3 khi số cung 0 là số lẻ và số cung 1 cũng là số lẻ. Từ đây suy ra những xâu ứng với đường đi từ q0 và trở về q0 phải có số bit 0 là chẵn và số bit 1 cũng chẵn, và ngôn ngữ đoán nhận được bởi M là ngôn ngữ chứa các xâu gồm có số lượng chẵn ký hiệu 0 và số lượng chẵn ký hiệu 1. Ngôn ngữ đoán nhận được bởi FA M=<, Q, , q0, F> có đồ thị chuyển biểu diễn bởi h.2 ở trên (FA trong ví dụ 2) xác định như sau: Xuất phát từ q0, đường đi qua các cung và đến được q2 thì phải có 2 cung 1 liền nhau. Khi đã ở đỉnh q2 thì chỉ có thể đi theo cung 1 và vẫn ở đỉnh q2. Khi ở đỉnh q0 có thể đi theo cung 0 hoặc 1 và vẫn ở lại q0. Từ đây suy ra những xâu ứng với đường đi từ q0 đến q2 có kết thúc 1 q1 1 q0 1 0, 1 q2 1 h.2
- 30. 11, và ngôn ngữ đoán nhận được bởi M là ngôn ngữ chứa các xâu bit 0, 1 có kết thúc bởi 11. 1.4. Sự tương đương giữa DFA và NFA Theo định nghĩa của DFA và NFA, có thể thấy rằng DFA là trường hợp riêng của NFA vì hàm chuyển của DFA có thể coi là trường hợp riêng của hàm chuyển của NFA khi mỗi trạng thái của Q là 1 tập con gồm 1 phần tử. Như vậy ngôn ngữ đoán nhận được bởi 1 DFA nào đó thì cũng sẽ được đoán nhận bởi 1 NFA tương ứng. Nếu ta gọi lớp các ngôn ngữ đoán nhận được bởi DFA là L(DFA) và lớp các ngôn ngữ đoán nhận được bởi NFA là L(NFA), thì có bao hàm thức L(DFA) L(NFA). Vấn đề đặt ra là bao hàm thức này có thực sự hay không, hay nói cách khác, lớp ngôn ngữ đoán nhận được bởi DFA có thực sự “nhỏ hơn” lớp ngôn ngữ đoán nhận được bởi NFA hay không? Hay nói cách khác, hai lớp ngôn ngữ này có trùng nhau hay không? Nếu chúng trùng nhau thì người ta nói đến sự tương đương giữa DFA và NFA, theo nghĩa 1 ngôn ngữ đoán nhận được bởi DFA thì cũng đoán nhận được bởi NFA và ngược lại. Câu trả lời là khẳng định, được phát biểu bởi dịnh lý sau đây: Định lý: Lớp ngôn ngữ đoán nhận được bởi DFA trùng với lớp ngôn ngữ đoán nhận được bởi NFA. Chứng minh: Nếu ta gọi lớp các ngôn ngữ đoán nhận được bởi DFA là L(DFA) và lớp các ngôn ngữ đoán nhận được bởi NFA là L(NFA), thì ta cần phải chứng minh đẳng thức: L(DFA)=L(NFA), hay cần chứng minh đồng thời hai bao hàm thức L(DFA) L(NFA) và L(NFA) L(DFA). Giả sử có ngôn ngữ L1 L(DFA), khi đó sẽ tồn tại 1 DFA M1=<, Q, 1, q0, F> sao cho L1=L(M1). Ta xây dựng 1 NFA N1=<, Q, 1’, q0, F> dựa theo M như sau: các thành phần của N1 trùng với các thành phần của M1 ngoại trừ hàm chuyển, của M1 là 1, còn của N1 là 1’. Hàm chuyển 1’ của N1 xác địng như sau: 1’: Q x 2Q , cho tương ứng mỗi cặp (q, a) với q Q và a vào 1 tập con gồm 1 phần tử là trạng thái xác định bởi hàm chuyển 1(q, a) của M1. Theo cách định nghĩa này thì sự hoạt động của M1 và N1 là hoàn toàn như nhau, và N1 cũng đoán nhận được ngôn ngữ L1, hay suy ra L1 L(NFA).
- 31. nếu L1 L(DFA) thì L1 L(NFA) vậy suy ra L(DFA) L(NFA) (1) Giả sử có ngôn ngữ L2 L(NFA), khi đó sẽ tồn tại 1 NFA N2=<, Q, 2, q0, F> sao cho L2=L(N2). Ta xây dựng 1 DFA M2=<’, Q’, 2’, p0, F’> dựa theo N như sau: ’=, Q’=2Q , p0={q0}, F’={U Q U F }, hàm chuyển 2’ xác định như sau: 2’: Q’ x ’ Q’, cho tương ứng mỗi cặp (q’, a) với q’ Q’ và a ’ vào 1 phần tử xác định p’ thuộc Q’ là 1 tập con của Q xác định bởi hợp các tập con 2(q, a) với các phần tử q q’. q’ Q’, a ’: 2’(q’, a)= q'q a)(q,δ2 Theo cách định nghĩa này thì N2 và M2 đoán nhận cùng 1 ngôn ngữ, hay nói cách khác L2=L (M2). Vậy nếu L2 L(NFA) thì L2 L(DFA) vậy suy ra L(NFA) L(DFA) (2). Từ (1) và (2) ta có điều phải chứng minh. Nhận xét: Để xây dựng DFA tương đương với NFA cho trước, thực hiện theo cách chứng minh định lý ở trên trong trường hợp tập Q có nhiều trạng thái sẽ cho DFA có số trạng thái rất lớn và dẫn đến 1 DFA rất phức tạp. Trong thực hành, việc tìm DFA tương đương với NFA cho trước có thể thực hiện trực tiếp bằng cách giải bài toán xây dựng DFA đoán nhận ngôn ngữ cho trước. Ví dụ: Hãy xây dựng DFA tương đương với NFA sau đây Theo phương pháp chỉ ra trong chứng minh định lý trên thì DFA cần tìm là M=<, Q, , p0, F>, với các thành phần như sau: ={0, 1} Q={, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}} p0={q0} F={{q2}, {q0, q2}, {q1, q2}, {q0, q1, q2}} Để đơn giản cho việc vẽ đồ thị chuyển, ta kí hiệu lại các trạng thái của Q theo đúng thứ tự liệt kê ở trên như sau: 1 q1 0 q0 0, 1 q2 0
- 32. p0, p1, p2, p3, p4, p5, p6} Đồ thị chuyển cần tìm là: Có thể xây dựng DFA tương đương theo cách khác: Dễ dàng thấy rằng ngôn ngữ đoán nhận được bởi NFA đã cho là ngôn ngữ gồm những xâu bit 0, 1 có kết thúc là 00. DFA đoán nhận ngôn ngữ này có đồ thị chuyển là: Thực ra cũng có thể đưa đồ thị chuyển ở h.3 về h.4 nếu như lược bỏ khỏi đồ thị này những đỉnh và những cung thừa. Theo cách xây dựng DFA tương đương với NFA chỉ ra trong chứng minh định lý là phương pháp có tính tổng quát, luôn đúng trong mọi trong hợp. Theo cách này, nếu số trạng thái của NFA là n thì số trạng thái của DFA tương đương tìm được sẽ có số trạng thái là 2n . Nói chung thì có thể lược bỏ đi 1 số đỉnh và cung thừa để thu được đồ thị chuyển đơn giản hơn và từ đó có DFA với số trạng thái ít hơn. Tuy nhiên không phải lúc nào cũng lược bỏ được như vậy. Nhận xét: Nếu 2 FA, một là DFA còn một là NFA cùng đoán nhận 1 ngôn ngữ thì nói chung số trạng thái của NFA ít hơn và đồ thị chuyển của NFA cũng đơn giản hơn. Vì vậy, do sự tương đương giữa 2 loại FA, nên khi gặp bài toán tìm FA đoán nhận ngôn ngữ cho trước, nếu không nói rõ loại FA nào thì nói chung nên xây dựng NFA, vì loại FA này đơn giản và dễ xây dựng hơn. Trong những trường hợp cần tìm DFA đoán nhận ngôn ngữ cho trước, nhưng nếu tìm NFA tương p3 0 p0 1 p6 0 0 1 p1 p4 01 p2 0 p6 1 0, 1 10 1 0, 1 h.3 q1 0 q0 1 q2 0 0 1 1 h.4
- 33. đơn giản hơn thì có thể tìm NFA trước, sau đó theo phương pháp chỉ ra ở trên để xác định DFA cần tìm. 2. Ngôn ngữ chính quy và biểu thức chính quy 2.1. Ngôn ngữ chính quy Ở chương 1 đã định nghĩa về các loại văn phạm và ngôn ngữ sinh bởi văn phạm tương ứng. Việc xác định kiểu ngôn ngữ thông qua văn phạm có những lúc bất tiện, vì vậy người ta đưa ra các tiếp cận khác để xác định loại ngôn ngữ không cần phải xét đến văn phạm sinh ra ngôn ngữ đó. Đối với ngôn ngữ chính quy, chúng ta có thể định nghĩa theo cách khác, xuất phát từ khái niệm tập hợp. Xét bảng hữu hạn ký hiệu gọi là bảng chữ cái . Ký hiệu * là tập tất cả các xâu, kể cả xâu rỗng tạo bởi các ký hiệu của , còn ký hiệu + là tập tất cả các xâu khác rỗng tạo bởi các ký hiệu của , hay nói cách khác: *=+ {}. Như vậy, một tập con của * chính là một ngôn ngữ trên , còn * cũng là một ngôn ngữ (lớn nhất) trên . Trên tập hợp tất cả các ngôn ngữ trên chúng ta xét các phép toán sau: Phép hợp: ký hiệu . Hợp của 2 ngôn ngữ E1 và E2 là 1 ngôn ngữ gồm tất cả những từ thuộc E1 hoặc thuộc E2. E1 E2={ E1 hoặc E2} Phép nhân: ký hiệu là dấu chấm “.”. Cho 2 ngôn ngữ E1 và E2. Phép nhân E1 với E2 ký hiệu E1.E2 là 1 ngôn ngữ gồm tất cả những từ ghép 1 từ của E1 với 1 từ của E2 E1. E2={ E1 và E2} Phép lặp: Cho 2 ngôn ngữ E trên , phép lặp của E ký hiệu là E+ , là 1 ngôn ngữ vô hạn nhận được từ phép hợp của các ngôn ngữ là các lũy thừa bậc 1, bậc 2, … của E E+ =E E2 E3 … , ký hiệu Ek =E.E…E (k lần) Phép lặp mở rộng của E, ký hiệu là E*, chính là E+ hợp với xâu rỗng: E*=E+ {} Ngôn ngữ sơ cấp trên : Giả sử ={a1, a2, … , an}, các ngôn ngữ và ngôn ngữ chỉ gồm 1 ký hiệu của , tức là các ngôn ngữ {ai}, i=1, 2, … , n gọi là ngôn ngữ sơ cấp.
- 34. nghĩa: a) Các ngôn ngữ sơ cấp trên là ngôn ngữ chính quy trên b) Nếu E và F là 2 ngôn ngữ chính quy trên thì E F, E.F, E+ cũng là ngôn ngữ chính quy trên c) Không có ngôn ngữ chính quy nào khác trên ngoài các ngôn ngữ chính quy được định nghĩa tại các mục a) và b) ở trên. 2.2. Biểu thức chính quy Ngôn ngữ chính quy được định nghĩa qua tập hợp và các phép toán tập hợp nên để diễn đạt các ngôn ngữ chính quy người ta đưa ra biểu thức chính quy. Định nghĩa: a) là biểu thức chính quy biểu diễn ngôn ngữ rỗng. b) Nếu a thì a là biểu thức chính quy biểu diễn ngôn ngữ {a} c) Nếu r, s là 2 biểu thức chính quy trên biểu diễn 2 ngôn ngữ chính quy tương ứng là R và S. Khi đó: (r) (s) là biểu thức chính quy biểu diễn ngôn ngữ R S (r).(s) là biểu thức chính quy biểu diễn ngôn ngữ R.S (r)+ , (r)* là biểu thức chính quy biểu diễn ngôn ngữ R+ , R*. Chú ý: Với phép hợp có thể thay ký hiệu bởi ký hiệu + Có thể sử dụng các cặp dấu ngoặc đơn (…) để chỉ phạm vi và thứ tự thực hiện phép toán trong biểu thức chính quy. Ví dụ: Biểu thức chính quy (0+1)* 00(0+1)* xác định ngôn ngữ gồm những xâu bit 0, 1 có chứa cặp 00. Biểu thức chính quy (0+1)+ 00(0+1)+ xác định ngôn ngữ gồm những xâu bit 0, 1 có chứa cặp 00 giữa 2 xâu bit 0,1 khác rỗng. Từ định nghĩa của biểu thức chính quy ta có kết luận sau:
- 35. ngôn ngữ chính quy trên đều nhận được từ các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu hạn lần các phép toán hợp, nhân và lặp. Ngôn ngữ chính quy là vô hạn nếu trong biểu thức chính quy của nó có chứa phép lặp. Một ngôn ngữ trên là ngôn ngữ chính quy khi và chỉ khi nó được biểu diễn bởi 1 biểu thức chính quy. Lớp ngôn ngữ chính quy trên là lớp ngôn ngữ nhỏ nhất chứa các tập hữu hạn và đóng đối với các phép toán hợp, nhân và lặp. 2.3. Thuật toán Thompson Thuật toán này xây dựng 1 NFA đoán nhận ngôn ngữ chính quy cho bởi 1 biểu thức chính quy cho trước. Input: biểu thức chính quy r trên Output: NFA đoán nhận ngôn ngữ chính quy biểu diễn bởi r Trước hết tách biểu thức chính quy r thành các biểu thức chính quy thành phần biểu diễn các ngôn ngữ sơ cấp trên : r1, r2, … , rk. Sau đó áp dụng các luật 1, luật 2 để xây dựng các NFA: N1, N2, … , Nk tương ứng đoán nhận các ngôn ngữ chính quy biểu diễn bởi các biểu thức chính quy r1, r2, … , rk. Cuối cùng áp dụng luật 3 để xây dựng NFA đoán nhận ngôn ngữ chính quy biểu diễn bởi biểu thức chính quy r đã cho. Luật 1: đối với ký hiệu , xây dựng NFA đoán nhận ngôn ngữ {} như sau: Với i là trạng thái ban đầu, f là trạng thái kết thúc. Luật 2: đối với ký hiệu a , xây dựng NFA đoán nhận ngôn ngữ {a} như sau: Với i là trạng thái ban đầu, f là trạng thái kết thúc. Luật 3: Giả sử N(s) và N(r) là các NFA đoán nhận các ngôn ngữ chính quy biểu diễn bởi các biểu thức chính quy thành phần s và r tương ứng. 1 i f 1 i fa
- 36. Đối với biểu thức chính quy (s) (r) ta xây dựng NFA đoán nhận ngôn ngữ biểu diễn bởi biểu thức chính quy (s) (r) như sau: Với i là trạng thái ban đầu, f là trạng thái kết thúc của N và N tạo thành bằng cách tổ hợp hai NFA thành phần N(s) và N(r) theo sơ đồ bảng chuyển trên. b) Đối với biểu thức chính quy (s) .(r) ta xây dựng NFA đoán nhận ngôn ngữ biểu diễn bởi biểu thức chính quy (s) .(r) như sau: Với i là trạng thái ban đầu, f là trạng thái kết thúc của N và N tạo thành bằng cách tổ hợp hai NFA thành phần N(s) và N(r) theo sơ đồ bảng chuyển trên, bằng cách lấy trạng thái ban đầu của N(s) là trạng thái ban đầu của N, lấy trạng thái kết thúc của N(r) là trạng thái kết thúc của N. c) Đối với biểu thức chính quy (r)+ ta xây dựng NFA đoán nhận ngôn ngữ biểu diễn bởi biểu thức chính quy (r)+ như sau: Với i là trạng thái ban đầu, f là trạng thái kết thúc của N. d) Đối với biểu thức chính quy (r)* ta xây dựng NFA đoán nhận ngôn ngữ biểu diễn bởi biểu thức chính quy (r)* như sau: i f N(s) N(r) i f N(s) N(r) i f N(r) i f N(r)
- 37. i là trạng thái ban đầu, f là trạng thái kết thúc của N. 2.4. Tính chất của ngôn ngữ chính quy Lớp tất cả các ngôn ngữ chính quy trên là đóng đối với các phép toán hợp, giao, hiệu, lấy phần bù, nhân ghép và lặp. Tính đóng của lớp tất cả các ngôn ngữ chính quy trên đối với các phép toán hợp, nhân ghép và lặp được chứng minh dựa trên định nghĩa của biểu thức chính quy. Với các phép toán khác có thể chứng minh như sau: Phép hiệu: Giả sử R1 và R2 là 2 ngôn ngữ chính quy trên . Gọi R=R1 R2. Giả sử M1 và M2 là 2 FA đoán nhận R1 và R2, với M1=<, Q1, 1, q1, F1> và M2=<, Q2, 2, q2, F2>. Ta xây dựng FA M đoán nhận R như sau: M=<, Q, , q0, F>, với Q=Q1 x Q2, q0=(q1, q2), F=F1 x (Q2 F2), : Q x Q được xác định: ((q, q’), a)=(1(q, a), 2(q’, a)), với q Q1, q’ Q2, a . Với cách xây dựng M như vậy thì L(M)=R, suy ra R là ngôn ngữ chính quy. Phép lấy phần bù: Nếu R là ngôn ngữ chính quy trên thì phần bù của R ký hiệu là R cũng là ngôn ngữ chính quy. Ta chỉ cần chỉ ra rằng tồn tại FA đoán nhận ngôn ngữ R . Giả sử M=<, Q, , q0, F> là FA đoán nhận ngôn ngữ chính quy R, khi đó M’=<, Q, , q0, F’> với F’=Q F sẽ là FA đoán nhận ngôn ngữ R , hay R cũng là ngôn ngữ chính quy. Phép giao: Giả sử R1 và R2 là 2 ngôn ngữ chính quy, ta có thể biểu diễn phép giao của 2 ngôn ngữ qua các phép hợp và phủ định: R1 R2= 21 RR Suy ra R1 R2 cũng là ngôn ngữ chính quy.
- 38. Quan hệ giữa FA và ngôn ngữ chính quy 3.1. Văn phạm chính quy mẫu Văn phạm chính quy suy rộng: Văn phạm G=<, , I, R> được gọi là văn phạm chính quy suy rộng nếu mọi quy tắc trong R đều có dạng A aB, A a hoặc có dạng A , trong đó A, B , a , là xâu rỗng. Chú ý: Văn phạm chính quy suy rộng khác văn phạm chính quy là có xuất hiện quy tắc có dạng A , quy tắc này được gọi là quy tắc rỗng. Dễ dàng chứng minh được rằng với văn phạm chính quy suy rộng G luôn tìm được văn phạm chính quy G’ sao cho L(G’)=L(G) {}. Văn phạm chính quy mẫu: Văn phạm chính quy suy rộng được gọi là văn phạm chính quy mẫu nếu không có quy tắc dạng A a. Định lý: Với mỗi văn phạm chính quy suy rộng luôn tồn tại văn phạm chính quy mẫu tương đương. Chứng minh: Giả sử G=<, , I, R> là văn phạm chính quy suy rộng. Bổ sung thêm 1 ký hiệu K và , và đặt ’= {K}. Trong R, với mỗi quy tắc dạng A a thay thế bởi cặp quy tắc A aK, K , còn các quy tắc khác giữ nguyên, thu được tập quy tắc mới gọi là R’. Kết quả được văn phạm G’=<, ’, I, R’> là văn phạm chính quy mẫu và L(G)=L(G’), ta có điều phải chứng minh. 3.2. Đồ hình của văn phạm chính quy mẫu Cho văn phạm chính quy mẫu G=<, , I, R>. Xây dựng 1 đồ thị có hướng dựa theo văn phạm G như sau: Mỗi đỉnh là 1 ký hiệu không kết thúc của được khoanh bởi 1 vòng tròn nhỏ. Nếu A aB là 1 quy tắc của R thì sẽ có 1 cung đi từ đỉnh A đến đỉnh B và trên cung này sẽ được đánh dấu bởi ký hiệu kết thúc a. Đỉnh chứa ký hiệu I gọi là đỉnh ban đầu và có một mũi tên trỏ vào, nếu A là 1 quy tắc của R thì đỉnh chứa ký hiệu A gọi là đỉnh kết thúc và được khoanh bởi 2 vòng tròn lồng nhau. Đồ thị tạo được theo quy tắc này được gọi là đồ hình của văn phạm G. Ví dụ: Cho văn phạm chính quy mẫu G=<, , I, R>, với các thành phần: ={a, b}; ={I, A, B, C};
- 39. aI, I aA, A bA, A bB, B } Đồ hình của G được xây dựnh như sau: Nhận xét: - Đồ hình của văn phạm chính quy mẫu có cấu trúc giống như một FA. - Vì mỗi văn phạm chính quy luôn tìm được 1 văn phạm chính quy mẫu tương đương (có thể sai khác 1 từ rỗng), nên với mỗi văn phạm chính quy cũng có thể xây dựng được 1 đồ hình tương ứng. - Một dẫn xuất đầy đủ trong văn phạm chính quy G tương ứng với 1 đường đi trong đồ hình tương ứng xuất phát từ đỉnh ban đầu I đến một đỉnh kết thúc nào đó. 3.3. Quan hệ giữa FA và ngôn ngữ chính quy Từ nhận xét ở trên ta nhận thấy có mối liên hệ chặt chẽ giữa văn phạm chính quy, biểu thức chính quy, FA. Mối liên hệ này liên quan đến lớp ngôn ngữ chính quy, được phát biểu bởi định lý sau: Định lý: Lớp ngôn ngữ chính quy trùng với lớp ngôn ngữ do văn phạm chính quy sinh ra, trùng với lớp ngôn ngữ đoán nhận được bởi FA. Một ngôn ngữ đoán nhận được bởi FA khi và chỉ khi ngôn ngữ đó là ngôn ngữ chính quy. 4. Bổ đề bơm Ngôn ngữ chính quy gắn liền với FA. Để phân biệt ngôn ngữ chính quy với các loại ngôn ngữ khác, dựa trên đặc trưng về số lượng hữu hạn trạng thái của automat, người ta đưa ra một dấu hiệu đặc biệt gọi là bổ đề bơm như sau: Bổ đề: Nếu L là ngôn ngữ chính quy thì tồn tại hằng số n (phụ thuộc vào L) sao cho với mỗi xâu L với l() n đều có thể tách thành 3 xâu con =xyz sao cho y và l(xy) n thì với mọi k 0 có xâu xyk z cũng thuộc L. Tức là chúng ta luôn I B a A b a b
- 40. thể tìm được một xâu con y khác rỗng trong xâu đã cho sao cho có thể “bơm lên”, nghĩa là lặp lại một số lần tùy ý để thu được xâu mới cũng thuộc L. Chứng minh: Giả sử L là ngôn ngữ chính quy, thế thì sẽ tồn tại một automat hữu hạn M=<, Q, , q0, F> sao cho L=L(M). Giả sử số trạng thái của M là n. Xét xâu =a1a2…am với m n và mỗi ai là 1 ký hiệu kết thúc của M. Với mỗi i=0, 1, … , n gọi pi là trạng thái của M sau khi đã đọc xâu từ a1 đến ai tức là (q0, a1a2…ai)=pi với p0=q0 Theo nguyên lý chuồng chim bồ câu, chúng ta không thể có n+1 trạng thái pi khác nhau vì M chỉ có n trạng thái, do đó chắc chắn tìm được 2 số nguyên khác nhau i, t với sao cho: 0 i <t n và pi=pt. Bây giờ tách thành xyz như sau: x=a1a2…ai y=ai+1ai+2…at z=at+1at+2…am Như vậy ta có: (q0, x)=pi , (pi, y)=pt=pi Nghĩa là M xuất phát từ trạng thái pi đọc hết xâu y thì lại quay lại đúng trạng thái pi. Vì vậy, có thể lặp lại việc đọc xâu con y bao nhiêu lần tùy thích thì sau khi đọc xong M vẫn ở trạng thái pi, suy ra M đoán nhận được xâu thì cũng đoán nhận được xâu xyk z với k là số tùy ý k 0 và y khác rỗng. đpcm. Bổ đề bơm thường được áp dụng để chứng minh một ngôn ngữ có phải chính quy hay không, ví dụ: Chứng tỏ rằng ngôn ngữ L={1n n là số nguyên tố} không phải ngôn ngữ chính quy. Ta chứng minh bằng phản chứng. Giả sử ngược lại, L là ngôn ngữ chính quy, theo bổ đề bơm thì tồn tại hằng số n thỏa mãn điều kiện của bổ đề. Xét số nguyên pn+2 và đặt =1p . Ta tách =xyz với y và l(xy) n. Đặt m=l(y), suy ra l(xz)=p-m. Bây giờ xét xâu xyp-m z, theo bổ đề bơm thì xâu này cũng thuộc L. Xét độ dài xâu xyp-m z: l(xyp-m z)=l(xz) + (p-m)l(y)=p-m + (p-m)m=(m+1)(p-m).
- 41. m>0 nên m+1>1; p n+2 m+2 suy ra p-m 2. suy ra (m+1)(p-m) không phải là số nguyên tố. Điều này mâu thuẫn với khẳng định xâu xyp-m z thuộc L. Mâu thuẫn này chứng tỏ điều giả sử ngôn ngữ L là ngôn ngữ chính quy là sai, vậy L không phải chính quy. Có đpcm. 5. Bài tập chƣơng 2 1) Cho Automat M = <, Q, , q0 , F > với: = { 0, 1 }; Q = { q0 , q1 }; F = { q0 }; hàm chuyển cho bởi bảng sau: 0 1 q0 q1 q1 q1 q0 q0 Hãy tìm ngôn ngữ đoán nhận được bởi M trong số các ngôn ngữ sau: a. L = * b. L = + c. L = { * và l() là số chẵn} d. L = { + và l() là số chẵn } 2) Cho Automat M = <, Q, , q0 , F > với: = { 0, 1 }; Q = { q0 , q1 , q2 }; F = { q0 }; hàm chuyển cho bởi bảng sau: 0 1 q0 q1 q0 q1 q2 q1 q2 q0 q2 Hãy tìm ngôn ngữ đoán nhận được bởi M trong số các ngôn ngữ sau: a.L = { * và có số lượng ký tự 0 là số lẻ} b.L = { * và có số lượng ký tự 0 là bội số của 2} c.L = { * và có số lượng ký tự 0 là bội số của 3} d.L = { * và có số lượng ký tự 1 là bội số của 2} 3) Cho Automat M = <, Q, , q0 , F > với: = { 0, 1 }; Q = { q0 , q1 }; F = { q1 }; hàm chuyển cho bởi bảng sau: 0 1 q0 {q0} { q0,q1} q1 {q1}
- 42. tìm ngôn ngữ đoán nhận được bởi M trong số các ngôn ngữ sau: a.L = { 0m 12n m 0, n 0 } b.L = { 1 * } c.L = { 11 * } d.L = { 111 * } 4) Cho Automat M = <, Q, , q0 , F > với: = { 0, 1 }; Q = { q0 , q1 , q2 }; F = { q0 }; hàm chuyển cho bởi bảng sau: 0 1 q0 q1 q1 q1 q2 q2 q2 q0 q0 Hãy tìm ngôn ngữ đoán nhận được bởi M trong số các ngôn ngữ sau: a. L = * b. L = + c. L = { * và l()là bội số của 3} d. L = { * và l()là số lẻ } 5) Cho Automat M = <, Q, , q0 , F > với: = { 0, 1 }; Q = { q0 , q1 }; F = { q1 }; hàm chuyển cho bởi bảng sau: 0 1 q0 { q0,q1} {q0} q1 {q1} Hãy tìm ngôn ngữ đoán nhận được bởi M trong số các ngôn ngữ sau: a.L = { 1m 0n m 0, n 0 } b.L = { 0 * } c.L = { 10 * } d.L = { 00 * } 6) Cho Automat M = <, Q, , q0 , F > với: = { 0, 1 }; Q = { q0 , q1 , q2 }; F = { q2 }; hàm chuyển cho bởi bảng sau: 0 1 q0 {q0, q1} {q1} q1 {q2} q2 {q2}
- 43. tìm ngôn ngữ đoán nhận được bởi M trong số các ngôn ngữ sau: a.L = { 1m 00m 0 } b.L = { 1m 0m 0 } c.L = { 0 * } d.L = { 00 * } 7) Cho ngôn ngữ L={ 11 * } và 2 Automat M1 = <, Q, 1, q0 , F >; M2 = <, Q, 2, q0 , F > với cùng các tập , Q, F là = {0, 1}; Q={q0 , q1 , q2}; F = { q2 }; còn các hàm chuyển 1 và 2 cho bởi các bảng sau: 1 0 1 2 0 1 q0 q0 q1 q0 {q0} {q0, q1} q1 q0 q2 q1 {q2} q2 q0 q2 q2 {q2} Hãy chọn phát biểu đúng nhất trong các phát biểu sau: a.L=L(M1) và LL(M2) b.L=L(M2) và LL(M1) c.L=L(M1) và L=L(M2) d.LL(M1) và LL(M2) 8) Cho ngôn ngữ L={11* } và 2 Automat M1, M2 cho bởi các đồ thị chuyển sau: M1: M2: Hãy chọn phát biểu đúng nhất trong các phát biểu sau: a.L=L(M1) và LL(M2) b.L=L(M2) và LL(M1) c.L=L(M1) và L=L(M2) d.LL(M1) và LL(M2) q0 q1 0,1 1 1 q2 q0 q1 1 1 1 q2 0 0 0
- 44. Cho Automat M có đồ thị chuyển như sau: Hãy xác định L(M): a.L={00 * } b.L={00 * } c.L={00 * } d.L={00 , * } 10) Cho Automat M có đồ thị chuyển như sau: Hãy xác định L(M): a.L={11* } b.L={011* } c.L={111* } d.L={0011* } 11) Cho Automat M có đồ thị chuyển như sau: Hãy xác định L(M): a.L={{0,1}* có số lượng ký tự 0 và số lượng ký tự 1 đều là số chẵn} b.L={{0,1}* có số lượng ký tự 0 và số lượng ký tự 1 bằng nhau} c.L={{0,1}* có số lượng ký tự 0 và số lượng ký tự 1 đều là số lẻ} d.L={{0,1}* có số lượng ký tự 0 chẵn và số lượng ký tự 1 lẻ } 12) Biểu thức chính quy (0+1)* 00(0+1)* xác định ngôn ngữ nào ? a.L={{0,1}* có 2 ký tự 0} q1q0 1 1 q2 1 0 q3 1 000 q0 q1 0,1 0 0 q2 0,1 q0 q1 1 1 1 q2 0 0 0
- 45. có số lượng 0 chẵn} c.L={{0,1}* có chứa 00} d.L={{0,1}* có số lượng 0 lớn hơn 2} 13) Cho Automat M có đồ thị chuyển như sau: Hãy xác định L(M): a.L={{0,1}* bắt đầu bởi 00} b.L={{0,1}* bắt đầu bởi 11} c.L={{0,1}* bắt đầu bởi 00 hoặc 11} d.Không phải 3 ngôn ngữ kể trên 14) Biểu thức chính quy (0+1)* 100 xác định ngôn ngữ nào ? a.L={{0,1}* có 1 ký tự 1} b.L={{0,1}* có số lượng 0 chẵn } c.L={{0,1}* có chứa 100} d.L={{0,1}* kết thúc bởi 100} 15) Cho 2 văn phạm chính quy G1=<,,I,R1> và G2=<,,I,R2> với ={0,1}; ={I,A,B}; R1={I0A, I1B, A0A, A0, A, B}; R2={I0A, I1B, A0A, B1B, A, B}; Hãy chọn phát biểu đúng nhất trong các phát biểu sau đây: a.Chỉ có G1 là văn phạm chính quy mẫu b.Chỉ có G2 là văn phạm chính quy mẫu c.Cả G1 và G2 đều là văn phạm chính quy mẫu d.Cả G1 và G2 đều không phải là văn phạm chính quy mẫu 16) Cho 2 ngôn ngữ L1={0n 1n n≥0} và L2={0m 1n m≥0,n≥0}. Hãy chọn phát biểu đúng nhất trong các phát biểu sau đây: a.Chỉ có L1 là ngôn ngữ chính quy b.Chỉ có L2 là ngôn ngữ chính quy c.Cả L1 và L2 đều là ngôn ngữ chính quy d.Cả L1 và L2 đều không phải là ngôn ngữ chính quy 17) Cho 2 ngôn ngữ L1={{0,1}* có số lượng 0 chẵn} và L2={{0,1}* có số lượng 0 và 1 đều chẵn}. Hãy chọn phát biểu đúng nhất trong các phát biểu sau đây: q1q0 1 0 q2q3 10 0,1
- 46. có L1 là ngôn ngữ chính quy b.Chỉ có L2 là ngôn ngữ chính quy c.Cả L1 và L2 đều là ngôn ngữ chính quy d.Cả L1 và L2 đều không phải là ngôn ngữ chính quy 18) Cho ngôn ngữ L={0n 1n n≥0} Hãy chọn phát biểu đúng nhất trong các phát biểu sau đây: a.Chỉ có thể đoán nhận L bởi Automat hữu hạn b.Chỉ có thể đoán nhận L bởi Automat đẩy xuống c.Có thể đoán nhận L bởi Automat hữu hạn hoặc Automat đẩy xuống d.Cả 3 phát biểu trên đều sai 19) Cho ngôn ngữ L = { * , *, là từ gương của } Hãy chọn phát biểu đúng nhất trong các phát biểu sau đây: a.Chỉ có thể đoán nhận L bởi Automat hữu hạn b.Chỉ có thể đoán nhận L bởi Automat đẩy xuống c.Có thể đoán nhận L bởi Automat hữu hạn hoặc Automat đẩy xuống d.Cả 3 phát biểu trên đều sai 20) Cho ngôn ngữ L = { am bn am bn m 0, n 0 } Hãy chọn phát biểu đúng nhất trong các phát biểu sau đây: a.Chỉ có thể đoán nhận L bởi Automat hữu hạn b.Chỉ có thể đoán nhận L bởi Automat đẩy xuống c.Có thể đoán nhận L bởi Automat hữu hạn hoặc Automat đẩy xuống d.Cả 3 phát biểu trên đều sai 21) Chọn phát biểu đúng (FA: automat hữu hạn, NNCQ: ngôn ngữ chính quy) a. Một FA chỉ đoán nhận 1 NNCQ b. Một NNCQ chỉ được đoán nhận bởi 1 FA c. Một FA có thể đoán nhận nhiều NNCQ d. Một NNCQ không thể được đoán nhận bởi nhiều FA Đáp án: a 22) Chọn phát biểu đúng (FA: automat hữu hạn, VPCQ: văn phạm chính quy) a. Một FA chỉ tương ứng 1 VPCQ b. Một VPCQ chỉ tương ứng 1 FA c. Một FA có thể tương ứng nhiều VPCQ d. Một FA có thể không có VPCQ tương ứng 23) Chọn phát biểu đúng (DFA:automat hữu hạn đơn định, NDFA:automat hữu hạn không đơn định) a. Một DFA chỉ có 1 NDFA tương đương b. Một NDFA chỉ có 1 DFA tương đương c. Một NDFA có thể không có DFA tương đương
- 47. Một DFA có thể có nhiều NDFA tương đương 24) Tìm phát biểu sai (DFA:automat hữu hạn đơn định, NDFA:automat hữu hạn không đơn định) a. DFA và NDFA đều có hữu hạn trạng thái b. DFA và NDFA đều có thể đoán nhận ngôn ngữ vô hạn c. DFA và NDFA đều có thể đoán nhận 1 ngôn ngữ cụ thể nào đó d. DFA và NDFA đều chỉ có thể đoán nhận ngôn ngữ chính quy 25)Cho L là ngôn ngữ hữu hạn.Tìm phát biểu sai: a. L có thể biểu diễn bởi biểu thức chính quy b. L chỉ có thể đoán nhận bởi automat đẩy xuống c. L có thể do văn phạm phi ngữ cảnh tạo ra d. L có thể đoán nhận bởi automat hữu hạn 26)Tìm phát biểu sai (DFA:automat hữu hạn đơn định, NDFA:automat hữu hạn không đơn định) a. Mỗi DFA luôn có ít nhất 1 NDFA tương đương b. Mỗi NDFA luôn có ít nhất 1 DFA tương đương c. Tồn tại NDFA chỉ có 1 DFA tương đương d. Tồn tại ngôn ngữ được đoán nhận bởi cả DFA và NDFA 27)Xét 2 automat hữu hạn M1=<, Q, , q0, F1>, M2=<, Q, , q0, F2> chỉ khác nhau tập trạng thái kết thúc F1≠F2. Gọi L1, L2 là 2 ngôn ngữ đoán nhận được bởi M1 và M2. Tìm phát biểu đúng nhất: a. L1≠L2 b. L1 có thể trùng L2 c. Nếu F1F2 thì L1L2 d. L1=L2 28)Xét 2 automat hữu hạn M1=<, Q, , q0, F1>, M2=<, Q, , q0, F2> chỉ khác nhau tập trạng thái kết thúc F1 không chứa q0 còn F2=F1{q0}. Gọi L1, L2 là 2 ngôn ngữ đoán nhận được bởi M1 và M2. Tìm phát biểu đúng nhất: a. L2=L1{} b. L1 có thể trùng L2 c. L1L2 d. Tồn tại xL1 mà xL2 29)Nếu tập trạng thái kết thúc của automat hữu hạn M có chứa trạng thái ban đầu thì có thể nói gì về ngôn ngữ L đoán nhận được bởi M? a. L có chứa từ rỗng b. L có thể là ngôn ngữ rỗng c. L là ngôn ngữ tùy ý d. L là ngôn ngữ vô hạn 30)Nếu automat hữu hạn M=<, Q, , q0, F> có F=Q thì có thể nói gì về ngôn ngữ L đoán nhận được bởi M? a. Nếu M là đơn định thì L=* b. Nếu M là không đơn định thì L=* c. L=* trong mọi trường hợp d. L có thể rỗng 31) Cho Automat M1 và M2 có đồ thị chuyển như sau, tìm phát biểu sai?
- 48. L(M1)=L(M2) b. M1 không đơn định c. M2 đơn định d. M1 không đọc được xâu 1001 32) Cho Automat M1 và M2 có đồ thị chuyển như sau, tìm phát biểu sai? a. L(M1)=L(M2) b. M1 không đơn định c. M2 không đơn định d. M2 không đọc được xâu 1111 33) Tìm phát biểu sai? a. Nếu thêm một trạng thái vào tập kết thúc của automat hữu hạn thì chắc chắn sẽ mở rộng được ngôn ngữ đoán nhận. b. Nếu thêm một trạng thái vào tập trạng thái của automat hữu hạn thì khả năng đoán nhận ngôn ngữ có thể được mở rộng. c. Số lượng trạng thái của automat hữu hạn có ý nghĩa quan trọng trong việc đoán nhận ngôn ngữ. d. Nếu tập trạng thái kết thúc của automat hữu hạn khác rỗng thì chưa chắc ngôn ngữ đoán nhận của automat sẽ khác rỗng. 34)Automat hữu hạn không thể đoán nhận ngôn ngữ nào trong các ngôn ngữ sau? a. L={am bn ck | m>0, n>0, k>0} b. L={am bn ck | m>n>k>0 } c. L={am bn ck | m>0,n>1,k>2 } d. L={am bn ck | n>1,n>1,k>1 } 35)Chứng minh rằng ngôn ngữ L={{0,1}* có số lượng ký tự 0 và số lượng ký tự 1 bằng nhau} không phải ngôn ngữ chính quy. q 0 q 1 0,1 0 0 q2 q 0 q 1 0 0 0 q2 1 1 1 M1 M2 0q 0 q 1 0,1 0 0 q2 M1 q 0 q 20,1 0 0 q3 M2 q 1 00
|
