ươ
ễ Nguy n Ph ọ
ng Thái ộ B môn Khoa h c Máy tính http://www.coltech.vnu.vn/~thainp/
ừ ố ừ ị , t
ẫ v , m u
v ng: t
Nội dung Phân tích t ừ ự t REs, FA (DFA, NFA) Nâng cao: REs NFA; NFA DFA; DFA minimal
ậ
state DFA M t s bài t p ộ ố
ươ 15/11/15 2 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Vai trò của hệ phân tích từ vựng (scanner)
(t
t )ừ ố
(cây cú pháp)
(mã ngu n)ồ
ỗ ừ ự
(l
v ng)
i t
ừ ố
ữ ậ
ư ừ
ố
T t
trong ngôn ng l p trình cũng gi ng nh t
trong
ữ ự
nhiên ừ ự
ạ ộ
v ng ho t đ ng nh m t th t c đ
c
ngôn ng t H phân tích t ệ ọ ở ệ
ư ộ ầ
ủ ụ ượ ộ ừ ố ớ m i t
g i b i h phân tích cú pháp khi nó c n m t t trong dòng vào
ươ 15/11/15 3 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ư
ượ
Từ tố (token) T t
trong VC đ
ạ c phân lo i nh sau:
ị ừ
khóa (vd int, if hay while)
∗
(vd “+” hay “ ”, “<=”)
ự
ẳ
ạ
T p t
ư ữ ậ ph thu c vào ngôn ng l p trình: ch ng h n nh
, trong ngôn ng t
T
ạ ừ ố ộ t
: đ ng t
ừ ố các đ nh danh (vd sum, i, j) các t các toán t ử các ký hi u phân tách (vd “{”, ‘}”, “;”) ệ các h ng (nguyên, th c, logic, xâu) ằ ậ ừ ố ụ ộ t ử trong C toán t ng t ừ
gán là = còn trong Pascal là := nhiên, các lo i t ừ ụ
ừ
ộ
ữ ự ậ , v.v. T p các t
ự , tính t
ừ , ữ ụ ph thu c vào ngôn ng c
ươ danh t thể
ươ 15/11/15 4 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ộ ừ ố
ừ ị ủ
ự ạ
t
t o thành t
ừ ố t
Từ vị (lexeme) T v c a m t t ỗ : chu i ký t Ví d :ụ
ươ 15/11/15 5 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Mẫu (từ tố)
ễ
ộ ừ ố ụ ể
c th
t
ả ậ t p các t ỗ
ậ ớ
ẫ ẫ
ể ể ừ ị v mà có th bi u di n m t t ự
ậ
M u: lu t mô t M u kh p v i m i xâu ký t ớ
trong t p đó
ạ ừ ố
Lo i t
t
INTLITERAL
M uẫ a string of decimal digits
T vừ ị 127, 0
FLOATLITERAL
fill a verbal spec here for C!
127.1, .1, 1.1e2
ID
sum, line num
a string of letters, digits and underscores beginning with a letter or underscore
+
the character ‘+’
+
while
the letters ‘w’, ‘h’, ‘i’, ’l’, ’e’
while
⇒
ứ
ể
ễ
ế
Bi u di n hình th c cho t
ừ ố t
ầ là c n thi
t
REs, NFA, DFA
ươ 15/11/15 6 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các biểu thức chính qui (REs) cho số nguyên và số thực trong C
ươ 15/11/15 7 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các máy hữu hạn trạng thái (FSMs) cho số nguyên và số thực
ươ 15/11/15 8 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ừ ố ừ ị , t
ẫ v , m u
v ng: t
Nội dung Phân tích t ừ ự t REs, FA (DFA, NFA) Nâng cao: REs NFA; NFA DFA; DFA minimal
ậ
state DFA M t s bài t p ộ ố
ươ 15/11/15 9 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ị
Thompson’s construction, Algorithm 3.3,
REs, DFA và NFA Đ nh nghĩa REs, DFA và NFA REs NFA ( ⇒
Red Dragon/Algorithm 3.23, Purple Dragon)
subset construction, Algorithm 3.2, Red
NFA DFA ( ⇒
Dragon/Algorithm 3.20, Purple Dragon)
⇒
state minimisation, Algorithm
DFA minimalstate DFA (
3.6, Red Dragon/Algorithm 3.39, Purple Dragon)
ươ 15/11/15 10 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ả ầ ượ ả
ấ ứ ơ ệ ố
Ứng dụng của biểu thức chính qui B t c n i nào mà m u văn b n c n đ ả ẫ c mô t H th ng, c s d li u và qu n tr m ng Unix: ị ạ ơ ở ữ ệ
grep,
fgrep, egrep, sed, awk ả
Các văn b n HTML: Javascript và VBScript Perl: J. Friedl, Mastering Regular Expressions, O’reilly,
ả ừ ố
ươ
ệ
ừ
t
cho các ch
ng trình sinh h phân tích t
1997 Mô t ự
t v ng (lex, JLex, v.v.)
http://www.robotwisdom.com/net/regexres.html
ươ 15/11/15 11 ễ Nguy n Ph ng Thái Coltech Compiler 2009
⇒
ầ ứ
ể
ạ
ố
ố
Ứng dụng của ôtômát hữu hạn Thi
i thi u hóa tr ng thái
t k ph n c ng (t
t
ể i thi u
ữ
ươ
ệ
ng trình sinh h phân tích t
ừ ự (lex and
v ng
ế ế hóa giá thành) Lý thuy t ngôn ng ế Đ ph c t p tính toán ộ ứ ạ Các ch JLex)
JCT: //humboldt.sunyit.edu/JCT
ươ 15/11/15 12 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Bộ chữ cái, xâu ký tự và ngôn ngữ B ch cái ∑: t p h u h n ký hi u ệ ậ ữ ạ ị
ộ ữ B ch cái nh phân {0,1} (cho ngôn ng máy) B ch cái ASCII (cho các ngôn ng b c cao)
ữ ữ ậ ộ
ệ
ộ ữ ộ ữ Xâu ký t ự
: chu i h u h n ký hi u thu c ∑
ố ượ
ộ
ệ ng ký hi u trong s
ườ
ặ
ợ
ệ
ε | = 0) Ngôn ng : t p các xâu trên ∑; hai tr
ng h p đ c bi
t:
ậ ỗ
ỗ ữ ạ Đ dài |s| c a xâu s: s l ủ ε: xâu r ng (| ỗ ữ ậ ∅: t p r ng {ε}
ươ 15/11/15 13 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ỉ
ộ
ỉ ỉ ỉ
ự
ỗ
ươ
ộ là m t ch
ng trình
Ví dụ về ngôn ngữ ∑= {0, 1} – m i xâu là m t ch th ị ỗ T p ch th c a M68K ị ủ T p ch th c a Pentium ị ủ T p ch th c a MIPS ị ủ ∑ = t p ASCII – m i xâu ký t ươ ng trình Haskell ươ ng trình C ươ ng trình VC
ậ ậ ậ ậ T p các ch ậ T p các ch ậ T p các ch ậ
ươ 15/11/15 14 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các thuật ngữ về xâu ký tự (Figure 3.7 of Text)
ữ
ị
Đ nh nghĩa
ề ố ủ
Thu t ngậ Prefix of s (ti n t
c a s)
a string obtained by removing 0 or more trailing symbols of s
ậ ố ủ
Suffix of s (h u t
c a s)
a string obtained by removing 0 or more leading symbols of s
Substring of s (xâu con c a s)ủ
a string obtained by deleting a prefix and a suffix from s
ề ố ậ ố
, h u t
, xâu
ủ
proper prefix suffix, substring of s (ti n t ợ con phù h p (?) c a s)
Any nonempty string x that is, respectively, a prefix, suffix or substring of s such that s ≠ x
ươ 15/11/15 15 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ạ
ở
ổ
Ghép xâu N u x và y là các xâu, xy là xâu t o b i phép b xung y
ế vào x Ví d :ụ
x y xy key word keyword java script javascript ε is the identity: εx = xε = x
ươ 15/11/15 16 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các phép toán trên ngôn ngữ (Figure 3.8 of Text)
ươ 15/11/15 17 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ví dụ về các phép toán trên ngôn ngữ
ươ 15/11/15 18 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ví dụ về các phép toán trên ngôn ngữ
ươ 15/11/15 19 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ơ ở
ạ
Các biểu thức chính qui – Regular Expressions (REs) – trên bộ chữ cái ∑ C s qui n p:
ữ
ộ
1. ε là m t RE, khi đó ngôn ng chính qui – regular language (RL) – ộ RL là {ε} ∈ 2. a ướ
∑ là m t RE, khi đó RL là {a} ả ử
ươ ứ
ạ
s r và s là các RE, các RL t
ng ng là L(r)
L(s)∪
∗
∗
ộ
B c qui n p: Gi and L(s). Khi đó: ộ 1. (r)|(s) là m t RE, RL là L(r) ộ 2. (r)(s) là m t RE, RL là L(r)L(s) ộ 3. (r) là m t RE, RL là L(r) 4. (r) là m t RE, RL là L(r)
ể ượ ọ
ữ
Chú ý: ngôn ng chính qui cũng có th đ
ậ c g i là t p chính qui
ươ 15/11/15 20 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ứ ự ư
Thứ tự ưu tiên và tính kết hợp của các toán tử “chính qui” Th t
u tiên: ộ ư
ứ
ử ề
ế ợ
“ ” ∗ có đ u tiên cao nh t ấ “ghép” có đ u tiên th nhì ộ ư “|” có đ u tiên th p nh t ấ ấ ấ ả t c các toán t
ộ ư Tính k t h p: — t ế ợ
đ u có tính k t h p
trái Ví d :ụ
≡ ∗ a|b c ừ ặ
∗ (c)) ấ
ầ ử ụ
(a)|((b) Không c n s d ng các d u ngo c th a!
ươ 15/11/15 21 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ữ
ị
Một ví dụ về RE và RL B ch cái: ∑ = {0, 1} ộ ữ RE: 0(0|1)∗ Câu h i: RE trên đ nh nghĩa ngôn ng nào? Tr l
∗
ỏ ả ờ i: L(0(0|1)
∗ )
∗
) = L(0)L((0|1) = {0}L(0|1)∗ ∪ L(1)) = {0}(L(0) ∗ ∪ = {0}({0} {1}) = {0}{0, 1}∗ = {0}{ε, 0, 1, 00, 01, 10, 11, . . . } = {0, 00, 01, 000, 001, 010, 011, . . . } ả ậ
ự ị
ắ ầ
ớ
t p các xâu ký t
ộ ố nh phân b t đ u v i m t s
RE trên mô t 0
ươ 15/11/15 22 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các ví dụ khác: ∑ = {0, 1}
ươ 15/11/15 23 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ề
ộ
Giải thích một số ký hiệu M t hay nhi u instance +: r+ = rr∗
ữ
ư
u tiên và tính k t h p nh ∗
ế ợ ε
Ngôn ng (L(r))+ Có cùng th t ứ ự ư Không hay m t instance ?: r? = r| ộ
ữ
ε}
{∪ ế t (r)? đ ch nhóm (vd (12)?) Các l p ký t ớ
Ngôn ng L(r) Vi ể ỉ ự : [A − Za − z ][A − Za − z0 − 9 ]∗
ươ 15/11/15 24 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các biểu thức chính qui cho VC (hay C)
ồ
ữ c a VC, ch cái g m c “_” ữ ố
ặ ả ủ ữ
ị
Trong đ c t ả Trong Java, ch cái và ch s thu c t p Unicode. Do đó các đ nh danh có ộ ậ
th là:ể
ươ 15/11/15 25 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Các văn phạm chính qui cho số nguyên và số thực trong VC
ươ 15/11/15 26 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ôtômát hữu hạn (hay máy hữu hạn trạng thái)
ộ
ộ ộ ữ ạ M t ôtômát h u h n là m t b 5: (∑, S, T, F, I)
ạ ạ
S→
ế
ạ
ọ
ạ
trong đó ∑ là b ch cái ộ ữ S là t p h u h n tr ng thái ậ ữ ạ T là hàm chuy n tr ng thái: T : S × ∑ ể F là t p h u h n các tr ng thái k t thúc hay còn g i là ậ ữ ạ ậ tr ng thái nh n
ắ ầ
ạ
I là tr ng thái b t đ u: I
S.∈
ươ 15/11/15 27 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Biểu diễn và chấp nhận
ồ ị
ể
Đ th chuy n:
ộ
ấ
ậ ườ
ậ ể ừ ạ
ế ắ ầ
ữ ạ ng đi nào đó trong đ th chuy n t ấ
ế ạ
ườ
ậ
ờ
Ch p nh n: M t Ôtômát h u h n ch p nh n m t xâu vào x n u và ch ỉ ộ ế ồ ị tr ng thái b t đ u đ n ạ ồ ng đi đó t o
ấ n u có đ tr ng thái ch p nh n nào đó, đ ng th i các nhãn trên đ thành x
ươ 15/11/15 28 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ôtômát hữu hạn này đoán nhận ngôn ngữ nào?
ươ 15/11/15 29 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ví dụ 1
ươ 15/11/15 30 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Trạng thái lỗi ẩn
ươ 15/11/15 31 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ộ
ế
ể ε, và
ệ
ớ
Ôtômát hữu hạn đơn định (DFA) và ôtômát hữu hạn không đơn định (NFA) ộ M t FA là m t DFA n u Không tr ng thái nào có m t chuy n ộ ạ V i m i tr ng thái s và ký hi u vào a, có không quá m t ộ ỗ ạ cung nhãn a ra kh i sỏ ế ộ ộ
ộ
ả ệ
ứ
ộ
ơ
ị
M t FA là m t NFA n u nó không ph i m t DFA: Không đ n đ nh: ng v i m t ký hi u vào có th có vài ể ớ
chuy nể
ươ 15/11/15 32 ễ Nguy n Ph ng Thái Coltech Compiler 2009
DFA hay NFA? Các ngôn ngữ được đoán nhận là gì?
ươ 15/11/15 33 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Hai ví dụ
ự ủ
ủ
ề
c a a mà chi u dài c a chúng là
ồ
Cùng ngôn ng : t p các xâu ký t ữ ậ ộ ố ủ b i s c a 2 hay 3 (g m c
ả ε)
ươ 15/11/15 34 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ừ ố ừ ị , t
ẫ v , m u
v ng: t
Nội dung Phân tích t ừ ự t REs, FA (DFA, NFA) Nâng cao: REs NFA; NFA DFA; DFA minimal
ậ
state DFA M t s bài t p ộ ố
ươ 15/11/15 35 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ề
ườ
ự
ườ
ợ
Thuật toán Thompson để xây dựng NFA từ các RE Đi u khi n b i cú pháp ở ể Quy n p: Các tr ợ ạ ng h p (case) trong xây d ng NFA ị ớ ươ ứ ng h p trong đ nh nghĩa RE ng ng v i các tr t Đi u quan tr ng: n u m t ký hi u xu t hi n vài l n ầ ệ ấ ộ ế ọ ề ỗ ệ ượ ạ
ộ
c t o cho m i
t đ
ệ
ệ ộ trong m t RE r, m t NFA riêng bi ấ ầ l n xu t hi n
ề
ậ
Thu t toán Thompson là m t trong nhi u thu t toán đã ộ
ậ ượ ư c đ a ra
đ
ươ 15/11/15 36 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ơ ở
ạ
Thuật toán Thompson C s qui n p:
ạ
1. V i ớ ε, t o NFA
∈ớ
ạ
2. V i a
∑, t o NFA
ướ
ạ
ả ử
ủ
s N(r) và N(s) là các NFA c a các
B c qui n p: gi RE r và s. Khi đó
ươ 15/11/15 37 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Thuật toán Thompson (Cont’d)
ươ 15/11/15 38 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ể
ộ
ổ
Ví d : RE NFA⇒ ụ ∗ ∗ ∗ Chuy n đ i (0|10 1) 10 thành m t NFA
ươ 15/11/15 39 ễ Nguy n Ph ng Thái Coltech Compiler 2009
⇒
Ví dụ: RE
NFA
ươ 15/11/15 40 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ví dụ: DFA (Cont’d)
ậ
ự
ậ
ở
Thu t toán này đ
ư ớ ậ
ậ ủ
ượ tr ng thái c a DFA t
ế ế c bi ươ ứ ng ng v i t p con các tr ng thái c a NFA
t đ n nh là thu t toán xây d ng t p con b i vì ạ ố ạ
ạ
ổ
ố
ủ n tr ng thái DFA, trong đó n là t ng s tr ng thái NFA
ạ Có t
i đa 2
ươ 15/11/15 41 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Xây dựng tập con: các toán tử được sử dụng
ể
ạ
ừ
Phép toán εclosure(s)
Mô tả ậ T p các tr ng thái NFA có th đi đ n (reachable) t ạ tr ng thái NFA s theo các chuy n
ế ể ε.
ậ
ế ừ ạ
εclosure(T)
tr ng thái NFA
ạ ộ
T p các tr ng thái NFA có th đi đ n t nào đó thu c T theo các chuy n
ể ể ε.
ậ
ể
ạ
ừ ạ
move(T,a)
tr ng
ộ
ớ
T p các tr ng thái NFA mà có chuy n nhãn a t thái NFA nào đó thu c T t
i.
ươ 15/11/15 42 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Thuật toán xây dựng tập con
ạ
ắ ầ ủ
ấ ạ
ứ
ư ượ
G i sọ 0 là tr ng thái b t đ u c a NFA; DFAstates ch a duy nh t tr ng thái ch a đ
c đánh d u
ấ εclosure(s0)
ộ ạ
ượ
ấ
while có m t tr ng thái không đ
c đánh d u T trong DFAstates
do begin
ệ
do begin
đánh d u Tấ ỗ for m i ký hi u vào a U := εclosure(move(T, a)); if U không có trong DFAstates then
ư ộ ạ
ư ượ
Thêm U vào DFAstates nh m t tr ng thái ch a đ
c
đánh d u;ấ
DFATrans[T, a] := U;
end;
end;
ươ 15/11/15 43 ễ Nguy n Ph ng Thái Coltech Compiler 2009
ả ử
ẽ
s (∑, S, T, F, s
ầ 0) là NFA ban đ u. DFA s là:
ạ
t c các tr ng thái có trong DFAstates
ạ
ắ ầ εclosure(s0) ấ ả ậ
ạ
ạ
Xây dựng tập con: Định nghĩa của DFA Gi B ch cái: ∑ ộ ữ Các tr ng thái: t ấ ả ạ Tr ng thái b t đ u: Các tr ng thái ch p nh n: t
ấ ứ
ấ
ậ
ấ
t c các tr ng thái trong ộ ạ DFAstates mà ch a ít nh t m t tr ng thái ch p nh n ủ trong F c a NFA Các chuy n: DFATrans ể
ươ 15/11/15 44 ễ Nguy n Ph ng Thái Coltech Compiler 2009
g m hai nhóm
ồ ạ
ế ế
Thuật toán cực tiểu hóa trạng thái DFA ∏ ả ử ầ s Ban đ u, gi ậ ấ ả t c các tr ng thái k t thúc (1) T p t ạ ậ (2) T p các tr ng thái không k t thúc new = ∏ Kh i t o ∏ ở ạ for m i nhóm G trong ∏ ỗ
new {
ạ
ộ
ệ
ạ
ớ
ọ ạ
ủ
i các tr ng thái trong cùng nhóm c a ∏
new
ượ ạ
ậ
ậ
c t o ra
Chia G thành các nhóm con sao cho hai tr ng thái s và t thu c cùng ế ỉ ế nhóm n u và ch n u v i m i ký hi u vào a các tr ng thái s và t ớ ể có chuy n nhãn a t Thay G trong ∏new b ng t p các t p con đ ằ
}
ươ 15/11/15 45 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Ví dụ (Cont’d): Các trạng thái được gán nhãn lại
ế ấ ả
ế
ả
ể ượ
ạ
ậ
K t qu lý thuy t: t
c nh n d ng
ữ t c các ngôn ng chính qui có th đ b i ở
ấ
ạ
ạ
ộ m t DFA tr ng thái c c ti u mà là duy nh t (theo tên tr ng thái) 15/11/15
ự ể ễ Nguy n Ph
ươ 46 ng Thái Coltech Compiler 2009
ừ ố ừ ị , t
ẫ v , m u
v ng: t
Nội dung Phân tích t ừ ự t REs, FA (DFA, NFA) Nâng cao: REs NFA; NFA DFA; DFA minimal
ậ
state DFA M t s bài t p ộ ố
ươ 15/11/15 47 ễ Nguy n Ph ng Thái Coltech Compiler 2009
A. 4 Phân loại Chomsky
ươ 15/11/15 48 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Phân loại văn phạm của Chomsky
3
1 2
0
ệ ớ ớ
ữ
Chúng ta đang làm vi c v i l p 3: ngôn ng chính qui
ươ 15/11/15 49 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Bài tập
ể
ữ
ứ
ả ư
nh sau (∑ = {0,1}):
t bi u th c chính qui cho các ngôn ng có mô t
ể
ộ ộ
ớ ớ
ệ
ế
ộ
ớ
ấ ả ấ ả ấ ả ấ ả
ướ
ệ
ệ
ỗ
ế Bài 1. Vi ấ ả (a) T t c các xâu có th (b) Không có xâu nào (c) Xâu r ngỗ (d) Xâu 011 (e) Các xâu 0 và 011 ắ ầ (f) T t c các xâu b t đ u v i m t 1 ắ ầ ệ (g) T t c các xâu b t đ u v i m t ký hi u 1 và k t thúc v i m t ký hi u 0 ệ ứ (h) T t c các xâu ch a đúng ba ký hi u 1 ề (i) T t c các xâu mà m i ký hi u 0 đ u có ký hi u 1 đi tr
c và đi sau
ươ 15/11/15 50 ễ Nguy n Ph ng Thái Coltech Compiler 2009
Bài tập
ữ ạ
ữ
ể
ậ
ơ
ị
t k các ôtômát h u h n đ n đ nh (DFA) đ đoán nh n các ngôn ng sau
Bài 2. Thi
ế ế (∑ = {0,1}):
ọ
ấ
ượ
ệ
ở c theo sau b i ký hi u 0.
ế
ẵ
ố ượ
ệ
ể ả
ệ
ẵ
ả ng ký hi u 0 ph i là ch n và s l
ng ký hi u 1 cũng ch n (k c xâu
ệ ủ (a) M i xu t hi n c a xâu con 11 đ ệ ứ (b) Ký hi u th ba (n u có) là 1. ố ượ (c) S l ỗ r ng).
ế ế
ữ ạ
ơ
ị
ừ
ứ
ể
t k các ôtômát h u h n không đ n đ nh (NFA) t
các bi u th c chính
Bài 3. Thi qui sau:
(a) (a|b)* (b) a*|b* (c) a|(b|c)* (d) a(a|b)*b
ươ 15/11/15 51 ễ Nguy n Ph ng Thái Coltech Compiler 2009
