Ch ng 2:ươ
ÔTÔMÁT H U H N VÀ BI U Ữ Ạ Ể
TH C CHÍNH QUYỨ
1
I. Bi u th c chính quy (BTCQ)ể ứ
Đnh nghĩa:ị Cho b ch ộ ữ
là m t BTCQộ
ε là m t BTCQộ
a thì a là m t BTCQộ
, là các BTCQ(+), (.), (*) là các BTCQ
2
Bi u th c chính quy …ể ứ
Quy c:ướ
Đ l c b t các vòng đn, áp d ng các m c u ể ượ ớ ơ ụ ứ ư
tiên v i các toán t theo th t *, ., +ớ ử ứ ự
Toán t “*” đc vi t v trí ch s trên.ử ượ ế ở ị ỉ ố
Toán t ghép ti p (.) có th đc b qua: vi t ử ế ể ượ ỏ ế
β thay vì .β
3
Giá tr c a BTCQị ủ
M t BTCQ trên ộ bi u di n m t ngôn ng trên ể ễ ộ ữ
L()= ; L(ε)= {ε}
L(a)={a} v i ớa
L((+))=L()L()
L(( ))=L().L()
L((*))=(L())*
Ta g i ọngôn ng chính quyữ là m i ngôn ng có th ọ ữ ể
đc ch đnh b i m t bi u th c chính quy. ượ ỉ ị ở ộ ể ứ
4
Bi u th c chính quy …ể ứ
Ví d : ụ={0, 1}
BTCQ Giá trị
00 {00}
(0+1)* {0,1}*
(0+1)*00(0+1)* {x|x{0,1}* và x chứa 2 con 0
liên tiếp}
(1+10)* {x|x {0,1}* x có con 1 ở đầu và
không có hai con 0 liên tiếp}
5