Giáo trình Ngôn ngữ hình thức và Ôtômat - Trường Đại học Hàng Hải
BỘ GIAO THÔNG VẬN TẢI
TRƢỜNG ĐẠI HỌC HÀNG HẢI
́ ́
BỘ MÔN: KHOA HOC MAY TINH
̣
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
NGÔN NGỮ HÌNH THỨC VÀ ÔTÔMAT
TÊN HỌC PHẦN : Ngôn ngữ hình thức và Ôtômat
MÃ HỌC PHẦN : 17204
TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG - 2008
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
ĐỀ CƢƠNG CHI TIẾT
Tên học phần: Ngôn ngữ hình thức và Ôtômat
Bộ môn phụ trách giảng dạy: Khoa học Máy tính
Mã học phần: 17204
Loại học phần: 1
Khoa phụ trách: CNTT
Tổng số TC: 2
TS tiết Lý thuyết Thực hành/Xemina Tự học
45 45
Bài tập lớn
Đồ án môn học
0
0
0
0
Điều kiện tiên quyết:
Sinh viên phải học xong môn học toán rời rạc.
Mục tiêu của học phần:
-
-
Cung cấp các kiến thức cơ bản về ngôn ngữ, văn phạm và otomat.
Cơ bản về chương trình dịch.
Nội dung chủ yếu
Gồm các phần:
- Văn phạm và ngôn ngữ
- Ngôn ngữ chính quy và otomat đẩy xuống
- Ngôn ngữ phi ngữ cảnh và otomat đẩy xuống
- Cơ bản về chương trình dịch
Nội dung chi tiết của học phần:
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
MỞ ĐẦU
Chƣơng I. Văn phạm và ngôn ngữ.
1.1. Bảng chữ cái, từ và ngôn ngữ
TS
05
LT TH/Xemina BT KT
04
01
1.2. Tích ghép, phép chia, phép soi gương
1.3. Các phép toán trên ngôn ngữ
1.4. Văn phạm
1.5. Các ví dụ về văn phạm
Chƣơng II. Ngôn ngữ chính quy và otomat hữu hạn
2.1. Nguồn và ngôn ngữ được sinh bởi nguồn
2.2. Các phép toán trên nguồn
16
12
03
01
2.3. Otomat hữu hạn không lối ra và ngôn ngữ được
đoán nhận bởi otomat hữu hạn không lối ra
2.4. Sự tương đương của nguồn và Otomat hữu hạn
không lối ra
2.5. Sự tương đương của nguồn và văn phạm chính quy
2.6. Sự tương đương của nguồn và biểu thức chính quy
2.7. Bài tập tổng hợp
2.8. Tính đóng của lớp ngôn ngữ chính quy
2.9. Điều kiện cần của ngôn ngữ chính quy
2.10. Điều kiện cần và đủ của lớp ngôn ngữ chính quy
2.11. Otomat hữu hạn có lối ra
2.12. Ngôn ngữ chính quy
i
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
TS
LT TH/Xemina BT KT
02
Chƣơng III. Ngôn ngữ phi ngữ cảnh và otomat đẩy 09
xuống.
06
01
3.1. Cây và phép thế cây
3.2. Dạng chuẩn Chomsky
3.3. Cây dẫn xuất và các tính chất
3.8. Khái niệm về Otomat đẩy xuống
02
01
Chƣơng IV: Cơ bản về chƣơng trình dịch
4.1.Giới thiệu chương trình dịch
15
12
4.2.Chương trình dịch
4.2.1. Định nghĩa chương trình dịch
4.2.2. Cấu trúc của chương trình dịch
4.2.3. Cấu trúc tĩnh (cấu trúc logic)
4.2.4. Cấu trúc động
4.2.5. Vị trí của chương trình dịch trong hệ thống dịch
4.3.Sự cần thiết nghiên cứu chương trình dịch
4.4. Bộ phân tích cú pháp
Nhiệm vụ của sinh viên :
Tham dự các buổi thuyết trình của giáo viên, tự học, tự làm bài tập do giáo viên giao, tham
dự các bài kiểm tra định kỳ và cuối kỳ.
Tài liệu học tập :
Nguyễn Văn Ba, Ngôn ngữ hình thức, Trường Đại học Bách khoa Hà nội, 1997
-
-
Phan Đình Diệu, Lý thuyết otomat và thuật toán, Nhà xuất bản Đại học và Trung học
Chuyên nghiệp, 1971
-
-
-
Đỗ Đức Giáo, Đặng Huy Ruận, Ngôn ngữ hình thức, Nhà xuất bản KHKT, 1991
Phạm Hồng Nguyên, Giáo trình chương trình dịch, ĐH KHTN HN
Nguyễn Văn Ba, Phân tích cú pháp, ĐH Bách khoa HN
Hình thức và tiêu chuẩn đánh giá sinh viên:
-
-
Hình thức thi cuối kỳ : Thi viết.
Sinh viên phải đảm bảo các điều kiện theo Quy chế của Nhà trường và của Bộ
Thang điểm: Thang điểm chữ A, B, C, D, F
Điểm đánh giá học phần: Z = 0,2X + 0,8Y.
Bài giảng này là tài liệu chính thức và thống nhất của Bộ môn Khoa học máy tính,
Khoa Công nghệ thông tin và được dùng để giảng dạy cho sinh viên.
Ngày phê duyệt:
/
/2010
Trƣởng Bộ môn: Thạc sỹ Nguyễn Hữu Tuân
ii
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
MỤC LỤC
Nội dung
Trang
Mục lục
Chƣơng 1: Văm phạm và ngôn ngữ
1. 1. Bảng chữ cái, từ và ngôn ngữ
1. 2. Tích ghép, phép chia, phép soi gương
1. 3. Các phép toán trên ngôn ngữ
1. 4. Văn phạm
1
1
2
4
6
1. 5. Các ví dụ về văn phạm
8
Bài tập
8
Chƣơng 2: Ngôn ngữ chính quy và Otomat hữu hạn
2. 1. Nguồn và ngôn ngữ được sinh bởi nguồn
2. 2. Các phép toán trên nguồn
2. 3. Otomat hữu hạn không lối ra và ngôn ngữ được đoán nhận bởi Otomat hữu
hạn không lối ra
9
9
10
18
2. 4. Sự tương đương của nguồn và Otomat hữu hạn
2. 5. Sự tương đương của nguồn và văn phạm chính quy
2. 6. Sự tương đương của nguồn và biểu thức chính quy
2. 7. Bài tập tổng hợp
2. 8. Tính đóng của lớp ngôn ngữ chính quy
2. 9. Điều kiện cần của ngôn ngữ chính quy
2. 10. Điều kiện cần và đủ của lớp ngôn ngữ chính quy
2. 11. Otomat hữu hạn có lối ra
2. 12. - Ngôn ngữ chính quy
Bài tập
Chƣơng 3: Ngôn ngữ phi ngữ cảnh và Otomat đẩy xuống
3. 1. Cây và phép thế cây
3. 2. Dạng chuẩn Chomsky
3. 3. Cây dẫn xuất và các tính chất
3. 4. Khái niệm về Otomat đẩy xuống
Bài tập
Chƣơng 4: Cơ bản về chƣơng trình dịch
4. 1. Giới thiệu về chương trình dịch
4. 2. Chương trình dịch
4. 2. 1. Định nghĩa chương trình dịch
4. 2. 2. Cấu trúc của chương trình dịch
4. 2. 3. Cấu trúc tĩnh của chương trình dịch
4. 2. 4. Cấu trúc động của chương trình dịch
4. 2. 5. Vị trí của chương trình dịch trong hệ thống dịch
4. 3. Sự cần thiết phải nghiên cứu chương trình dịch
4. 4. Bộ phân tích cú pháp
26
30
30
30
31
31
31
31
31
31
32
32
32
32
32
32
33
33
33
33
37
44
50
58
58
60
62
63
64
Bài tập
Một số đề thi mẫu
Tài liệu tham khảo
iii
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
CHƢƠNG 1: VĂN PHẠM VÀ NGÔN NGỮ
Kiến thức cơ bản: Để tiếp thu tốt nội dung của chương này, sinh viên cần có một số các kiến
thức liên quan về chuỗi, ký hiệu, từ trong các ngôn ngữ tự nhiên như tiếng Việt, tiếng Anh; cấu
trúc cú pháp của các chương trình máy tính viết bằng một số ngôn ngữ lập trình cơ bản như
Pascal, C…
1.1. Bảng chữ cái, từ, ngôn ngữ
Các ngôn ngữ lập trình (như Pascal, C, ...) lẫn ngôn ngữ tự nhiên (như tiếng Việt, tiếng Anh,
...) đều có thể xem như là tập hợp các câu theo một cấu trúc quy định nào đó. Câu của ngôn ngữ,
trong tiếng Việt như "An là sinh viên giỏi" hay trong Pascal là một đoạn chương trình bắt đầu
bằng từ khóa program cho đến dấu chấm câu kết thúc chương trình, đều là một chuỗi liên tiếp các
từ, như “An”, “giỏi” hay “begin”, “if”, “x2”, “215”, tức các chuỗi hữu hạn các phần tử của một
bộ chữ cái cơ sở nào đó. Ta có thể xem chúng như là các ký hiệu cơ bản của ngôn ngữ.
Từ nhận xét đó, ta dẫn tới một quan niệm hình thức về ngôn ngữ như sau (theo từ điển):
Ngôn ngữ, một cách không chính xác là một hệ thống thích hợp cho việc biểu thị các ý nghĩ, các
sự kiện hay các khái niệm, bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng.
Định nghĩa trên chỉ cung cấp một ý niệm trực quan về ngôn ngữ chứ không đủ là một định
nghĩa chính xác để nghiên cứu về ngôn ngữ hình thức. Chúng ta bắt đầu xây dựng định nghĩa này
bằng các khái niệm mà mọi ngôn ngữ đều đặt nền tảng trên đó.
1.1.1. Bảng chữ cái
Một dãy hữu hạn hoặc vô hạn các phần tử, kí hiệu được gọi là một bảng chữ cái trong đó
mỗi phần tử a được gọi là một kí hiệu (một chữ cái).
Ví dụ:
= {0,1}
: Bảng chữ cái nhị phân
= {0,1,…,9} : Bảng chữ cái thập phân
1.1.2. Từ
Một dãy kí hiệu a1, a2,…, an (ai, i=1 n) được gọi là một từ .
Ví dụ :
= {0,1}
a1 = 0, a2 = 1, a3 = 00, a4 = ,…
Từ rỗng đựơc kí hiệu là , mọi bảng chữ cái đều sinh ra từ rỗng.
Tổng số các kí hiệu tạo nên từ được gọi là độ dài của từ.
Ví dụ :
= {a,b,c}
a1 = aabb, a2 = ac, | a1| = 4, |a2| = 2
1
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
Độ dài của từ rỗng = 0.
Nếu a là một từ thuộc bảng chữ cái , là một bảng chữ cái chứa bảng chữ cái thì a
. Ví dụ :
= {0,1} , = {0,1,2,…,9}
a1 = 0110 , a
Tập hợp tất cả các từ kể cả từ rỗng kí hiệu là *.
Tập hợp tất cả các từ trừ rỗng kí hiệu là +. Vậy + = * \ {}
1.1.3. Ngôn ngữ
Ngôn ngữ là một tập hợp các câu có một cấu trúc qui định nào đó. Một câu của ngôn ngữ là
một dãy (hay xâu) các từ có sẵn được liệt kê trong một bảng chữ nào đó, như là các ký hiệu cơ
bản của ngôn ngữ. Giả sử có bảng chữ cái .
Tập A * được gọi là một ngôn ngữ sinh bởi .
Ví dụ :
= {a,b,c}
A = {x */x bắt đầu bởi kí hiệu a} được gọi là một ngôn ngữ *.
Ngôn ngữ trống kí hiệu .
Mọi bảng chữ cái đều sinh ra .
Ngôn ngữ trống và ngôn ngữ chứa từ rỗng là khác nhau.
1.2. Tích ghép, phép chia, phép soi gƣơng
1.2.1. Tích ghép hai xâu
Giả sử có bảng chữ cái
Các từ = a1a2a3…an , = a1a2…am ( ai )
Tích ghép của và được hình thành bằng cách ghép từ vào sau từ .
= . = a1a2a3…ana1a2…am
Ví dụ :
={0,1}
= 011, =1101
= 0111101
Tính chất của tích ghép
+ Tích ghép không có tính chất giao hoán
+ Tích ghép có tính chất kết hợp
() = ()
2
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
+ Tích ghép của một xâu với một xâu rỗng bằng chính nó
. = . =
Với tích ghép: =.
: Tiếp đầu ngữ
: Tiếp vị ngữ
1.2.2. Chia xâu
Giả sử có z = x.y ( x,y,z * )
+ Phép chia trái
Nếu ta thực hiện ngắt bỏ xâu x ra khỏi z có nghĩa là ta đã thực hiện phép chia trái xâu z cho x
và kết quả là xâu y.
Kí hiệu
x\Z = y
Phép chia phải
Nếu ta thực hiện ngắt xâu y ra khỏi xâu z có nghĩa là ta đã thực hiện phép chia phải xâu z
cho xâu y và kết quả là xâu x.
Kí hiệu
Ví dụ :
Z/y = x
= {0,1}, x = 10, y = 11
Z = x.y = 1011
x\Z = 11
Z/y = 10
1.2.3. Phép soi gương
Giả sử có bảng chữ cái
Từ = a1a2…am-1am *
Từ ̃ = amam-1…a2a1 được gọi là từ soi gương của từ hay còn gọi là từ ngược của từ
| | = | |
̃
1.3. Các phép toán trên ngôn ngữ
1.3.1. Phép hợp hai ngôn ngữ
Giả sử có bảng chữ cái , A, B, C là các ngôn ngữ được sinh ra bởi
C = A B = {x */x A hoặc x B}
Ví dụ
= {a,b,c}
A = {a, b, ab, ac, cb}, B = {aa, bb, cc}
3
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
C = A B = {a, b, ab, ac, cb, aa, bb, cc}
+ Tính chất
Phép hợp có tính chất giao hoán
Có tính chất kết hợp
A B = B A
(A B) C= A (B C)
1.3.2. Phép giao hai ngôn ngữ
Giả sử có bảng chữ cái , A, B, C là các ngôn ngữ sinh ra bởi
C = A B = {x * | x A và x B}
Ví dụ :
= {a, b}
A = {a, ab, ac, cb}, B = {b, ab, cb, aa, bc}
C = A B = {ab, cb}
+ Tính chất
Tính kết hợp
C (A B) = B (A C)
Tính giao hoán
A B = B A
A = A =
1.3.3. Phép tích ghép hai ngôn ngữ
+ Giả sử có bảng chữ cái , A, B, C là các ngôn ngữ được sinh bởi từ
C=A.B={z *| z=x.y | x A, y B}
Ví dụ :
= {a, b, c}
A = {a, b, ab, ac}, B{c, cb}
C = A.B = {ac, bc, abc, acc, acb, bcb, abcb. accb}
+ Tính chất
- Không có tính chất giao hoán
A.B B.A
- Có tính chất kết hợp
A.(B.C) = (A.B).C
- Có tính chất phân bố (đối với phép hợp)
A.(B C) = (A.B) (A.C)
4
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
- Tính chất lũy thừa
A.A.A…A = An
1.3.4. Phép hiệu
Giả sử có bảng chữ cái , A, B, C là các ngôn ngữ sinh bởi
C = A\B = {x * | x A, x B}
được gọi là ngôn ngữ hiệu của hai ngôn ngữ A và B.
Ví dụ :
= {a, b, c}
A = {a, b, ac, bc, aa}, B = {b, bc, ab, bb}
C = B\A = {b, ab, bb}
1.3.5. Phép lấy phần bù
Giả sử có bảng chữ cái , A, B là các ngôn ngữ được sinh ra bởi
A = CB = { x */ x B}
được gọi là ngôn ngữ phần bù hay ngôn ngữ bù của ngôn ngữ B.
Ví dụ :
Cho B = {a, bc}.
Khi đó ngôn ngữ bù của ngôn ngữ B sẽ là :
A = {x * | x a, x bc}.
1.3.6. Phép chia hai ngôn ngữ
Giả sử có bảng chữ cái , A, B là các ngôn ngữ được sinh ra bởi .
Tập các từ C = {z *| x A, y B, x=y.z} được gọi là phép chia trái của ngôn ngữ
A cho ngôn ngữ B và kí hiệu B\A .
Tập các từ C = {z * | x A, y B, x = z.y } được gọi là phép chia phải của ngôn
ngữ A cho ngôn ngữ B và kí hiệu là A/ B.
Ví dụ :
= {a, b, c}
A = {a, bc, abc, aba} , B = {, b, ab, cbc}
B\A = { a, bc, abc, aba, c}
A/B = {a, bc, abc, aba}
1.3.7. Phép soi gương ngôn ngữ
Giả sử có bảng chữ cái ,A, B là các ngôn ngữ được sinh bởi .
5
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
B = Ã = {x ̃ * / x ̃ là từ soi gương của x A }.
Ví dụ
= {0, 1}
A = {0, 1, 10, 110}
B = Ã ={0, 1, 01, 011}
1.3.8. Phép lặp
Giả sử có bảng chữ cái , A là ngôn ngữ được sinh bởi .
A* = { } A A ….An gọi là ngôn ngữ lặp của ngôn ngữ A.
Tính chất :
-
(A* )* = A*
-
{}* = {}
-
()* = {} . … = {}
-
()+ = . … =
1.4. Văn phạm
Với mục đích sản sinh (hay đoán nhận) ngôn ngữ, văn phạm được dùng như một cách thức
hiệu quả để biểu diễn ngôn ngữ.
1.4.1. Định nghĩa văn phạm cấu trúc (Grammar)
Theo từ điển, văn phạm, một cách không chính xác, là một tập các quy tắc về cấu tạo từ
và các quy tắc về cách thức liên kết từ lại thành câu.
Để hiểu rõ hơn khái niệm này, ta xét ví dụ cây minh họa cấu trúc cú pháp của một câu đơn trong
ngôn ngữ tiếng Việt "An là sinh viên giỏi" ở thí dụ 1.5 của chương 1. Xuất phát từ nút gốc theo
dần đến nút lá, ta nhận thấy các từ ở những nút lá của cây như “An”, “sinh viên”, “giỏi”, … là
những từ tạo thành câu được sản sinh. Ta gọi đó là các ký hiệu kết thúc bởi vì chúng không còn
phát sinh thêm nút nào trên cây và câu được hoàn thành. Trái lại, các nút trong của cây như “câu
đơn”, “chủ ngữ”, “danh từ”, … sẽ không có mặt trong dạng câu sản sinh, chúng chỉ giữ vai trò
trung
gian
trong việc sinh chuỗi, dùng diễn tả cấu trúc câu. Ta gọi đó là các ký hiệu chưa kết thúc. Quá trình
sản sinh câu như trên thực chất là sự diễn tả thông qua cấu trúc cây cho một quá trình phát sinh
chuỗi. Các chuỗi được phát sinh bắt đầu từ một ký hiệu chưa kết thúc đặc biệt, sau mỗi bước thay
thế một ký hiệu chưa kết thúc nào đó trong chuỗi thành một chuỗi lẫn lộn gồm các ký hiệu kết
thúc và chưa, cho đến khi không còn một ký hiệu chưa kết thúc nào nữa thì hoàn thành. Quá trình
này chính là phương thức phát sinh chuỗi của một văn phạm, được định nghĩa hình thức như sau:
6
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
Định nghĩa : Văn phạm cấu trúc G là một hệ thống gồm bốn thành phần xác định như sau G
(,V, S, P), trong đó:
- : tập hợp các ký hiệu kết thúc (terminal)
- V : tập hợp các biến (variables) hay các ký hiệu chưa kết thúc (non terminal)
- P: tập hữu hạn các quy tắc ngữ pháp được gọi là các luật sinh (production.
- S: ký hiệu chưa kết thúc dùng làm ký hiệu bắt đầu (start)
Người ta thường dùng các chữ cái Latinh viết hoa (A, B, C, ...) để chỉ các ký hiệu trong tập biến
V; các chữ cái Latinh đầu bảng viết thường (a, b, c, ...) dùng chỉ các ký hiệu kết thúc thuộc tập
.
Nhận xét : Bằng quy ước này chúng ta có thể suy ra các biến, 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 văn phạm, một cách đơn giản người ta chỉ cần liệt kê tập luật sinh của chúng.
1.4.2. Sự phân cấp Chomsky trên văn phạm
Bằng cách áp đặt một số quy tắc hạn chế trên các luật sinh, Noam Chomsky đề nghị một
hệ thống phân loại các văn phạm dựa vào tính chất của các luật sinh. Hệ thống này cho phép xây
dựng các bộ nhận dạng hiệu quả và tương thích với từng lớp văn phạm. Ta có 4 lớp văn phạm
như sau :
1) Văn phạm loại 0: Một văn phạm không cần thỏa ràng buộc nào trên tập các luật sinh được gọi
là văn phạm loại 0 hay còn được gọi là văn phạm không hạn chế (Unrestricted Grammar)
2) Văn phạm loại 1: Nếu văn phạm G là văn phạm các phép thế dạng và thỏa ||<|| thì G
là văn phạm loại 1 hoặc còn được gọi là văn phạm cảm ngữ cảnh CSG (Context-Sensitive
Grammar)
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ cảm ngữ cảnh (CSL)
3) Văn phạm loại 2: Nếu văn phạm G có các luật sinh dạng A với A là một biến đơn và là
một chuỗi các ký hiệu thuộc (V T)* thì G là văn phạm loại 2 hoặc còn được gọi là văn phạm phi
ngữ cảnh CFG (Context-Free Grammar)
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ phi ngữ cảnh (CFL)
4) Văn phạm loại 3: Nếu văn phạm G có mọi luật sinh dạng tuyến tính phải (rightlinear): A
wB hoặc A w với A, B là các biến đơn và w là chuỗi ký hiệu kết thúc (có thể rỗng); hoặc có
dạng tuyến tính trái (left-linear): A Bw hoặc A w thì G là văn phạm loại 3 hay còn được
7
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
gọi là văn phạm chính quy RG (Regular Grammar)
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ chính quy (RL)
Ký hiệu : L0, L1, L2, L3 là các lớp ngôn ngữ sinh ra bởi các văn phạm loại 0, 1, 2, 3 tương ứng.
Ta có : L3 L2 L1 L0 và các bao hàm thức này là nghiêm ngặt.
1.6. Các ví dụ về văn phạm
Cho bảng chữ cái ∑ = a ,a ,...,a . Xây dựng văn phạm sinh các ngôn ngữ sau:
n
1
2
VD 1. L = *
VD 2. L = +
VD 3. L = Các xâu có độ dài chẵn dương trên
VD 4. L = Các xâu có độ dài chẵn trên
VD 5. L = Các xâu có độ dài lẻ trên
VD 6. Cho bảng chữ cái 0,1,2 . ây dựng văn phạm G sinh ngôn ngữ L như sau:
L = gồm các từ bắt đầu bằng 011, chứa từ con 11211 và kết thúc bằng 1210
BÀI TẬP
Bài 1. Cho các ngôn ngữ sau: L1 = {a, ab, abb, aabbb, abbaa, aaaabb, ababba}
L2 = {, ab, bb, aba, bbb, aabb}
Tìm các ngôn ngữ hợp, giao, tích ghép, lặp của L1và L2. Tìm ngôn ngữ chia trái, chia phải của L1
cho L2. Tìm ngôn ngữ soi gương của L1.
Bài 2. Cho bảng chữ cái = {a, b, c}. Xây dựng văn phạm sinh ngôn ngữ
L = {anb2n+1ck *n > 0, k 0}
8
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
CHƢƠNG II: NGÔN NGỮ CHÍNH QUY VÀ OTOMAT HỮU HẠN
2.1. Nguồn và ngôn ngữ đƣợc sinh bởi nguồn
2.1.1. Định nghĩa: Nguồn là một đa đồ thị có hướng và có khuyên, có một đỉnh tách ra làm đỉnh
vào, kí hiệu là( →O), một tập con các đỉnh mà mỗi đỉnh này được gọi là một đỉnh ra hay đỉnh kết
và đặt trong một ô chữ nhật (□), đồng thời trên mỗi cung ghi một ký hiệu thuộc bảng chữ cái
{}.
Cung trên đó ghi từ rỗng gọi là cung rỗng hay cung trống và thường người ta không ghi từ
rỗng trên các cung này. Cung trên đó ghi ký hiệu thuộc được gọi là cung cốt yếu. Đỉnh kết yếu
là đỉnh có cung cốt yếu đi tới.
Ví dụ về nguồn :
a
S1
S2
a,c
b,c
a
S5
S3
c
b,a
S4
Hình 1.1. Nguồn I1
2.1.2. Nguồn đơn định
Nguồn I được gọi là nguồn đơn định nếu nó không chứa cung rỗng và hai cung tùy ý xuất
phát từ một đỉnh đều được ghi bằng hai ký hiệu khác nhau. Nguồn I1 là nguồn đơn định.
2.1.3. Nguồn đầy đủ
Nguồn đầy đủ là nguồn mà từ một đỉnh các cung đi ra phải chứa đầy đủ các ký hiệu bảng
chữ cái .
2.1.4. Nguồn đơn định và đầy đủ
Là nguồn vừa đơn định vừa đầy đủ
r0
Ví dụ :
a
b,c
a,b,c
a,b
r1
r2
c
Hình 1.2. Nguồn đơn định và đầy đủ I2
9
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
2. 1. 5. Từ được sinh bởi nguồn
- Từ đựơc sinh bởi nguồn là dãy các ký hiệu của bảng chữ cái nằm trên các cung của
nguồn đi từ đỉnh vào và đến một trong những đỉnh kết.
- Ngôn ngữ được sinh bởi nguồn I là tập hợp các từ được sinh bởi nguồn I, ký hiệu là N(I) =
{x *| x NI(v(I),s), s F(I)}.
Trong đó
v(I) : đỉnh vào
F(I) : Tập đỉnh kết
- Theo nguồn trên ta xác định ngôn ngữ được sinh bởi nguồn I
NI(s1,s3) = {b,c}
NI(s1,s4) = NI(s1,s3).{b,a}.c* = {b,c}.{b,a}.{cs|s = 0,1,2,…}
= {bbcs,bacs,cbcs,cacs | s = 0,1,2…}
NI(s1,s2) = {a} NI(s1,s4).{a} = {a}. {bbcsa,bacsa,cbcsa,cacsa}
={bbcsa,bacsa,cbcsa,cacsa,a | s=0,1,2…}
NI(s1,s5)=NI(s1,s2).{a,c} =
bbcsaa,bacsaa,cbcsaa,cbcsaa,aa,bbcsac,bacsac,cbcsac,cacsac,ac|s=0,1,2…}
Ngôn ngữ được sinh bởi nguồn I1 là :
N(I1) = NI(s1,s4) NI(s1,s5) = {bbcs,bacs,cbcs,cacs |s = 0,1,2…} bbctaa, bactaa, cbctaa,
cbctaa, aa, bbctac, bactac, cbctac, cactac, ac |t = 0,1,2…} = {aa, ac, bbcs, bacs, cbcs, cacs, bbctaa,
bactaa, cbctaa, cbctaa, bbctac, bactac, cbctac, cactac |s, t = 0,1,2…}
2.2. Các phép toán trên nguồn
2.2.1. Phép đơn định hóa
Giả sử nguồn I chưa đơn định và đầy đủ trên bảng chữ cái , cần xây dựng nguồn K đơn
định, đầy đủ tương đương với nó.
Thuật toán đơn định hoá nguồn như sau:
1) Đối với ký hiệu a tùy ý thuộc và đỉnh s tùy ý của nguồn I xác định tập:
T1(s,a) = {u D(I) |a N(s,u)}.
Đối với tập con M tùy ý của tập D(I) và mọi ký hiệu a xác định tập:
H1(M,a) =
T1(s,a).
sM
2) Xây dựng nguồn đơn định đầy đủ K
a. Đỉnh và cung:
10
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
Đỉnh vào của K: v(K)= {v(I)}.
Đối với mọi đỉnh M A(K) đã được xác định, ta xác định đỉnh H1(M,a) và kẻ một cung trên
đó ghi ký hiệu a đi từ đỉnh M sang đỉnh H1(M,a).
b.Tập đỉnh kết của K :
F(K) = {M A(K) | M F(I) }
c.Với cách xây dựng như trên có nguồn K tương đương với nguồn I và K đơn định, đầy đủ.
Chú ý: Nếu ta loại tập rỗng ra khỏi A(K) thì nguồn K nhận được đơn định, nhưng không đầy
đủ.
Ví dụ : Cho nguồn chưa đơn định và đầy đủ I :
a,b
a,b
a
b
S2
S0
S1
Hình 1.3. Nguồn I chưa đơn định đầy đủ
Thực hiện đơn định hóa nguồn I :
b
b
a
b
a
q2={S0,S2 }
q2={S0,S2 }
q0={S0}
b
q1={S0,S1}
a
b
Nguồn đã đơn định đầy đủ, tương đương với I là :
a
b
a
b
a
a
a
q2
q3
q0
q1
b
Hình 1.4. Nguồn I' đơn định đầy đủ
2. 2. 2. Phép lấy phần bù
Giả sử I là nguồn tùy ý trên bảng chữ cái . Để xây dựng nguồn sinh ngôn ngữ phần bù của
ngôn ngữ do I sinh ra ta thực hiện một thuật toán gồm các bước sau:
1. Nếu I chưa đơn định và đầy đủ, ta xây dựng nguồn K đơn định, đầy đủ tương đương với I,
tức là N(I)= N(K).
11
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
2. Trên nguồn K ta đổi các đình kết thành không kết và không kết thành kết. Khi đó nguồn
nhận được sẽ sinh ra ngôn ngữ phần bù của ngôn ngữ do nguồn K sinh ra.
Vậy N(M) = C N(K) = C N(I).
2.2.3. Phép hợp nguồn
Giả sử I1 và I2 là các nguồn trên bảng chữ cái . Cần xây dựng nguồn I sinh ngôn ngữ là hợp
của hai ngôn ngữ do I1 và I2 sinh ra, tức là N(I) = N(I1) N(I2). Nguồn I được gọi là nguồn hợp
của các nguồn I1 và I2.
Thuật toán:
Để xây dựng nguồn I hợp của hai nguồn I1 và I2, ta giữ nguyên cấu trúc của I1 và I2, thêm
vào một đỉnh mới (không phụ thuộc I1 cũng như I2) và thừa nhận đỉnh này là đỉnh vào của nguồn
I, đồng thời từ đỉnh mới thêm vào kẻ các cung rỗng đi tới các đỉnh v(I1) và v(I2).
Tập đỉnh kết của nguồn I là F(I) = F(I1) F(I2).
Với cách xây dựng trên dễ dàng nhận thấy rằng: N(I) = N(I1) N(I2).
Chú ý: Ta có thể mở rộng phép hợp trên cho s (s>2) nguồn tùy ý.
Định lý: Đối với s (s > 1) nguồn tùy ý I1, I2,…, In luôn luôn xây dựng được nguồn I, để nó
s
sinh ra ngôn ngữ là hợp của các ngôn ngữ do I1, I2,…, In sinh ra, tức là N(I)=
Cho 2 nguồn I1 và I2 :
N(Ii).
i1
S0
q0
S2
q2
S1
q1
Hình 1.5. Nguồn I1 và I2
Hợp của I1 và I2 là :
v(I)
q0
S
q2
q1
S2
S1
12
Hình 1.6. Hợp của I1 và I2
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
2.2.4. Phép giao nguồn
Giả sử có các nguồn I1, I2. Cần xây dựng nguồn I, sinh ngôn ngữ là giao của các ngôn ngữ do
I1, I2 sinh ra, tức là N(I)= N(I1) N(I2). Nguồn I được gọi là nguồn giao của các nguồn I1, I2.
Thuật toán xây dựng nguồn giao I:
Để có nguồn giao I của các nguồn I1, I2 ta xác định đỉnh và cung của nó bằng phép quy nạp
như sau:
1. Đỉnh vào của nguồn I: v(I) = {v(I1), v(I2)};
2. Giả sử B = (P,Q), trong đó P D(I1), Q D(I2) là các đỉnh tùy ý đã được xác định và a
H
là ký hiệu bất kỳ thuộc . Khi đó xác định đỉnh C = HI (P,a),
(Q,a)), đồng thời kẻ một cung
I2
1
trên đó ghi ký hiệu a, đi từ đỉnh B sang C.
3. Đỉnh D = (S,R) được thừa nhận là đỉnh kết của nguồn I (D F(I)) khi và chỉ khi S F(I1)
và R F(I2) .
Với cách xây dựng trên nguồn I sinh ngôn ngữ là giao của các ngôn ngữ do I1, I2 sinh ra.
Lấy ví dụ với 2 nguồn I1 và I2 (hình 1.5 )
S0, q0
, q1
, S2
S0,q0
a,c
a,b
,
S2,
, q2
a,b,c
a,b,c
a,b,c
13
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
Nguồn giao của chúng là :
S1
S0
Hình 1.7. Nguồn giao cuả I1 và I2
2.2.5. Phép tích ghép hai nguồn
Đối với hai nguồn I1, I2 tùy ý, cần xây dựng nguồn I, sinh ngôn ngữ là tích ghép của các
ngôn ngữ do I1, I2 sinh ra, tức là N(I)= N(I1).N(I2).
Nguồn I được gọi là nguồn tích ghép của nguồn I1, I2.
Thuật toán xây dựng nguồn tích ghép:
Để xây dựng nguồn tích ghép (I) của các nguồn I1,I2, ta giữ nguyên cấu trúc của I1,I2 thừa
nhận đỉnh vào I1 là đỉnh vào của nguồn I(v(I)=v(I1)), các đỉnh kết của nguồn I2 là đỉnh kết của
nguồn I(F(I)=F(I2)), đồng thời từ mỗi đỉnh kết của nguồn I1 kẻ một cung rỗng đi tới đỉnh vào của
nguồn I2. Đồng thời chuyển các đỉnh kết của I1 thành đỉnh thường.
Với cách xây dựng như trên nguồn I, sinh ngôn ngữ là tích ghép của các ngôn ngữ do I1, I2
sinh ra.
Tích ghép của hai nguồn I1 và I2 (hình 1.5) :
S
S
S
Hình 1.8. Tích ghép 2
nguồn I1 và I2
q
q2
q1
2.2.6. Phép lặp
Đối với nguồn I1 tùy ý, cần xây dựng nguồn I1 sinh ngôn ngữ là lặp của ngôn ngữ do I sinh
ra. Nguồn I1 được gọi là nguồn lặp của nguồn I.
Thuật toán xây dựng nguồn lặp I:
Để xây dựng nguồn I, sinh ngôn ngữ là lặp của ngôn ngữ do nguồn I1 sinh ra, ta giữ nguyên
14
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
cấu trúc của I1, thêm vào một đỉnh mới và thừa nhận đỉnh này là đỉnh vào đồng thời là đỉnh kết
duy nhất của nguồn I. Từ đỉnh mới kẻ thêm một cung rỗng đi tới đỉnh v(I1), đồng thời từ mỗi
đỉnh kết của nguồn I1 kẻ một cung rỗng đi tới đỉnh mới thêm.
Nguồn sinh ngôn ngữ là lặp cắt của ngôn ngữ được sinh bởi I1 chỉ khác với nguồn trên ở chỗ:
đỉnh mới thêm chỉ được thừa nhận là đỉnh vào, còn tập đỉnh kết của I1 được thừa nhận là đỉnh kết
của nguồn mới.
Với cách xây dựng trên nguồn lặp (nguồn lặp cắt I) sinh ngôn ngữ là lặp (lặp cắt) của ngôn
ngữ do I1 sinh ra, tức là N(I) = N(I1) * (N(I) = N(I1)*) .
Nguồn lặp của nguồn I1 :
S
S
S2
S1
Hình 1.9. Nguồn lặp của I1
2.2.7. Phép soi gương nguồn
Đối với nguồn I1 tùy ý, cần xây dựng nguồn I sinh ngôn ngữ soi gương của ngôn ngữ do I1
sinh ra. Nguồn I được gọi là nguồn soi gương của nguồn I1.
Thuật toán xây dựng nguồn soi guơng:
Để được nguồn I sinh ngôn ngữ soi gương của ngôn ngữ do I1 sinh ra ta thực hiện các bước
sau:
1) Thêm vào một đỉnh mới, thừa nhận nó là đỉnh vào của nguồn I, đồng thời từ đỉnh mới
thêm (v(I)) kẻ các cung rỗng đi tới đỉnh kết của nguồn I1.
2) Thừa nhận đỉnh vào của I1 (v(I1)) là đỉnh kết duy nhất của nguồn I.
F(I) = {v(I1)};
3) Đối với mỗi cung của nguồn I1, giữ nguyên ký hiệu ghi trên nó, nhưng đổi chiều ngược
lại.
15
Bài giảng môn học: Ngôn ngữ hình thức và Otomat
Với cách xây dựng trên ta có : N(I) = N(I1).
Nguồn soi gương của I1 :
S
S0
S2
S
Hình 1.10. Nguồn soi gương của I1
2.2.8. Phép chia trái
Giả sử I1, I2 là các nguồn trên bảng chữ cái . Cần xây dựng nguồn K sinh ngôn ngữ là
thương bên trái của các ngôn ngữ do I1, I2 sinh ra.Nguồn K được gọi là nguồn thương bên trái của
các nguồn I1, I2.
Thuật toán xây dựng nguồn thương bên trái:
1) Xây dựng nguồn giao I của các nguồn I1, I2.
2) Thêm vào một đỉnh mới và thừa nhận đỉnh này là đỉnh vào của nguồn K. ký hiệu bằng
v(K);
3) Tập đỉnh kết: F(K) = F(I1);
4) Giả sử Q = (S,T) là một đỉnh tùy ý của nguồn giao I. Khi đó đối với mỗi đỉnh x S (S
A(I1)) từ đỉnh vào của nguồn K (v(K)) có cung đi tới x khi và chỉ khi T F(I2) .
N(I1)
Với cách xây dựng này ta có: N(K) =
N(I2)
2. 2. 9. Phép chia phải
Giả sử I1, I2 là các nguồn trên bảng chữ cái . Cần xây dựng nguồn K sinh ngôn ngữ là
thương bên phải của các ngôn ngữ do I1, I2 sinh ra. Nguồn K được gọi là nguồn thương bên phải
của các nguồn I1, I2.
Thuật toán xây dựng nguồn thương bên phải:
1) Dựa vào cấu trúc của I1 đối với mỗi s1 D(I1) xây dựng nguồn Is có đỉnh vào là si (v(Is )
i
i
= si) và F(Is ) = F(I1)
i
16
Tải về để xem bản đầy đủ
68 trang
17960
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Ngôn ngữ hình thức và Ôtômat - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_ngon_ngu_hinh_thuc_va_otomat_truong_dai_hoc_hang.pdf
