GIẢ NG V I Ê N : T S . H À C H Í T R U N G
B Ộ M Ô N : K H M T
K H O A C N T T , H V K T Q S
Đ T : 0 1 6 8 . 5 5 8 . 2 1 . 0 2
E M A I L : H C T 2 0 0 9 @ Y A H O O . C O M

Lý thuyết automata và
ngôn ngữ hình thức
©copyright by PhD. C.T.Ha, Le Quy Don Technical University
Ngôn ngữ
hình thức
Grammar
Automata
2
Bài 1. Nhập môn Theory of automata and
formal languagues – TA&FL (AL)
MỤC ĐÍCH:
 Trang bị những hiểu biết chung nhất về môn học;
 Khái quát lại một số khái niệm, cơ sở toán học làm cơ sở
học tập môn học.
YÊU CẦU:
 Về nhà, sinh viên phải hệ thống lại các kiến thức cơ sở về
toán liên quan và kiến thức lập trình.
©copyright by PhD. C.T.Ha, Le Quy Don Technical University
Bài 1. Nhập môn TA&FL
1.1. Giới thiệu về môn học TA&FL
1.2. Yêu cầu với môn học
1.3. Tài liệu tham khảo môn TA&FL
1.4. Bổ túc một số khái niệm toán học
1.4.1. Tập hợp
1.4.2. Quan hệ

 Kiến thức về ngôn ngữ hình thức và automat là nền tảng
cho nhiều lĩnh vực của khoa học máy tính và CNTT.
5
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.1. Giới thiệu về môn học TA&FL
 Ứng dụng của lý thuyết ngôn ngữ hình thức và automata:
 Dùng trong xử lý từ vựng và cú pháp ngôn ngữ tự nhiên;
 Dùng trong xây dựng ngôn ngữ lập trình ctd;
 Dùng trong nhận dạng (đối với những mẫu nhận dạng có
cấu trúc);
 Dùng trong tin sinh học (Bio-informatics);
 Dùng trong tính toán phân tử (DNA Computing);
 Dùng trong xử lý ảnh (nén ảnh Fractal, );
 Dùng trong công nghệ phần mềm ( mã hóa dữ liệu, mô
hình hoá các hệ thống động, các tiến trình hệ thống…);
 Trong lĩnh vực trí tuệ nhân tạo…
6
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.1. Giới thiệu về môn học TA&FL
 Nội dung chính của môn học TA&FL:
1. Cơ sở toán học của môn TA&FL
2. Văn phạm và ngôn ngữ hình thức
3. Automata hữu hạn và ngôn ngữ hình thức
4. Văn phạm chính quy và các tính chất
5. Văn phạm phi ngữ cảnh
6. Pushdown automata (automata đẩy xuống)
7. Máy Turing
8. Phần bài tập lý thuyết và thực hành

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
Bài 1. Nhập môn TA&FL
1.1. Giới thiệu về môn học TA&FL
1.2. Yêu cầu với môn học
1.3. Tài liệu tham khảo môn TA&FL
1.4. Bổ túc một số khái niệm toán học
1.4.1. Tập hợp
1.4.2. Quan hệ
1.4.3. Phép chứng minh
1.4.4. Đồ thị và cây

10
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.3. Tài liệu môn học
11
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1. Bài giảng của giảng viên.
2. Nguyễn Gia Định. Lý thuyết ngôn ngữ hình thức và
ôtômát. Đại học khoa học Đại học Huế - 2004.
3. Nguyễn Văn Xuất. Giáo trình Automata, ngôn ngữ hình
thức và nguyên lý chương trình dịch - HVKTQS – 2004.
4. Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ
hình thức – Nhà xuất bản Đại học quốc gia Tp. Hồ Chí
Minh – 2002.
5. John E. Hopcropft, Rareev Motwani, Jeffrey D. Ullman.
Introduction to Automata Theory, Languages, and
Computation (2nd Edition) -Addison-Wesley 2001.


Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.4.1. Tập hợp
14
07/03/2012
 ĐN 1.2: Tập rỗng, ký hiệu là  hoặc { }
 ĐN 1.3: Tập hợp con (subset)
