G I N G 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
Automat
a
2
Bài 2. Văn 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ạ

ĐN 2.1. T p Σ khác r ng g m h u h n hay vô h n các ký hi u ậ ỗ ồ ữ ạ ạ ệ
đ c g i là ượ ọ b ng ch cáiả ữ . M i ph n t đ c g i là m t ỗ ầ ử ượ ọ ộ
ch cái ữ hay m t ộ ký hi uệ .

∑ = {a, b, c, … , x, y, z} b ng ch cái ti ng Anh;ả ữ ế

Δ = {α, β, γ, δ, ε, η, , κ, μ, χ, ν, π, θ, ρ, σ, τ, ω,ξ, ψ};ϕ

Г = {0, 1} b ng ch cái nh phân;ả ữ ị

Đ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};ừ ả ữ

ε, beautiful, happy… là các t trên Σ = {a, b, c, …, z}.ừ
a
∈Σ
{ }
1 2
, , ,
m
a a a
Σ =
1 2

i i it
a a a
α
=

7
5/13/14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University

Ngôn ng : ữ theo t đi n, ừ ể 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 t p các ký hi u, các qui t c đ v n d ng chúng.ồ ậ ệ ắ ể ậ ụ

ĐN 2.8: M t ngôn ng (hình th c) L trên b ch cái ộ ữ ứ ộ ữ Σ là
m t ộ t p h p các chu iậ ợ ỗ t các ký hi u c a b ch cái ừ ệ ủ ộ ữ Σ.

Σ* : t p h p t t c các chu i con, k c chu i r ng ε, ậ ợ ấ ả ỗ ể ả ỗ ỗ
sinh ra t b ch cái ừ ộ ữ Σ.

Σ+ : t p h p t t c các chu i con, ngo i tr chu i r ng ậ ợ ấ ả ỗ ạ ừ ỗ ỗ
ε, sinh ra t b ch cái ừ ộ ữ Σ.
Σ* = Σ+ + {ε} Σ+ = Σ* - {ε}
2.1.1. Các khái ni m c b nệ ơ ả
8
5/13/14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University

Ví d 1: ụ Cho Σ = {0,1} thì:

Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, …}

Σ+ = {0, 1, 00, 01, 10, 11, 000, …}


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ơ ượ ề
10
5/13/14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
2.1.2. Các phép toán trên từ
11
5/13/14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University

ĐN 2.8. Chu i n i k t (concatenation): ỗ ố ế chu i đ c t o thành ỗ ượ ạ
b ng cách vi t chu i th nh t, sau đó chu i th hai, ằ ế ỗ ứ ấ ỗ ứ
o
N i ghép c a chu i ố ủ ỗ Long và Int là LongInt
o
N i k t c a chu i r ng: εw = wε = w (v i m i w) ε là đ n v c a →ố ế ủ ỗ ỗ ớ ọ ơ ị ủ
phép n i k tố ế

ĐN 2.9. Chu i đ o ng c (reverse)ỗ ả ượ : c a chu i w, ký hi u wR, là ủ ỗ ệ
chu i w đ c vi t theo th t ng c l i.ỗ ượ ế ứ ự ượ ạ
o
w = abcd wR = dcba→ εR = ε

Phép c t trái ắ c a t α cho t β - là ph n còn l i c a t α sau khi c t ủ ừ ừ ầ ạ ủ ừ ắ
b ph n đ u β trong t α.ỏ ầ ầ ừ

Phép c t ph i ắ ả c a t α cho t β - là ph n còn l i c a t α sau khi c t ủ ừ ừ ầ ạ ủ ừ ắ
b ph n đuôi β trong t α.ỏ ầ ừ


Phép nhân ghép (concatenation):
L1L2 = {w1w2 | w1 ∈ L1 và w2 ∈ L2} trên b ch cái ộ ữ Σ1 ∪ Σ2
o
LLL…LL = Li (k t n i i l n trên cùng ngôn ng L)ế ố ầ ữ
o
L0 = {ε}
{ }
*
1 2 1 2
|L L L or L
ω ω ω
∪ = ∈Σ ∈ ∈
{ }
*
1 2 1 2
|L L L and L
ω ω ω
∩ = ∈Σ ∈ ∈
( )
C L
Σ
2.1.3. Các phép toán trên ngôn ngữ
14
5/13/14
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 đóng kleene, ho c *-closure):ặ


