Ôtômát và ngôn ngữ hình thức
1
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP VINH
KHOA CÔNG NGHỆ
NGÀNH CÔNG NGHỆ THÔNG TIN
NGUYỄN NGỌC THUẦN
ÔTÔMÁT VÀ NGÔN NGỮ HÌNH THỨC
Vinh, 2016
Ôtômát và ngôn ngữ hình thức
2
LỜI NÓI ĐẦU
Ôtômát và ngôn ngữ hình thức là lĩnh vực thuộc chuyên ngành Khoa học máy tính,
chủ yếu dùng trong việc mô tả, hình thức hóa các dãy tính toán và điều khiển tự
động, được phát sinh trong nhiều ngành khoa học khác nhau từ các hệ thống tính
toán, ngôn ngữ học đến sinh học,. ....
Ngày nay, các ngôn ngữ lập trình, các hệ thống máy tính, các quá trình xử lý thông
tin và các quá trình tính toán nói chung đều được hình thức hoá thành các mô hình
toán học mà lý thuyết ôtômát và ngôn ngữ hình thức là công cụ. Ôtômát và ngôn
ngữ hình thức được áp dụng rộng rãi trong nhiều lĩnh vực khoa học và ứng dụng
như: mô hình hoá, mô phỏng các hệ thống tính toán, các kỹ thuật dịch, thông dịch,
trí tuệ nhân tạo, công nghệ tri thức, ...
Nhằm đáp ứng nhu cầu giảng dạy, học tập và nghiên cứu cho các sinh viên ngành
Công nghệ thông tin của trường Đại học Công nghiệp Vinh – là trường Đại học
hoạt động theo hướng thực hành, chúng tôi biên soạn giáo trình “Ôtômát và ngôn
ngữ hình thức” theo hướng kết hợp ba mảng chính: lý thuyết ôtômát, ngôn ngữ
hình thức và lý thuyết tính toán gồm những khái niệm, kiến thức cơ bản nhất với
nhiều ví dụ minh hoạ, bỏ qua các chứng minh lý thuyết không thực sự cần thiết,
nhằm tập trung tối đa thời gian cho việc giải các bài tập, ví dụ thực tiễn.
Giáo trình giới thiệu một cách hệ thống những khái niệm cơ bản và các tính chất
chung của ôtômát và ngôn ngữ hình thức.
Chương mở đầu trình bày các khái niệm cơ bản, các tính chất quan trọng của các
cấu trúc đại số, logic mệnh đề,... làm cơ sở cho các chương sau. Chương 2, giới
thiệu về Văn phạm và các ngôn ngữ hình thức. Lý thuyết Ôtômát, những khái niệm
cơ sở và các hoạt động của Ôtômát được đề cập ở Chương 3. Những vấn đề liên
quan đến tập chính qui, ngôn ngữ chính qui và ôtômát hữu hạn được trình bày chi
tiết ở Chương 4. Chương 5, nghiên cứu các khái niệm cơ sở, mối quan hệ giữa các
lớp ngôn ngữ và các tính chất rất quan trọng của ngôn ngữ phi ngữ cảnh, Ôtômát
đẩy xuống.
Sau mỗi Chương có các bài tập hệ thống hoá lại kiến thức và thông qua đó, học
viên nắm bắt được các khái niệm cơ bản, các kiến thức chủ yếu của từng Chương
và cuối cùng là để nâng cao sự hiểu biết về ôtômát và ngôn ngữ hình thức, đồng
thời phát triển khả năng ứng dụng chúng trong nghiên cứu và triển khai ứng dụng
Công nghệ thông tin.
Ôtômát và ngôn ngữ hình thức
3
Mặc dù đã có nhiều cố gắng, nhưng tài liệu này chắc không tránh khỏi những thiếu
sót. Chúng tôi rất mong nhận được các ý kiến, góp ý của các đồng nghiệp và bạn
đọc để hoàn thiện hơn cuốn giáo trình Ôtômát và ngôn ngữ hình thức. Các ý kiến
đóng góp xin được gửi về: Bộ môn CNTT, Khoa Công Nghệ, trường ĐHCN Vinh.
Số 26, Đường Nguyễn Thái Học, Phường Đội Cung, Tp. Vinh, Tỉnh Nghệ An.
Chủ biên
TS. Nguyễn Ngọc Thuần
Ôtômát và ngôn ngữ hình thức
4
MỤC LỤC
Nội dung
Trang
Chương 1: Bổ túc – Các khái niệm cơ bản.
1.1 Tập hợp
1.2 Quan hệ và Đô thi.
1.3. Đa
i cương vê ngôn ngư.
1.4. Bai tâ
p:
Chương 2: Văn phạm và các ngôn ngữ hình thức
2.1 Văn phạm và các ngôn ngữ
Định nghĩa Văn phạm: Bộ 4 thành phần G = (∑,V, P, S).
2.2. Các dẫn xuất và và ngôn ngữ sinh bởi văn phạm
+ Dẫn xuất
+ Ngôn ngữ sinh.
+ Văn phạm tương đương
+ Bài toán thuận và Bài toán ngược.
2.3. Phân loại ngôn ngữ (Văn pha
m) của Chomsky
2.4. Tính đệ qui và tập đệ qui.
2.5. Các phép toán trên các ngôn ngữ.
2.6. Các ví dụ và bài tập.
Chương 3: Lý thuyết Ôtômát
3.1 Ôtômát hữu hạn
3.1.1 Hàm chuyển trạng thái và tính chất
3.1.2 Các phương pháp biểu diễn ôtômát
3.1.3 Ngôn ngữ đoán nhận được của ôtômát
3.2. Ôtômát hữu hạn không đơn định
3.3. Sự tương đương của ôtômát đơn định và không đơn định.
3.4. Cực tiểu hoá ôtômát hữu hạn.
3.5. Các ví dụ và Bài tập.
1 – 10
1
3
7
10
11 – 37
11
12
13
14
15
15
16 - 21
22 - 27
28 - 30
31 – 35
36 – 37
38 - 57
38
40
41
42
44
47 - 50
51 – 55
56 – 57
Ôtômát và ngôn ngữ hình thức
5
Chương4: Tập chính qui và văn phạm chính qui
4.1 Các biểu thức chính qui.
4.2 Sự tương đương của các biểu thức chính qui
Định lý (Định lý Arden)
4.3 Ôtômát hữu hạn và biểu thức chính qui
4.3.1 Phương pháp đại số ứng dụng định lý Arden
4.3.2 Thiết lập ôtômát hữu hạn tương đương với biểu thức chính qui
4.4 Bổ đề Bơm đối với các tập chính qui.
4.5 Ứng dụng Bổ đề Bơm
4.6 Các tập chính qui và văn phạm chính qui
4.6.1 Xây dựng VP chính qui tương đương với ÔTĐĐ cho trước
4.6.2 Xây dựng ÔTĐĐ hữu hạn tương đương với VP chính qui G
4.5. Các ví dụ và Bài tập.
Chương 5: Ngôn ngữ phi ngữ cảnh va Ôtômát đẩy xuống
5.1 Ngôn ngữ phi ngữ cảnh và cây dẫn xuất
5.2 Sự nhập nhằng trong văn phạm phi ngữ cảnh
5.3 Dạng chuẩn Chomsky
5.4 Bổ đề Bơm cho ngôn ngữ phi ngữ cảnh
5.5 Ôtômát đẩy xuống (PDA) và ứng dụng.
5.5.1. Câ u ta
o va hoa
t đô ng cua PDA
5.5.2. Đoan nhâ
n xâu vao cua PDA
5.5.3. Ngôn ngư đoan nhâ
n cua PDA
5.5.4. Mối quan hệ giữa PDA và Văn pha
m phi ngư canh
5.6. Các ví dụ và Bài tập.
58 - 75
58
59
60
62
63 - 66
67
67
68
69
69 -70
70 - 71
71 - 75
76 - 95
76 -81
82
82
83 -85
86
87
88
89 - 90
91 - 93
94 - 95