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
Có thể bạn quan tâm!
Xem toàn bộ 254 trang tài liệu này.
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
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
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
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.
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ú
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ì?.
- 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à <chủ ngữ>, từ “ăn” là <vị ngữ>, từ “cơm” là <bổ ngữ>, 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:
<Chủ ngữ> <vị ngữ> <bổ ngữ>
Trong đó <chủ ngữ> có thể là <đại từ> hoặc <danh từ>, thay cho các viết này ta viết ngắn gọn:
<Chủ ngữ> <đại từ>|<danh từ> Tương tự như vậy ta có thể viết:
<Đại từ> anh | tôi | nó| ông | bà | em |….
<Danh từ> cam | bánh | kẹo | xôi | báo | voi….
<Vị ngữ> <động từ>
<Động từ> đi | đứng | học | làm | nhảy | viết | vẽ…
<Bổ ngữ> <danh từ>
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, …
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à .