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 4. Văn ph m chính quyạ
(Regular grammars)
M C ĐÍCH:Ụ

Trang b nh ng khái ni m v văn ph m chính quy;ị ữ ệ ề ạ

Bi n đ i t ng đ ng gi a RG và FAế ổ ươ ươ ữ

Các tính ch t c a văn ph m tính quy.ấ ủ ạ
YÊU C U:Ầ

Sinh viên n m v ng các khái ni m.ắ ữ ệ

V nhà, c th hóa các thu t toán b ng ch ng trình.ề ụ ể ậ ằ ươ
©copyright by PhD. C.T.Ha, Le Quy Don Technical
University
Bài 4. Văn ph m chính quyạ

Σ - 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 symbols);

Δ , Δ Σ =Ø, g i là b ng ký hi u ph (báng ch cái không k t ∩ ọ ả ệ ụ ữ ế
thúc – non-terminal symbols);

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).ọ ắ ặ ậ ế ạ
Recursively enumerable
Context-sensitive
Context-free
Regula
r
4.1. Khái ni m văn ph m chính quyệ ạ
6/27/14
6

Phân lo i theo Chomsky:ạ
4.1. Khái ni m văn ph m chính quyệ ạ
6/27/14
7

ĐN 4.1. Văn ph m chính quy (RG) ạ là văn ph m mà t t ạ ấ
c các lu t sinh c a nó đ u có d ng tuy n tính trái (ho c ả ậ ủ ề ạ ế ặ
tuy n tính ph i):ế ả

Tuy n tính tráiế : d ng A ạ → Bw ho c A ặ → w


Đ nh lý 4.1: ị N u L đ c sinh ra t m t văn ph m chính quy thì L là t p ế ượ ừ ộ ạ ậ
h p chính quy.ợ

Ý nghĩa: nh v y, m t ư ậ ộ RG có th đ c bi u di n b i m t ể ượ ể ễ ở ộ FA.
Bài 4. Văn ph m chính quyạ
6/27/14
9
4.1. Văn ph m chính quyạ
4.2. S t ng đ ng gi a RG và FAự ươ ươ ữ
4.2.1. Gi i thu t bi n đ i t RG sang FAả ậ ế ổ ừ
4.2.2. Gi i thu t bi n đ i t FA sang RGả ậ ế ổ ừ
4.3. B đ b m (pumching lemma) cho RSổ ề ơ
4.4. Tính đóng c a t p h p chính quyủ ậ ợ
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
4.2.1. Gi i thu t bi n đ i t RG sang FAả ậ ế ổ ừ
6/27/14
10

Gi i thu t ả ậ xây d ng ự FA cho văn ph m tuy n tính ph iạ ế ả :

Xây d ng t p Q g m các tr ng thái có d ng [α] v i α là S ho c ự ậ ồ ạ ạ ớ ặ
chu i h u t c a v ph i m t lu t sinh nào đó trong P. ỗ ậ ố ủ ế ả ộ ậ

N u A là m t bi n và (A ế ộ ế → α) ∈ P: δ([A], ε) = {[α]}

N u a là m t ký hi u k t thúc: ế ộ ệ ế δ([aα], a) = {[α]}

Tr ng thái b t đ u ạ ắ ầ [S], tr ng thái k t thúc ạ ế [ε]

trí b t đ u và ng c l i.ắ ầ ượ ạ
4.2.1. Gi i thu t bi n đ i t RG sang FAả ậ ế ổ ừ
4.2.1. Gi i thu t bi n đ i t RG sang FAả ậ ế ổ ừ
6/27/14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical Universityữ ứ
12

Ví d 4.4:ụ xét văn ph m tuy n tính trái G = < Σ, Δ, S, P > :ạ ế
P: S → S10 | 0
Xây d ng FA cho văn ph m tuy n ự ạ ế
tính ph i G’ = < Σ, Δ, S, P’ >:ả
P’: S → 01S | 0
S] [01S]
[ε]
ε
[0]
[1S]
ε
1
0
[0]
ε
ε
[01S]
[ε]
0
1
0
[S] [1S]
Bài 4. Văn ph m chính quyạ

4.2.2. Gi i thu t bi n đ i t FA sang RGả ậ ế ổ ừ
6/27/14
15
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
A → 0B | 1D | 0
B → 0D | 1C
C → 0B | 1D | 0
D → 0D | 1D
A → 0B | 0
B → 1C
C → 0B | 0
Do D không có ích nên có th rút g n G nh sau:ể ọ ư
Ví d 4.5:ụ xét DFA cho 0(10)* sau:
A CB
0
1
0, 1
D
0
1
1
0
4.2.2. Gi i thu t bi n đ i t FA sang RGả ậ ế ổ ừ
6/27/14
16

Gi i thu t xây d ng RG tuy n tính trái cho FA:ả ậ ự ế

B t đ u v i m t NFA cho LRắ ầ ớ ộ

δ(q0, a1a2…ai) = qi, n u m>n, theo nguyên lý Dirichlet, ph i có ít ế ả
nh t 2 tr ng thái trùng nhau.ấ ạ
o
Gi s đó là hai s nguyên j và k sao cho 0 ≤ j < k ≤ n th a mãn qj ả ử ố ỏ
= qk.
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
4.3. B đ b m cho t p h p chính quyổ ề ơ ậ ợ
6/27/14
19
o
z ∈ L → qm ∈ F → a1…ajak+1…am ∈ L(A) →
a1…aj(aj+1…ak)iak+1…am ∈ L(A), v i i ≥ 0 ớ

Vì j < k nên chu i aj+1 ak có đ dài ít nh t b ng 1 và vì k ≤ n nên k-j ỗ ộ ấ ằ
≤ n. Chu i đó t o thành m t ỗ ạ ộ vòng l pặ :

Vòng l p trong hình trên có th đ c l p l i s l n tùy ý, do đó chu i ặ ể ượ ặ ạ ố ầ ỗ
a1 aj (aj+1 ak)i ak+1 am L(M), i ≥ 0.∈ ∀
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
q0
a1. . . aj
qj=qk
ak+1. . am
aj+1. . ak
u
v
w
qm


Gi s L là t p chính quy ả ử ậ t n t i DFA ch p nh n L. → ồ ạ ấ ậ
G i n là s tr ng thái c a DFA.ọ ố ạ ủ

Xét chu i z = ỗ . Theo b đ b m: z=uvw v i 1≤ lvl ≤ n ổ ề ơ ớ
và uviw ∈ L

Xét i = 2, ta ph i có uv2w ả ∈ L

M t khác: n2 = lzl = luvwl < luvvwl ≤ n2 + n < (n+1)2ặ

Do n2 và (n+1)2 là 2 s chính ph ng liên ti p nên luv2wl ố ươ ế
không th là m t s chính ph ng, hay uv2w không ể ộ ố ươ
thu c L (trái gi thi t).ộ ả ế
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
2
0
i
2
0
n
Bài 4. Văn ph m chính quyạ
6/27/14
22
4.1. Văn ph m chính quyạ
4.2. S t ng đ ng gi a RG và FAự ươ ươ ữ
4.2.1. Gi i thu t bi n đ i t RG sang FAả ậ ế ổ ừ
4.2.2. Gi i thu t bi n đ i t FA sang RGả ậ ế ổ ừ
4.3. B đ b m (pumching lemma) cho RSổ ề ơ