Ngôn ngữ hình thức
Phạm Hùng Phú 1
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
Ngôn ngữ hình thức
Phạm Hùng Phú
2
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
Ngôn ngữ hình thức
Phạm Hùng Phú
3
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
4 Phạm Hùng Phú
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.
Ngôn ngữ hình thức
Phạm Hùng Phú
5
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ú