Tập bài giảng Ngôn ngữ hình thức - Phạm Hùng Phú
246 trang
17/05/2022
2670
Bạn đang xem 20 trang mẫu của tài liệu "Tập bài giảng Ngôn ngữ hình thức - Phạm Hùng Phú", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- tap_bai_giang_ngon_ngu_hinh_thuc_pham_hung_phu.pdf
Nội dung text: Tập bài giảng Ngôn ngữ hình thức - Phạm Hùng Phú
- Ngôn ngữ hình thức Mục lục LỜI NÓI ĐẦU 4 Chƣơng 1. TỔNG QUAN VỀ NGÔN NGỮ VÀ AUTOMAT 6 1.1. Các khái niệm cơ bản 6 1.1.1. Khái niệm ngôn ngữ hình thức 6 1.1.2. Bảng chữ cái (alphabet) 8 1.1.3. Xâu trên bảng chữ cái 8 1.1.4. Các phép toán trên xâu 9 1.1.5. Ngôn ngữ (language) 10 1.2. Văn phạm và ngôn ngữ 13 1.2.1. Văn phạm 13 1.2.2. Ngôn ngữ sinh bởi Văn phạm 15 1.2.3. Văn phạm tƣơng đƣơng 16 1.3. Phân loại văn phạm và ngôn ngữ 16 1.3.1. Văn phạm và ngôn ngữ loại 0 16 1.3.2. Văn phạm và ngôn ngữ loại 1 17 1.3.3. Văn phạm và ngôn ngữ loại 2 17 1.3.4. Văn phạm và ngôn ngữ loại 3 17 1.3.5. Ví dụ 18 1.4. Một số tính chất của ngôn ngữ 19 1.4.1. Tính chất 1 19 1.4.2 Tính chất 2 20 1.4.3. Tính chất 3 20 1.4.4. Tính chất 4 21 1.4.5. Tính chất 5 (Tính đệ quy của ngôn ngữ) 21 1.5. Automat 23 1.5.1. Mô tả automat 23 1.5.2. Phân loại automat 24 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 25 Phạm Hùng Phú 1
- Ngôn ngữ hình thức Chƣơng 2. VĂN PHẠM CHÍNH QUY VÀ AUTOMAT HỮU HẠN 30 2.1. Automat hữu hạn (FINITE AUTOMAT - FA) 31 2.1.1. Định nghĩa Automat hữu hạn 31 2.1.2. Automat hữu hạn đơn định 36 2.1.3. Automat hữu hạn không đơn định-NFA (Nondeterministic Finite Automata) 42 2.1.4. Sự tƣơng đƣơng giữa DFA và NFA 49 2.1.5. NFA với ε-dịch chuyển (NFAε) 56 2.1.6. Sự tƣơng đƣơng giữa NFA có và không có ε-dịch chuyển 62 2.2. Biểu thức chính quy (RE: Regular Expressions) 64 2.2.1. Định nghĩa 65 2.2.2. Một số tính chất đại số của biểu thức chính quy 66 2.2.3. Sự tƣơng đƣơng giữa automat hữu hạn và biểu thức chính quy 67 2.3. Văn phạm chính quy 79 2.3.1. Văn phạm tuyến tính 79 2.3.2. Sự tƣơng đƣơng giữa văn phạm chính quy và automat hữu hạn 80 2.3.3. Tính chất của ngôn ngữ chính quy 87 2.3.4. Bổ đề bơm cho ngôn ngữ chính quy 90 2.3.5. Xác định ngôn ngữ chính quy 92 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 94 Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH VÀ AUTOMAT ĐẨY XUỐNG 107 3.1. Văn phạm phi ngữ cảnh (CFG: Context Free Grammar) 107 3.1.1. Định nghĩa 109 3.1.2. Dẫn xuất và ngôn ngữ 110 3.1.3. Cây dẫn xuất 111 3.1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất 113 3.1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất 115 3.1.6. Văn phạm nhập nhằng (mơ hồ) 116 3.2. Rút gọn văn phạm phi ngữ cảnh 117 3.2.1. Loại bỏ các ký tự thừa 118 2 Phạm Hùng Phú
- Ngôn ngữ hình thức 3.2.2. Luật sinh ε (ε quy tắc) 124 3.2.3. Luật sinh đơn vị 128 3.3. Chuẩn hóa văn phạm phi ngữ cảnh 130 3.3.1. Dạng chuẩn Chomsky - CNF (Chomsky Normal Form) 130 3.3.2. Dạng chuẩn Greibach (Greibach Normal Form - GNF) 134 3.4. Tính chất của ngôn ngữ phi ngữ cảnh 140 3.4.1. Bổ đề bơm đối với CFL (Dùng để chứng minh một ngôn ngữ không là ngôn ngữ phi ngữ cảnh) 140 3.4.2. Tính chất đóng của CFL 143 3.5. Automat đẩy xuống (Push down Automata) 145 3.5.1. Mô tả PDA 145 3.5.2. Định nghĩa Automat đẩy xuống 146 3.5.3. Ngôn ngữ đoán nhận bởi PDA 150 3.5.4. PDA và văn phạm phi ngữ cảnh 153 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 161 LỜI GIẢI TÓM TẮT HOẶC HƢỚNG DẪN 168 TÀI LIỆU THAM KHẢO 246 Phạm Hùng Phú 3
- LỜI NÓI ĐẦU LỜI NÓI ĐẦU Ngôn ngữ hình thức (Formal Languages) là bộ môn khoa học quan trọng của khoa học máy tính. Ở nhiều nước trên thế giới, môn học này đã trở thành môn học cơ sở đối với sinh viên các ngành thuộc lĩnh vực công nghệ thông tin. Ở nước ta, hiện nay nhiều trường đại học cũng đang giảng dạy môn học “Ngôn ngữ hình thức” cho sinh viên các ngành khoa học máy tính và công nghệ thông tin. Tuy nhiên tài liệu phục vụ giảng dạy cho môn học ở nước ta còn ít, thời lượng dành cho môn học cũng còn rất khác nhau ở mỗi trường. §Ó cã mét néi dung thèng nhÊt cho c¸c ngµnh thuộc lÜnh vùc c«ng nghÖ th«ng tin cña Tr•êng, tr•êng §¹i häc S• ph¹m Kü thuËt Nam §Þnh ®· ban hµnh ch•¬ng tr×nh chi tiÕt cho m«n häc. Việc xuất bản tập đề cương bài giảng nhằm đáp ứng nhu cầu cung cấp tài liệu môn học cho việc giảng dạy của giảng viên và học tập của sinh viên các ngành thuộc khoa Công nghệ Thông tin trường Đại học Sư phạm Kỹ thuật Nam Định nói riêng và làm tại liệu tham khảo cho sinh viên và cán bộ giảng dạy các trường nói chung. Tập đề cương bài giảng “Ngôn ngữ hình thức” được biên soạn theo chương trình chi tiết môn học “Ngôn ngữ hình thức” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về ngôn ngữ, văn phạm và automat; giúp sinh viên nắm vững các kiến thức cơ bản về văn phạm chính quy và automat hữu hạn, văn phạm phi ngữ cảnh và automat đẩy xuống là công cụ dùng để xây dựng và phân tích từ vựng, cú pháp của các ngôn ngữ lập trình. Đây là các kiến thức nền tảng, làm cơ sở cho việc xây dựng ra các ngôn ngữ lập trình và các chương trình dịch. Về nội dung, tập đề cương bài giảng được chia thành 3 chương: Chương 1. Tổng quan về ngôn ngữ và automat. Chương này trình bày: Các khái niệm, kiến thức cơ bản về bảng chữ cái, xâu trên bảng chữ cái, các phép toán trên xâu; khái niệm văn phạm và ngôn ngữ, phân loại văn phạm và ngôn ngữ, các phép toán trên ngôn ngữ và biểu diễn ngôn ngữ; khái niệm, phân loại automat. Chương 2. Văn phạm chính quy và automat hữu hạn. Chương này trình bày các kiến thức cơ bản về: Automat hữu hạn (FA); automat hữu hạn đơn định (DFA) và Automat hữu hạn không đơn định (NFA); Sự tương đương giữa DFA và NFA; Biểu thức chính quy; sự tương đương giưa FA và biểu thức chính quy; Văn phạm chính quy, sự tương đương giữa văn phạm chính quy và FA; tính chất của văn phạm chính quy. 4 Phạm Hùng Phú
- Ngôn ngữ hình thức Chương 3. Văn phạm phi ngữ cảnh và automat đẩy xuống. Chương này trình bày các kiến thức cơ bản về: Văn phạm phi ngữ cảnh (CFG); rút gọn văn phạm phi ngữ cảnh; chuẩn hoá văn phạm phi ngữ cảnh; tính chất của văn phạm phi ngữ cảnh; automat đẩy xuống (PDA); sự tương đương của PDA và CFG. Đặc biệt cuối mỗi chương còn đưa ra hệ thống câu hỏi, bài tập nhằm củng cố, khắc sâu, nâng cao và vận dụng các kiến thức vào giải các bài tập và cuối cùng là phần lời giải tóm tắt hoặc hướng dẫn cho các bài tập nhằm giúp sinh viên tự rèn luyện kỹ năng và kiểm tra kiến thức. Trong quá trình biên soạn, tập đề cương bài giảng không tránh khỏi những sai sót, rất mong đồng nghiệp và các em sinh viên góp ý kiến để tập đề cương bài giảng ngày càng được hoàn thiện hơn. Người biên soạn Phạm Hùng Phú Phạm Hùng Phú 5
- Chương 1. Tổng quan về Ngôn ngữ và Automat Chƣơng 1 TỔNG QUAN VỀ NGÔN NGỮ VÀ AUTOMAT Mục tiêu: Giúp sinh viên có khả năng: - Hiểu đƣợc các khái niệm cơ bản: xâu, ngôn ngữ, văn phạm. - Hiểu đƣợc các phép toán trên xâu, ngôn ngữ. - Xác định đƣợc các thành phần của văn phạm. - Biết đƣợc mối quan hệ giữa văn phạm và ngôn ngữ, cách phân loại văn phạm và ngôn ngữ, các phƣơng pháp biểu diễn ngôn ngữ. - Vận dụng đƣợc các kiến thức vào giải các bài tập. Nội dung chính: - Các khái niệm cơ bản. - Khái niệm, phân loại văn phạm và ngôn ngữ. - Các phép toán trên ngôn ngữ và biểu diễn ngôn ngữ. - Khái niệm, phân loại và biểu diễn automat. 1.1. Các khái niệm cơ bản 1.1.1. Khái niệm ngôn ngữ hình thức Ta đã từng nghe, từng nói nhiều về ngôn ngữ nhƣ ngôn ngữ tiếng Anh, tiếng Việt, ngôn ngữ lập trình Pascal, ngôn ngữ thuật toán, Song ít ngƣời có thể trả lời chính xác câu hỏi ngôn ngữ là gì?; có bao nhiêu loại ngôn ngữ? và điều quan trọng hơn, thu hút sự quan tâm hơn là làm thế nào để có ngôn ngữ?. Từ lâu các nhà ngôn ngữ học đã nghiên cứu về ngôn ngữ, song việc nghiên cứu của họ thiên về các khía cạnh xã hội, lịch sử của ngôn ngữ nhƣ: quá trình hình thành ngôn ngữ, các đặc trƣng ngôn ngữ của các dân tộc, Từ khi máy tính ra đời, xuất hiện nhu cầu phải dùng ngôn ngữ đễ diễn đạt thuật toán, phải dịch từ ngôn ngữ thuật toán này sang ngôn ngữ thuật toán khác, khi đó bắt buộc phải giải quyết một loạt các vấn đề đƣợc đặt ra nhƣ: - Ngôn ngữ là gì?. 6 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat - Làm thế nào để biểu diễn ngôn ngữ?. - Ngôn ngữ thuật toán cần phải có đặc trƣng gì?. - Thế nào là dịch từ ngôn ngữ này sang ngôn ngữ khác?. - Thế nào là bản dịch đúng? Quan tâm nghiên cứu, giải quyết những vấn đề nêu trên là lĩnh vực nghiên cứu của ngôn ngữ hình thức và chƣơng trình dịch. Trƣớc hết đề cập đến ngôn ngữ hình thức, một cách ngắn gọn ngôn ngữ hình thức đƣợc coi là bộ môn khoa học mà đối tƣợng nghiên cứu của nó là ngôn ngữ và công cụ nghiên cứu của nó là toán học. Nhờ toán học, ngƣời ta có thể gạt bỏ đi những đặc trƣng riêng của từng loại ngôn ngữ, trừu tƣợng hoá, hình thức hoá những vấn đề bản chất nhất của ngôn ngữ để nghiên cứu chúng. Chính vì lý do này mà ngôn ngữ hình thức còn có tên gọi là “Lý thuyết ngôn ngữ lập trình”. Để minh hoạ cho cách tiếp cận nghiên cứu ngôn ngữ của bộ môn khoa học này, ta xét ví dụ sau: Xét trong câu tiếng Việt: “Tôi ăn cơm” Từ “tôi” là , từ “ăn” là , từ “cơm” là , khi đó ta có thể khái quát câu trong tiếng Việt gồm 3 thành phần sắp xếp ở dạng sau: Trong đó có thể là hoặc , thay cho các viết này ta viết ngắn gọn: | Tƣơng tự nhƣ vậy ta có thể viết: anh | tôi | nó| ông | bà | em | . cam | bánh | kẹo | xôi | báo | voi . đi | đứng | học | làm | nhảy | viết | vẽ Theo nguyên tắc này, ngƣời ta có thể tạo ra các câu một cách máy móc. Ví dụ nhƣ: tôi viết báo cáo, anh ấy học bài, Phạm Hùng Phú 7
- Chương 1. Tổng quan về Ngôn ngữ và Automat 1.1.2. Bảng chữ cái (alphabet) Một bảng chữ cái hay bộ chữ cái là một tập hợp hữu hạn, khác rỗng các phần tử, ký hiệu là . Các phần tử của một bảng chữ cái đƣợc gọi là các chữ cái hoặc các ký tự (character) hay ký hiệu (symbol). Ví dụ: - Tập hợp các chữ cái La tinh a, b, c, , A, B, , Z là một bảng chữ cái và a, b, , A, là các chữ cái hay các ký tự. - Tập hợp các bít nhị phân 0, 1 là một bảng chữ cái và 0, 1 là các ký hiệu hay các ký tự. - Tập hợp các chữ cái Hy Lạp = , , , , là một bảng chữ cái và , , , , , là các ký hiệu hay các ký tự. - Tập hợp các chữ số thập phân 0, 1, , 9 là một bảng chữ cái và 1, , 9 là các chữ cái hoặc các ký hiệu hay các ký tự. Để chỉ một chữ cái hoặc ký tự hay ký hiệu thuộc hay không thuộc một bảng chữ cái ta dùng ký hiệu hoặc . Ví dụ: ; 9 1.1.3. Xâu trên bảng chữ cái Xâu (string) hay từ (word) trên một bảng chữ cái là một dãy hữu hạn gồm một số lớn hơn hay bằng không các ký tự của bảng chữ cái đó; Trong đó, một ký tự có thể xuất hiện nhiều lần. Ví dụ: - Aaab, bbbbb là các từ trên bảng chữ cái La Tinh. - , 0, 1, 00101, 000011 là các từ trên bảng chữ cái = 0, 1. Độ dài của từ hay xâu w là số ký tự tạo thành xâu w và đƣợc ký hiệu là |w| Chú ý: - Thuật ngữ xâu hay từ còn đồng nghĩa với xâu ký tự. - Xâu rỗng là xâu không có chữ cái nào, độ dài của xâu rỗng bằng không, xâu rỗng đƣợc ký hiệu là . 8 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat Xâu x đƣợc gọi là xâu con của xâu w nếu x đƣợc tạo từ các ký tự nằm liền kề nhau trong xâu w. Tiền tố của xâu w là một xâu con bất kỳ nằm ở đầu xâu w. Hậu tố của xâu w là một xâu con bất kỳ nằm ở cuối xâu w. Ví dụ: cho các xâu w = abc và x = de trên bảng chữ cái La tinh; - |w| = 3; |x| = 2. - Các xâu a, b, c, ab, bc, abc là các xâu con của xâu w. - Các xâu a, ab, abc là các tiền tố của xâu w. - Các xâu c, bc, abc là các hậu tố của xâu w. 1.1.4. Các phép toán trên xâu 1) Phép nhân ghép hai xâu Cho hai xâu x = x1x2 xn và y = y1y2 ym trên bảng chữ cái , phép nhân ghép hai xâu x và y là phép cho ta một xâu xy = x1x2 xny1y2 ym trên bảng chữ cái . Xâu xy đƣợc gọi là xâu ghép của hai xâu x và y. Nhƣ vậy, xâu ghép của hai xâu là một xâu đƣợc tạo ra bằng cách viết xâu thứ nhất, sau đó là xâu thứ hai (không có khoảng trống ở giữa). Ví dụ: Xâu ghép của hai xâu w = abc và u = de trên bảng chữ cái La Tinh là xâu wu = abcde và w = w = w. Ta ký hiệu: w0 = ; w1 = w; w2 = ww; , wi = wwi-1 với i > 0. 2) Phép đảo ngược xâu: Cho xâu w = a1a2 an trên bảng chữ cái , phép đảo ngƣợc xâu w là phép R R cho ta kết quả là một xâu trên bảng chữ cái , ký hiệu là w và w = anan-1 a2a1. Xâu wR đƣợc gọi là xâu đảo ngƣợc của xâu w. Nhƣ vậy, xâu đảo ngƣợc của xâu w là một xâu đƣợc tạo ra từ xâu w bằng cách viết w theo thứ tự ngƣợc lại và hiển nhiên εR = ε. Phạm Hùng Phú 9
- Chương 1. Tổng quan về Ngôn ngữ và Automat 1.1.5. Ngôn ngữ (language) 1) Khái niệm ngôn ngữ Cho là một bảng chữ cái, ký hiệu * là tập hợp tất cả các xâu trên kể cả xâu rỗng, + là tập hợp tất cả các xâu trên trừ xâu rỗng; nhƣ vậy, giữa * và + có mối liên hệ * = + {} hay + = *- {}. Ví dụ: = a, b, c; *= aabcc, aaaaa, cab, . là các xâu trên bảng chữ cái . = 0,1; * = e,0,1,00,01,10,11,000 là tập các xâu trên . + = 0,1,00,01,10,11,000 Ta quy ƣớc xâu dạng aaaa a gồm n kí tự a ký hiệu là an. Cho bảng chữ cái , tập con bất kỳ của tập hợp * đƣợc gọi là ngôn ngữ (ngôn ngữ hình thức) trên bảng chữ cái . Ví dụ: Cho = a; L = ai với a và i N thì L là ngôn ngữ trên bảng chữ cái . 2) Các phép toán trên ngôn ngữ Theo khái niệm ngôn ngữ thì ngôn ngữ L là một tập hợp. Ký hiệu |L| là số các xâu hay số phần tử của L; nếu |L| là một số hữu hạn thì nói rằng L là ngôn ngữ hữu hạn. Từ các ngôn ngữ cho trƣớc, ta có thể thu đƣợc các ngôn ngữ mới nhờ áp dụng các phép toán trên ngôn ngữ. Vì ngôn ngữ L là một tập hợp nên các phép toán hợp (union), giao (intersect), hiệu (difference) của lý thuyết tập hợp đều có thể áp dụng trên các ngôn ngữ của cùng một bảng chữ cái để thu đƣợc ngôn ngữ mới cũng trên bảng chữ cái đó. Tức là: - Cho là bảng chữ cái. L1, L2 là hai ngôn ngữ trên thì: L1 L2 = x x L1 hoặc x L2; 10 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat L1 L2 = x x L1 và x L2; L1 - L2 = x x L1 và x L2 cũng là các ngôn ngữ trên . Ngoài ra, còn có một số phép toán thƣờng gặp khác nhƣ: - Phép lấy phần bù (complement): Phần bù của một ngôn ngữ L trên bảng chữ cái là một ngôn ngữ trên , ký hiệu là L và đƣợc xác định nhƣ sau: L = *- L - Phép nhân ghép (concatenation): Tích ghép của hai ngôn ngữ L1và L2 trên bảng chữ cái Σ là một ngôn ngữ trên bảng chữ cái Σ và đƣợc xác định nhƣ sau: L1L2 = {w1w2 | w1 L1 và w2 L2 } - Phép lặp (loop) Cho L là ngôn ngữ trên bảng chữ cái . Ký hiệu: L0 = , ở đây ký hiệu cho từ rỗng, đó là từ không chứa ký hiệu nào của bảng chữ cái, hay là từ có độ dài bằng 0. L1 = L; L2 = L1L; L3 = L2L, Tổng quát: ký hiệu Li = Li-1L với i = 1, 2, , n - Phép lấy bao đóng (closure) + Bao đóng dƣơng (positive) L+ = L1 L2 L3 = Li với mọi n > 0; có thể coi L+ là tập tất cả i 1 các xâu có độ dài hữu hạn và khác không. + Bao đóng kleene L* = Li với mọi n 0; nhƣ vậy, L* là tập tất cả các xâu có độ dài hữu hạn. i 1 Chú ý: L+ = LL* = L*L = L* - {ε}. L* = L+ {ε}. Hiển nhiên, lặp, bao đóng của một ngôn ngữ L trên bảng chữ cái Σ là một ngôn ngữ trên bảng chữ cái Σ. Phạm Hùng Phú 11
- Chương 1. Tổng quan về Ngôn ngữ và Automat Ví dụ: Cho ngôn ngữ L = { a, ba } thì: - L2 = {aa, aba, baa, baba}; - L3 = { aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa}; - L* = { ε, a, ba, aa, aba, baa, baba, aaa, aaba, abaa, ababa, baaa, baaba, }. 3) Biểu diễn ngôn ngữ Ta biết rằng một ngôn ngữ L trên một bảng chữ cái Σ là một tập con của tập Σ*. Vậy vấn đề đặt ra là đối với một ngôn ngữ L, làm thế nào có thể chỉ rõ các xâu có thuộc vào L hay không ?. Đó chính là vấn đề biểu diễn ngôn ngữ. Để biểu diễn ngôn ngữ, ta có thể: - Liệt kê: + Liệt kê hết: Đối với một ngôn ngữ hữu hạn, số lƣợng xâu của nó có ít, để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê tất cả các xâu thuộc vào ngôn ngữ đó. Ví dụ: L1 = {ε} L2 = { a, ba, aaba, bbbbb } + Liệt kê không hết hết: Liệt kê một số xâu của ngôn ngữ và có ám chỉ quy luật để tìm các xâu khác. Ví dụ: L1 = { ε, a, aa, aaa, aaaa, } L 2 = { ε, ab, aabb, aaabbb, } - Chỉ ra tính chất đặc trƣng: Trong trƣờng hợp một ngôn ngữ là vô hạn hoặc không thể liệt kê đƣợc tất cả các xâu thuộc vào ngôn ngữ đó. Trong những trƣờng hợp không phức tạp lắm, ngƣời ta thƣờng phải tìm ra tính chất đặc trƣng chung của các xâu và xác định các xâu bằng cách chỉ rõ tính chất đặc trƣng của các xâu đó. Tính chất đặc trƣng này thƣờng đƣợc mô tả thông qua một vị từ. i Ví dụ: L1 = { a | i là một số nguyên tố } i i L2 = { a b | i ≥ 0 } i j L3 = { a b | i ≥ j ≥ 0 } - Trong phần lớn các trƣờng hợp, ngƣời ta thƣờng biểu diễn ngôn ngữ một cách tổng quát thông qua một văn phạm hoặc một automat. Văn phạm là cơ chế hay 12 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat công cụ cho phép sản sinh ra mọi xâu của một ngôn ngữ; trong khi đó automat lại là cơ chế hay công cụ cho phép đoán nhận một xâu bất kỳ có thuộc ngôn ngữ hay không. Về mặt hình thức, cả văn phạm và automat đều là cách biểu diễn khác nhau của ngôn ngữ. Ví dụ: Cho L là một ngôn ngữ trên bộ chữ cái Σ = {a, b} đƣợc định nghĩa nhƣ sau: - ε L (1) - Nếu w L thì awb L (2) - Không còn xâu nào khác thuộc L (3) Định nghĩa đệ quy trên cho ta một cách sản sinh ra các xâu thuộc ngôn ngữ L nhƣ sau: Do (1) nên ta có xâu đầu tiên trong L là ε. Xem đó là w thì theo (2) ta lại có đƣợc xâu thứ hai aεb hay ab. Áp dụng lặp đi lặp lại quy tắc (2) ta lại tìm đƣợc các xâu: aabb, rồi lại aaabbb, Cứ nhƣ thế có thể phát sinh tất cả các xâu thuộc ngôn ngữ L. Bằng cách áp dụng (một số hữu hạn) quy tắc phát sinh nhƣ trên, ta có thể phát sinh bất kỳ xâu nào trong ngôn ngữ. Dễ dàng nhận thấy: L = {ai bi | i ≥ 0}. Trong giáo trình này, các chƣơng sau sẽ tập trung nghiên cứu hai công cụ dùng để biểu diễn ngôn ngữ, nhƣ đã nói ở trên, đó là văn phạm và automat, bằng cách ấn định các dạng khác nhau vào các công cụ để có thể đƣa ra đƣợc nhiều loại văn phạm và automat khác nhau, từ đơn giản đến phức tạp và cũng sẽ nghiên cứu các ngôn ngữ đƣợc sinh bởi văn phạm hoặc đƣợc đoán nhận bởi automat và mối liên quan của chúng với nhau. 1.2. Văn phạm và ngôn ngữ 1.2.1. Văn phạm Một công cụ để mô tả ngôn ngữ là văn phạm. Đây là công cụ có định nghĩa toán học chặt chẽ, đƣợc các nhà toán học nghiên cứu kỹ và trở thành một thành phần quan trọng, chính yếu của lý thuyết ngôn ngữ. 1) Định nghĩa Văn phạm G là một hệ thống gồm bốn thành phần đƣợc xác định nhƣ sau: G = (N, T, P, S) trong đó: Phạm Hùng Phú 13
- Chương 1. Tổng quan về Ngôn ngữ và Automat + N – Là một tập hữu hạn các ký hiệu không kết thúc (Nonterminal) hay tập các biến (variables). + T – Là tập hữu hạn các ký hiệu kết thúc hay ký hiệu cuối (Terminal) với N T = . + P – Là tập hữu hạn các quy tắc sinh hay còn đƣợc gọi là luật sinh. Nói một cách khác P là một ánh xạ từ tập (N T) + sang tập (N T)* P: (N T)+ → (N T)* α β Giả sử α (N T)+, β (N T)* và β là ảnh của α qua ánh xạ P, khi đó cặp (α, β) là một luật sinh và đƣợc ký hiệu là α β. + S N - là ký hiệu chƣa kết thúc đặc biệt dùng làm ký hiệu bắt đầu (start). Ví dụ: Văn phạm G = (N, T, P, S) trong đó: - N = {S}; - T = {a, b}; - P = {S1 aS1b; S1 }; - S = S. 2) Quy ước - Các chữ cái La Tinh viết hoa (A, B, C, ) để chỉ các ký hiệu trong tập ký hiệu không kết thúc N; Chữ cái in hoa nằm ở vế trái của luật sinh đầu tiên là ký tự khởi đầu của văn phạm. - Các chữ cái viết thƣờng ở đầu bảng chữ cái La Tinh (a, b, c, ) hoặc các chữ số để chỉ các ký hiệu kết thúc thuộc tập ký hiệu kết thúc T. - Các chữ cái viết thƣờng ở cuối bảng chữ cái La Tinh (x, y, z, w, ) để chỉ xâu các ký hiệu kết thúc. Nhận xét: Bằng quy ƣớc này có thể suy ra đƣợc các ký hiệu không kết thúc, các ký hiệu kết thúc và ký hiệu bắt đầu của văn phạm một cách xác định và duy nhất bằng cách xem xét các luật sinh. Vì vậy, để biểu diễn một văn phạm, một cách đơn giản ngƣời ta chỉ cần liệt kê tập các luật sinh mà không cần chỉ rõ đầy đủ các thành phần của của văn phạm. 14 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat 1.2.2. Ngôn ngữ sinh bởi Văn phạm 1) Dẫn xuất Nếu α → β là một luật sinh thì γ α δ γ β δ đƣợc gọi là một dẫn xuất (trực tiếp), có nghĩa là áp dụng luật sinh α → β vào xâu γ α δ để sinh ra xâu γ β δ. Nếu các xâu α , α , , α (NT)* và α α , α α , , α α thì ta nói 1 2 m 1 2 2 3 m-1 m rằng: α đƣợc suy dẫn ra từ α thông qua dãy dẫn xuất α α , α α , , α α m 1 1 2 2 3 m-1 m hay α dẫn xuất (gián tiếp) ra α . 1 m Ký hiệu: - α i α là dẫn xuất qua i bƣớc; 1 m - α * α là dẫn xuất qua không, một hoặc nhiều bƣớc; 1 m - α + α là dẫn xuất qua một hoặc nhiều bƣớc. 1 m 2) Ngôn ngữ sinh bởi văn phạm Ngôn ngữ sinh bởi văn phạm G = (N, T, P, S) là tập hợp các xâu w T* đƣợc dẫn xuất ra từ ký hiệu bắt đầu S của văn phạm bởi các luật sinh thuộc tập P và đƣợc ký hiệu là L(G). Nhƣ vậy: L (G) = {w | w T* và S * w} . Ví dụ: 1. Cho G = (N, T, P, S) Với N = S, T = a P = S aaa, S aaaS Khi đó L(G) = a3i i N 2. Cho văn phạm G = (N, T, P, S) với: N = S, T = 0,1; P = S 0S1; S 01; Ta có nhận xét mọi dãy dẫn xuất có thể có trong G phải có dạng: S 0S1 00S11 0i S1i Từ đây suy ra L(G) = 0i1i i 1 Phạm Hùng Phú 15
- Chương 1. Tổng quan về Ngôn ngữ và Automat 1.2.3. Văn phạm tƣơng đƣơng Cho hai văn phạm G1 = (N1, T, P1, S1) và G2 = (N2, T, P2, S2), ta nói rằng G1 tƣơng đƣơng với G2 , ký hiệu là G1 G2 nếu L(G1) = L(G2). Nói cách khác hai văn phạm đƣợc gọi là tƣơng đƣơng nếu chúng sinh ra cùng một ngôn ngữ. Ví dụ: Cho văn phạm G1 = (N1, T1, P1, S1) trong đó: N1 = {S1}; T1 = {a, b}; P1 = {S1 aS1b; S1 }. n n Ta thấy ngay L(G1) = {a b | n 0}. Và G2 = (N2, T2, P2, S2) trong đó: N2 = {S2};T2 = {a, b}; P2 = {S2 aS2b; S2 ab; S2 }. n n Ta cũng thấy ngay L(G2) = {a b | n 0} Nhƣ vậy, G1 và G2 là hai văn phạm tƣơng đƣơng. 1.3. Phân loại văn phạm và ngôn ngữ Ở trên đã xem xét văn phạm là một công cụ để sinh ra ngôn ngữ, tiếp theo ta sẽ xem xét các vấn đề liên quan đến câu hỏi có bao nhiêu loại ngôn ngữ ?. Quan hệ giữa chúng nhƣ thế nào ?. Liên quan đến các câu hỏi trên đã có nhiều nhà khoa học đƣa ra cách phân loại khác nhau, song một cách phân loại đƣợc coi là tốt nhất, phù hợp với mục đích nghiên cứu là cách phân loại của nhà toán học Chomsky. Chomsky đƣa ra cách phân loại ngôn ngữ dựa vào các quy tắc sinh và đƣợc sử dụng nhƣ là cách phân loại chủ yếu trong lý thuyết ngôn ngữ hình thức. 1.3.1. Văn phạm và ngôn ngữ loại 0 Văn phạm G đƣợc gọi là văn phạm loại 0 nếu các quy tắc sinh của nó không có bất kỳ một điều kiện ràng buộc nào. Văn phạm loại 0 còn có tên gọi là văn phạm ngữ cấu hay văn phạm không hạn chế (Unrestricted Grammar). Ngôn ngữ sinh bởi văn phạm loại 0 đƣợc gọi là ngôn ngữ loại 0. 16 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat 1.3.2. Văn phạm và ngôn ngữ loại 1 Văn phạm G đƣợc gọi là văn phạm loại 1 nếu các quy tắc sinh của nó có dạng: , với điều kiện (NT)+ và Văn phạm loại 1 còn đƣợc gọi là văn phạm cảm ngữ cảnh (Context Sensitive Grammar - CSG). Ngôn ngữ sinh bởi văn phạm loại 1 đƣợc gọi là ngôn ngữ loại 1 và còn đƣợc gọi là ngôn ngữ cảm ngữ cảnh (CSL). 1.3.3. Văn phạm và ngôn ngữ loại 2 Văn phạm G đƣợc gọi là văn phạm loại 2 nếu các quy tắc sinh của nó có dạng: ; với N (NT)*. Văn phạm loại 2 còn đƣợc gọi là văn phạm phi ngữ cảnh (Context free Grammar - CFG). Ngôn ngữ sinh bởi văn phạm loại 2 đƣợc gọi là ngôn ngữ loại 2 và còn đƣợc gọi là ngôn ngữ phi ngữ cảnh (CFL). 1.3.4. Văn phạm và ngôn ngữ loại 3 Văn phạm G đƣợc gọi là văn phạm loại 3 nếu mọi quy tắc sinh của nó có một trong hai dạng: 1. A Bw hoặc A w (văn phạm tuyến tính trái); 2. A wB hoặc A w (văn phạm tuyến tính phải). * Trong đó: A, B N và w T . Văn phạm loại 3 còn đƣợc gọi là văn phạm chính quy (Regular Grammar - RG). Ngôn ngữ sinh bởi văn phạm loại 3 đƣợc gọi là ngôn ngữ loại 3 và còn đƣợc gọi là ngôn ngữ chính quy (RL). Chú ý: Từ cách phân loại trên ta có nhận xét: Văn phạm loại 3 cũng là văn phạm loại 2; văn phạm loại 2 cũng là văn phạm loại 1; văn phạm loại 1 cũng là văn phạm loại 0. Tức là: G3 G2 G1 G0. Từ đây suy ra nhận xét trên cũng đúng với các loại ngôn ngữ. Tức là: L3 L2 L1 L0. Phạm Hùng Phú 17
- Chương 1. Tổng quan về Ngôn ngữ và Automat 1.3.5. Ví dụ 1) Xét văn phạm G = (N, T, P, S): a) - N = {S, A}; - T = {a, b}; - S = S; - P = {S → aS; S → aA; A → bA; A → b} Đây là văn phạm loại 3 (vì tập luật sinh có dạng tuyến tính phải). Chẳng hạn, một dẫn xuất từ S có dạng: 3 4 S aS aaS aaaA aaabA aaabbA aaabbbA aaabbbb = a b m n Hay văn phạm sinh ra ngôn ngữ L(G) = {a b | m, n ≥ 1} b) - N = {S}; - T = {a, b}; - S = S; - P: S → abS a là văn phạm tuyến tính phải. c) - N = {S, A, B}; - T = {a, b}; - S = S; - P: S → Aab; A → Aab B; B → a là văn phạm tuyến tính trái. 2) Xét văn phạm G = (N, T, P, S): N = {S}; T = {a, b}; P = { S → aSb; S → ab } Đây là văn phạm loại 2 (CFG). Chẳng hạn, một dẫn xuất từ S có dạng: 4 4 S aSb aaSbb aaaSbbb aaaabbbb = a b n n Hay văn phạm sinh ra ngôn ngữ L(G ) = {a b | n ≥ 1} 2 18 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat 3) Xét văn phạm G = (N, T, P, S): N = {S, B, C}; T = {a, b, c}; P = { S → aSBC; S → aBC; CB → BC; aB →ab; bB → bb; bC → bc; cC → cc}. Đây là văn phạm loại 1 (CSG). Chẳng hạn, một dẫn xuất từ S có dạng: S aSBC aaBCBC aabCBC aabBCC aabbCC aabbcC 2 2 2 aabbcc = a b c n n n Hay văn phạm sinh ra ngôn ngữ L(G ) = {a b c | n > 0}. 1 4) Xét văn phạm G = (N, T, P, S): N = {S, A}; T = {a, b, c}; S = S; P: SA → a; S → bcA; acS → cA. Đây là văn phạm loại 0. 1.4. Một số tính chất của ngôn ngữ Bản chất của ngôn ngữ là tập hợp vì vậy ngôn ngữ mang đầy đủ các tính chất của tập hợp, mặt khác ngôn ngữ lại đƣợc sinh ra bởi văn phạm vì vậy cần phải xem xét ngoài các tính chất của tập hợp ngôn ngữ còn có thêm những tính chất gì ?. Phần này sẽ trình bày một số tính chất của ngôn ngữ do văn phạm sinh ra. 1.4.1. Tính chất 1 Loại của ngôn ngữ đóng với phép hợp. Nói cách khác, tính chất 1 khẳng định rằng hợp của 2 ngôn ngữ cùng loại là ngôn ngữ cùng loại. Giả sử cho 2 văn phạm cùng loại G1 = (N1, T, P1, S1), G2 = (N2, T, P2, S2), văn phạm G1, G2 tƣơng ứng sinh ra ngôn ngữ L1, L2. Giả sử L = L1 L2 ta cần chứng minh: L là ngôn ngữ đƣợc sinh ra bởi văn phạm G cùng loại với văn phạm G1, G2. Điều đáng lƣu ý ở đây là hai văn phạm phải có cùng bảng chữ cái T thì việc xem xét mới có nghĩa. Phạm Hùng Phú 19
- Chương 1. Tổng quan về Ngôn ngữ và Automat Ta xây dựng văn phạm G = (N, T, P, S) thoả mãn 2 điều kiện: - G cùng loại với G1, G2; - G sinh ra L mà L = L1 L2. Muốn thế, ta lấy N = N1N2 S (S không thuộc N1, N2); P = P1P2 S S1, S S2. Với cách xây dựng G nhƣ trên rõ ràng G cùng loại với G1, G2. Bây giờ, ta cần chứng tỏ: L = L(G) = L1L2. Giả sử w L, theo định nghĩa S * w trong G, từ cách xây dựng P, bƣớc đầu tiên trong G chỉ có thể: * * * * S S1 w hoặc S S2 w; nhƣng từ S1 w hoặc S2 w ta suy ra w L1L2. Ngƣợc lại nếu w L1 L2, khi đó w L1 hoặc w L2. * * Theo định nghĩa suy ra S1 w hoặc S2 w. Nếu w L1 có nghĩa là * * * S1 w . Suy ra S S1 w ; tức là S w hay w L, còn nếu w L2 có nghĩa * * * là S2 w. Suy ra S S2 w suy ra S w hay w L. 1.4.2 Tính chất 2 Loại của ngôn ngữ đóng với phép lặp. Tính chất 2 khẳng định rằng phép lặp của một ngôn ngữ là một ngôn ngữ cùng loại. Nghĩa là nếu M = L L L = Li thì M là ngôn ngữ cùng loại với L. Ta có thể kiểm tra tính đúng đắn của các tính chất trên. 1.4.3. Tính chất 3 Cho G = (N, T, P, S) không phải là văn phạm loại 0, có ký hiệu ban đầu S ở vế phải của quy tắc sinh khi đó tồn tại văn phạm G‟ cùng loại và tƣơng đƣơng với G không có ký hiệu bắt đầu ở vế phải của quy tắc sinh. Chứng minh: Giả sử cho G = (N, T, P, S) là văn phạm loại 1, hoặc loại 2, hoặc loại 3, ta xây dựng G‟= (N‟, T, P‟, S‟) nhƣ sau: N‟= N S‟; ở đây S‟ là ký hiệu mới chƣa có trong N và T. P‟ = P S‟ nếu S P, (NT)+ 20 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat Nói cách khác P‟ gồm tất cả các quy tắc sinh của G có bổ sung thêm các quy tắc sinh dạng S‟ nếu trong P có quy tắc sinh dạng S . Với cách xây dựng trên rõ ràng trong G‟ không có quy tắc nào mà ký hiệu bắt đầu S‟ xuất hiện ở vế phải. Bây giờ, ta chỉ cần chứng minh G và G‟ là tƣơng đƣơng, nghĩa là L(G) = L(G‟). Giả sử w L(G) khi đó theo định nghĩa ta có dẫn xuất S * w, tách bƣớc đầu tiên của dẫn xuất này ta có S * w, với (NT)+. Theo cách xây dựng G‟ vì trong G có quy tắc S nên trong G‟ có quy tắc S‟ . Khi đó, dẫn xuất S‟ * w là ở trong G‟ vì dẫn xuất * w trong G cũng là dẫn xuấu trong G‟. Suy ra w L(G‟) hay L(G) L(G‟). Ngƣợc lại giả sử w L(G‟) khi đó theo định nghĩa ta có S‟ * w. Lập luận tƣơng tự nhƣ trên ta có L(G) L(G‟). Suy ra L(G) = L(G‟). Chú ý: Tính chất 3 cho phép ta coi các văn phạm loại 1, 2, 3 không có ký hiệu bắt đầu ở vế phải của các quy tắc sinh. Do đó nếu từ rỗng L(G) thì trong P ắt phải có quy tắc S . 1.4.4. Tính chất 4 Cho G = (N, T, P, S) không phải là văn phạm loại 0, khi đó L(G)\ hoặc L(G) là ngôn ngữ cùng loại L(G). Chứng minh: Tính chất 4 dễ dàng đƣợc chứng minh nhờ tính chất 3 vì nếu văn phạm không phải là văn phạm loại 0 sinh ra từ rỗng thì tập các quy tắc sinh P có chứa quy tắc S . Vì vậy, tập ngôn ngữ L(G)- hoặc L(G) tƣơng ứng với việc loại bỏ khỏi hay bổ sung thêm vào P quy tắc sinh S và với điều này rõ ràng không làm thay đổi loại của ngôn ngữ. 1.4.5. Tính chất 5 (Tính đệ quy của ngôn ngữ) Ta nói rằng văn phạm G là đệ quy nếu tồn tại thuật toán xác định một từ w cho trƣớc có thuộc L(G) hay không? Trƣớc khi nói đến tính đệ quy của ngôn ngữ ta có vài nhận xét sau: Phạm Hùng Phú 21
- Chương 1. Tổng quan về Ngôn ngữ và Automat - Giả sử G = (N, T, P, S) là văn phạm cảm ngữ cảnh, xâu rỗng L(G) khi và chỉ khi tập P có quy tắc S . Nhƣ vậy, ta cần phải kiểm tra quy tắc S có trong P hay không? Bằng cách loại quy tắc S khỏi P, ta có văn phạm cảm ngữ cảnh mới: G‟ = (N, T, P‟, S) Văn phạm G‟ sinh ra L(G) \ , mỗi dẫn xuất trong G‟ thoả mãn điều kiện của văn phạm cảm ngữ cảnh. Nghĩa là trong mọi quy tắc sinh của G‟ có độ dài vế phải lớn hơn hoặc bằng vế trái. Giả sử V = NT, V = n và w là xâu khác xâu rỗng thuộc L(G‟). Ta suy ra S * w. Giả sử dẫn xuất có dạng: S 1 2 m (a) Ở đây m= w. Từ nhận xét trên ta suy ra: 1 2 m Giả sử rằng tồn tại i sao cho các xâu i, i+j trong dãy dẫn xuất trên có độ dài nhƣ nhau và bằng p. Giả sử rằng j > np khi đó suy ra trong dãy dẫn xuất (a) có ít nhất hai xâu giống nhau, do đó suy ra trong V* chỉ có nhiều nhất là np xâu có độ dài p trong trƣờng hợp ngƣợc lại ta có thể bỏ đi ít nhất một bƣớc trong dãy dẫn xuất trên. Giả sử r = s với r < s khi đó dẫn xuất (a) có thể viết lại ngắn hơn là: S i r s+1 m= w. Về mặt trực quan cho phép ta nhận xét nếu có một dẫn xuất của w thì nó sẽ có dẫn xuất không quá dài. Nhận xét này là cơ sở cho định lý sau: Định lý: Cho G = (N, T, P, S) là văn phạm cảm ngữ cảnh khi đó G là văn phạm đệ quy. Chứng minh: Từ nhận xét ở trên, giả sử L(G) không chứa từ rỗng, khi đó ta có quyền giả thiết P không chứa quy tắc S và w thuộc L(G), w T+ và w = n. Ta cần chỉ ra thuật toán xác định w có thuộc L(G) hay không? Ta định nghĩa tập Tm nhƣ sau: + * Tm = V ; n ; S có không quá m bƣớc Rõ ràng T0 = S; Ta cũng dễ dàng thấy rằng có thể tìm Tm qua Tm-1 Tm = Tm-1 ; Tm-1; n (b) 22 Phạm Hùng Phú
- Chương 1. Tổng quan về Ngôn ngữ và Automat * Nếu S và n thì phải thuộc vào một Tm nào đó, trái lại nếu không dẫn xuất đƣợc ra hoặc > n thì sẽ không thuộc bất kỳ Tm nào. Từ cách xây dựng Tm ở trên suy ra Tm là dãy không giảm Tm-1 Tm với mọi m 1; hơn nữa, dãy này bị chặn nên tồn tại m mà Tm= Tm-1 = T‟. Nếu w không thuộc * Tm khi đó w không thuộc L(G) và đƣơng nhiên nếu w thuộc Tm thì S w. Giả sử V = NT và V= q, khi đó trong V+ số xâu có độ dài nhỏ hơn hoặc bằng n là s = q + q2 + q3+ + qn. Ta có s < (1+q)n+1, rõ ràng số từ này là hữu hạn trong T‟. Vì vậy, ta có thể so w với các từ có trong T‟. Nghĩa là tồn tại thuật toán để xác định xem w có thuộc L(G) hay không?. Ví dụ: Cho G = (N, T, P, S): N= S, B, C; T= a, b, c; P: S aSBC; S aBC; CB BC; aB ab; BB bb; bC bc; cC cc; Xét từ w = abac trong L(G); theo cách xây dựng Tm trong định lý trên ta có: T0 = S; T1 = S, aSBC, aBC; T2 = S, aSBC, aBC, abc; T3 = S, aSBC, aBC, abc; T3 = T2 = T‟ Vì w = abac không thuộc T‟ nên w không thuộc L(G). 1.5. Automat 1.5.1. Mô tả automat Ngoài văn phạm, ngƣời ta còn sử dụng một phƣơng tiện khác để biểu diễn ngôn ngữ; đó là automat. Automat đƣợc hiểu là một “máy” trừu tƣợng có cơ cấu và hoạt động rất đơn giản nhƣng có khả năng đoán nhận ngôn ngữ. Với một xâu bất kỳ, sau một số bƣớc làm việc, automat sẽ cho câu trả lời xâu đó có thuộc ngôn ngữ hay không. Để có đƣợc quá trình tự động nhƣ vậy, ngƣời ta thƣờng phải lập trình sẵn cho nó một “lộ trình” thực hiện và các máy chỉ cần hoạt động theo đúng lộ trình này. Một trong số những máy tự động này điển hình mạnh nhất có thể nói chính là Phạm Hùng Phú 23
- Chương 1. Tổng quan về Ngôn ngữ và Automat máy tính số ngày nay. Tuy hoạt động theo kiểu “máy”, song thực chất mỗi bƣớc làm việc của automat là một sự thay thế ký hiệu, nghĩa là một bƣớc dẫn xuất nhƣ đã nói ở trên. Nói chung, một mô hình automat thƣờng bao gồm những thành phần chủ yếu nhƣ sau: a a a a a a 1 2 3 4 i n Băng vào Đầu đọc Bộ điều khiển Hình 1. Mô hình chung cho một automat Xâu vào cần xác định sẽ đƣợc lƣu trữ trên băng vào (input). Tại mỗi thời điểm, ứng với trạng thái hiện thời, máy đọc một ký tự trên băng vào (input), có thể kết hợp với việc xem xét ký hiệu tƣơng ứng trong bộ nhớ, bộ điều khiển của automat sẽ quyết định bƣớc chuyển đến trạng thái tiếp theo. Các loại automat tƣơng ứng với một số lớp văn phạm sẽ đƣợc giới thiệu lần lƣợt trong các chƣơng tiếp theo. 1.5.2. Phân loại automat Dựa vào sự hoạt động của automat, có thể chia automat thành hai loại automat đơn định và automat không đơn định. Automat đơn định (Deterministic Automata): Là một automat mà tại mỗi bƣớc di chuyển, bộ điều khiển chỉ có duy nhất một khả năng lựa chọn trạng thái đƣợc chuyển đến tiếp theo khi đọc vào một ký tự trên băng vào. Sự duy nhất này thể hiện tính đơn định, nghĩa là hàm chuyển của automat dạng này luôn là đơn trị. Automat không đơn định (Non - deterministic Automata): Là một automat mà tại mỗi bƣớc di chuyển, bộ điều khiển có một vài khả năng để chọn lựa trạng thái đƣợc chuyển đến tiếp theo khi đọc vào một ký tự trên băng vào. Sự chọn lựa này thể hiện tính không đơn định, nghĩa là hàm chuyển của automat dạng này là đa trị. 24 Phạm Hùng Phú
- Câu hỏi và bài tập chương 1 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 1.1. Nêu khái niệm ngôn ngữ hình thức, công cụ và lĩnh vực nghiên cứu của nó. 1.2. Nêu các khái niệm: bảng chữ cái, xâu trên bảng chữ cái, tiền tố, hậu tố; cho ví dụ. 1.3. Nêu các phép toán trên xâu; cho ví dụ. 1.4. Nêu các khái niệm: *, +, ngôn ngữ; cho ví dụ. 1.5. Nêu các phép toán trên ngôn ngữ; cho ví dụ. 1.6. Nêu định nghĩa văn phạm; cho ví dụ. 1.7. Nêu khái niệm ngôn ngữ sinh bởi văn phạm; cho ví dụ. 1.8. Nêu cách phân loại và các loại văn phạm và ngôn ngữ; cho ví dụ. 1.9. Nêu khái niệm văn phạm tƣơng đƣơng; cho ví dụ. 1.10. Nêu các tính chất của ngôn ngữ. 1.11. Mô tả automat, cách phân loại và các loại automat. 1.12. Nêu các phƣơng pháp biểu diễn ngôn ngữ; cho ví dụ. 1.13. Cho bảng chữ cái T = {0 ,1}. Ta ký hiệu T* là tập tất cả các xâu (kể cả xâu rỗng ). 1) Hãy biểu diễn T* dƣới dạng liệt kê theo thứ tự độ dài tăng dần và trong các xâu có cùng độ dài thì theo thứ tự từ điển. 2) Chỉ ra một số ngôn ngữ trên bảng chữ cái T. 1.14. Cho bảng chữ cái T = {0 ,1}. L1 và L2 là hai ngôn ngữ trên bảng chữ cái T; với: L1 = {0, 1}; L2 = {, 0, 1, 00, 11, 000, 001, 010, 011, 100}. Hãy tính: 1) L1 L2 2) L1 L2 3) L1 - L2 4) L2 - L1 5) L1L2 Phạm Hùng Phú 25
- Câu hỏi và bài tập chương 1 1.15. Cho bảng chữ cái = {a , b}. L là một ngôn ngữ trên bảng chữ cái ; với: L = {, a, b}. Hãy tính: 1) L 0 1 2 3 2) L , L , L , L 1.16. Tìm các biểu diễn hữu hạn cho các ngôn ngữ vô hạn sau: 1) L1 = {, ab, aabb, aaabbb, } 2) L2 = {, 0, 1, 00, 01, 000, 001, 011, 111, 0000, 0001, 0011, 0001, 1111, } 1.17. Cho các văn phạm sau đây: 1) G = (N, T, P, S) với tập quy tắc sinh là: P ={S ABC; AB aADb; Dab bDb; DbC BaC; aB Ba; AB ; C }. 2) G = (N, T, P, S) với tập quy tắc sinh là: P = {S ABaDF; BD DCB; BC bB; AD AAE; EC AE; EB BE; EF BBDF; DF B | }. 3) G = (N, T, P, S) với tập quy tắc sinh là: P = {S SS; S aSb; S bSa; S ab; S ba}. 4) G = (N, T, P, S) với tập quy tắc sinh là: P = {S aA; S a; A abB B ; }. a) Cho biết văn phạm nào là văn phạm chính quy, văn phạm nào là văn phạm phi ngữ cảnh, văn phạm nào là văn phạm ngữ cấu; Tại sao. b) Viết lại mỗi văn phạm dƣới dạng đầy đủ theo định nghĩa của văn phạm. 1.18. Hãy chỉ ra mỗi văn phạm sau đây thuộc loại nào?. Nêu các thành phần của mỗi văn phạm đó. 1) S Sab; S b; S Aa; A Sa; A Abbba; A a; S . 2) S AB; AB BA; A aA; B Bb; A a; B b. 3) S A; S AAB; Aa Aba; A aa; Bb Abb; AB ABB; B b. 1.19. Cho văn phạm có tập các luật sinh: S Sa; S a; S . 26 Phạm Hùng Phú
- Câu hỏi và bài tập chương 1 1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên. 2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau: - w = ; - w = a; - w = aa; - w = ai ; với i N. 3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên. 1.20. Cho văn phạm có tập các luật sinh: S aA; A aA; A aB; B bB; B b. 1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên. 2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau: - w = aab; - w = aaaaabb; - w = ai bj; với i, j N+; i 2. 3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên. 1.21. Cho văn phạm có tập các luật sinh: S bSa; S . 1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên. 2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau: - w = ; - w = ba; - w = bbbaaa; - w = bi ai; với i N. 3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên. 1.22. Cho văn phạm có tập các luật sinh: S aAb; S ; A aAb; A . 1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên. 2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau: - w = ; - w = ab; - w = aaaabbbb; - w = ai bi; với i N. 3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên. Phạm Hùng Phú 27
- Câu hỏi và bài tập chương 1 1.23. Cho văn phạm có tập các luật sinh: S AB; A aA; A a; B aB; B b. 1) Văn phạm trên thuộc loại nào; nêu đầy đủ các thành phần của văn phạm trên. 2) Chỉ ra các dẫn xuất sinh ra mỗi từ sau: - w = aab; - w = aaaaabb; - w = ai b; với i N+. 3) Chỉ ra ngôn ngữ sinh bởi văn phạm trên. 1.24. Chỉ ra văn phạm G có tập T = a, b sao cho xâu L(G) có một trong các tính chất sau: 1) Bắt đầu bằng kí tự a. 2) Kết thúc bằng hai kí tự ab. 3) Kết thúc bằng hai kí tự ba. 4) Không kết thúc bằng ab. 1.25. Cho ngôn ngữ: L = {0i 1 | i N+ } 1) Chỉ ra văn phạm tuyến tính trái sinh ra ngôn ngữ trên. 2) Chỉ ra văn phạm tuyến tính phải sinh ra ngôn ngữ trên. 3) Chỉ ra văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên. 1.26. Cho ngôn ngữ: L = {03 1i| i N+ } 1) Chỉ ra văn phạm tuyến tính trái sinh ra ngôn ngữ trên. 2) Chỉ ra văn phạm tuyến tính phải sinh ra ngôn ngữ trên. 3) Chỉ ra văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên. 1.27. Cho ngôn ngữ: L = {0i1i 2j 3j | i N+, j N }. Xây dựng văn phạm phi ngữ cảnh sinh ra ngôn ngữ trên. 1.28. Cho ngôn ngữ L = {an bn cm | n N+, m N}. Hãy chỉ ra văn phạm phi ngữ cảnh G sao cho L(G) = L. 1.29. Cho ngôn ngữ L = {(ab)n cm | n, m N+}. Hãy chỉ ra: 1) Văn phạm tuyến tính phải sinh ra ngôn ngữ trên. 2) Văn phạm tuyến tính trái sinh ra ngôn ngữ trên. 3) Văn phạm phi ngữ cảnh sinh ra ngôn ngữ trên. 1.30. Cho ngôn ngữ: L = {031i 2j | i, j N+} 28 Phạm Hùng Phú
- Câu hỏi và bài tập chương 1 1) Xây dựng văn phạm tuyến tính trái sinh ra ngôn ngữ trên. 2) Xây dựng văn phạm tuyến tính phải sinh ra ngôn ngữ trên. 3) Xây dựng văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên. 1.31. Cho ngôn ngữ: L = {0i1j 2k | i, j, k N } 1) Xây dựng văn phạm tuyến tính trái sinh ra ngôn ngữ trên. 2) Xây dựng văn phạm tuyến tính phải sinh ra ngôn ngữ trên. 3) Xây dựng văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên. 1.32. Cho ngôn ngữ: L = {0i1j 2k 3m| i, j, k, m N } 1) Xây dựng văn phạm tuyến tính trái sinh ra ngôn ngữ trên. 2) Xây dựng văn phạm tuyến tính phải sinh ra ngôn ngữ trên. 3) Xây dựng văn phạm phi ngữ cảnh (không chính quy) sinh ra ngôn ngữ trên. Phạm Hùng Phú 29
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Chƣơng 2. VĂN PHẠM CHÍNH QUY VÀ AUTOMAT HỮU HẠN (Regular Grammar -RG and Finite Automata -FA) Mục tiêu: Giúp sinh viên có khả năng: - Trình bày đƣợc khái niệm và xác định đƣợc các thành phần của một FA và phân loại đƣợc FA. - Biết cách chuyển từ NFA sang NFA và từ NFA sang DFA. - Viết đƣợc biểu thức chính quy ký hiệu cho ngôn ngữ chính quy. - Hiểu đƣợc mối liên hệ giữa FA và biểu thức chính quy và xây dựng đƣợc NFA từ một biểu thức chính quy và ngƣợc lại. - Nhận dạng đƣợc lớp ngôn chính quy do văn phạm chính quy (RG) sinh ra. - Xây dựng đƣợc văn phạm chính quy sinh ra ngôn ngữ đƣợc đoán nhận FA và ngƣợc lại. Nội dung chính: - Automat hữu hạn (FA): định nghĩa, ngôn ngữ đoán nhận bởi FA. - Automat hữu hạn đơn định (DFA) và Automat hữu hạn không đơn định (NFA) . - Sự tƣơng đƣơng giữa DFA và NFA. - Biểu thức chính quy: định nghĩa và tính chất. - Sự tƣơng đƣơng giƣa FA và biểu thức chính quy - Văn phạm chính quy: văn phạm tuyến tính, sự tƣơng đƣơng giữa văn phạm chính quy và FA - Tính chất của RL (Regular Languages ). 30 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2.1. Automat hữu hạn (FINITE AUTOMAT - FA) Automat hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các thông tin vào (input) và các thông tin ra (output). Tại mỗi thời điểm, hệ thống có thể đƣợc xác định ở một trong số hữu hạn các cấu hình nội bộ gọi là các trạng thái (states). Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liên quan đến những input đã chuyển qua và xác định các phép chuyển tiếp theo trên dãy input tiếp theo. Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự nhiên của khái niệm và khả năng ứng dụng đa dạng trong nhiều lĩnh vực thực tế. Automat hữu hạn (FA) đƣợc chia thành 2 loại: đơn định (DFA) và không đơn định (NFA). Cả hai loại automat hữu hạn đều có khả năng nhận dạng chính xác tập chính quy. Automat hữu hạn đơn định có khả năng nhận dạng ngôn ngữ dễ dàng hơn automat hữu hạn không đơn định, nhƣng thay vào đó thông thƣờng kích thƣớc của nó lại lớn hơn so với automat hữu hạn không đơn định tƣơng đƣơng. Automat hữu hạn đƣợc coi là một công cụ hữu hiệu để nghiên cứu một lớp các ngôn ngữ quan trọng, đó là ngôn ngữ chính quy. Trƣớc hết, ta đƣa ra định nghĩa về Automat hữu hạn. 2.1.1. Định nghĩa Automat hữu hạn Một cách hình thức ta coi Automat hữu hạn là một hệ thống gồm 5 thành phần, ký hiệu là M = trong đó: Q - Tập hữu hạn khác rỗng các trạng thái. - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào). - Ánh xạ còn gọi là hàm chuyển trạng thái và có một trong hai dạng sau: 1) : Q Q (q, a) p 2) : Q 2Q Phạm Hùng Phú 31
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. F tập các trạng thái kết thúc; F Q . Nếu p là ảnh của (q, a) qua ánh xạ thì ký hiệu là (q,a) = p; với q Q, a và p Q hoặc p 2Q. a 1 a2 a3 a4 ai an Băng vào Đầu đọc Bộ điều khiển Hình 2.1. Mô hình mô tả một FA Ta vẽ FA nhƣ là bộ điều khiển hữu hạn trạng thái, với mỗi trạng thái q Q, FA đọc một ký hiệu a Σ viết trên băng vào (nhƣ hình vẽ). Trong một lần chuyển, FA đang ở trạng thái q đọc ký hiệu vào a trên băng vào, chuyển sang trạng thái đƣợc xác định bởi hàm chuyển δ(q, a), rồi dịch đầu đọc sang phải một ký tự. Nếu δ(q, a) chuyển đến một trong những trạng thái kết thúc thì FA đoán nhận xâu đƣợc viết trên băng vào (input) phía trƣớc đầu đọc, nhƣng không bao gồm ký tự tại vị trí đầu đọc vừa dịch chuyển đến. Trong trƣờng hợp đầu đọc đã dịch đến cuối xâu trên băng thì FA mới đoán nhận toàn bộ xâu trên băng vào. Ví dụ: 1) Cho automat hữu hạn M = trong đó: -q0 = q0 ; - = 0, 1; 32 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn - Q = q0, q1, q2, q3; - F = q0; - : (q0, 0) = q2 ; (q0, 1) = q1 ; (q1, 0) = q3 ; (q1, 1) = q0 ; (q2, 0) = q0 ; (q2, 1) = q3 ; (q3, 0) = q1 ; (q3, 1) = q2 (Hàm chuyển thuộc dạng 1). 2) Cho automat hữu hạn M = trong đó: - Q = q0, q1, q2, q3; - = 0,1; - q0 = q0 ; - F = q3; - : (q0, 0) = q2 ; (q0, 1) = q1 ; (q1, 0) = q2 ; (q1, 1) = {q1, q3 } ; (q2, 0) = q3 ; (q2, 1) = q1 ; (q3, 0) = q3 ; (q3, 1) = q3. (Hàm chuyển thuộc dạng 2). 2.1.1. Biểu diễn Automat hữu hạn 1) Phương pháp đồ thị Để tiện cho việc xem xét một cách trực quan, ngƣời ta dùng sơ đồ để biểu diễn Automat, phƣơng pháp này gọi là phƣơng pháp đồ thị. Trong đồ thị, ngƣời ta biểu diễn mỗi Automat ứng với một đồ thị có hƣớng, có trọng số. Mỗi trạng thái của Q ứng với một đỉnh của đồ thị; mỗi cung có hƣớng đi từ đỉnh q đến đỉnh p có trọng số là a nếu (q, a) = p. Phạm Hùng Phú 33
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2) Phương pháp bảng Trong phƣơng pháp này, ngƣời ta dùng bảng gồm m dòng, n cột trong đó m là số trạng thái của Q, n là số kí tự vào của bảng chữ cái vào . - Mỗi hàng là một trạng thái qi với i = 1, , m ; - Mỗi cột là một ký hiệu vào aj với j = 1, , n; - Ô (i, j), giao của hàng i và cột j là qk nếu (qi, aj) = qk. Ví dụ 1: Cho automat M = trong đó: -q0 = q0 ; - = 0, 1; - Q = q0, q1, q2, q3; - F = q0; - : (q0, 0) = q2 ; (q0, 1) = q1 ; (q1, 0) = q3 ; (q1, 1) = q0 ; (q2, 0) = q0 ; (q2, 1) = q3 ; (q3, 0) = q1 ; (q3, 1) = q2 Biểu diễn của automat trên bằng phƣơng pháp đồ thị 0 0 1 Start 1 1 q0 q1 q2 q3 1 0 0 Hình 2.2. Biểu diễn Automat bằng đồ thị Biểu diễn automat bằng bảng -q0 = q0 ; 34 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn - F = q0 Q 0 1 q0 q2 q1 q1 q3 q0 q2 q0 q3 q3 q1 q2 Bảng 2.1. Bảng chuyển trạng thái Ví dụ 2: Cho automat hữu hạn M = trong đó: - Q = q0, q1, q2, q3; - = 0,1; - q0 = q0 ; - F = q3; - : (q0, 0) = q2 ; (q0, 1) = q1 ; (q1, 0) = q2 ; (q1, 1) = {q1, q3 } ; (q2, 0) = q3 ; (q2, 1) = q1 ; (q3, 0) = q3 ; (q3, 1) = q3. Biểu diễn của automat trên bằng phƣơng pháp đồ thị 1 1 1 Start 1 0 0 q q0 q1 q2 3 0 1 0 Hình 2.3. Đồ thị biểu diễn Automat Phạm Hùng Phú 35
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Biểu diễn automat bằng bảng - q0 = q0 ; - F = q3; Q 0 1 q0 {q2} {q1} q1 {q2} {q1,q3} q2 {q3} {q1} q3 {q3} {q3} Bảng 2.2. Bảng chuyển trạng thái 2.1.2. Automat hữu hạn đơn định 1) Định nghĩa Cho Automat hữu hạn M = , ta gọi M là Automat hữu hạn đơn định nếu:Với a , q Q ta có (q, a) = 1 và hàm chuyển có dạng 1 (*) Cụ thể: Automat hữu hạn đơn định là một hệ thống gồm 5 thành phần; ký hiệu là M = , trong đó: Q - Tập hữu hạn khác rỗng các trạng thái. - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào). - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng: : Q Q (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. F - Tập con của Q ( F Q) là tập các trạng thái kết thúc. 36 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Nếu p là ảnh của (q, a) qua ánh xạ thì ký hiệu là (q, a) = p; với q, p Q; a và đƣợc gọi là một phép chuyển từ trạng thái q sang trạng thái p khi automat nhận ký tự vào là a. Nhƣ vậy, Automat hữu hạn đơn định đang ở trạng thái q, nhận một ký tự vào a thì nó hoặc không thay đổi trạng thái (chuyển vào chính nó) hoặc xác định duy nhất một trạng thái chuyển tiếp theo. Ngƣợc lại, Automat không thoả mãn điều kiện (*) gọi là Automat không đơn định (Nondeterministic Automat). Nếu M là Automat hữu hạn không đơn định thì sẽ a , q Q sao cho (q, a) 1 hay (q, a) sẽ là một tập con của Q. 2) Hàm chuyển trạng thái mở rộng Để có thể mô tả cách hình thức hoạt động của DFA trên một xâu vào, ta mở rộng hàm chuyển δ để áp dụng đối với một trạng thái trên một xâu. Ta định nghĩa hàm chuyển mở rộng δ* là một ánh xạ từ Q × Σ* → Q với ý nghĩa δ*(q, w) là trạng thái DFA chuyển đến từ trạng thái q trên xâu vào w: 1. δ* (q, ε) = q 2. δ*(q, wa) = δ(δ*(q, w), a); với q Q; w Σ* và a Σ. Suy ra: * (q, a a a ) = q, a1 an-1 an 1 2 n * (q, a a a ) = q, a1 an-1 an 1 2 n = q1, a2 an-1 an = = q n-2, an-1 an = qn-1, an = qn Ví dụ: Cho Automat hữu hạn M = Phạm Hùng Phú 37
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Q = q0, q1, q2, q3; = 0, 1; q0 = q0 ; F = q0 Hàm chuyển xác định nhƣ sau: (q0, 0) = q2; (q0, 1) = q1; (q1, 0) = q3; (q1, 1) = q0; (q2, 0) = q0; (q2, 1) = q3; (q3, 0) = q1; (q3, 1) = q2. Hãy tính (q2, 1010). Áp dụng công thức (1), ta có: (q2, 1) = q3; (q3, 0) = q1; (q1, 1) = q0; (q0, 0) = q2; Vậy (q2, 1010) = q2. 3) Ngôn ngữ đoán nhận bởi automat hữu hạn đơn định Cho Automat hữu hạn đơn định M = , ta gọi ngôn ngữ đoán nhận bởi Automat hữu hạn đơn định M là tập: * * * L(M) = w Σ (q0,w) = q F và w Nhƣ vậy, ngôn ngữ đoán nhận bởi Automat hữu hạn đơn định DFA M là tập * tất cả các xâu vào w sao cho khi Automat ở trạng thái ban đầu q0, nhận từ vào w thì nó có thể chuyển dịch về trạng thái kết thúc thuộc tập F. Một xâu vào w = a a a đƣợc đoán nhận bởi một DFA nếu có tồn tại một dãy 1 2 n các phép chuyển, tƣơng ứng với xâu vào, từ trạng thái bắt đầu đến trạng thái kết thúc. w = a1 a2 a3 an -1 an q q q q q 0 1 2 n-1 n Hình 2.4. Mô tả quá trình DFA M đoán nhận xâu Nhƣ vậy, để kiểm tra một xâu vào w = a a a đƣợc đoán nhận bởi một 1 2 n * NFA hay không ?. Ta phải tính (q0,w). 38 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn * * (q0,w) = (q0, a a a ) = q0, a1 an-1 an 1 2 n = q0, a1 an-1 an = q1, a2 an-1 an = = q n-2, an-1 an = qn-1, an = qn Nếu qn F thì w N(M); ngƣợc lại qn F thì w N(M). Ở đây q1q2qn Q. Ví dụ: Cho Automat hữu hạn M = trong ví dụ trên và đƣợc biểu diễn dƣới dạng bảng là: q0 = q0 ; F = q0 0 1 Q q q q 0 2 1 q q q 1 3 0 q q q 2 0 3 q q q 3 1 2 Bảng 2.3. Biểu diễn automat bằng bảng Hãy kiểm tra xem xâu w = 110101 có thuộc L(M) không?. Ta có δ(q , 1) = q ; 0 1 δ(q , 1) = q ; 1 0 δ(q , 0) = q ; 0 2 (q2, 1) = q3; (q3, 0) = q1; Phạm Hùng Phú 39
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn (q1, 1) = q0; * Và cuối cùng δ (q , 110101) = q F. Vậy 110101 L(M). 0 0 Ta có thể chứng minh đƣợc rằng L(M) là tập mọi xâu có số chẵn số 0 và số chẵn số 1. Từ các kết quả trên, ta có giải thuật sử dụng DFA để đoán nhận xâu của ngôn ngữ. 4) Giải thuật mô phỏng hoạt động của một DFA Input : Xâu vào w kết thúc bởi $ Output: Câu trả lời "YES" nếu DFA đoán nhận đƣợc xâu w và "NO" nếu ngƣợc lại. Process q := q ; 0 c := getchar() ; {c là ký hiệu vào đầu tiên} While c $ do begin q := δ(q, c); c := nextchar(); {c là ký hiệu vào đƣợc đọc tiếp theo} end; If q F then write("YES" ) Else write("NO" ) Ví dụ: Sử dụng giải thuật trên với automat đƣợc cho ở hình 2.5 để đoán nhận các từ sau: - w = bbaaabb$ a Start a b b 0 1 2 3 b Hình 2.5. Đồ thị biểu diễn Automat Ta trình bày giải thuật sử dụng automat đơn định đoán nhận w bằng bảng sau: 40 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Bƣớc q c khởi tạo 0 b 1 0 b 2 0 a 3 1 a 4 1 a 5 1 b 6 2 b 7 3 $ Bảng 2.4. Quá trình Automat đoán nhận xâu Ta có q = 3 F. Vậy automat trên đoán nhận đƣợc từ w = bbaaabb. - w = bbaaaaab$ Ta trình bày giải thuật sử dụng automat đơn định đoán nhận w bằng bảng sau: Bƣớc q c khởi tạo 0 b 1 0 b 2 0 a 3 1 a 4 1 a 5 1 a 6 1 a 7 1 b 8 2 $ Bảng 2.5. Quá trình Automat đoán nhận xâu Ta có q = 2 F. Vậy automat trên không đoán nhận đƣợc từ w = bbaaaaab. Phạm Hùng Phú 41
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2.1.3. Automat hữu hạn không đơn định-NFA (Nondeterministic Finite Automata) Xét một dạng sửa đổi mô hình DFA có thể lựa chọn một trong nhiều hơn một phép chuyển từ một trạng thái trên cùng một ký hiệu vào để di chuyển đến đến trạng thái tiếp theo. Mô hình mới này gọi là automat hữu hạn không đơn định (NFA). 1) Định nghĩa Cho Automat hữu hạn M = , ta gọi M là Automat hữu hạn không đơn định nếu: a và q Q sao cho (q, a) >1 và hàm chuyển có dạng 2. Cụ thể: Automat hữu hạn không đơn định là một hệ thống gồm 5 thành phần, ký hiệu là M = trong đó: Q - Tập hữu hạn khác rỗng các trạng thái. - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào). - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng: : Q 2Q (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. F - Tập con của Q là tập các trạng thái kết thúc. Nếu p là ảnh của (q, a) qua ánh xạ thì ký hiệu là (q,a) = p; với q Q, a Q và p 2 (p Q). Nhƣ vậy, δ(q, a) là tập hợp p tất cả các trạng thái pi Q sao cho có phép chuyển trên nhãn a từ trạng thái q tới pi . Ví dụ: Cho automat hữu hạn không đơn định (NFA) M = trong đó: - Q = {q , q , q , q , q }; 0 1 2 3 4 - {0, 1}; - (q0, 0) = {q , q }; 0 3 (q0, 1) = {q , q }; 0 1 42 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn (q1, 1) = {q }; 2 (q2, 0) = {q }; 2 (q2, 1) = {q }; 2 (q3, 0) = {q }; 4 (q4, 0) = {q }; 4 (q4, 1) = {q }; 4 - q0 = q0; - F = {q , q }. 2 4 - Biểu diễn NFA trên bằng bảng, ta có Q 0 1 {q ,q } {q ,q } q0 0 3 0 1 {q } q1 2 {q } {q } q2 2 2 {q } q3 4 {q } {q } q4 4 4 Bảng 2.6. Bảng chuyển trạng thái - Biểu diễn NFA trên bằng đồ thị, ta có 1 1 1 q q 1 1 2 1 Start q0 0 0 0 q3 q4 0 0 Hình 2.6. Đồ thị của NFA Phạm Hùng Phú 43
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2) Hàm chuyển trạng thái mở rộng Để có thể mô tả cách hình thức hoạt động của NFA trên một xâu vào, ta mở rộng hàm chuyển δ để áp dụng đối với một trạng thái trên một xâu. Ta định nghĩa hàm chuyển mở rộng δ* là một ánh xạ từ Q × Σ* → Q với ý nghĩa δ*(q, w) là tập trạng thái mà NFA có thể chuyển đến từ trạng thái q trên xâu vào w: 1. δ*(q, ε) = {q} ; 2. δ*(q, wa) = δ(δ*(q, w), a) với q Q; w Σ* và a Σ 3. δ*(P, a) = δ*(q, a) với P Q. q P Suy ra: δ*(P, a) = δ(δ* (q, ), a) = δ(q, a) q P q P Hay δ*(P, a) = δ(q, a) với P Q. q P Ví dụ: Cho automat trong ví dụ trên biểu diễn bằng đồ thị ở hình 2.6. * Hãy tính (q0, 01001). Áp dụng công thức 2 ở trên, ta có: * (q0, 01001) = q0, 0100 1 = q0, 010), 0 1 = q0, 01), 0), 0 1 = q0, 0), 1), 0), 0 1 = q0, ), 0), 1), 0), 0 1 = q0, 0), 1), 0), 0 1 (q0, 0) = {q , q }; 0 3 q0, 0), 1) = {q , q }, 1) = q , 1) q , 1) = {q , q } ∅ 0 3 0 3 0 1 = {q , q }; 0 1 44 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn q0, 0), 1), 0) = {q , q }, 0) = q , 0) q , 0) = {q , q }∅ 0 1 0 1 0 3 = {q , q }; 0 3 q0, 0), 1), 0), 0 {q , q }, 0 0 3 = δ (q , 0) δ (q , 0) = {q , q } {q } ={q , q , q }; 0 3 0 3 4 0 3 4 q0, 0), 1), 0), 0 1 δ({q , q , q }, 1) = δ (q , 1) δ (q , 1)δ (q , 1) 0 3 4 0 3 4 = {q , q }∅ {q } ={q , q , q }; 0 1 4 0 1 4 δ*(q , 01001) = {q , q , q }; 0 0 1 4 Tƣơng tự nhƣ DFA, NFA cũng hoạt động với một bộ điều khiển gồm hữu hạn trạng thái và một đầu đọc đọc các ký hiệu trên xâu vào. Tuy nhiên, tại mỗi thời điểm, bộ điều khiển có thể chứa một tập các trạng thái. Khi đó, để có sự lựa chọn trạng thái tiếp theo, chẳng hạn nhƣ từ trạng thái q trên ký hiệu vào 0 ở ví dụ trên, ta 0 phải tƣởng tƣợng nhƣ có các bản sao của automat đang thực hiện đồng thời. Mỗi trạng thái tiếp theo mà automat có thể chuyển đến sẽ tƣơng ứng với một bản sao của automat mà tại đó bộ điều khiển đang chứa trạng thái đó. Chẳng hạn, với xâu 01001, ta có: 0 1 0 0 1 q0 q0 q0 q0 q0 q0 0 1 0 0 1 q3 q1 q3 q3 q1 0 q 4 1 q4 Hình 2.7. Quá trình suy diễn để đoán nhận xâu trong NFA 3) Ngôn ngữ đoán nhận bởi automat không đơn định Cho Automat hữu hạn không đơn định M = , ta gọi ngôn ngữ đoán nhận bởi Automat hữu hạn không đơn định M là tập: Phạm Hùng Phú 45
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn * * * L(M) = w Σ (q0,w) = q F và w Hay L(M) = {w * | δ*(q , w) có chứa một trạng thái trong F } 0 Nhƣ vậy, ngôn ngữ đoán nhận bởi Automat hữu hạn không đơn định M là tập tất cả các xâu vào w * nếu tồn tại một dãy các phép chuyển (đƣờng đi) sao cho khi Automat ở trạng thái ban đầu q0, nhận từ vào w thì nó có thể chuyển dịch về một trong các trạng thái kết thúc thuộc tập F. Chú ý rằng có thể xem automat hữu hạn đơn định - DFA là một trƣờng hợp đặc biệt của NFA, trong đó với mỗi trạng thái và mỗi ký hiệu vào chỉ có duy nhất một lựa chọn phép chuyển sang trạng thái tiếp theo. Vì thế trong DFA, với một xâu vào w và một trạng thái bắt đầu q0, chỉ có đúng một đƣờng đi nhãn w bắt đầu từ q0. Để xác định xâu w có đƣợc đoán nhận bởi DFA hay không chỉ cần kiểm tra đƣờng đi này. Nhƣng đối với NFA, có thể có nhiều đƣờng đi có nhãn là w bắt đầu từ q0 và do đó tất cả phải đƣợc kiểm tra để thấy có hay không có đƣờng đi tới trạng thái kết thúc. Do đó, một xâu vào w = a a a đƣợc đoán nhận bởi một NFA nếu có tồn tại 1 2 n một dãy các phép chuyển, tƣơng ứng với xâu vào, từ trạng thái bắt đầu đến trạng thái kết thúc. Nhƣ vậy, để kiểm tra một xâu vào w = a a a đƣợc đoán nhận bởi 1 2 n * một NFA hay không ?. Ta phải tính (q0,w). * * (q0,w) = (q0, a a a ) = q0, a1 an-1 an 1 2 n = q0, a1 an-1 an = q1, a2 an-1 an = = q n-2, an-1 an = qn-1, an = qn. Nếu qn F ≠ thì w N(M); ngƣợc lại qn F thì w N(M). Ở đây q1q2qn Q. 46 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Ví dụ: Cho automat hữu hạn không đơn định (NFA): M = trong ví dụ trên. Hãy kiểm tra xem xâu w = 01001 có thuộc ngôn ngữ L(M) hay không ?. Ta có: δ (q , 0) = {q , q }; 0 0 3 δ({q , q },1) = δ (q , 1) δ (q , 1) = {q , q } ∅ = {q , q }; 0 3 0 3 0 1 0 1 δ({q , q }, 0) = δ (q , 0) δ (q , 0) = {q , q } ∅={q , q }; 0 1 0 1 0 3 0 3 δ({q , q }, 0) = δ (q , 0) δ (q , 0) = {q , q } {q } ={q , q , q }; 0 3 0 3 0 3 4 0 3 4 δ({q , q , q }, 1) = δ (q , 1) δ (q , 1)δ (q , 1) = {q , q }∅ {q } 0 3 4 0 3 4 0 1 4 ={q , q , q }; 0 1 4 δ*(q , 01001) = {q , q , q }; 0 0 1 4 Do {q , q , q } {q } = {q } ≠ nên w N(M). 0 1 4 4 4 Automat này đoán nhận đƣợc tất cả các xâu có hai số 0 liên tiếp hoặc hai số 1 liên tiếp. Từ các kết quả trên, ta có giải thuật sử dụng DFA để đoán nhận xâu của ngôn ngữ. 4) Giải thuật mô phỏng hoạt động của một NFA Input : xâu vào w kết thúc bởi $ Output: Câu trả lời "YES" nếu NFA đoán nhận đƣợc xâu w và "NO" nếu ngƣợc lại. Process q := q ; 0 c := getchar() ; {c là ký hiệu vào đầu tiên} While c $ do begin q := δ(q, c); c := nextchar() ; {c là ký hiệu vào đƣợc đọc tiếp theo} end; Phạm Hùng Phú 47
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn If q F ≠ then write("YES" ) Else write("NO" ) Ví dụ: Sử dụng giải thuật trên với automat hữu hạn đƣợc cho bằng đồ thị sau để đoán nhận các xâu: w = aaabbbb$ a b Start a b b 0 1 2 3 a Hình 2.8. Đồ thị biểu diễn Automat Ta trình bày giải thuật sử dụng automat hữu hạn không đơn định đoán nhận w bằng bảng sau: Bƣớc q c khởi tạo 0 a 1 {0, 1} a 2 {0, 1} a 3 {0, 1} b 4 {2} b 5 {2, 3} b 6 {2, 3} b 7 {2, 3} $ Bảng 2.7. Mô tả quá trình đoán nhận xâu Ta có q = {2, 3} F = {3} . Vậy automat trên đoán nhận đƣợc từ w = aaabbbb. 48 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2.1.4. Sự tƣơng đƣơng giữa DFA và NFA Mỗi DFA là một NFA đặc biệt, nên rõ ràng lớp ngôn ngữ đƣợc đoán nhận bởi NFA cũng bao gồm các tập chính quy (đây chính là ngôn ngữ đƣợc đoán nhận bởi DFA ). Tuy nhiên, không có cơ sở để nói rằng NFA chỉ đoán nhận duy nhất các tập hợp này. Điều đó cho thấy DFA có thể mô phỏng đƣợc hoạt động của NFA, nghĩa là với mỗi NFA, ta có thể xây dựng một DFA tƣơng đƣơng (đoán nhận cùng một ngôn ngữ với nó). Để một DFA mô phỏng đƣợc hoạt động của NFA ta cho các trạng thái của DFA tƣơng ứng với tập các trạng thái của NFA. Tại mỗi thời điểm, DFA lƣu giữ trong bộ điều khiển tất cả các trạng thái mà NFA có thể chuyển đến khi đọc cùng một ký hiệu vào nhƣ DFA. 1) Định lý Giả sử L(M) là ngôn ngữ đoán nhận bởi Automat hữu hạn không đơn định M, khi đó sẽ tồn tại Automat hữu hạn đơn định M‟ đoán nhận L(M) hay nói cách khác L(M) = L(M‟). Chứng minh: Giả sử cho M = là Automat không đơn định, ta xây dựng Automat M‟= nhƣ sau: - Q‟ = {[U]U Q; U ≠ } (Q‟ là tập tất cả các tập con khác rỗng của Q). Tại mỗi thời điểm, M‟ sẽ lƣu giữ trong trạng thái của nó tất cả các trạng thái có thể có của M. Một trạng thái trong Q‟ là ký hiệu là [q , q , , q ] trong đó {q , q , 1 2 i 1 2 , q } là một tập con của Q. Ta coi [q , q , , q ] là một trạng thái đơn của automat i 1 2 i M‟ và nó tƣơng ứng với một tập trạng thái của automat hữu hạn không đơn định M. - q‟0 = [q0]; q‟0 là tập con của Q có một phần tử q0. - F‟ = U] Q U F , F‟ là tập các tập con của Q giao với F khác rỗng hay F‟ là tập hợp các trạng thái của Q‟ có chứa ít nhất một trạng thái kết thúc trong tập F của M. - Ánh xạ ‟ đƣợc xây dựng bằng cách dựa vào nhƣ sau: Phạm Hùng Phú 49
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn ‟: Q‟ Q‟ xác định nhƣ sau: δ‟(U, a) = δ‟( [q , q , , q ], a) = [p , p , , p ] = V 1 2 i 1 2 j δ ({q , q , , q }, a) = {p , p , , p } 1 2 i 1 2 j Hay ‟ (U, a) = V = q U (q, a) với U, V Q‟ và a Rõ ràng với cách xây dựng nhƣ trên thì M‟ là Automat hữu hạn đơn định. Bây giờ ta chứng minh quy nạp theo độ dài của xâu vào w rằng: δ‟(q‟ , w) = [q , q , , q ] δ(q , w) = {q , q , , q } (1) 0 1 2 i 0 1 2 i Với w = 0 , ta có w = ε và q‟ = {q } nên (1) hiển nhiên đúng 0 0 Giả sử (1) đúng với các xâu vào w có độ dài tới m. Xét xâu vào có độ dài m + 1, đặt xâu này là wa với a Σ, ta có: δ‟(q‟0, wa) = δ‟(δ‟(q‟0, w), a) Theo định nghĩa hàm chuyển δ‟, ta có: δ‟([q , q , , q ], a) = [p , p , , p ] 1 2 i 1 2 j δ ({q , q , , q }, a) = {p , p , , p } 1 2 i 1 2 j Mặt khác theo giả thiết quy nạp δ‟(q‟0, w) = [p , p , , p ] 1 2 j δ(q , w) = {p , p , , p } 0 1 2 j Nên thay vào ta có δ‟(q‟0, wa) = [r , r , , r ] 1 2 k δ(q , wa) = {r , r , , r }. 0 1 2 k Dễ thấy rằng δ‟(q‟0, w) F‟ δ(q , w) F . 0 Vậy L(M) = L(M‟). Từ định lý, ta có giải thuật chuyển NFA về DFA. 2) Giải thuật chuyển NFA về DFA Input: NFA M = Output: DFA M‟ = ; L(M) = L(M‟) 50 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Process: - Q‟ = { [U]U Q; U ≠ }; - q‟0 = [q0]; - ‟= ; - F‟ = [U] Q‟ U F ; - ‟: Với mỗi [U] Q‟ thực hiện Với mỗi a ‟ tính δ‟([U], a) = δ‟( [q , q , , q ], a) = δ ({q , q , , q }, a) 1 2 i 1 2 i q U (q , a) = {p , p , , p } i i 1 2 j = [p , p , , p ] = V. 1 2 j Hay ‟ (U, a) = V Ví dụ: 1. Cho NFA: M = , trong đó: - Q = {q , q }; 0 1 - {0, 1}; - q q 0 0 - F = {q }; 1 - δ: δ(q , 0) = {q , q }; δ(q ,1) = {q }; δ(q , 0) = ∅; δ(q , 1) = {q , q }. 0 0 1 0 1 1 1 0 1 Biểu diễn M bằng đồ thị: 0 1 Start 0 1 q q 0 1 1 Hình 2.9. Đồ thị của NFA Phạm Hùng Phú 51
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Biểu diễn M bằng bảng: 0 1 Q q {q ,q } {q } 0 0 1 1 q {q ,q } 1 0 1 Bảng 2.8. Bảng chuyển trạng thái Ta xây dựng DFA tƣơng đƣơng M‟ = <Q‟, ‟, δ‟, q‟0, F‟) đoán nhận L(M) nhƣ sau: - Q‟: chứa tất cả các tập con của Q = {q , q }; 0 1 Vậy Q‟ = {[q ], [q ], [q , q ]}; đặt A = [q ], B = [q ], C = [q , q ]; 0 1 0 1 0 1 0 1 - ‟= = {0, 1}; - q‟0 = [q ] = A; 0 - F‟ = {[q ], [q , q ]} = {B, C} 1 0 1 - Hàm chuyển δ‟: δ‟(q‟ , 0) = δ‟([q ], 0) 0 0 δ‟(A, 0) = δ(q , 0) = [q , q ] = C 0 0 1 Tƣơng tự: δ‟(A, 1) = B; δ‟(B, 0) = ∅; δ‟(B, 1) = C; Cuối cùng: δ‟(C, 0) = C vì δ‟(C, 0) = δ‟([q , q ], 0) = δ({q , q },0) = δ(q , 0) δ(q , 0) 0 1 0 1 0 1 = {q , q } ∅ = [q , q ] = C. 0 1 0 1 52 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn δ‟(C, 1) = C vì δ‟(C, 1) = δ‟([q , q ], 1) = δ({q , q }, 1) = δ(q , 1) δ(q , 1) 0 1 0 1 0 1 = {q } {q , q } = [q , q ] = C. 1 0 1 0 1 Biểu diễn M‟ bằng đồ thị: 0 Start 0 A C 1 1 1 B Hình 2.10. Biểu diễn M’ bằng đồ thị Biểu diễn M‟ bằng bảng: ‟ 0 1 Q‟ A C B B C C C C Bảng 2.9. Biểu diễn M’ bằng bảng 2. Cho M = ; Trong đó: - Q = {q0, q1, q2}; - = {0, 1}; - F = { q2}; - q0 = q0; : (q0, 0) = {q0, q1}; (q1, 1) = {q2}; (q2, 1) = {q2}. Phạm Hùng Phú 53
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Biểu diễn M bằng đồ thị: 0 Start 1 1 q0 0 q1 q2 Hình 2.11. Biểu diễn M bằng đồ thị Biểu diễn M bằng bảng: 0 1 Q q {q ,q } 0 0 1 q {q } 1 2 q {q } 2 2 Bảng 2.10. Biểu diễn M bằng bảng Automat trên là automat không đơn định đoán nhận ngôn ngữ L = {0m1n với m 1, n 0}. Theo định lý trên, ta đi xây dựng M‟ = đơn định tƣơng đƣơng đoán nhận cùng một ngôn ngữ trên. - Q‟ = {q0], [q1], [q2], [q0 , q1], [q0 , q2], [q1 , q2], [q0 , q1 , q2]} - q0‟ = [q0] = A ; - F‟ = {[q2], [q0, q2], [q1 , q2], [q0 , q1 , q2]} -‟: ‟([q0], 0) = (q0, 0) = [q0, q1]; (1) ‟([q0], 1) = (q0, 1) = ; 54 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn ‟([q1], 0) = (q1, 0) = ; ‟([q1], 1) = (q1, 1) = [q2]; (2) ‟([q2], 0) = (q2, 0) = ; ‟([q2], 1) = (q2, 1) = [q2]; (3) ‟([q0, q1], 0) = (q0, 0) (q1, 0) = [q0, q1]; (4) ‟([q0, q1], 1) = (q0, 1) (q1, 1) = [q2]; (5) ‟([q0, q2], 0) = (q0, 0) (q2, 0) = [q0, q1] ; (6) ‟([q0, q2], 1) = (q0, 1) (q1, 1) = [q2] ; (7) ‟([q1, q2], 0) = (q1, 0) (q2, 0) = ; ‟([q1, q2], 1) = (q1, 1) (q2, 1) = [q2] ; (8) ‟([q0, q1, q2], 0) = (q0, 0) (q1, 0) (q2, 0) = [q0, q1]; (9) ‟([q0, q1, q2], 1) = (q0, 1) (q1, 1) (q2, 1) = [q2]; (10) Đặt [q0 ] = A; [q0 , q1] = B; [q1] = C; [q2 ] = D; [q0, q2] = E; [q1, q2] = H; [q0, q1 , q2] = I; Từ: (1) ‟(A, 0) = B; (2) ‟(C, 1) = D; (3) ‟(D, 1) = D; (4) ‟(B, 0) = B; Phạm Hùng Phú 55
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn (5) ‟(B, 1) = D; (6) ‟(E, 0) = B; (7) ‟(E, 1) = D; (8) ‟(H, 1) = D; (9) ‟(I, 0) = B; (10) ‟(I, 1) = D. Sau khi loại đi các trạng thái thừa, ta có automat hữu hạn đơn định M‟ tƣơng ứng với M. Trong đó: - Q‟= {A, B, D} ; - F‟ = {D}; - q‟0 = A; - ‟: ‟(A, 0) = B ; ‟(B, 0) = B ; ‟(B, 1) = D ; ‟(D, 1) = D ; 0 1 Start 1 A 0 B D Hình 2.12. Automat hữn hạn đơn định đoán nhận ngôn ngữ L 2.1.5. NFA với ε-dịch chuyển (NFAε) Ta mở rộng mô hình NFA cho phép các phép chuyển trên nhãn rỗng ε. Automat hữu hạn không đơn định với ε - dịch chuyển đƣợc biểu diễn bằng đồ thị dƣới đây đoán nhận các xâu gồm một số bất kỳ (không thể là 0) chữ số 0 sau đó là một số bất kỳ chữ số 1(có thể là 0) và cuối cùng là một số bất kỳ chữ số 2 (có thể là 0) . Thông thƣờng, ta nói NFA đoán nhận một xâu w nếu có một dãy các phép 56 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn chuyển dịch (đƣờng đi) từ trạng thái bắt đầu đến một trạng thái kết thúc khi nhận đƣợc xâu vào là w. Chẳng hạn, xâu 002 đƣợc đoán nhận bởi NFA trên bởi vì có đƣờng đi q , q , q , q , q với các cung có nhãn tƣơng ứng 0, 0, ε, 2. 0 0 1 2 2 Ví dụ: Đồ thị của một NFA với ε-dịch chuyển: 0 1 2 Start 0 q0 q1 q2 Hình 2.13. NFA với ε - dịch chuyển 1) Định nghĩa Automat hữu hạn không đơn định với ε-dịch chuyển (NFA với ε-dịch chuyển) là một hệ thống gồm 5 thành phần; ký hiệu là M = trong đó: Q - Tập hữu hạn khác rỗng các trạng thái. - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào). - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng: : Q ( {}) 2Q (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. F - Tập con của Q là tập các trạng thái kết thúc. Nếu p là ảnh của (q, a) qua ánh xạ thì ký hiệu là (q,a) = p; với q Q; a {} và p 2Q (p Q). Nhƣ vậy, NFA với ε-dịch chuyển là một NFA đƣợc bổ sung thêm phép chuyển trạng thái trên nhãn rỗng và ký hiệu δ(q, a) gồm tất cả các trạng thái p sao cho có phép chuyển trên nhãn a từ q tới p, trong đó a là một ký hiệu thuộc Σ hoặc là ε. Ví dụ 1: Cho NFA M = với Q = {q0, q1, q2}; q0 = q0; Phạm Hùng Phú 57
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn F = { q2}; q0 q0 q0 q1 q11 q1 q1 q2 q22 q2 - Biểu diễn NFA trên dƣới dạng đồ thị: 0 1 2 Start q q q 0 1 2 Hình 2.14. NFA với ε - dịch chuyển - Biểu diễn NFA trên dƣới dạng bảng: {} 0 1 2 Q q {q } {q } 0 0 1 q {q } {q } 1 1 2 q {q } 2 2 Bảng 2.11. Bảng chuyển trạng thái 2) Hàm chuyển trạng thái mở rộng Q Ta mở rộng hàm chuyển δ thành hàm chuyển δ* ánh xạ từ Q × Σ* → 2 . δ*(q, w) chứa tất cả các trạng thái p sao cho có thể đi từ q tới p theo đƣờng đi khi nhận vào xâu w (có thể chứa cạnh nhãn ε). Ta sử dụng hàm -CLOSURE(q) là tập hợp các trạng thái p sao cho có đƣờng đi từ một trạng thái q tới p khi M nhận vào từ rỗng . Ví dụ 2: Trong hình trên, ε-CLOSURE(q ) = {q , q , q }. 0 0 1 2 58 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Vì đƣờng đi chỉ có một đỉnh q (không có cung trên đƣờng đi) là đƣờng đi từ 0 q tới q có tất cả các cạnh nhãn là ε. Đƣờng đi q , q chỉ ra rằng q thuộc ε- 0 0 0 1 1 CLOSURE(q ) và đƣờng đi q , q , q chỉ ra rằng q thuộc ε-CLOSURE(q ). 0 0 1 2 2 0 -CLOSURE(T) là tập hợp các trạng thái p sao cho có thể đi từ mỗi trạng thái q T tới trạng thái p khi M nhận vào từ rỗng với T Q. ε-CLOSURE(T) = ε-CLOSURE(q) với T Q q T Q Ta định nghĩa hàm δ mở rộng là một ánh xạ δ*:Q × Σ* → 2 thoả mãn điều kiện: 1. δ*(q, ε) = ε-CLOSURE(q) * 2. δ*(q, wa) = ε-CLOSURE(P), trong đó tập P = {p | có r trong δ (q, w) sao * cho p δ(r, a)}, w Σ và a Σ. Hay δ*(q, wa) = ε-CLOSURE(δ(δ*(q, w), a)) δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a)) với mọi q Q và a = ε-CLOSURE(δ(ε- closure(q), a)) Ta mở rộng δ và δ* trên tập hợp các trạng thái T với T Q nhƣ sau: 3. δ* (T, a) = δ*(q, a) q T Ví dụ 3: Cho NFAε trong ví dụ 1. Tính δ*(q , 012) . 0 Ta có: δ*(q , ε) = ε-CLOSURE(q ) = {q , q , q } 0 0 0 1 2 Vậy δ*(q , 0) = ε-CLOSURE(δ(δ*(q , ε), 0) 0 0 = ε-CLOSURE(δ({q , q , q }, 0)) 0 1 2 = ε-CLOSURE(δ(q , 0) δ(q , 0) δ(q , 0)) 0 1 2 = ε-CLOSURE({q } ∅ ∅ ) 0 = ε-CLOSURE({q }) = {q , q , q } 0 0 1 2 và δ*(q , 01) = ε-CLOSURE(δ(δ*(q , 0), 1)) 0 0 = ε-CLOSURE(δ({q , q , q }, 1)) 0 1 2 = ε-CLOSURE(δ(q , 1) δ(q , 1) δ(q , 1)) 0 1 2 Phạm Hùng Phú 59
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn = ε-CLOSURE(∅ {q } ∅ ) 1 = ε-CLOSURE({q }) = {q , q } 1 1 2 δ*(q , 012) = ε-CLOSURE(δ( δ*(q , 01), 2)) 0 0 = ε-CLOSURE(δ({q , q }, 2)) 1 2 = ε-CLOSURE(δ(q , 2) δ(q , 2)) 1 2 = ε-CLOSURE(∅ {q }) 2 = ε-CLOSURE({q }) = {q } 2 2 Nhận xét: δ*(q, a) và δ(q, a) không bằng nhau vì δ*(q, a) gồm tất cả các trạng thái có thể chuyển đến đƣợc từ q trên nhãn a gồm cả đƣờng đi nhãn ε (a *), trong khi đó δ(q, a) chỉ gồm các trạng thái có thể đến đƣợc từ q chỉ bằng các cung nhãn a (a ). Tƣơng tự δ*(q, ε) có thể cũng không bằng δ(q, ε). Vì vậy ta phải phân biệt ký hiệu δ và δ* đối với NFA với ε-dịch chuyển. 3) Ngôn ngữ được đoán nhận bởi NFAε Cho NFAε M = , ngôn ngữ đƣợc đoán nhận bởi NFAε M là tập hợp 0 các xâu L(M) đƣợc xác định nhƣ sau: L(M) = {w Σ* | δ*(q , w) F } 0 4) Giải thuật mô phỏng hoạt động của một NFAε Input: Xâu vào w đƣợc kết thúc bởi $. Output: Câu trả lời "YES" nếu NFAε đoán nhận xâu w và "NO" nếu ngƣợc lại. phƣơng pháp q:= ε-CLOSURE(q ); 0 c:= getchar() ; {c là ký hiệu vào đầu tiên} While c <> $ do begin q:= ε-CLOSURE(δ(q, c)); 60 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn c:= nextchar() ; {c là ký hiệu vào đƣợc đọc tiếp theo} end If q F then write ("YES") else write ("NO"); Ví dụ: Cho Automat đƣợc biểu diễn bằng đồ thị hình 2.13. Sử dụng giải thuật trên để kiểm tra Automat đoán nhận từ w = aababb a 2 3 Start b 6 a b 0 1 7 8 9 10 b 4 5 Hình 2.15. NFA với ε - dịch chuyển Ta có thể trình bày giải thuật sử dụng automat trên đoán nhận w bằng bảng sau: Bƣớc q = ε -closure((q,c)) c khởi tạo {0, 1, 2, 4, 6, 7} a 1 {1, 2, 3, 4, 6, 7, 8} a 2 {1, 2, 3, 4, 6, 7, 8} b 3 {1, 2, 4, 5, 6, 7, 9} a 4 {1, 2, 3, 4, 6, 7, 8} b 5 {1, 2, 4, 5, 6, 7, 9} b 6 {1, 2, 4, 5, 6, 7, 10} $ Bảng 2.12. Mô tả quá trình đoán nhận xâu q F = {10} . Vậy automat trên đoán nhận đƣợc w = aababb Phạm Hùng Phú 61
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2.1.6. Sự tƣơng đƣơng giữa NFA có và không có ε-dịch chuyển 1) Định lý Nếu L đƣợc đoán nhận bởi một NFA có ε-dịch chuyển thì L cũng đƣợc đoán nhận bởi một NFA không có ε-dịch chuyển. Chứng minh: Đặt M = là NFA với ε-dịch chuyển. 0 Ta xây dựng NFA M‟= tƣơng đƣơng không có ε-dịch 0 chuyển, trong đó: F {q } nếu ε-CLOSURE(q ) F - F‟ = 0 0 F trong các trƣờng hợp còn lại - δ‟(q, a) = δ*(q, a) với q Q và a Σ. Chú ý rằng M‟ không có ε-dịch chuyển . Ta chứng minh bằng quy nạp trên | w | rằng δ‟(q , w) = δ*(q , w). 0 0 Tuy nhiên, điều đó có thể không đúng với w = ε vì δ‟(q , ε) = {q } trong khi đó 0 0 δ*(q , ε) = ε-CLOSURE(q ). Do đó, cơ sở quy nạp bắt đầu với độ dài xâu là 1. 0 0 Với | w | = 1 thì w là một ký tự a và δ‟(q, a) = δ(q, a) theo định nghĩa δ‟. Giả sử với | w | = n (n >1) ta đã có δ‟(q , w) = δ*(q , w). Ta phải chứng minh 0 0 δ‟(q , w) = δ*(q , w) với | w | = n + 1 . Tức là δ‟(q , wa) = δ*(q , wa) với a là một ký 0 0 0 0 tự trong Σ. Ta có δ‟(q, wa) = δ‟(δ‟(q , w), a) 0 Theo giả thiết quy nạp thì δ‟(q , w) = δ*(q , w). Đặt δ*(q , w) = T, ta cần chỉ 0 0 0 ra rằng δ*(T, a) = δ*(q , wa). 0 Ta có δ‟(T, a) = δ‟(q, a) = δ*(q, a). q T q T Hơn nữa vì T = δ*(q , w) nên δ*(q, a) = δ*(q , wa) ( theo quy tắc 2 trong 0 q T 0 định nghĩa δ mở rộng). Vậy δ‟(q , wa) = δ*(q , wa) 0 0 Để chứng minh đầy đủ, ta còn phải chỉ ra rằng δ‟(q , w) F‟ nếu và chỉ 0 nếu δ*(q , w) F . 0 Nếu w = ε thì điều đó hiển nhiên đúng (theo định nghĩa của F‟) 62 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Nếu w ≠ ε thì ta đặt w = wa với a Σ. Nếu δ*(q , w) F F thì chắc chắn 0 δ‟(q , w) F‟ chứa cùng trạng thái trong F‟. Ngƣợc lại, nếu δ‟(q , w) chứa một 0 0 trạng thái trong F‟ khác hơn q thì δ*(q , w) phải chứa một trạng thái trong F (vì tập 0 0 F và F‟ chỉ chênh lệch nhau trạng thái q ). Nếu δ‟(q , w) có chứa trạng thái q và q 0 0 0 0 cũng là một trạng thái thuộc tập trạng thái kết thúc F thì vì δ*(q , w) = 0 ε-CLOSURE(δ(δ (q , w),a)), nên trạng thái chung trong ε-CLOSURE(q ) và trong F 0 0 phải ở trong δ*(q , w). 0 Từ định lý, ta có giải thuật chuyển NFA có - dịch chuyển về NFA không có - dịch chuyển. 2) Giải thuật chuyển NFA về DFA Input: NFA M = Output: NFA M‟ = ; L(M) = L(M‟) Process: - Q‟ = Q; - Σ‟ = Σ; - q’0 = q 0 F {q } nếu ε-CLOSURE(q ) F 0 0 - F‟ = F nếu ε-CLOSURE(q ) F = 0 - Hàm chuyển δ‟: Với mỗi q Q‟ thực hiện Với mỗi a ‟ tính δ‟(q, a) = δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a)) = ε-CLOSURE(δ(e- closure(q), a)) = p Ví dụ: Chuyển NFA với ε-dịch chuyển ở hình sau sang dạng NFA không có chứa 1 2 ε-dịch chuyển. 0 Start q0 q1 q2 Hình 2.16. NFA với ε - dịch chuyển Phạm Hùng Phú 63
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Ta xây dựng NFA tƣơng đƣơng M‟= đoán nhận L(M) với: 0 - Q = {q , q , q }; 0 1 2 - Σ = {0, 1, 2}; - Trạng thái bắt đầu: q 0 - F‟ = {q , q } do ε-CLOSURE(q ) = {q , q , q } F = {q } 0 2 0 0 1 2 2 - Hàm chuyển δ‟ của M‟ đƣợc xác định theo công thức: δ‟(q, a) = δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a)) với mọi q Q và a = ε-CLOSURE(δ(ε- closure(q), a)) Kết quả bảng chuyển trạng thái đƣợc chỉ ra trong bảng sau: 0 1 2 Q q {q , q , q } {q , q } {q } 0 0 1 2 1 2 2 q {q , q } {q } 1 1 2 2 q {q } 2 2 Bảng 2.13. Bảng chuyển trạng thái Biểu diễn NFA trên bằng đồ thị 0 1 2 Start 0, 1 1, 2 q0 q1 q2 0, 1, 2 Hình 2.17. NFA tương đương với NFA 2.2. Biểu thức chính quy (RE: Regular Expressions) Lớp ngôn ngữ đƣợc đoán nhận bởi một automat hữu hạn cũng có thể đƣợc mô tả thông qua một dạng biểu thức ngắn gọn và súc tích gọi là biểu thức chính quy. Trong phần này, chúng ta sẽ giới thiệu sự kết hợp của các phép toán hợp, nhân ghép và lấy bao đóng Kleene trên các tập hợp xâu để định nghĩa biểu thức chính quy và chứng tỏ rằng lớp ngôn ngữ đƣợc đoán nhận bởi một automat hữu hạn thì thực sự là lớp ngôn ngữ đƣợc mô tả bởi biểu thức chính quy. 64 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2.2.1. Định nghĩa Cho Σ là một bộ chữ cái. Biểu thức chính quy trên Σ và các tập hợp mà chúng mô tả đƣợc định nghĩa một cách đệ quy nhƣ sau: 1. ∅ là biểu thức chính quy ký hiệu cho tập rỗng 2. ε là biểu thức chính quy ký hiệu cho tập {ε} 3. a Σ, a là biểu thức chính quy ký hiệu cho tập {a} 4. Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs) và ( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R S, RS, R* tƣơng ứng. Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lƣu ý rằng thứ tự ƣu tiên của các phép toán xếp theo thứ tự giảm dần là: phép bao đóng, phép nhân ghép, phép hợp. Chẳng hạn: Biểu thức ((0(1* )) + 1) có thể viết là 01*+ 1. Phép lấy bao đóng dƣơng cũng có thể đƣợc sử dụng khi viết biểu thức chính quy. Ta có thể viết rút gọn r r* hay r*r thành r+. Nếu cần thiết phân biệt thì ta sẽ dùng ký hiệu r cho biểu thức chính quy r và L(r) cho ngôn ngữ đƣợc ký hiệu bởi biểu thức chính quy r; ngƣợc lại một cách tổng quát, ta có thể dùng r cho cả hai trƣờng hợp. Ví dụ: 1. Một số biểu thức chính quy ký hiệu cho các ngôn ngữ: - 00 là biểu thức chính quy biểu diễn tập {00}. - (0+1)* ký hiệu cho tập hợp tất cả các xâu số 0 và số 1, kể cả xâu rỗng = {ε, 0, 1, 00, 01, 10, 11, 010, 011, 0010 } - (0+1)* 00(0+1)* ký hiệu cho tập hợp tất cả các xâu 0,1 có ít nhất hai số 0 liên tiếp. = {00, 000, 100, 0000, 0001, 1000, 1001, 011001, } - (1+10)* ký hiệu cho tất cả các xâu 0, 1 bắt đầu bằng số 1 và không có hai số 0 liên tiếp = {ε, 1, 10, 11, 1010, 111, 101010, } - (0 + ε)(1+10)* ký hiệu cho tất cả các xâu không có hai số 0 liên tiếp. Phạm Hùng Phú 65
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn = {ε, 0, 01, 010, 1, 10, 01010, 0111, } - (0+1)*011 ký hiệu cho tất cả các xâu 0, 1 tận cùng bởi 011. = {011, 0011, 1011, 00011, 11011, } - 0*1*2* ký hiệu cho tất cả các xâu có một số bất kỳ các số 0, theo sau là một số bất kỳ số 1 và sau nữa là một số bất kỳ số 2. = {ε, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, } - 00*11*22* ký hiệu cho tất cả các xâu trong tập 0*1*2* với ít nhất một trong + + + mỗi ký tự. 00*11*22* có thể đƣợc viết gọn thành 0 1 2 2. Biểu thức chính quy ký hiệu cho tập hợp các xâu là tên biến đúng trong ngôn ngữ lập trình Pascal: Một xâu là tên biến (identifiers) đƣợc gọi là hợp lệ trong một chƣơng trình Pascal nếu nhƣ nó bắt đầu bằng một chữ cái và theo sau đó là các chữ cái, số, ký hiệu underline hoặc một vài ký tự cho phép khác trên bàn phím máy tính. Biểu thức chính quy có dạng nhƣ sau: r = (A + + Z + a + + z) (A + + Z + a + + z + 0 + + 9 + _ + )* 3. Biểu thức chính quy ký hiệu cho tập hợp các số nguyên trong ngôn ngữ lập trình Pascal: Một xâu là số nguyên trong một chƣơng trình Pascal có thể bắt đầu bằng dấu âm (-) hoặc dấu dƣơng (+) hay không chứa ký hiệu dấu, và theo sau đó là một xâu các ký tự số với ít nhất là một số. Biểu thức chính quy có dạng nhƣ sau: r = ( „+‟ + „-‟ + ε) ( 0 + + 9 (0 + +9 )* Nhận xét: Thông thƣờng, việc tìm một biểu thức chính quy ký hiệu cho một ngôn ngữ khó hơn việc xác định ngôn ngữ đƣợc ký hiệu bởi một biểu thức chính quy vì không có giải thuật cho loại bài toán này. 2.2.2. Một số tính chất đại số của biểu thức chính quy Dễ dàng chứng minh rằng, nếu cho r, s, t là các biểu thức chính quy thì ta có các đẳng thức sau: 1. r + s = s + r 66 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 2. r + r = r 3. r + (s+t) = (r+s) + t 4. r (st) = (rs) t 5. r (s+t) = rs + rt 6. (r+s) t = rt + st 7. r ε = ε r = r 8. ∅r = r∅ = ∅ 9. r + ∅ = r 10. ∅* = ∅ 11. (ε + r)* = r* * * 12. r + r = r 13. ( r* )* = r* 14. ( r s* )* = (r + s)* 15. r r* = r* r = r+ Trong đó, ta có r = s có nghĩa là L(r) = L(s). 2.2.3. Sự tƣơng đƣơng giữa automat hữu hạn và biểu thức chính quy Các ngôn ngữ đƣợc đoán nhận bởi automat hữu hạn cũng là các ngôn ngữ đƣợc mô tả bởi biểu thức chính quy. Chính vì điều này mà ngôn ngữ đoán nhận bởi automat hữu hạn còn đƣợc gọi là tập chính quy. 1) Xây dựng NFA ε đoán nhận L(r). a) Định lý Nếu r là biểu thức chính quy thì tồn tại một NFA với ε-dịch chuyển đoán nhận L(r). Chứng minh: Ta sẽ chứng minh quy nạp theo số phép toán của biểu thức chính quy r rằng có tồn tại một NFA M với ε-dịch chuyển có một trạng thái kết thúc và không có các phép chuyển khỏi trạng thái này đoán nhận biểu thức chính quy r: L(M) = L(r). - r không có phép toán: Biểu thức chính quy r không có phép toán thì r chỉ có thể là ∅, ε hoặc a với a Σ. Phạm Hùng Phú 67
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Các NFA dƣới đây thoả mãn điều kiện trên: ε Start Start q0 q0 qf r = ε r = ε Start Start a q0 qf q0 qf r = ∅ r = a Hình 2.18. Các NFAε biểu diễn cho các biểu thức không có phép toán - r có chứa các phép toán: Giả sử định lý đúng với r có ít hơn i phép toán, i ≥ 1. Xét r có i phép toán. Có các trƣờng hợp: 1. r = r + r 1 2 Cả hai biểu thức chính quy r , r có ít hơn i phép toán, giả sử có 2 automat 1 2 hữu hạn NFA M = và M = sao cho 1 1 1 1 1 1 2 2 2 2 2 2 L(M ) = L(r ) và L(M ) = L(r ). 1 1 2 2 Vì các trạng thái có thể thay đổi tên nên ta giả sử hai tập trạng thái Q và Q 1 2 là rời nhau. Đặt q là trạng thái bắt đầu mới và {f } là tập trạng thái kết thúc mới, ta 0 0 xây dựng NFA M = , trong đó δ đƣợc xác 1 2 0 0 1 2 0 0 định nhƣ sau: - δ(q , ε) = {q , q }; 0 1 2 - δ(q, a) = δ (q, a) với q Q – {f } và a Σ {ε}; 1 1 1 1 - δ(q, a) = δ (q, a) với q Q – {f } và a Σ {ε}; 2 2 2 2 - δ(f , ε) = δ(f , ε) = {f }. 1 2 0 Chú ý do giả thiết quy nạp là không có phép chuyển nào ra khỏi f , f trong 1 2 M , M . Vì vậy tất cả các phép chuyển của M và M đều có trong M. Cách xây 1 2 1 2 dựng M chỉ ra trong hình 2.19. Bất kỳ đƣờng đi nào trong sơ đồ chuyển của M từ q 0 tới f phải bắt đầu bằng cách đi tới q hoặc q bằng nhãn ε. Nếu đƣờng đi qua q thì 0 1 2 1 nó theo một đƣờng đi nào đó trong M tới f rồi sau đó tới f bằng nhãn ε. 1 1 0 68 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Tƣơng tự trong trƣờng hợp đƣờng đi qua q . Có một đƣòng đi từ q đến f 2 0 0 nhãn x khi và chỉ khi có đƣờng đi nhãn x trong M từ q đến f hoặc có đƣờng đi 1 1 1 nhãn x trong M từ q đến f . 2 2 2 Vậy L(M) = L(M ) L(M ). 1 2 ε q1 M1 f1 ε Start q f 0 0 ε ε q M f2 2 2 r = r + r 1 2 Hình 2.19. NFAε biểu diễn cho phép hợp (cộng) 2. r = r1 r2 Đặt M và M là các automat NFA nhƣ trong trƣờng hợp trên và ta xây dựng 1 2 automat M = trong đó, δ đƣợc xác định nhƣ sau: 1 2 - δ(q, a) = δ (q, a) với q Q – {f } và a Σ {ε}; 1 1 1 1 - δ(f , ε) = {q }; 1 2 - δ(q, a) = δ (q, a) với q Q và a Σ {ε}. 2 2 2 Cách xây dựng M chỉ ra trong hình 2.20a. Mỗi đƣờng đi trong M từ q tới f 1 2 là đƣờng đi có nhãn x từ q tới f sau đó là một cung từ f tới q nhãn ε và tiếp đến là 1 1 1 2 đƣờng đi từ q tới f . Hoặc cách xây dựng M chỉ ra trong hình 2.20b. Mỗi đƣờng đi 2 2 trong M từ q tới f là đƣờng đi có nhãn x từ q tới f sau đó là đƣờng đi từ f cũng 1 2 1 1 1 chính là q tới f . (f q ) 2 2 1 2 Vậy L(M) = {xy | x L(M ) và y L(M )} hay L(M) = L(M ) L(M ). 1 2 1 2 ε Start q1 M1 f1 q2 M2 f2 r = r r 1 2 Hình 2.20a Phạm Hùng Phú 69
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Start q1 M1 qf12 M2 f2 r = r r 1 2 Hình 2.20b. NFAε biểu diễn cho phép nhân ghép 3. r = r + 1 Đặt M = và L(M ) = r . 1 1 1 1 1 1 1 1 Xây dựng M = 0. Vậy L(M) = (L(M ))+. 1 2 j 1 ε Start ε ε q 0 q1 M1 f1 f0 + r = r1 Hình 2.21. NFAε biểu diễn cho phép lấy bao đóng dương 4. r = r * 1 Đặt M = và L(M ) = r . 1 1 1 1 1 1 1 1 Xây dựng M = , trong đó δ đƣợc cho: 1 0 0 1 0 0 - δ(q , ε) = {q , f }; 0 1 0 - δ(q, a) = δ (q, a) với q Q – {f } và a Σ {ε}; 1 1 1 1 - δ(f , ε) = {q , f }. 1 1 0 70 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Cách xây dựng M đƣợc chỉ ra trong hình 2.22. Mỗi đƣờng đi từ q tới f gồm: 0 0 hoặc đƣờng đi từ q tới f bằng nhãn ε; hoặc đƣờng đi từ q tới q bằng nhãn ε và sau 0 0 0 1 đó là đƣờng đi từ q tới f trên xâu thuộc L(M), rồi đến f bằng nhãn ε. Nhƣ vậy có 1 1 0 đƣờng đi từ q tới f nhãn là x nếu và chỉ nếu ta có thể viết x = x x x với j ≥ 0 0 0 1 2 j (trƣờng hợp j = 0 khi x = ε) với x L(M ). Vậy L(M) = (L(M ))*. i 1 1 ε Start ε ε q0 q1 M1 f1 f0 ε * r = r1 Hình 2.22. NFAε biểu diễn cho phép lấy bao đóng Kleen Ví dụ: Xây dựng NFAε đoán nhận ngôn ngữ đƣợc ký hiệu bởi biểu thức chính quy r = 01* + 1. Ta thấy L(r) = { 1, 0, 01, 011, 0111, 01111, 011111, } là tập ngôn ngữ chứa các bit đơn 0, 1 và các xâu bit nhị phân bắt đầu bằng bit 0, theo sau là một xâu bit 1 với độ dài tuỳ ý. Theo quy luật thứ tự ƣu tiên, biểu thức 01* + 1 thực chất là (0(1*)) + 1, vì vậy nó có dạng r + r với r = 01* và r = 1. 1 2 1 2 Ta sẽ lần lƣợt xây dựng các NFA cho các biểu thức chính quy con, sau đó dựa vào các quy tắc kết hợp để xây dựng NFA cho toàn bộ biểu thức chính quy đã cho. - NFA cho r = 1 dễ dàng đƣợc xây dựng: 2 Start 1 q1 q2 - NFA cho r = 01*: 1 Ta tách r = r r , trong đó r = 0 và r = 1* 1 3 4 3 4 + NFA cho r = 0: 3 Start 0 q3 q4 Phạm Hùng Phú 71
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn + NFA r = 1*: 4 * Ta viết r = r , trong đó r = 1. 4 5 5 NFA cho r = 1: 5 Start 1 q5 q 6 Theo quy tắc 4) ta xây dựng đƣợc NFA cho r = r * = 1* nhƣ sau: 4 5 ε Start 1 q7 q5 q6 q8 ε Theo quy tắc 2) ta xây dựng đƣợc NFA cho r = r r = 01* nhƣ sau: 1 3 4 ε 0 1 Start q q q q q q 3 4 7 5 6 8 ε Cuối cùng, theo quy tắc 1) ta xây dựng NFA cho r = r + r = 01* + 1 nhƣ sau: 1 2 1 q1 q2 Start q0 q10 ε 0 1 q3 q4 q7 q5 q6 q8 ε Hình 2.23. NFAε biểu diễn cho r = 01* + 1 72 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Chứng minh của Định lý trên cũng chính là cơ sở của giải thuật chuyển một biểu thức chính quy r thành automat hữu hạn NFAε. Một điểm cần lƣu ý là thứ tự ƣu tiên của các phép toán đƣợc sử dụng trong biểu thức chính quy, điều này rất quan trọng cho quá trình phân tích biểu thức chính quy thành các biểu thức con trong những trƣờng hợp viết biểu thức chính quy ở dạng tắt (không có dấu ngoặc). b) Giải thuật xây dựng NFA ε đoán nhận L(r). Input: Biểu thức chính quy r Output: NFA M = ; L(M) = L(r) Process: - Bƣớc 1: + Tìm phép toán phải thực hiện cuối cùng. + Nếu có thì tìm các toán hạng của phép toán đó. Ngƣợc lại nếu không có thì đó là biểu thức không có phép toán. - Bƣớc 2: + Với mỗi toán hạng quay lại bƣớc 1 cho đến khi toán hạng là biểu thức không có phép toán. + Xây dựng các automat đơn giản cho các biểu thức chính quy không chứa phép toán. + Xây dựng các automat cho mỗi biểu thức chính quy có chứa phép toán theo thứ tự ngƣợc lại cho đến khi xây dựng xong automat cho biểu thức chính quy r. Ví dụ: Xây dựng NFAε đoán nhận ngôn ngữ đƣợc ký hiệu bởi biểu thức chính quy r = a*(a + b) b+. + Phân tích r - Ta có r = r r ; r = a*(a + b); r = b+. 1 2 1 2 - r = r r ; r = a*; r = (a + b). 1 3 4 3 4 - r = (r )* ; r = a. 3 5 5 - r = r + r ; r = a; r = b. 4 6 7 6 7 - r = (r ) + ; r = b. 2 8 8 + Xây dựng r Phạm Hùng Phú 73
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn - r = b 8 Start b 0 1 - r = b 7 Start b 2 3 - r = a 6 Start a 4 5 - r = a 5 a Start 6 7 - r = r + r 4 6 7 a ε 4 5 ε Start 8 9 b ε ε 2 3 - r = (r )* 3 5 ε Start a 10 6 7 11 ε - r = (r ) + 2 8 ε Start b 12 0 1 13 - r = r r 1 3 4 ε a ε 4 5 ε a Start 10 7 6 8 9 ε b ε ε 2 3 - r = r r 1 2 ε a ε 4 5 ε Start a 10 6 7 8 ε 9 ε 2 b 3 ε b 12 0 1 13 * Hình 2.24. NFAε biểu diễn cho r = a (a + b) b+ 74 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn Nhƣ vậy, biết biểu thức chính quy r ta xây dựng đƣợc automat hữu hạn NFAε đoán nhận ngôn ngữ L(r). Vấn đề đặt ra là biết automat hữu hạn M bằng phƣơng pháp nào có thể đƣa ra đƣợc biểu thức chính quy biểu diễn cho ngôn ngữ đƣợc đoán nhận bởi M. 2) Xây dựng biểu thức chính quy r biểu diễn L(M) a) Định lý Nếu L đƣợc đoán nhận bởi một DFA, thì L đƣợc ký hiệu bởi một biểu thức chính quy. Chứng minh: Đặt L là tập hợp đƣợc đoán nhận bởi DFA M = . 1 2 n 1 k Đặt R là tập hợp tất cả các xâu x sao cho δ(q , x) = q và nếu δ(q , y) = q , với y là ij i j i l k tiền tố bất kỳ của x, khác x hoặc ε, thì l ≤ k. Tức là R là tập hợp tất cả các xâu làm ij cho automat đi từ trạng thái qi tới qj không đi ngang qua trạng thái nào (đƣợc đánh số) lớn hơn k. (Chú ý, khái niệm “đi ngang qua một trạng thái” có nghĩa là có phép chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k). Vì chỉ có n n trạng thái nên R sẽ là tập hợp tất cả các xâu làm automat đi từ qi tới qj. ij k Ta định nghĩa R một cách đệ quy nhƣ sau: ij k k-1 k-1 k-1 k-1 R = R (R )* R R (1) ij ik kk kj ij 0 { a | δ(q , a) = q } nếu i ≠ j R = i j ij { a | δ(q , a) = q } {ε} nếu i = j i j k Một cách hình thức, R định nghĩa nhƣ trên là các xâu vào hay nguyên nhân ij đƣa M từ q tới q không đi ngang qua trạng thái cao hơn q , nghĩa là xảy ra một i j k trong hai trƣờng hợp sau: k-1 1. Nằm trong R (để không bao giờ đi ngang qua một trạng thái nào cao ij nhƣ q ). k Phạm Hùng Phú 75
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn k-1 2. Bao gồm một xâu trong R ik (xâu làm M chuyển đến qk), theo sau bởi k-1 không hoặc nhiều xâu trong R ik (xâu làm M chuyển từ qk trở về qk mà không k-1 ngang qua qk hoặc một trạng thái nào cao hơn) và cuối cùng là một xâu trong R kj (xâu làm M chuyển từ q đến q ). k j k Ta sẽ chỉ ra rằng với mỗi i, j và k tồn tại biểu thức chính quy r ký hiệu cho ij k ngôn ngữ R . Ta quy nạp theo k nhƣ sau: ij 0 0 - k = 0: khi đó R là tập hợp hữu hạn các xâu có một ký hiệu hoặc ε. Vậy r ij ij có thể viết dƣới dạng a + a + + a (hoặc a + a + + a + ε nếu i = j). Trong đó 1 2 p 1 2 p {a , a , , a } là tập hợp tất cả các ký hiệu a sao cho δ(q , a) = q . Nếu không có ký 1 2 p i j 0 hiệu a nào nhƣ thế thì ∅ (hoặc ε khi i = j) ký hiệu cho r . ij k - Công thức (1) cho R chỉ liên quan đến các phép toán trên biểu thức chính ij quy: hợp, nhân ghép và bao đóng. Hơn nữa theo giả thiết quy nạp, với mỗi l, k và k-1 k-1 k-1 k m tồn tại biểu thức chính quy r sao cho L(r ) = R . Vậy đối với r ta có lm lm lm ij thể chọn biểu thức chính quy: k-1 k-1 k-1 k-1 (r ) (r )* (r ) + r ik kk kj ij n n Cuối cùng ta có nhận xét rằng L(M) = R vì R ký hiệu cho tất cả qj F 1j 1j các nhãn của tất cả các đƣờng đi từ q tới q . 1 j n n n Vậy L(M) đƣợc ký hiệu bởi biểu thức chính quy r = r + r + + r , 1j1 1j2 1jp trong đó tập F = {q , q , , q }. j1 j2 jp Ví dụ: Viết biểu thức chính quy ký hiệu cho ngôn ngữ đƣợc đoán nhận bởi DFA hình sau: 76 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 0 0 Start 0 1 q1 q2 q3 1 1 Hình 2.25. DFA Gọi DFA đƣợc chỉ ra trong hình 2.16 là M = trong đó: - Q = {q , q , q }; 1 2 3 - = {0, 1}; - δ: δ(q , 0) = {q }; 1 2 δ(q , 1) = {q }; 1 3 δ(q , 0) = {q }; 2 1 δ(q , 1) = {q }; 2 3 δ(q , 0) = {q }; 3 2 δ(q , 1) = {q }; 3 2 - q0 = q ; 1 - F = {q , q }. 2 3 Ta thấy, tập hợp tất cả các xâu đƣợc đoán nhận bởi DFA trên là các xâu làm cho automat chuyển từ trạng thái bắt đầu q đến một trong hai trạng thái kết thúc q 1 2 và q và không chuyển qua số tối đa là 3 (k = 3) trạng thái của automat. Vậy ta cần 3 viết biểu thức chính quy ký hiệu cho tập hợp này nhƣ sau: 3 3 r = r + r 12 13 Theo công thức đã đƣợc chứng minh trong định lý trên, ta có thể tính đƣợc k các giá trị r với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, nhƣ chỉ ij ra trong bảng sau: Phạm Hùng Phú 77
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn k = 0 k = 1 k = 2 k r ε ε (00)* 11 k r 0 0 0(00)* 12 k r 1 1 0*1 13 k r 0 0 0(00)* 21 k r ε ε + 00 (00)* 22 k r 1 1 + 01 0*1 23 k r (0 + 1)(00)*0 31 ∅ ∅ k r 0 + 1 0 + 1 (0 + 1)(00)* 32 k r ε ε ε + (0 + 1)0*1 33 Bảng 2.14. Mô tả quá trình tính r Bằng cách dùng các công thức tƣơng đƣơng nhƣ (r + s) t = rt + st và (ε + r)* = r* để đơn giản các biểu thức, chẳng hạn khi tính biểu thức: 1 0 0 0 0 r = r (r )* r + r = 0(ε)*0 + ε = 00 + ε 22 21 11 12 22 Tƣơng tự, khi đơn giản biểu thức 2 1 1 1 1 r = r (r )* r + r = 0(00 + ε)*(1 + 01) + 1 13 12 22 23 13 Ta nhận thấy (00 + ε)* tƣơng đƣơng với (00)* và (1 + 01) thì tƣơng đƣơng với (ε + 0)1 nên ta rút gọn: 2 r = 0(00)*(ε + 0)1 + 1 13 Mặt khác, chú ý rằng (00)*(ε + 0) thì tƣơng đƣơng với 0*, vì thế 0(00)*(ε + 0)1 + 1 cũng bằng 00*1 + 1 hay cuối cùng là 0*1. 3 Để hoàn thành việc xây dựng biểu thức chính quy cho M, ta cần tính r và 12 3 r . Ta viết: 13 78 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn 3 2 2 2 2 r = r (r )* r + r 12 13 33 32 12 = 0*1(ε + (0 + 1)0*1)*(0 + 1)(00)* + 0(00)* = 0*1((0 + 1)0*1)*(0 + 1)(00)* + 0(00)* 3 2 2 2 2 và r = r (r )* r + r 13 13 33 33 13 = 0*1(ε + (0 + 1)0*1)*(ε + (0 + 1))0*1) + 0*1 = 0*1((0 + 1)0*1)* Vậy biểu thức chính quy có dạng: 3 3 r = r + r = 0*1((0 + 1)0*1)*(ε + (0 + 1)(00)*) + 0(00)* 12 13 Nhƣ vậy, về nguyên tắc, biết automat hữu hạn ta có thể xây dựng đƣợc biểu thức chính quy biểu diễn cho ngôn ngữ đƣợc đoán nhận bởi automat hữu hạn. Vì từ NFA ta chuyển về đƣợc NFA đoán nhận cùng một ngôn ngữ; từ NFA ta chuyển về đƣợc DFA đoán nhận cùng một ngôn ngữ và từ DFA theo định lý trên ta tìm đƣợc biểu thức chính quy biểu diễn cho ngôn ngữ đƣợc đoán nhận bởi DFA. 2.3. Văn phạm chính quy Phần này sẽ chứng tỏ sự tƣơng đƣơng của hai quan điểm, quan điểm sinh và quan điểm đoán nhận ngôn ngữ. Nói cách khác ta sẽ chứng tỏ ngôn ngữ sinh bởi văn phạm chính quy trùng với ngôn ngữ đƣợc đoán nhận đƣợc bởi Automat hữu hạn. 2.3.1. Văn phạm tuyến tính 1) Định nghĩa - Văn phạm G = (N, T, P, S) đƣợc gọi là tuyến tính trái (left – linear) nếu mọi * luật sinh của nó có dạng A → Bw hoặc A → w; trong đó: A, B N và w T . - Văn phạm G = (N, T, P, S) đƣợc gọi là tuyến tính phải (right – linear) nếu * mọi luật sinh của nó có dạng A → wB hoặc A → w; trong đó: A, B N và w T . - Văn phạm G = (N, T, P, S) đƣợc gọi là văn phạm chính quy nếu nó là văn phạm tuyến tính trái hoặc văn phạm tuyến tính phải. 2) Ví dụ a) Các văn phạm sau đây là văn phạm chính quy: Phạm Hùng Phú 79
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn - Văn phạm G = ({S}, {a, b}, P , S) với các luật sinh đƣợc cho nhƣ sau: 1 1 S → abS a là văn phạm tuyến tính phải. - Văn phạm G ({S, A, B}, {a, b}, P , S) với các luật sinh đƣợc cho nhƣ sau: 2 2 S → Aab; A → AabB; B → a là văn phạm tuyến tính trái. - Văn phạm G = (N , T , P , S ), trong đó: 1 1 1 1 1 N = {S}; T = {a, b}; S = S; P với các luật sinh đƣợc cho nhƣ sau: 1 1 1 1 S → bS| a. G là văn phạm tuyến tính phải. 1 Ngôn ngữ sinh bởi văn phạm G là r = b*a. 1 - Văn phạm G = (N , T , P , S ), trong đó: 2 2 2 2 2 N = {S, A, B}; T = {a, b}; S = S; P với các luật sinh: S → Sb | a; 2 2 2 2 A → Aa| Bb| b | ; B → a | b. G là văn phạm tuyến tính tính trái. 2 Ngôn ngữ sinh bởi văn phạm G là r = ab*. 1 b) Ngôn ngữ đƣợc biểu diễn bởi biểu thức chính quy 01* đƣợc sinh bởi văn phạm tuyến tính phải có các luật sinh: S → 0A; A → 1A|ε (1) Và bởi văn phạm tuyến tính trái có các luật sinh: S → S1| 0 (2) 2.3.2. Sự tƣơng đƣơng giữa văn phạm chính quy và automat hữu hạn 1) Định lý 1 Nếu G = (N, T, P, S) là văn phạm chính quy thì tồn tại Automat hữu hạn M sao cho L(M) = L(G). Chứng minh: Trƣớc hết, ta giả sử văn phạm tuyến tính phải G = (N, T, P, S) sinh ra ngôn ngữ chính quy L(G). Ta xây dựng một NFA có chứa ε-dịch chuyển M (Q, T, δ, [S], [ε]) mô phỏng các dẫn xuất trong G (đoán nhận L(M) = L(G)). Q bao gồm các trạng thái có dạng [α] với α là S hoặc chuỗi hậu tố của vế phải một luật sinh nào đó trong P. Ta định nghĩa δ nhƣ sau : 1) Nếu A là một biến, thì δ([A], ε) = {[α] | A → α là một luật sinh} 80 Phạm Hùng Phú
- Chương 2. Ngôn ngữ chính quy và Automat hữu hạn * 2) Nếu a thuộc T và α thuộc (NT) =V, thì δ([aα], a) = {[α]} Sau đó, có thể dễ dàng chứng minh quy nạp theo độ dài của dẫn xuất rằng δ([S], w) chứa [α] khi và chỉ khi có chuỗi dẫn xuất S * xA xyα với A → yα là một luật sinh trong P và xy = w, hay nếu α = S thì w = ε. Khi [ε] là trạng thái kết thúc duy nhất, M chấp nhận w khi và chỉ khi S * xA w. Nhƣng vì mọi chuỗi dẫn xuất cho một chuỗi ký hiệu kết thúc qua ít nhất 1 bƣớc, nên ta thấy rằng M chấp nhận w khi và chỉ khi G dẫn xuất ra w. Bây giờ, giả sử G = (N, T, P, S) là một văn phạm tuyến tính trái. Đặt văn phạm G‟= (N, T, P‟, S) với P‟ chứa các luật sinh của P có vế phải đảo ngƣợc, nghĩa R là: P‟ = {A → α | A → α P}. Nếu đảo ngƣợc xâu - vế phải các luật sinh trong một văn phạm tuyến tính trái sẽ có văn phạm tuyến tính phải và ngƣợc lại. Do đó, hiển nhiên sẽ có G‟ là một văn R phạm tuyến tính phải và cũng dễ dàng để chỉ ra rằng L(G‟) = L(G). Nhƣ vậy, áp dụng các bƣớc xây dựng NFA M‟ cho văn phạm G‟ và nếu đảo ngƣợc các cạnh của NFA M‟ và chuyển đổi vai trò của các trạng thái bắt đầu và kết thúc thì sẽ có một NFA M đoán nhận ngôn ngữ L(G). Để xây dựng từ vựng cho các ngôn ngữ lập trình bậc cao chỉ cần văn phạm chính quy trong trƣờng hợp w bằng a T hoặc . Do đó, phần này chỉ đi sâu vào văn phạm chính quy trong trƣờng hợp các luật sinh của nó có dạng A aB a (tuyến tính phải) hoặc A Ba a (tuyến tính trái) với A, B N; a T hoặc a = . Theo cách chứng minh định lý trên, ta có giải thuật xây dựng Atomat hữu hạn khi biết văn phạm chính quy trong trƣờng hợp đặc biệt này nhƣ sau. b) Giải thuật xây dựng Atomat hữu hạn biết văn phạm chính quy Input: RG G = (N, T, P, S) Output: FA M = ; L(M) = L(G) Process: 1. Nếu G – văn phạm tuyến tính phải thì xây dựng Automat hữu hạn M có - Q = N A; A là trạng thái mới bổ sung; A chƣa có trong N; - = T; - q0 = S; - F ={A}; Phạm Hùng Phú 81
