Xem mẫu
- 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
cho ta kết quả là một xâu trên bảng chữ cái , ký hiệu là wR và wR = 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 xL1 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 xL1 và x L2;
L1 - L2 = x xL1 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 | w1L1 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ừ.
Ví dụ: L1 = { ai | i là một số nguyên tố }
L2 = { ai bi | i ≥ 0 }
L3 = { ai bj | 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à α β.
+ SN - 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 iN
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 }.
Ta thấy ngay L(G1) = {anbn | n 0}.
Và G2 = (N2, T2, P2, S2) trong đó:
N2 = {S2};T2 = {a, b};
P2 = {S2 aS2b; S2 ab; S2 }.
Ta cũng thấy ngay L(G2) = {anbn | 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, BN và wT .
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 G 1, 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 SS1, SS2.
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ử wL, 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ú
nguon tai.lieu . vn