1

i n
i
L L L L L
∞
+
=
= = ∪ ∪ ∪ ∪
U
{ }
*
\ | ,Z Y X z x X y Y mà x yz
= = ∈Σ ∈ ∈ =
{ }
/ | ,Z X Y z x X y Y mà x zy
∗
= = ∈Σ ∈ ∈ =
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ơ ượ ề
15

Δ , Δ Σ =Ø, g i là b ng ký hi u ph (báng ch cái không k t ∩ ọ ả ệ ụ ữ ế
thúc – nonterminal symbol);

S Δ - ký hi u xu t phát hay tiên đ (∈ ệ ấ ề start variable);

P - t p các lu t sinh (ậ ậ production rules) d ng α β, α, β (Σ → ∈ ∪ạ
Δ)*, trong α ch a ít nh t m t ký hi u không k t thúc (đôi khi, ta ứ ấ ộ ệ ế
g i chúng là các qui t c ho c lu t vi t l i).ọ ắ ặ ậ ế ạ
2.2.1. Văn ph m và các khái ni m liên quanạ ệ
18
5/13/14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University

Qui cướ : Trong môn h c s d ng:ọ ử ụ

Ch cái in hoa ữ A, B, C,… đ bi u th các bi n, trong đó ể ể ị ế S là ký hi u xu t ệ ấ
phát;

X, Y, Z,… đ bi u di n các ký t ch a bi t ho c các bi n;ể ể ễ ự ư ế ặ ế

a, b, c, d, e,… đ bi u di n ch cái;ể ể ễ ữ

u, v, w, x, y, z,… đ bi u di n chu i ch cái;ể ể ễ ỗ ữ

α, β, ω,… bi u th chu i các bi n ho c các ký hi u k t thúc.ể ị ỗ ế ặ ệ ế

Ví d 2: ụ G = ({a, b}, {S, A, B}, S, P), trong đó:
P: S aAS|bBS|ε,→
A aaA|b,→

S
A1n
A2m
A12

A23

a4
an
A22
a3
a2
a1
A21
A11
2.2.1. Văn ph m và các khái ni m liên quanạ ệ
5/13/14
21

Ví d 3: ụ Xét văn ph m G ={{a, b}, {S, A}, S, P}, ạ
trong đó
P = { S aS, S aA, A bA, A b }→ → → →

Ngôn ng sinh b i văn ph m G:ữ ở ạ
2.2.1. Văn ph m và các khái ni m liên quanạ ệ
5/13/14
22

Ví d 4: ụ Cho văn ph m:ạ
S→aAS; A→SbA ; A→SS; S→a; A→ba

24

Avram Noam Chomsky đ a ra 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.ạ ự ấ ủ ậ

ĐN 2.20. Văn ph m lo i 0 ạ ạ – Văn ph m không h n ch ạ ạ ế (UG –
Unrestricted Grammar): không c n th a đi u ki n ràng bu c ầ ỏ ề ệ ộ
nào trên t p các lu t sinh;ậ ậ

ĐN 2.21. Văn ph m lo i 1 ạ ạ – Văn ph m c m ng c nh ạ ả ữ ả (CSG –
Context Sensitive Grammar): n u văn ph m G có các lu t sinh ế ạ ậ
d ng α β và :→ạ
,|β| ≥ |α|;

ĐN 2.22. Văn ph m lo i 2 ạ ạ – Văn ph m phi ng c nh ạ ữ ả (CFG –
Context-Free Grammar): có lu t sinh d ng A α v i A là m t →ậ ạ ớ ộ
bi n đ n và α là chu i các ký hi u thu c (Σ ế ơ ỗ ệ ộ ∪ Δ)*;
( )
, , , ,A A
α α α α α β
∗
′ ′′ ′ ′′
= ∈ ∆ ∈ Σ ∪ ∆
2.2.2. Chomsky hierarchy -1956
5/13/14
25

ĐN 2.23. Văn ph m lo i 3 ạ ạ – Văn ph m chính quy ạ (RG –
Regular Grammar): có m i lu t sinh d ng ọ ậ ạ tuy n tính ph iế ả ho c ặ
tuy n tính tráiế .