oKý hiệu: A  B (Ngược lại: A  B )
o{ 1, 2, 4 }  { 1, 2, 3, 4, 5 } nhưng { 2, 4, 6 }  { 1, 2, 3, 4, 5 }
 ĐN 1.4: Tập hợp bằng nhau
oKý hiệu: A = B nếu ( x  A )  ( x  B ),
(ngược lại: A

B )
o{ 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 }

{ 2, 1 }
 ĐN 1.5: Tập lũy thừa (power set)
oKý hiệu: 2
A
oA = { 1, 2, 3 } thì 2
A
= {, {1}, {2}, {3}, {1, 2},
{2, 3}, {3, 1}, {1, 2, 3} }
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.4.1. Tập hợp
15
07/03/2012
 Kết quả của một số phép toán sau đây trên các tập hợp là
một tập hợp mới.
 Phần bù (complement):

1.4.2. Quan hệ
1.4.3. Phép chứng minh
1.4.4. Đồ thị và cây

17
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.4.2. Quan hệ
18
07/03/2012
 ĐN 1.6: Cho các tập hợp A
1
, A
2
, , A
n
. Một quan hệ
(relations) n-ngôi trên các các tập hợp này là tập hợp con của
tích Đềcác A
1
◦A
2
◦ ◦ A
n
mà thỏa mãn một số tính chất nào đó.
Các tập hợp A
1
, A
2
, , A

07/03/2012
 Các tính chất của quan hệ:
 Phản xạ (reflexive): nếu aRa là đúng với aS
 Đối xứng (symmetric): nếu aRb thì bRa
 Bắc cầu (transitive): nếu aRb và bRc thì aRc
 Ví dụ 1.5: cho S = {0, 1, 2, 3}
o Quan hệ ‘thứ tự nhỏ hơn’:
L = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) }
o Quan hệ ‘bằng’: E = { (0, 0), (1, 1), (2, 2), (3, 3) }
o Quan hệ ‘chẵn lẻ’:
P = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)}
o Tính chất: L không là quan hệ phản xạ hay đối xứng, E
và P mang tính phản xạ, đối xứng và bắc cầu

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.4.2. Quan hệ
21
07/03/2012
 ĐN 1.8: quan hệ mang tính phản xạ, đối xứng và bắc cầu
được gọi là quan hệ tương đương.
 Ví dụ 1.6: E và P là quan hệ tương đương, L không là quan
hệ tương đương.
 ĐN 1.9: Nếu R là quan hệ tương đương trên S thì R phân
hoạch S thành các lớp tương đương không rỗng và rời
nhau: S = S
1
 S
2
 …
 Tính chất:

+

o Không còn gì thêm trong R
+

 ĐN 1.12: Bao đóng phản xạ và bắc cầu R*:
o R* = R
+
 { (a, a)  a  S }
 Ví dụ 1.8: R = { (1, 2), (2, 2), (2, 3) } trên S = {1, 2, 3}
o R
+
= { (1, 2), (2, 2), (2, 3), (1, 3) }
o R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) }
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
Bài 1. Nhập môn TA&FL
1.1. Giới thiệu về môn học TA&FL
1.2. Yêu cầu với môn học
1.3. Tài liệu tham khảo môn TA&FL
1.4. Bổ túc một số khái niệm toán học
1.4.1. Tập hợp
1.4.2. Quan hệ
1.4.3. Phép chứng minh
1.4.4. Đồ thị và cây

23
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
1.4.3. Phép chứng minh
24



B
Case 2: A
2


B
…
Case n: A
n


B
 Ví dụ 1.10: chứng minh với mọi số nguyên n thì biểu thức:
9n
2
+ 3n -2
biểu diễn một số chẵn.
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University