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
Languague
Grammar
Automata
2
Bài 2.  phạm và ngôn ngữ hình thức
Grammars and formal languagues
MỤC ĐÍCH:
 Trang bị những khái niệm cơ bản của môn học TA&FL;
YÊU CẦU:
 Sinh viên nắm vững các khái niệm làm cơ sở cho các bài
học tiếp theo.
©copyright by PhD. C.T.Ha, Le Quy Don Technical University
Bài 2. Văn phạm và ngôn ngữ hình thức
2.1. Ngôn ngữ
2.1.1. Các khái niệm cơ bản
2.1.2. Các phép toán trên từ
2.1.3. Các phép toán trên ngôn ngữ
2.2. Văn phạm
2.2.1. Văn phạm và các khái niệm liên quan
2.2.2. Phân loại văn phạm theo Chomsky
2.2.3. Tính chất của văn phạm và ngôn ngữ
2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm

 ĐN 2.2. Cho , một dãy ,
ược gọi là một từ hay một xâu (chuỗi) trên bảng 
 , 0, 01, 101, 1010, 110011 là các từ trên bảng chữ cái 
{0,1};
 là các từ trên 

a
 
12
, , ,
m
a a a
12

i i it
a a a


ij
a 
2.1.1. Các khái niệm cơ bản
6
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
 ĐN 2.3. Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi
• |abca| = 4
 ĐN 2.4. Chuỗi rỗng: ký hiệu ε, chuỗi không có ký hiệu nào
• || = 0
 ĐN 2.5. Chuỗi con: chuỗi v là chuỗi con của w nếu v ược
tạo bởi các ký hiệu liền kề nhau trong chuỗi w.

 * = {ε
 
+

 Chuỗi 010210  * vì có số 2  

2.1.1. Các khái niệm cơ bản
9
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
 Biểu diễn ngôn ngữ:
 Liệt kê các phần tử (chuỗi): L = {aa, aba, baa, baba}
 Mô tả đặc điểm chủ yếu: L = {a
i
| i là số nguyên tố}
 Biểu diễn ngôn ngữ một cách tổng quát thông qua văn
phạm (grammar) và automata:
 Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ;
 Automata: là một máy trừu tượng, hay một cơ chế cho
phép  nhận một chuỗi bất  có thuộc một ngôn ngữ
L hay không

Bài 2. Văn phạm và ngôn ngữ hình thức
2.1. Ngôn ngữ
2.1.1. Các khái niệm cơ bản
2.1.2. Các phép toán trên từ
2.1.3. Các phép toán trên ngôn ngữ
2.2. Văn phạm
2.2.1. Văn phạm và các khái niệm liên quan
2.2.2. Phân loại văn phạm theo Chomsky

2.1. Ngôn ngữ
2.1.1. Các khái niệm cơ bản
2.1.2. Các phép toán trên từ
2.1.3. Các phép toán trên ngôn ngữ
2.2. Văn phạm
2.2.1. Văn phạm và các khái niệm liên quan
2.2.2. Phân loại văn phạm theo Chomsky
2.2.3. Tính chất của văn phạm và ngôn ngữ
2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm
2.3. Sơ lược về automata

12
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
2.1.3. Các phép toán trên ngôn ngữ
13
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
 Vì mỗi ngôn ngữ là một tập hợp nên ta có các phép toán
đại số tập hợp như là phép hợp, phép giao, phép hiệu,
phép lấy bù trên các ngôn ngữ.
 Phép hợp:
 Phép giao:
 Phép phần bù (complement): = * \ L
 Phép nhân ghép (concatenation):
L
1
L
2
= {w

1 2 1 2
|L L L and L
  
    
 
CL

2.1.3. Các phép toán trên ngôn ngữ
14
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
 ĐN 2.10. Ngôn ngữ lặp (bao  kleene, hoặc *-closure):
 ĐN 2.11. Ngôn ngữ lặp cắt (bao  dương  positive
closure):
 ĐN 2.12. Ngôn ngữ ngược:
 ĐN 2.13. Ngôn ngữ cắt trái của ngôn ngữ X cho ngôn ngữ Y:
 ĐN 2.14. Ngôn ngữ cắt phải của ngôn ngữ X cho ngôn ngữ Y:
 
*
|
RR
LL

  
 
*2
0

in
i

2.2.3. Tính chất của văn phạm và ngôn ngữ
2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm
2.3. Sơ lược về automata

15
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
2.2.1. Văn phạm và các khái niệm liên quan
16
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
 Theo từ ển, văn phạm 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.
 Ví dụ ơn giản về  phạm:
<câu>→<chủngữ><vịngữ>
<chủngữ>→tôi | anh | chị
<vịngữ>→<ộngtừ><danhtừ>
<ộngtừ>→ | uống
<danhtừ>→cơm | phở | sữa | café.

2.2.1. Văn phạm và các khái niệm liên quan
17
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
 ĐN 2.15:  phạm G là một bộ sắp thứ tự gồm 4 thành
phần trong :
 - bảng chữ cái, gọi là bảng chữ cái cơ bản (bảng chữ cái
kết thúc  terminal symbol);
 ∩ gọi là bảng ký hiệu phụ (báng chữ cái không
kết thúc  nonterminal symbol);

, , 
m

 * và 
1
→ 
2
, 
2
→ 
3
, , 
m-1
→ 
m
thì 
m
có thể ược
dẫn xuất gián tiếp từ 
1


1
→ * 
m
 ĐN 2.18. Ngôn ngữ L sinh bởi văn phạm G:
L (G) = {w  w  * và S → * w}
 ĐN 2.19. Văn phạm tương đương: là 2  phạm sinh ra
cùng một ngôn ngữ (G
1

A
2m
 a
1
a
2
a
n

 Khi , ta có thể biểu diễn nó dưới dạng cây như sau:

S
A
1n
A
2m

A
12A
23a
4

a
n


S
a
A
S
a
b b
S
a
a
A
Bài 2. Văn phạm và ngôn ngữ hình thức
2.1. Ngôn ngữ
2.1.1. Các khái niệm cơ bản
2.1.2. Các phép toán trên từ
2.1.3. Các phép toán trên ngôn ngữ
2.2. Văn phạm
2.2.1. Văn phạm và các khái niệm liên quan
2.2.2. Phân loại văn phạm theo Chomsky
2.2.3. Tính chất của văn phạm và ngôn ngữ
2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm
2.3. Sơ lược về automata

23
07/03/2012
Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
2.2.2. Chomsky hierarchy -1956
07/03/2012
24
 Avram Noam Chomsky ưa ra một hệ thống phân loại

0
, L
1
, L
2
, L
3
là lớp các ngôn ngữ ược sinh ra
bởi  phạm loại 0, 1, 2, 3 tương ứng, ta có:
L
3
 L
2
 L
1
 L
0
.