›
›

Giáo trình Lý thuyết ngôn ngữ hình thức và ôtômát - Nguyễn Thanh Bình

pdf 93 trang phuongnguyen 1480
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết ngôn ngữ hình thức và ôtômát - Nguyễn Thanh Bình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_ly_thuyet_ngon_ngu_hinh_thuc_va_otomat_nguyen_tha.pdf

Nội dung text: Giáo trình Lý thuyết ngôn ngữ hình thức và ôtômát - Nguyễn Thanh Bình

  1. Khoa Công ngh Thông tin Trng i hc Bách khoa i hc à Nng GIÊO TRÏNH LÐ THUY&T NGÓN NG( HÏNH TH)C V ÓTÓMÊT Nguy/n Thanh Bình
  2. ,1c l1c 1.1 Gi5i thi u 6 1.2 Khái ni m v: ngôn ng; 6 1.2.1 Bng ch (alphabet) 6 1.2.2 Xâu (String) 7 1.2.3 Các phép toán trên xâu 7 1.2.4 Ngôn ng 7 1.2.5 Các phép toán trên ngôn ng 8 1.3 Khái ni m v: v=n phm 9 1.4 Khái ni m v: ôtômát 11 2.1 Ótômát h;u hn ČBn ČCnh (deterministic finite automata - DFA) 12 2.1.1 Mô t không hình th+c 12 2.1.2 Mô t hình th+c 13 2.1.3 DFA x/ lí xâu nh1 th2 nào 13 2.1.4 Các cách bi4u di6n Č8n gin h8n c9a DFA 14 2.1.5 Hàm d r?ng 14 2.1.6 Ngôn ng Č1@c thAa nhBn b>i DFA 16 2.1.7 Bài tBp 17 2.2 Ótômát h;u hn không ČBn ČCnh (non deterministic finite automata - NFA)17 2.2.1 C r?ng 18 2.2.3 Ngôn ng Č1@c thAa nhBn b>i NFA 19 2.3 SP tBng ČBng gi;a DFA và NFA 20 2.3.1 Xây dFng DFA tA NFA 20 2.3.2 SF t18ng Č18ng gi a NFA và DFA 23 2.3.3 Bài tBp 24 2.4 )ng d1ng 25 2.4.1 NFA cho tìm ki2m tA khóa 25 2.4.2 DFA cho tìm ki2m tA khóa 26 2.4.3 Bài tBp 26 2
  3. 3.1 BiSu thTc chính quy (regular expresssion) 27 3.1.1 C<nh nghDa hình th+c c9a bi4u th+c chính quy 27 3.1.2 C? 1u tiên các phép toán trên bi4u th+c chính quy 28 3.1.3 Các tính chKt ČLi sN c9a bi4u th+c chính quy 28 3.1.4 Bài tBp 29 3.2 BiSu thTc chính quy và ngôn ng; chính quy 29 3.2.1 Bài tBp 33 3.3 )ng d1ng cXa biSu thTc chính quy 33 3.3.1 Phân tích tA vFng (lexical analysis) 33 3.4 V=n phm chính quy 33 3.4.1 VQn phLm tuy2n tính phi và vQn phLm tuy2n tính trái 33 3.4.2 Ngôn ng chính quy và vQn phLm chính quy 34 3.4.3 Bài tBp 36 3.5 Các tính chZt Čóng cXa ngôn ng; chính quy 36 3.5.1 Tính Čóng c9a ngôn ng chính quy d1Si các phép toán tBp h@p 36 3.5.2 Tính Čóng d1Si các phép toán khác 38 3.6 Các thu\t toán liên quan Č^n ngôn ng; chính quy 39 3.7 SP tBng ČBng cXa các ôtômát và cPc tiSu hóa ôtômát 40 3.7.1 SF t18ng Č18ng c9a các trLng thái 40 3.7.2 SF t18ng Č18ng c9a các DFA 41 3.7.3 CFc ti4u hóa DFA 42 3.7.4 Bài tBp 43 3.8 Nh\n bi^t các ngôn ng; không là chính quy 44 3.8.1 C<nh lð —b8m“ cho ngôn ng chính quy 44 3.8.2 Wng dXng Č<nh —b8m“ 45 3.8.3 Bài tBp 46 4.1 V=n phm phi ng; c`nh 47 4.1.1 C<nh nghDa vQn phLm và ngôn ng phi ng cnh 47 4.1.2 DYn xuKt trái nhKt và dYn xuKt phi nhKt 49 4.1.3 Cây dYn xuKt 49 4.1.4 Bài tBp 51 4.2 )ng d1ng cXa v=n phm phi ng; c`nh 52 4.2.1 Mô t ngôn ng lBp trình 52 4.3 SP nh\p nhang trong v=n phm phi ng; c`nh 52 4.3.1 Bài tBp 54 4.4 Dng chubn cXa v=n phm phi ng; c`nh 54 4.4.1 LoLi b[ kí hi\u vô ích 54 4.4.2 LoLi b[ luBt sinh-ε 57 4.4.3 LoLi b[ luBt sinh Č8n v< 59 4.4.4 Gin l1@c vQn phLm phi ng cnh 61 4.4.5 DLng chu_n Chomsky 61 4.4.6 Bài tBp 63 3
  4. R.1 'tômát Čby xucng (PushDown Automata - PDA) 64 5.1.1 Mô t không hình th+c 64 5.1.2 C i trLng thái cuNi 67 5.2.2 Coán nhBn b>i ngQn x2p rbng 68 5.2.3 Chuy4n tA PDA Čoán nhBn b>i ngQn x2p rbng vc PDA Čoán nhBn b>i trLng thái cuNi 69 5.2.4 Chuy4n PDA Čoán nhBn b>i trLng thái cuNi vc PDA Čoán nhBn b>i ngQn x2p rbng 71 5.2.5 Bài tBp 72 5.3 SP tBng ČBng gi;a PDA và v=n phm phi ng; c`nh 72 5.3.1 Chuy4n vQn phLm phi ng cnh thành PDA 72 5.3.2 Chuy4n PDA thành vQn phLm phi ng cnh 73 5.3.3 Bài tBp 76 5.4 Ótômát Čby xucng ČBn ČCnh 76 5.4.1 Bài tBp 77 5.5 Các tính chZt cXa ngôn ng; phi ng; c`nh 77 5.6 Các thu\t toán liên quan Č^n ngôn ng; phi ng; c`nh 79 5.7 Nh\n bi^t các ngôn ng; không phi ng; c`nh 79 5.7.1 Kích th1Sc cây dYn xuKt 80 5.7.2 C i máy Turing 88 6.1.5 Bài tBp 88 6.2 Tính toán bgi máy Turing 88 6.2.1 Bài tBp 89 6.3 Lu\n Č: Church-Turing (Church Turing thesis) 89 6.4 Các kh thu\t xây dPng máy Turing 90 6.4.1 NhS > b? Čicu khi4n h u hLn 90 6.4.2 BQng nhicu rãnh 90 6.4.3 Ch18ng trình con 91 6.5 Các mô hình khác cXa máy Turing 91 6.5.1 Máy Turing có nhicu bQng 91 4
  5. 6.5.2 Máy Turing không Č8n Č<nh 92 Tài li u tham kh`o j j j j j ?< 5
  6. M Ču Vào nh ng nQm 1930, Alain Turing Čã nghiên c+u các máy trAu t1@ng có kh nQng thFc hi\n các tính toán nh1 máy tính ngày nay. Các máy trAu t1@ng này Č1@c ggi là máy Turing. Vào nh ng nQm 1940 và 1950, các máy trAu t1@ng Č8n gin h8n, mà chúng ta ggi là ôtômát hu hn, Čã Č1@c nghiên c+u b>i các nhà khoa hgc. Sau Čó, vào nh ng nQm 1950, nhà ngôn ng hgc Chomsky Čã thFc hi\n các nghiên c+u vc vn phm hình th+c. VQn phLm này có mNi quan h\ chit chj vSi ôtômát và ngày nay vQn phLm là m?t phkn ncn tng c9a vi\c xây dFng m?t sN phkn mcm, Čic bi\t mà các ch18ng trình d<ch. Ótômát là mô hình h u ích cho nhicu phkn mcm quan trgng. Chmng hLn d1Si Čây là m?t sN +ng dXng: • Phkn mcm thi2t k2 và ki4m tra các mLch Či\n t/ sN. • B? phân tích tA vFng c9a m?t ch18ng trình d<ch. • D<ch tA ngôn ng bBc cao sang ngôn ng bBc thKp. • D<ch tA ngôn ng tF nhiên này sang ngôn ng tF nhiên khác (Anh, Pháp, Vi\t, ). • Tìm ki2m tA trong vQn bn. Ba khái ni\m c8 bn c9a môn hgc này là: ngôn ng , vQn phLm và ôtômát sj Č1@c trình bày tA các lSp Č8n gin Č2n các lSp ph+c tLp và mNi quan h\ mKt thi2t gi a chúng. M?t ngôn ng , cho dù là ngôn ng tF nhiên hay ngôn ng lBp trình, thì Čcu Č1@c xem là m?t tBp h@p các câu. Tuy nhiên, tr1Sc khi có Č<nh nghDa chính xác vc ngôn ng , chúng ta sj tìm hi4u m?t sN các quan ni\m hình th+c vc ngôn ng . 1.2.1 B ng ch (alphabet) Bng ch hay còn ggi là b? kí tF là m?t bng h u hLn các kí hi\u (symbol). Bng ch th1rng Č1@c kí hi\u là Σ. Cho các bng ch sau: {a, b, c, , z} : bng ch cái Latin {0, 1, , 9} : bng ch sN thBp phân {0, 1} : bng ch sN nh< phân 6
  7. 1.2.2 Xâu (String) Xâu (tA, chubi) là m?t dãy h u hLn các kí hi\u tA bng ch . Thông th1rng, ta s/ dXng các ch cái th1rng a, b, c, bi4u di6n các kí hi\u thu?c bng ch và các ch cái w, u, v, bi4u di6n các xâu. Cho bng ch Σ = {a, b, c}các xâu abcabc và aabbab thu?c Σ. Xâu rbng là xâu không chúa kí hi\u nào, th1rng Č1@c kí hi\u là ε. 1.2.3 Các phép toán trên xâu k dài (length) xâu c9a m?t xâu w Č1@c kí hi\u là |w|, là sN kí hi\u c9a xâu. K^t nci (concatenation) hai xâu u và v là xâu nhBn Č1@c b`ng cách nNi các kí hi\u c9a xâu v vào cuNi cùng bên phi c9a xâu u, t+c là: u = a1a2 an và v = b1b2 bm thì k2t nNi c9a u và v là xâu uv = a1a2 anb1b2 bm `o (reverse) xâu là xâu nhBn Č1@c b`ng cách vi2t các kí hi\u theo th+ tF ng1@c lLi, nghDa là R w = a1a2 an thì xâu Čo nhBn Č1@c là w = anan-1 a1 L1u ð, εR = ε. Ti:n tc (prefix) và h\u tc (postfix): n2u w = uv thì u Č1@c ggi là ticn tN c9a w và v là hBu tN c9a w. Lly thma (power) xâu: n2u w là m?t xâu thì wn là xâu nhBn Č1@c b`ng cách k2t nNi w vSi chính nó n lkn. wn = ww w (n lkn) L1u ð, w0 = ε vSi mgi w. 1.2.4 Ngôn ng Ngôn ng là m?t tBp h@p các xâu trên bng ch Σ. Ngôn ng th1rng Č1@c kí hi\u là L. * TBp tKt c các xâu trên bng ch Σ, Č1@c kí hi\u là Σ c|ng là m?t ngôn ng . Σ+ là tBp tKt c các xâu trên bng ch Σ loLi trA xâu rbng, nghDa là: + * Σ = Σ - ε ∅ là ngôn ng rbng, t+c là không ch+a bKt k~ kí hi\u nào. {ε} là ngôn ng ch• ch+a xâu rbng. L1u ð, ∅ khác vSi {ε}. Cho Σ = {0, 1} L = {(010)n | n >0} là m?t ngôn ng trên Σ. Còn Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, } L1 = {a, ab, abb, bba, bbb} là ngôn ng hu hn trên {a, b}. n L2 = {(ab) | n > 0} là ngôn ng vô hn trên {a, b}. 7
  8. 1.2.5 Các phép toán trên ngôn ng Ngôn ng là m?t tBp h@p, do Čó tKt c các phép toán trên tBp h@p Čcu có th4 áp dXng cho ngôn ng . Ngoài ra ngôn ng còn có m?t sN phép toán quan trgng khác. Cho các ngôn ng L, L1 và L2 trên bng ch Σ. L1 ∪ L2 = {w | w ∈ L1 hoic w ∈ L2} L1 ∩ L2 = {w | w ∈ L1 và w ∈ L2} L1 œ L2 = {w | w ∈ L1 và w ∉ L2} * L = {w | w ∉ L} hoic L = Σ - L L1L2 = = {w | w = uv, u ∈ L1 và v ∈ L2} Cho L1 = {0, 1} và L2 = {00, 11} L1L2 = {000, 011, 100, 111} LR = {w | wR ∈ L} Ln = LL L (n lkn) Hay L0 = {ε}, Li = LLi-1 L* = L0 ∪ L1 ∪ ∪ Ln L+ = L1 ∪ L2 ∪ ∪ Ln L1u ð: L* = L+ ∪ {ε} L+ = LL* = L*L Cho L = {a, b} L2 = {aa, ab, bb, ba} L3 = {aaaa, aaab, aabb, aaba, abaa, abab, abbb, abba, bbaa, bbab, bbbb, bbba, baaa, baab, babb, baba} 8
  9. Khi nghiên c+u ngôn ng ckn m?t c8 ch2 mô t ngôn ng Čó là vn phm (grammar). M?t cách không hình th+c, vQn phLm là các quy t‚c sinh câu Čúng. CNi vSi ngôn ng tF nhiên, vQn phLm là h\ thNng ng pháp. CNi vSi ngôn ng lBp trình, vQn phLm là các quy t‚c cú pháp vi2t ch18ng trình. C i vQn phLm sau: → → | → | → | VQn phLm trên sinh ra các câu Čúng sau: - Con h„ Qn con bò Čen. - Hgc sinh nói chuy\n nhicu. Cnh nghna 1.1. VQn phLm G Č1@c Č i Čku; - R là tBp các quy t‚c (rule) hoic các sn xuKt/luBt sinh (production), các luBt sinh có dLng: α → β trong Čó α ∈ (N ∪ Σ)+ có ch+a ít nhKt m?t bi2n, β∈ (N ∪ Σ)*. • Các bi2n/kí hi\u không k2t thúc thu?c N Č1@c bi4u di6n b>i các kí tF: A, B, C, • Các kí hi\u k2t thúc thu?c Σ Č1@c bi4u di6n b>i các kí tF: a, b, c, • Các xâu ch• gam các kí hi\u k2t thúc Č1@c bi4u di6n b>i các kí tF: w, u, v, • Các xâu gam các kí hi\u k2t thúc và các kí hi\u không k2t thúc Č1@c bi4u di6n b>i các kí tF: α, β, γ, - Cho vQn phLm G1 = ({S, A, B}, {a, b}, R, S), trong Čó R gam các luBt sinh sau: S → aS | bA, A → Bb, B → bB | aA | ε - Cho vQn phLm G2 = ({S}, {0, 1}, {S → 0S1 | ε}, S) TA vQn phLm Č4 sinh ra câu, chúng ta có khái ni\m dYn xuKt. Cnh nghna 1.2. 9
  10. Cho vQn phLm G = (N, Σ, R, S) và hai xâu u ∈ (N ∪ Σ)+ và v ∈ (N ∪ Σ)* • Dn xut trc tip (hay dYn xuKt m?t b1Sc): ta nói u dYn xuKt trFc ti2p ra v, kí hi\u u  v , n2u và ch• n2u: G u = xαy v = xβy α → β ∈ R • Dn xut gián tip (hay dYn xuKt nhicu b1Sc): ta nói u dYn xuKt gián ti2p ra v, kí * hi\u u  v , n2u và ch• n2u: G     u w1 w2 v G G G G Cnh nghna 1.3. Cho G = (N, Σ, R, S), câu w ∈Σ* do vQn phLm G sinh ra n2u và ch• n2u: * S  w G     NghDa là phi tan tLi: S w1 w2 w , các w1, w2, Č1@c ggi là các dng câu c9a G G G G dYn xuKt. Cnh nghna 1.4. Cho vQn phLm G = (N, Σ, R, S), ngôn ng L do vQn phLm G sinh ra là: * L(G) = {w ∈ Σ* | S  w } G Cho vQn phLm G1 = ({S}, {0, 1}, {S → 0S1 | ε}, S) thì S  0S1  00S11  000S111  000111 là m?t dYn xuKt ra câu. n n Ngôn ng t18ng +ng c9a vQn phLm G1 là: L(G1) = {0 1 | n ≥ 0}. Cho vQn phLm G2 = ({S, A}, {a, b}, {S → aA, A → aA, A → b}, S) n Ngôn ng t18ng +ng c9a vQn phLm G2 là: L(G2) = {a b | n > 0}. Theo Chomsky có 4 loLi vQn phLm theo các dLng c9a luBt sinh nh1 sau: 1. N2u các luBt sinh Čcu có dLng A → a hoic A → aB vSi A, B ∈ N, a ∈ Σ thì vQn phLm Č1@c ggi là vn phm chính quy hay vQn phLm loLi 3. 2. N2u các luBt sinh có dLng A → α, A ∈ N, α ∈ (N ∪ Σ)* thì vQn phLm Č1@c ggi là vn phm phi ng c"nh hay vQn phLm loLi 2. 3. N2u các luBt sinh có dLng α → β, α ∈ (N ∪ Σ)+, β ∈ (N ∪ Σ)* th[a mãn |α| ≤ |β| thì vQn phLm Č1@c ggi là vn phm c"m ng c"nh hay vQn phLm loLi 1. 4. N2u không có hLn ch2 gì trên các luBt sinh thì vQn phLm Č1@c ggi là vn phm ng cu (t do) hay vQn phLm loLi 0. 10
  11. L1u ð r`ng, vQn phLm loLi 3 là tBp con c9a vQn phLm loLi 2, vQn phLm loLi 2 là tBp con c9a vQn phLm loLi 1, và vQn phLm loLi 1 là tBp con c9a vQn phLm loLi 0. Có rKt nhicu h\ thNng có th4 Č1@c xem tLi mbi thri Či4m thì > trong m?t trLng thái (state) c9a m?t tBp h@p h u hLn các trLng thái. MXc Čích c9a trLng thái là ghi nhS lLi m?t phkn c9a l trLng thái b't, ng1ri s/ dXng Kn nút thì nó sj chuy4n sang trLng thái t(t, ng1@c lLi khi thi2t b trong trLng thái t(t ng1ri s/ dXng Kn nút thì nó chuy4n sang trLng thái b't. Mô hình ôtômát h u hLn cho m?t chuy4n mLch c9a thi2t b< Č1@c mô t trong hình vj 1.1. n nút T(t B't n nút Hình 1.1. Mô hình ôtômát hu hn mô t" thit b. chuy/n mch Ótômát trên mô t hai trLng thái b't và t(t c9a thi2t b<, khi có sF tác Č?ng tA bên ngoài —n nút“ thì nó sj chuy4n tA trLng thái này sang trLng thái khác. Ótômát mô t m?t phkn c9a b? phân tích tA vFng. Hình vj 1.2 mô t ôtômát h u hLn nhBn bi2t tA khóa begin. b e g i n b be beg begi begin Hình 1.2 Mô hình ôtônát hu hn Čoán nh'n t4 khóa begin Mbi trLng thái c9a ôtômát bi4u di6n phkn xâu Čã Č1@c nhBn bi2t c9a tA khóa begin. Quá trình nhBn bi2t b‚t Čku tA xâu rbng, cho Č2n khi tA begin Č1@c nhìn thKy thì trLng thái cuNi cho phép Čoán nhBn tA khóa. 11
  12. )t'm t hu h+n Ch18ng này sj giSi thi\u lSp ngôn ng , Č1@c ggi là —ngôn ng chính quy“. LSp ngôn ng này Č1@c mô t b>i ôtômát h u hLn. LSp ôtômát h u hLn Č1@c chia làm hai loLi: ôtômát h u hLn Č8n Č trong m?t trLng thái nhKt Č trong nhicu trLng thái khác nhau. 2.1.1 Mô t không hình th.c Ótômát h u hLn là m?t cái —máy“ Čoán nhBn xâu. Nó bao gam các b? phBn sau: - m?t bng vào Č1@c chia thành ô, dùng Č4 ghi xâu vào, mbi kí hi\u c9a xâu vào thu?c bng ch Σ Č1@c ghi trên m?t ô; - m?t Č:u Č;c, mbi thri Či4m Čgc (tr[) Č2n m?t ô trên bQng vào; - m?t b n Č.nh HoLt Č?ng c9a ôtômát Č1@c thFc hi\n nh1 sau: Ótômát hoLt Č?ng theo tAng b1Sc. Mbi b1Sc nh1 sau: tùy theo trLng thái hi\n thri c9a b? Čicu khi4n và kí hi\u mà Čku Čgc Čang Čgc, mà ôtômát chuy4n sang m?t trLng thái mSi, Čang thri Čku Čgc d i m?t hàm, Č1@c ggi là hàm d<ch chuy4n (transition function) nh1 sau: δ : Q x Σ → Q Trong Q, có m?t trng thái Č:u, th1rng kí hi\u q0 và m?t tBp h@p các trng thái cu?i/thAa nhBn, th1rng kí hi\u F (F ⊆ Q). Ta nói ôtômát th4a nh'n xâu vào w n2u sau khi xuKt phát tA trLng thái Čku q0 và Čku Čgc ch• vào kí tF bên trái nhKt c9a xâu w, sau m?t sN b1Sc d<ch chuy4n h u hLn, ôtômát Čgc xong xâu w và r8i vào m?t trong các trLng thái cuNi thu?c F. 12
  13. TBp h@p tKt c các xâu Čoán nhBn b>i ôtômát h@p thành ngôn ng Č1@c thAa nhBn b>i ôtômát Čó. 2.1.2 Mô t hình th.c Cnh nghna 2.1. M?t tômát hu hn Č>n Č.nh (DFA) Č1@c Č trLng thái q và Čgc kí hi\u a thì nó sj chuy4n sang trLng thái q‘. - q0 ∈ Q là trLng thái Čku. - F ⊆ Q là tBp các trLng thái thAa nhBn hay trLng thái cuNi. 2.1.3 DFA x2 lí xâu nh4 th5 nào Gi s/ w = a0a1 an là xâu vào. DFA sj b‚t Čku vSi trLng thái q0, nó sj thFc hi\n d trLng thái q1 và kí tF ti2p theo sj Čgc là a2, nó thFc hi\n d trLng thái này, DFA có th4 ti2p tXc Čgc bKt k~ kí hi\u nào. Nh1 th2, δ(q2, 0) = δ(q2, 1) = q2. Tr1rng h@p (2) sj t18ng +ng vSi trLng thái Čku q0, khi > trLng thái này DFA có th4 ti2p tXc Čgc kí tF cho Č2n khi gip kí tF 0 thì chuy4n sang trLng thái khác. Nh1 th2, δ(q0, 1) = q0, δ(q0, 0) = q1. Tr1rng h@p (3) sj t18ng +ng vSi trLng thái q1, khi Čã Čgc tr1Sc Čó ít nhKt m?t kí tF 0, nh1ng ch1a bao gir Čgc xâu 01. ‰ trLng thái q1 thì DFA có th4 ti2p tXc Čgc kí tF 0 cho Č2n khi gip kí tF 1, thì chuy4n sang trLng thái thAa nhBn q2. Nh1 th2, δ(q1, 0) = q1, δ(q1, 1) = q2. 13
  14. VBy, cuNi cùng chúng ta có DFA nh1 sau: M = ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) vSi δ Č1@c xây dFng nh1 trên. 2.1.4 Các cách bi7u di9n Č:n gi n h:n c;a DFA Cách mô t DFA b`ng b? nQm nh1 trên là t18ng ČNi khó hi4u và ít trFc quan. Có hai cách mô t Č8n gin h8n m?t DFA là: bi/u Č@ d.ch chuy/n (transition diagram) và b"ng d.ch chuy/n (transition table). M?t bi4u Ča d i hai vòng tròn. 5. Các trLng thái không thu?c F là các nút Č1@c bi4u di6n b>i ch• m?t vòng tròn. Dùng bi4u Ča d Čây là d i dKu ”→‘, các trLng thái cuNi sj Č1@c Čánh dKu b>i các dKu ”*‘. Bng d i m?t DFA, chúng ta sj Č<nh nghDa hàm d.ch chuy/n mE r<ng (extended transition function). 14
  15. Hàm d r?ng, kí hi\u là δ*, sj nhBn hai tham sN là trLng thái q và xâu w và tr vc trLng thái p. NghDa là, DFA Čang > trLng thái q, sau khi x/ lð xâu w thì DFA ČLt Č2n trLng thái p. Cnh nghna 2.2. Hàm d r?ng Č1@c Č lLi trLng thái Čó. 2. δ*(q, w) = δ(δ*(q, x), a), vSi w = xa, x∈Σ* và a∈Σ. Xây dFng DFA thAa nhBn ngôn ng : L = {w | w ch• ch+a các kí hi\u 0, 1 và luôn k2t thúc b>i kí hi\u 1} DFA phi phân bi\t hai kh nQng: (1) khi nó Čgc kí hi\u 1, thì ngay sau Čó có th4 k2t thúc; (2) khi nó Čgc kí hi\u 0 thì ngay sau Čó không Č1@c k2t thúc, mà phi Čgc ti2p các kí hi\u khác cho Č2n khi gip kí hi\u 1. Nh1 th2, DFA sj có ít nhKt hai trLng thái t18ng +ng vSi hai kh nQng trên. Ta xây dFng DFA nh1 sau: M = ({q0, q1}, {0, 1}, δ, q0, {q1}) Trong Čó, hàm δ nh1 sau: 0 1 1 q0 q1 0 )* h 2.2. DFA cho ví dD 2.4 Hay chúng ta có th4 bi4u di6n hàm δ b>i bng d r?ng Č4 Čoán nhBn xâu w=101101 c9a ngôn ng L. * δ (q0, ε) = q0 * * δ (q0, 1) = δ(δ (q0, ε), 1) = δ(q0, 1) = q1 * * δ (q0, 10) = δ(δ (q0, 1), 0) = δ(q1, 0) = q0 * * δ (q0, 101) = δ(δ (q0, 10), 1) = δ(q0, 1) = q1 * * δ (q0, 1011) = δ(δ (q0, 101), 1) = δ(q1, 1) = q1 * * δ (q0, 10110) = δ(δ (q0, 1011), 0) = δ(q1, 0) = q0 * * δ (q0, 101101) = δ(δ (q0, 10110), 1) = δ(q0, 1) = q1 Nh1 th2, xâu vào w = 101101 Č1@c thAa nhBn b>i DFA. 15
  16. Chúng ta có th4 bi4u di6n quá trình Čoán nhBn Č8n gin h8n nh1 sau: q0101101  q101101  q01101  q1101  q101  q01  q1 ∈ F. Nh'n xét: CNi vSi m?t xâu vào w, DFA ch• cho m?t quá trình Čoán nhBn duy nhKt. 2.1.6 Ngôn ng Č4Ac thBa nhCn bi DFA Cnh nghna 2.3. Cho DFA M = (Q, Σ, δ, q0, F), ngôn ng Č1@c thAa nhBn b>i M, Č1@c kí hi\u là L(M), Č1@c Č i m?t ôtômát h u hLn Č8n Č i xâu aa. a, b a a q0 q2 q3 b b q1 a, b Hình 2.3. DFA cho ví dD 2.5 Chúng ta có th4 d6 dàng nhBn thKy r`ng q1 là m?t trLng thái Čic bi\t, n2u ôtômát ČLt Č2n trLng thái này thì sj không bao gir thoát ra Č1@c. Ch+ng minh r`ng ngôn ng L = { abanbm | m,n >0 }là ngôn ng chính qui. C4 ch+ng minh m?t ngôn ng là chính qui, ta ch• ra r`ng tan tLi DFA thAa nhBn ngôn ng Čó. ThBt vBy L Č1@c thAa nhBn b>i DFA sau: a b a b q1 q2 q3 q0 q4 a b a b b a a, b q5 Hình 2.4. DFA th4a nh'n L = { abanbm | m,n >0 } Nh'n xét: CNi vSi m?t DFA M = (Q, Σ, δ, q0, F), +ng vSi m?t trLng thái bKt k~ q ∈ Q và m?t kí hi\u bKt k~ a ∈ Σ, thì hàm d<ch chuy4n δ phi cho m?t k2t qu xác Č<nh, t+c là m?t trLng thái và ch• m?t trLng thái p ∈ Q. 16
  17. 2.1.7 Bài tCp 1. Hãy xác Č i 00. c. TBp các xâu ch+a ba kí hi\u 0 liên ti2p nhau. d. TBp các xâu b‚t Čku hoic k2t thúc (hoic c hai) b>i 01. 2. Ch+ng minh các ngôn ng sau là chính qui: a. L1 = {abnabm | n,m ≥ 0}. b. L2 = {w ∈ {0, 1} | w không ch+a xâu con 11 nào c} 3. Mô t m?t cách không hình th+c ngôn ng Č1@c thAa nhBn b>i DFA sau: δ 0 1 → q0 q1 q0 * q1 q2 q0 q2 q2 q2 M?t ôtômát h u hLn không Č8n Č trong nhicu trLng thái khác nhau > tLi m?t thri Či4m. C|ng nh1 DFA, m?t NFA có m?t tBp h@p h u hLn các trLng thái, trong Čó có m?t trLng thái Čku và tBp các trLng thái thAa nhBn, và m?t tBp h u hLn các kí hi\u vào (bng ch vào). NFA c|ng có m?t hàm d n Č.nh (NFA) Č1@c Č<nh nghDa nh1 là m?t b? nQm: M = (Q, Σ, δ, q0, F) Trong Čó: - Q là tBp h u hLn các trLng thái, Q = {q0, q1, , qn}. - Σ là bng ch vào. - q0 ∈ Q là trLng thái Čku. - F ⊆ Q là tBp các trLng thái thAa nhBn hay trLng thái cuNi. - hàm d<ch chuy4n δ : Q x {Σ ∪ {ε}} → tBp con c9a Q. Nh1 th2, gi a NFA và DFA có hai sF khác bi\t c8 bn là: • giá tr< tr vc c9a hàm d<ch chuy4n δ: DFA ch• tr vc Čúng m?t trLng thái thu?c tBp Q, trong khi NFA tr vc m?t tBp các trLng thái là tBp con c9a Q. 17
  18. • m?t NFA có th4 có d i bi4u Ča d i kí hi\u 0 và k2t thúc b>i kí hi\u 1. NFA Č1@c xây dFng trong hình vj 2.5. 0 q1 1 q0 q2 0, 1 )* h vS 2.5. NFA cho ví dD 2.7 Gi s/ xâu vào w = 0101101, quá trình Čoán nhBn xâu w là nh1 sau: q00101101  q1101101  q101101  q11101  q1101  q101  q11  q2 ∈ F. Tuy nhiên, chúng ta có th4 d6 dàng nhBn thKy r`ng, quá trình Čoán nhBn trên ch• là m?t trong nh ng quá trình Čoán nhBn. Các quá trình Čoán nhBn khác thì không th4 thAa nhBn xâu vào. Nh'n xét: CNi vSi m?t xâu vào w, NFA có th4 có nhicu quá trình Čoán nhBn khác nhau, trong khi DFA thì ch• có m?t quá trình Čoán nhBn. NFA trên có th4 bi4u di6n dLng bng chuy4n d m?t trLng thái nào Čó, Čgc kí hi\u vào, không tan tLi d r?ng, kí hi\u δ*, khi NFA > m?t trLng thái q nào Čó, Čgc m?t xâu w tr vc tBp h@p các trLng thái. 18
  19. Cnh nghna 2.6. Hàm d r?ng Č1@c Č lLi trLng thái Čó. * * 2. VSi w = xa, x∈Σ và a∈Σ, gi s/ δ (q, x) = {p1, p2, , pk} và 5 δ = δ* 8 ( pi ,a) {r1 ,r2 , , rn } thì (q, w) = {r1, r2, , rn}. i=1 LUu ð: M?t kí hi\u a ∈Σ có th4 Č1@c xem là m?t xâu ε*aε*. NghDa là, ta có: δ (q, a) = δ * (q, ε *aε * ) * Cho NFA trong hình vj d1Si Čây, tính δ (q0, a). ε a q1 ε q0 q2 Hình vS 2.7. NFA cho ví dD 2.9 * Ta có: δ (q0, a) = {q0, q1, q2}. S/ dXng hàm d r?ng trong hình vj 2.5 Č4 x/ lð xâu w = 0101101. Các b1Sc Čoán nhBn nh1 sau: * 1. δ (q0, ε) = {q0} * 2. δ (q0, 0) = δ(q0, 0) = {q1} * 3. δ (q0, 01) = δ(q1, 1) = {q1, q2} * 4. δ (q0, 010) = δ(q1, 0) ∪ δ(q2, 0) = {q1} ∪ ∅ = {q1} * 5. δ (q0, 0101) = δ(q1, 1) = {q1, q2} * 6. δ (q0, 0101) = δ(q1, 1) ∪ δ(q2, 1) = {q1, q2} ∪ ∅ = {q1, q2} * 7. δ (q0, 01011) = δ(q1, 1) ∪ δ(q2, 1) = {q1, q2} ∪ ∅ = {q1, q2} * 8. δ (q0, 010110) = δ(q1, 0) ∪ δ(q2, 0) = {q1} ∪ ∅ = {q1} * 9. δ (q0, 0101101) = δ(q1, 1) = {q1, q2} 2.2.3 Ngôn ng Č4Ac thBa nhCn bi NFA Cnh nghna 2.7. Cho NFA M = (Q, Σ, δ, q0, F), ngôn ng Č1@c thAa nhBn b>i M, Č1@c kí hi\u là L(M), Č1@c Č i ôtômát trong hình vj d1Si Čây: 19
  20. 0 q1 1 q0 q2 0, 1 )* h vS 2.8. NFA cho ví dD 2.11 Ngôn ng L = {w ∉{0, 1} | w k2t thúc b>i xâu 01}. Chúng ta nhBn thKy r`ng Č hàm d i 01. B>i vì tBp các trLng thái c9a N là {q0, q1, q2}, sN tBp h@p các tBp con các trLng thái c9a N là 23. Nh1 th2, chúng ta có th4 xây dFng bng d i p0, {q1} Č1@c thay b>i p1, Ta có bng d<ch chuy4n nh1 sau: 20
  21. δ 0 1 p7 p7 p7 → p0 p3 p0 p1 p7 p2 * p2 p7 p7 p3 p3 p4 * p4 p3 p0 * p5 p7 p2 * p6 p3 p4 Trên bng d<ch chuy4n, chúng ta có th4 nhBn thKy tA trLng thái Čku p0 chúng ta ch• có th4 ČLt Č2n các trLng thái p0, p3 và p4, nQm trLng thái còn lLi là các trLng thái không ČLt Č2n Č1@c. Nh1 th2 có th4 loLi b[ các trLng thái này. Bng d<ch chuy4n ch• còn: δ 0 1 → p0 p3 p0 p3 p3 p4 * p4 p3 p0 Hay bi4u di6n dLng bi4u Ča trong hình vj 2.9. 1 0 0 1 p3 p0 p4 0 1 )* h vS 2.9. Bi/u Č@ d.ch chuy/n cZa DFA ví dD 2.11 Tuy nhiên, chúng ta có th4 nhBn thKy r`ng cách xây dFng DFA tA NFA nh1 trên là mKt nhicu thri gian, do phi tính các d<ch chuy4n cho tKt c (2n) các tBp con c9a các trLng thái c9a NFA. C4 thFc hi\n nhanh h8n, chúng ta có thuBt toán d1Si Čây. ThuBt toán chuy4n NFA thành DFA: Vào: NFA N = (QN, Σ, δN, q0, FN) Ra: DFA D = (QD, Σ, δD, {q0}, FD) Begin QD = {{q0}} δD = ∅ repeat LKy qd ∈ QD for each a ∈ Σ begin 21
  22. δ ( ) = δ = Tính D qd , a 8 N (qn , a) pd qn trong qd QD = QD ∪ {pd} δD = δD ∪ {δD(qd, a) = pd} end until H2t qd ∈ QD ch1a lKy FD = {qd ∈ QD | qd ∩ FN ≠ ∅} End. Xây dFng DFA D tA NFA N trong hình vj 2.7. theo thuBt toán trên. Ban Čku, QD ch• gam {q0}. δD({q0}, 0) = {q0, q1} δ D({q0}, 1) = {q0} δ D({q0, q1}, 0) = δN({q0}, 0) ∪ δ N({q1}, 0) ={q0, q1} δ D({q0, q1}, 1) = δ N({q0}, 1) ∪ δ N({q1}, 1) = {q0, q2} δ D({q0, q2}, 0) = δ N({q0}, 0) ∪ δ N({q0}, 0) = {q0, q1} δ D({q0, q2}, 1) = δ N({q0}, 1) ∪ δ N({q0}, 1) = {q0} QD = {{q0}, {q0, q1}, {q0, q2}} FD = {{q0, q2}} So vSi cách xây dFng DFA trong ví dX 2.10, ta nhBn thKy thuBt toán này cho phép thFc hi\n nhanh h8n, Č8n gin h8n. Xây dFng DFA cho NFA trong hình vj sau: q0 0 q1 0, 1 Hình vS 2.10. DFA cho ví dD 2.14 δD({q0}, 0) = {q1} δ D({q0}, 1) = ∅ δD({q1}, 0) = {q1} δ D({q1}, 1) = {q1} δD(∅, 0) = ∅ δ D(∅, 1) = ∅ VBy chúng ta có DFA nh1 sau: 22
  23. q0 0 q1 0, 1 1 ∅ 0, 1 )* h vS 2.11. DFA cho ví dD 2.14 2.3.2 SG t4:ng Č4:ng gia NFA và DFA Nh1 th2, chúng ta vAa ch• ra cách xây dFng DFA tA NFA, tuy nhiên chúng ta ckn phi ch+ng minh r`ng DFA Č1@c xây dFng phi thAa nhBn cùng m?t ngôn ng vSi DFA. ThBt vây, chúng ta có Č i vì N thAa nhBn w): q0a1a2 an  q1a2 an   qn-1an  qn, vSi qn ∈ FN. C|ng vSi xâu w trong D, chúng ta có dYn xuKt: p0a1a2 an  p1a2 an   pn-1an  pn VKn Čc là chúng ta ckn ch+ng minh r`ng pn ∈ FD. Chúng ta sj ch+ng minh b`ng quy nLp r`ng: vSi ∀i, 0 ≤ i ≤ n, qi ∈ pi. (*) - i = 0, ta có qi ∈ pi = {q0} theo thuBt toán trên. - Gi s/ (*) Čúng vSi i < n, t+c là qi ∈ pi, ckn ch+ng minh (*) Čúng vSi i + 1. Theo gi thi2t ban Čku, ta có : δD(pi, ai+1) = pi+1 và δN(qi, ai+1) ch+a qi+1 Vì qi ∈ pi, nên δD(pi, ai+1) ch+a δN(qi, ai+1). VBy, ta có δD(pi, ai+1) ch+a qi+1 hay pi+1 ch+a qi+1. Nói cách khác, qi+1 ∈ pi+1, (*) Čúng vSi i + 1. 23
  24. TA (*) suy ra qn ∈ pn, mà qn ∈ FN theo gi thi2t ban Čku, h8n n a thao cách xây dFng FD trong thuBt toán trên thì pn ∈ FD. VBy w ∈ L(D). Ch_ng minh nu w ∈ L(D) thì w ∈ L(N): * B>i vì w ∈ L(D) nên ta gi s/ có d r?ng trong D nh1 sau: δ D(p0, w) = p vSi p ∈ FD. Chúng ta sj ch+ng minh b`ng quy nLp theo Č? dài c9a l = |w| r`ng: ∀q ∈ p, tan tLi d<ch * chuy4n trong N: δ N(q0, w) = q. ( ) * - VSi l = 0, t+c là w = ε, thì ta có δ D(p0, ε) = p0, mà theo thuBt toán trên thì p0 = {q0}, vBy * * * δ D(p0, ε) = δ D({q0}, ε) = δ N(q0, ε) = q0. - Gi s/ ( ) Čúng vSi l œ1, ckn ch+ng minh ( ) c|ng Čúng vSi l. Gi s/ w = xa, x ∈ Σ*, a ∈ Σ. * Theo gi thi2t quy nLp (Čúng vSi l-1), ta có: δ D(p0, x) = p thì ∀q ∈ p, tan tLi d<ch chuy4n * trong N: δ N(q0, x) = q. * H8n n a, theo gi thi2t ban Čku, w ∈ L(D), t+c là δ D(p0, w) = pf, vSi pf ∈ FD, hay * * δ D(p0, w) = δ D(p0, xa) = δD(p, a) = pf. NghDa là δD(p, a) = pf. Xét qf bKt k~ thu?c pf, ta có δD(p, a) = pf mà theo cách xây dFng δD trong thuBt toán trên (t+c là p là m?t tBp h@p các trLng thái trong N và δD là tBp h@p các δN) thì tan tLi δN(qf, a) ch+a qf vSi qf ∈ pf. * H8n n a, theo gi thi2t quy nLp thì: δ N(q0, x) = q vSi ∀q ∈ p. * * VBy δ N(q0, w) = δ N(q0, xa) = δN(q, a) = qf, vSi ∀qf ∈ pf. Nh1 th2, ( ) c|ng Čúng vSi l+1. Quay lLi vSi gi thi2t w ∈ L(D) ckn ch+ng minh w ∈ L(N). * * Theo ( ) ta có: δ D(p0, w) = pf vSi pf ∈ FD thì tan tLi δ N(q0, w) = q vSi ∀q ∈ pf. Do q ∈ pf nên ∃qf ∈ pf sao cho qf ∈ FN theo thuBt toán xây dFng DFA. * VBy ta có: δ N(q0, w) = qf vSi qf ∈ FN, nghDa là w ∈ L(N). Nh1 th2, chúng ta Čã ch+ng minh Č1@c: L(N) = L(D). 2.3.3 Bài tCp Chuy4n các NFA sau thành DFA: 1. δ 0 1 → p {p, q} {p} q {r} {r} r {s} ∅ * s {s} {s} 2. δ 0 1 → p {q, s} {q} * q {r} {q, r} r {s} {p} 24
  25. * s ∅ {p} 3. δ 0 1 → p {p, q} {p} q {r, s} {t} r {p, r} {t} * s ∅ ∅ * t ∅ ∅ 4. δ ε a b c → p {q, r} ∅ {q} {r} q ∅ {p} {r} {p, q} * r ∅ ∅ ∅ ∅ Chúng ta sj nhBn thKy r`ng ôtômát h u hLn Č1@c +ng dXng rKt hi\u qu trong tìm ki2m vQn bn: chmng hLn nh1 tìm ki2m thông tin trên web, tìm ki2m trong tA Či4n, 2.4.1 NFA cho tìm ki5m tB khóa Gi s/ chúng ta có m?t tBp h@p các tA, ggi là các t4 khóa, chúng ta muNn tìm sF xuKt hi\n c9a các tA Čó. Trong tr1rng h@p này, chúng ta sj xây dFng m?t NFA nhBn bi2t m?t tA khóa khi nó ČLt Č2n m?t trong các trLng thái thAa nhBn. TLi m?t thri Či4m NFA sj Čgc m?t kí tF c9a vQn bn. NFA nh1 th2 Č1@c xây dFng nh1 sau: 1. M?t trLng thái b‚t Čku q0 thFc hi\n d trên, chúng ta xây dFng NFA nh1 sau: f 3 a 4 n 1 d 5 f 6 a 7 Hình vS 2.12. DFA nh'n bit các t4 và dfa 25
  26. Chúng ta có nhBn xét, quá trình NFA nhBn bi2t thFc sF ch1a thBt hi\u qu vì tA trLng thái Čku NFA phi —Čoán“ khi nào là b‚t Čku m?t tA khóa. N2u quá trình dF Čoán sai, thì phi quay lui. Xây dFng NFA nhBn bi2t các sN thBp phân bao gam: 1. M?t dKu + hoic -, hoic có th4 không có dKu; 2. M?t dãy các ch sN; 3. M?t dKu chKm; 4. M?t dãy các ch sN. Dãy các ch sN này hoic dãy các ch sN (2) có th4 rbng, tuy nhiên ít nhKt m?t trong hai dãy các ch sN này phi khác rbng. N = ({q0, q1, , q5}, {., +, -, 0, 1, 2, , 9}, δ, q0, {q5}) VSi δ Č1@c Č<nh nghDa nh1 sau: 0, 1, 9 0, 1, 9 q2 . 0, 1, 9 ε, +, - q0 q1 q4 q5 ε . 0, 1, 9 q3 )* h vS 2.13. DFA nh'n bit các các s? th'p phân Hay chúng ta có th4 bi4u di6n dLng bng d<ch chuy4n nh1 sau: δ ε +, - . 0, 1, , 9 → q0 {q1} {q1} ∅ ∅ q1 ∅ ∅ {q2} {q1, q3} q2 ∅ ∅ ∅ {q4} q3 ∅ ∅ {q4} ∅ q4 {q5} ∅ ∅ {q4} * q5 ∅ ∅ ∅ ∅ 2.4.2 DFA cho tìm ki5m tB khóa VSi cách xây dFng NFA nh1 trên, chúng ta có th4 s/ dXng thuBt Čoán chuy4n Č„i NFA thành DFA Č4 xây dFng DFA t18ng Č18ng. Xây dFng DFA tA NFA trong ví dX 2.13. Ví dX này Č1@c xem nh1 bài tBp. CNi vSi DFA, chúng ta nhBn thKy r`ng quá trình Čoán nhBn hi\u qu h8n vì không có sF quay lui. 2.4.3 Bài tCp 1. Xây dFng các NFA Čoán nhBn các tA sau: a) 101, 110 vSi bng ch là {0, 1} b) ab, bc, ca vSi bng ch là {a, b, c} 2. Chuy4n các NFA trên vc DFA. 26
  27. Bi7u th.c chính quy và vKn ph+m chính quy Chúng ta Čã tìm hi4u ôtômát h u hLn là c8 ch2 mô t ngôn ng chính quy. Ngoài ra, còn có nh ng cách khác Č4 mô t ngôn ng chính quy mà chúng ta sj tìm hi4u trong ch18ng này Čó là: bi4u th+c chính quy và vQn phLm chính quy. Chúng ta sj thKy r`ng bi4u th+c chính quy cho phép Č i ôtômát h u hLn: ngôn ng chính quy. Tuy nhiên, bi4u th+c chính quy thFc hi\n Čicu mà ôtômát không làm Č1@c là: mô t m?t cách t1rng minh các xâu thu?c ngôn ng . Bi4u th+c chính quy Č1@c s/ dXng nh1 là ngôn ng vào c9a m?t sN h\ thNng, chmng hLn: • Câu l\nh grep trong h\ Čicu hành Unix, Linux. Câu l\nh này s/ dXng m?t tham sN Čku vào có dLng bi4u th+c chính quy Č4 tìm ki2m các xâu ch trong các t\p tin vQn bn. • Câu l\nh sed trong h\ Čicu hành Unix, Linux. Câu l\nh này c|ng s/ dXng m?t tham sN Čku vào có dLng bi4u th+c chính quy Č4 x/ lð (s/a Č„i, thay th2, ) trên t\p vQn bn. • B? phân tích tA vFng Lex hay Flex, Č1@c s/ dXng Č4 phân tích tA vFng trong quá trình d<ch m?t ch18ng trình nguan. B? phân tích tA vFng s/ dXng dLng bi4u th+c chính quy Č4 mô t các Č8n v< tA vFng (token), nh1 tA khóa, bi2n, sN, và sau Čó sinh ra DFA t18ng +ng Č4 nhBn bi2t d li\u vào. 3.1.1 E=nh nghFa hình th.c c;a bi7u th.c chính quy Cnh nghna 3.1. Cho bng ch Σ, bi4u th+c chính quy (BTCQ) trên Σ Č1@c Č<nh nghDa Č\ quy nh1 sau: 1. ∅ là bi4u th+c chính quy 2. ε là bi4u th+c chính quy 3. ∀a ∈ Σ, a là bi4u th+c chính quy 4. N2u r và s là các bi4u th+c chính quy thì (r + s), (rs), (r)* là các bi4u th+c chính quy LUu ð: Chúng ta có th4 vi2t (r ∪ s) thay vì vi2t (r + s). Xem xét các bi4u th+c chính quy sau: - (a + b + c) là bi4u th+c chính quy ch• Č<nh ba xâu a, b, c trên {a, b, c}. - (a + b)* là bi4u th+c chính quy ch• Č<nh mgi xâu trên {a, b}. - (aa*bb*) là bi4u th+c chính quy ch• Č<nh các xâu b‚t Čku b`ng m?t sN kí hi\u a, ti2p theo là m?t sN kí hi\u b, trong Čó a và b Čcu có mit ít nhKt m?t lkn. - (b + ε)(a + ab)* là bi4u th+c chính quy ch• Č<nh các xâu trên {a, b} không ch+a bb. 27
  28. Cnh nghna 3.2. Ngôn ng L(r) Č1@c ch• Č i bi4u th+c chính quy r bKt k~ là Č1@c xây dFng theo các quy t‚c sau: 1. L(∅) = ∅ 2. L(ε) = {ε} 3. L(a) = {a} vSi ∀a ∈ Σ Cho r và s là các bi4u th+c chính quy. 4. L(r + s) = L(r) ∪ L(s) 5. L(rs) = L(r)L(s) 6. L((r)*) = (L(r))* Xây dFng bi4u th+c chính quy ch• Č i bi4u th+c chính * * * * quy: (a + b) . VBy bi4u th+c chính quy ch• Č<nh L1 là r1 = (a + b) a(a + b) b(a + b) . T18ng tF, * * * ta có bi4u th+c chính quy ch• Č<nh L2 là r2 = (a + b) b(a + b) a(a + b) . CuNi cùng, bi4u th+c chính quy ch• Č<nh L là: * * * * * * r1 + r2 = (a + b) a(a + b) b(a + b) + (a + b) b(a + b) a(a + b) 3.1.2 E? 4u tiên các phép toán trên bi7u th.c chính quy C? 1u tiên c9a các phép toán trên bi4u th+c chính quy Č1@c quy Č<nh theo th+ tF sau: phép bao Čóng (*) có Č? 1u tiên cao nhKt, sau Čó Č2n phép k2t nNi (.) và cuNi cùng có Č? 1u tiên thKp nhKt là phép h@p (+ hoic ∪). Cho bi4u th+c chính quy: r = 10* + 1, chúng ta có th4 nhóm lLi theo th+ tF 1u tiên nh1 sau: r = (1(0*)) + 1. 3.1.3 Các tính chLt Č+i sN c;a bi7u th.c chính quy Các bi4u th+c chính quy có th4 Č1@c Č8n gin hóa. C4 thFc hi\n Čicu Čó, chúng ta s/ dXng m?t sN các tính chKt ČLi sN c9a các bi4u th+c chính quy. Các tính chKt ČLi sN c9a bi4u th1c chính quy c|ng nh1 các tính chKt ČLi sN c9a các bi4u th+c sN hgc. Cho r, s và t là các bi4u th+c chính quy. r + s = s + r r + (s + t) = (r + s) + t r(st) = (rs)t 28
  29. r(s + t) = rs + rt (r + s)t = rt + st ∅ + r = r + ∅ = r εr = rε = r ∅r = r∅ = ∅ r + r = r (r*)* = r* ∅* = ε ε* = ε r+ = rr* = r*r r* = r+ + ε (r*s*)* = (r + s)* 3.1.4 Bài tCp 1. Xây dFng bi4u th+c chính quy cho các ngôn ng sau: a) TBp h@p các xâu trên {a, b} ch+a nhicu nhKt m?t cip bb Či licn nhau. b) TBp h@p các xâu trên {a, b, c} ch+a ít nhKt m?t kí hi\u a và ít nhKt m?t kí hi\u c. c) TBp h@p các xâu trên {0, 1} có t„ng sN các kí hi\u 0 và các kí hi\u 1 chia h2t cho 5. 2. Hãy mô t ngôn ng c9a các bi4u th+c chính quy sau: a) (b + ε)(ab)*(a + ε) /* các kí hi\u a và b xen kj nhau */ b) (a + ba)*bb* c) (a + b + c + d)*(a + d) Chúng ta Čã Č i ôtômát h a hLn Č8n Č i bi4u th+c chính quy thì c|ng Č1@c Č i ôtômát h u hLn. NghDa là, m?t ngôn ng Č1@c Č i bi4u th+c chính quy là ngôn ng chính quy. Ch_ng minh: Gi s/ L = L(r) vSi r là bi4u th+c chính quy. Chúng ta ch• ra r`ng L = L(M) vSi M là ôtômát h u hLn không Č8n Č<nh mà: 1. Ch• có m?t trLng thái thAa nhBn hay trLng thái cuNi, 2. Không có cung nào Či vào trLng thái Čku, 3. Không có cung nào Či ra kh[i trLng thái cuNi. Chúng ta sj ch+ng minh Č<nh lð b`ng quy nLp trên bi4u th+c chính quy r, dFa theo Č<nh nghDa Č\ quy bi4u th+c chính quy trong mXc 3.1. Tr1Sc h2t chúng ta xây dFng NFA t18ng +ng vSi các bi4u th+c chính quy c8 bn là ∅, ε và a. 29
  30. )* h vS 3.1. Các NFA tU>ng _ng vai các bi/u th_c chính quy ∅, ε và a ε a a) b) c) Trong hình vj trên, NFA trong phkn a) không Čoán nhBn bKt c+ xâu vào nào, nghDa là ngôn ng L(∅) = ∅. NFA trong phkn b) Čoán nhBn ngôn ng ch• gam xâu ε, nghDa là ngôn ng L(ε) = {ε}. NFA trong phkn c) Čoán nhBn ngôn ng ch• gam xâu a, nghDa là ngôn ng L(a) = {a}. Nh1 th2, chúng ta nhBn thKy r`ng các NFA này th[a mãn các Čicu ki\n 1, 2 và 3 theo gi thuy2t trên. Ta Čã ch• ra Č i các NFA vSi ch• m?t trLng thái cuNi. Có bNn tr1rng h@p nh1 sau: 1. Bi4u th+c chính quy là r + s vSi r và s là các bi4u th+c chính quy con. NFA trong hình vj 3.2 a) Č1@c s/ dXng. ThBt vBy, b‚t Čku b>i trLng thái Čku mSi chúng ta có th4 Č2n m?t trong hai trLng thái Čku c9a NFA t18ng +ng r hoic c9a NFA t18ng +ng s. Khi chúng ta ČLt Č2n m?t trong các trLng thái thAa nhBn c9a các NFA t18ng +ng r hoic s, thì thAa nhBn t18ng +ng các xâu thu?c L(r) hoic L(s), chúng ta ti2p tXc ČLt Č2n trLng thái cuNi mSi b>i d i NFA trong hình vj 3.2 a) là L(r)∪L(s). 2. Bi4u th+c chính quy là rs vSi r và s là các bi4u th+c chính quy con. NFA t18ng +ng vSi phép nNi hai bi4u th+c Č1@c ch• ra trong hình vj 3.2 b). Trong Čó, trLng thái Čku c9a NFA th+ nhKt sj tr> thành trLng thái Čku c9a NFA mSi và thLng thái cuNi c9a NFA th+ hai sj tr> thành trLng thái cuNi c9a NFA mSi. Chúng ta d6 dàng nhBn thKy r`ng, b‚t Čku b>i trLng thái Čku Či qua NFA t18ng +ng r sj thAa nhBn các xâu thu?c L(r) và ti2p tXc Či qua NFA t18ng +ng s sj thAa nhBn các xâu thu?c L(s). Nh1 th2, NFA t18ng +ng rs thAa nhBn các xâu thu?c ngôn ng L(r)L(s). 3. Bi4u th+c chính quy là r* vSi r là bi4u th+c chính quy con. Chúng ta s/ dXng NFA trong hình vj 3.2 c). NFA này cho phép: a. Ci trFc ti2p tA trLng thái Čku Č2n trLng thái cuNi theo cung có nhãn ε, nghDa là NFA thAa nhBn xâu ε thu?c L(r*), vSi bi4u th+c chính quy r bKt k~. b. TA trLng thái Čku c9a NFA t18ng +ng r, có th4 Či qua NFA t18ng +ng r m?t hoic nhicu lkn và sau Čó ČLt Č2n trLng thái cuNi. Nh1 th2, NFA sj chKp nhBn các xâu thu?c L(r), L(r)L(r), L(r)L(r)L(r), , nghDa là NFA sj chKp nhBn tKt c các xâu trong L(r*), ngoLi trA xâu ε Čã Č1@c thAa nhBn khi Či trFc ti2p tA trLng thái Čku Č2n trLng thái cuNi nh1 Čã Čc cBp trong 3a. 4. Bi4u th+c (r) vSi r là là bi4u th+c chính quy con. NFA t18ng +ng r c|ng sj là NFA t18ng +ng (r), b>i vì các dKu ngoic không làm thay Č„i ngôn ng Č1@c Č<nh nghDa. 30
  31. ε r ε ε s ε a) ε r s b) ε ε ε r ε c) )* h vS 3.2. Các NFA tUang _ng các bi/u th_c chính quy r+s, rs, r* Xây dFng NFA t18ng +ng vSi bi4u th+c chính quy (0 + 1)(00* + ε). Chúng ta sj xây dFng tr1Sc h2t các NFA t18ng +ng các bi4u th+c chính quy con 0, 1, (0 + * * * 1), 0 , 00 , 00 + ε trong các hình vj d1Si Čây. 0 1 Hình vS 3.3. Các NFA tU>ng _ng bi/u th_c 0, 1 31
  32. ε 0 ε ε ε 0 ε ε ε 1 ε a) NFA t18ng +ng 0+1 b) NFA t18ng +ng 0* ε 0 ε 0 ε ε c) NFA t18ng +ng 00* ε 0 ε ε 0 ε ε ε ε ε ε d) NFA t18ng +ng 00*+ε ε 0 ε ε ε 1 ε 0 ε 0 ε ε ε ε ε ε ε e) NFA t18ng +ng (0+1)(00*+ε) )* h vS 3.4. Xây dng NFA cho ví dD 3.4 32
  33. Ng1@c lLi, chúng ta c|ng có th4 xây dFng bi4u th+c chính quy t18ng +ng vSi ôtômát h u hLn cho m?t ngôn ng . Cnh lð 3.2. N2u L = L(M) vSi NFA M nào Čó, thì tan tLi bi4u th+c chính quy r sao cho L = L(r) (Xem ch+ng minh trong [1]). 3.2.1 Bài tCp 1. Xây dFng NFA t18ng +ng các bi4u th+c chính quy sau: a. (01)*(0 +10*)* b. 10 + (0 + 01)1*0 c. (0 + 1)*(11+00) (0 + 1)* 2. Xây dFng DFA t18ng +ng các bi4u th+c chính quy sau: a. (0)*(1010)* b. (00 +11)*1*0* 3.3.1 Phân tích tB vGng (lexical analysis) M?t trong nh ng +ng dXng Či4n hình c9a bi4u th+c chính quy là Čic t b? phân tích tA vFng c9a m?t ch18ng trình d<ch. B? phân tích tA vFng Čgc ch18ng trình nguan và nhBn bi2t các —token“, là các xâu kí hi\u liên quan lôgic vSi nhau, chmng hLn nh1 tA khóa, danh bi4u, sN, Trên h\ Čicu hành Unix/Linux, các công cX lex hay flex nhBn Čku vào là m?t danh sách các bi4u th+c chính quy, tA Čó tìm —token“ t18ng +ng và sinh b? phân tích tA vFng. Các công cX này Č1@c ggi là b< sinh phân tích t4 vng (lexical-analyzer generator). Chmng hLn, chúng ta lKy ví dX m?t ČoLn d li\u Čku vào c9a công cX lex nh1 sau: [A-Za-z] [A-Za-z]* { mã np danh biu vào bng các kí hi u; return(ID); } == { return(EQ);} Ngoài cách s/ dXng ôtômát h u hLn và bi4u th+c chính quy Č4 mô t ngôn ng chính quy, chúng ta còn có cách khác là vQn phLm chính quy (regular grammar). 3.4.1 VKn ph+m tuy5n tính ph i và vKn ph+m tuy5n tính trái Cnh nghna 3.3. - M?t vQn phLm G = (N, Σ, R, S) Č1@c ggi vn phm tuyn tính ph"i n2u tKt c các luBt sinh có dLng: A → wB, hoic 33
  34. A → w, trong Čó, A, B ∈ N, w ∈ Σ*. - M?t vQn phLm G = (N, Σ, R, S) Č1@c ggi vn phm tuyn tính trái n2u tKt c các luBt sinh có dLng: A → Bw, hoic A → w, trong Čó, A, B ∈ N, w ∈ Σ*. - Các vQn phLm tuy2n tính trái và vQn phLm tuy2n tính phi Č1@c ggi là các vn phm chính quy. Cho các vQn phLm sau: G1 = ({S1}, {a, b}, R1, S1) vSi R1: S1 → bS1 | ab G2 = ({S2}, {a, b}, R2, S2) vSi R2: S2 → S2ba | b G1 là vQn phLm tuy2n tính phi, còn G2 là vQn phLm tuy2n tính trái. Nh1 vBy, G1 và G2 là các vQn phLm chính quy. Có th4 ch+ng minh r`ng mgi ngôn ng sn sinh b>i m?t vQn phLm tuy2n tính phi thì c|ng có th4 Č1@c sn sinh b>i m?t vQn phLm tuy2n tính trái và ng1@c lLi. Nh1 th2, khi nói Č2n vQn phLm chính quy chúng ta có th4 coi Čó là vQn phLm tuy2n tính phi. 3.4.2 Ngôn ng chính quy và vKn ph+m chính quy Không phi ngYu nhiên mà chúng ta ggi các vQn phLm tuy2n tính trái và vQn phLm tuy2n tính phi là các vQn phLm chính quy. ThFc t2, ngôn ng sn sinh b>i vQn phLm chính quy là ngôn ng chính quy. Cnh lð 3.3. M?t ngôn ng là chính quy n2u và ch• n2u ngôn ng Čó Č1@c sn sinh b>i m?t vQn phLm chính quy. Ch_ng minh: ei=u kifn c:n: N2u L là ngôn ng chính quy thì tan tLi vQn phLm chính quy G sn sinh L. B>i vì L là ngôn ng chính quy nên theo Č thành m?t bi2n trong G) ‡ SG = q0 (trLng thái Čku c9a M là kí hi\u Čku c9a G) ‡ RG Č1@c xây dFng nh1 sau: - q → ap n2u δ(q, a) = p 34
  35. - qf → ε n2u qf ∈ F Bây gir ckn ch+ng minh r`ng, m?t câu Č1@c thAa nhBn b>i M n2u và ch• n2u nó Č1@c sn sinh b>i G. Cicu này là hi4n nhiên khi chúng ta ti2n hành ČNng thri quá trình d i M, gi s/ w = a1a2 an. Th2 thì tan tLi các d i vQn phLm chính quy thì Čó là ngôn ng chính quy. Chúng ta sj ch+ng minh r`ng, ngôn ng Č1@c sinh ra b>i vQn phLm chính quy thì Č1@c thAa nhBn b>i ôtômát h u hLn không Č8n Č i Čku trong G thì trLng thái Čku trong Q là q0 = SG ‡ N2u Ni → a1a2 an thu?c RG thì thêm vào Q và F trLng thái k2t thúc Nf ‡ N2u Ni → a1a2 anNj thu?c RG thì Čit vào δ các d i hình vj d1Si Čây: a1 a2 an Ni Nj Hình vS 3.5. Minh h;a d.ch chuy/n ‡ N2u Ni → a1a2 an thu?c RG thì Čit vào δ các d i hình vj d1Si Čây: a1 a2 an Ni Nf Hình vS 3.6. Minh h;a d.ch chuy/n 35
  36. Vi\c ch+ng minh xâu w Č1@c sinh b>i G thì c|ng Č1@c thAa nhBn b>i M t18ng tF nh1 phkn tr1Sc. Xây dFng ôtômát h u hLn không Č8n Č i vQn phLm sau: S → aaS | aA A → abcA | c NFA t18ng +ng trong hình vj d1Si Čây. a a b S A a a c c )* h vS 3.7. NFA cho ví dD 3.6 3.4.3 Bài tCp 1. Xây dFng vQn phLm chính quy t18ng +ng ôtômát sau: 0 0 q0 q1 0 1 1 1 0, 1 q 2 q3 Hình vS 3.8. DFA 2. Xây dFng NFA cho các vQn phLm sau: a. S → 0A, A → 0A | 1A | 101 b. S → 00S | 11S | A, A → 010A | 010 Trong mXc này, chúng ta sj ch+ng minh các Č i các phép toán, nh1 h@p, giao, , thì L c|ng là ngôn ng chính quy“. Các Č<nh lð này Č1@c ggi là các tính chKt Čóng c9a ngôn ng chính quy, vì chúng ch• ra r`ng lSp các ngôn ng chính quy là Čóng d1Si các phép toán Čó. 3.5.1 Tính Čóng c;a ngôn ng chính quy d4Ri các phép toán tCp hAp Cnh lð 3.4. N2u L1 và L2 là các ngôn ng chính quy thì L1 ∪ L2 c|ng là ngôn ng chính quy. Ch_ng minh: ThBt vBy, vì L1 và L2 là các ngôn ng chính quy, nên tan tLi các bi4u th+c chính quy r1 và r2 sao cho L1 = L(r1) và L2 = L(r2). Theo Č<nh nghDa, r1 + r2 c|ng là bi4u th+c chính quy ch• Č<nh ngôn ng L(r1) ∪ L(r2). VBy L1 ∪ L2 là ngôn ng chính quy. 36
  37. Cnh lð 3.5. N2u L là ngôn ng chính quy trên bng ch Σ, thì L = Σ* − L c|ng là ngôn ng chính quy. Ch_ng minh: Cho DFA M = (Q, Σ, δ, q0, F) thAa nhBn L, thì L Č1@c thAa nhBn b>i DFA M‘ = (Q, Σ, δ, q0, Q-F). NghDa là, M‘ hoàn toàn nh1 M, nh1ng các trLng thái không chKp nhBn trong M tr> thành các trLng thái chKp nhBn trong M‘ và ng1@c lLi. Nh1 th2, w thu?c L(M‘) n2u * và ch• n2u δ (q0, w) ⊆ Q-F, mà Čicu này ch• Čúng khi w không thu?c L(M). L1u ð, Čicu này ch• Čúng khi M là DFA. Cho L là ngôn ng gam các xâu trên bng ch Σ = {0, 1}k2t thúc b>i 1. Hình vj 3.8 (a) ch• ra DFA thAa nhBn L. Ngôn ng bù c9a L sj gam các xâu trên Σ không k2t thúc b>i 1, nghDa là k2t thúc b>i 0. DFA thùa nhBn {0, 1}* - L trong hình vj 3.8 (b). 0 0 1 0 1 0 q0 q1 q 1 q0 1 1 a) b) Hình vS 3.8. DFA cho ngôn ng bù Cnh lð 3.6. N2u L1 và L2 là các ngôn ng chính quy thì L1 ∩ L2 c|ng là ngôn ng chính quy. Ch_ng minh: Chúng ta có th4 ch+ng minh b`ng hai cách. Cách 1: Các phép toán h@p, bù và giao trên tBp h@p thFc ra có mNi quan h\ chit chj vSi nhau. ThBt vBy, ta có: ∩ = ∪ L1 L2 L1 L2 VBy áp dXng các Č<nh lð 3.4 và 3.5, ta có th4 k2t luBn r`ng L1 ∩ L2 c|ng là ngôn ng chính quy. Cách 2: Chúng ta xây dFng trFc ti2p DFA thAa nhBn ngôn ng L1 ∩ L2 tA các DFA thAa nhBn L1 và L2. Gi s/ M1 = (Q1, Σ1, δ1, q01, F1) và M2 = (Q2, Σ2, δ2, q02, F2) là các DFA thAa nhBn t18ng +ng L1 và L2. Chúng ta sj xây dFng DFA M b‚t ch1Sc thFc hi\n Čang thri M1 và M2. Mbi trLng thái c9a M sj là m?t cip trLng thái: m?t trLng thái c9a M1 và m?t trLng thái c9a M2. Bng ch c9a M sj là h@p c9a các bng ch c9a M1 và M2. M?t d<ch chuy4n trong M Č1@c xây dFng t18ng +ng m?t d<ch chuy4n Čang thri trên M1 và M2 khi Čgc cùng m?t kí hi\u. M sj Čoán nhBn xâu vào khi Čòng thri c hai DFA M1 và M2 cùng Čoán nhBn xâu vào. Nh1 vBy, M Č1@c xây dFng nh1 sau: M = (Q1 x Q2, Σ1 ∪ Σ2, δ, (q01, q02), F1 x F2) trong Čó, δ((p, q), a) = (δ1(p, a), δ2(q, a)), vSi p ∈ Q1, q ∈ Q2, a ∈ Σ1 ∪ Σ2. D6 dàng nhBn thKy r`ng L(M) = L(M1) ∩ L(M2). * * * ThBt vBy, δ ((q01, q02), w) = (δ1 (q01, w), δ2 (q02, w)), nh1 th2 M ch• chKp nhBn w khi * * δ1 (q01, w) ∈ F1 và δ2 (q02, w) ∈ F2, nghDa là M ch• chKp nhBn w khi M1 chKp nhBn w và M2 chKp nhBn w. VBy, M chKp nhBn L(M1) ∩ L(M2). 37
  38. Cho L1 là ngôn ng chính quy có ch+a ít nhKt m?t kí hi\u 0 Č1@c thAa nhBn b>i DFA M1 (trong hình vj 3.9 (a)) và L2 là ngôn ng chính quy có ch+a ít nhKt m?t kí hi\u 1 Č1@c thAa nhBn b>i DFA M2 (trong hình vj 3.9 (b)). Chúng ta ch• ra DFA M (trong hình vj 3.9 (c)) thAa nhBn ngôn ng giao c9a L1 và L2. 1 0, 1 0 0, 1 0 1 q0 q1 p0 p1 a) b) 1 1 q0, p0 q0, p1 0 0 0 1 0, 1 q1, p0 q1, p1 c) )* h vS 3.9. Xây dng DFA giao cZa hai DFA Chúng ta d6 dàng nhBn thKy r`ng, DFA M thAa nhBn ngôn ng gam ít nhKt m?t kí hi\u 0 và ít nhKt m?t kí hi\u 1. Cnh lð 3.7. N2u L1 và L2 là các ngôn ng chính quy thì L1 − L2 c|ng là ngôn ng chính quy. − = ∩ Ch_ng minh: Chúng ta nhBn thKy r`ng L1 L2 L1 L2 . Mà bù c9a L2 là ngôn ng chính ∩ − quy, L1 L2 là ngôn ng chính quy. VBy L1 L2 c|ng là ngôn ng chính quy. 3.5.2 Tính Čóng d4Ri các phép toán khác Cnh lð 3.8. N2u L1 và L2 là các ngôn ng chính quy thì L1L2 c|ng là ngôn ng chính quy. Ch_ng minh: T18ng tF nh1 ch+ng minh cho phép h@p. ThBt vBy, vì L1 và L2 là các ngôn ng chính quy, nên tan tLi các bi4u th+c chính quy r1 và r2 sao cho L1 = L(r1) và L2 = L(r2). Theo Č<nh nghDa, r1r2 c|ng là bi4u th+c chính quy ch• Č<nh ngôn ng L(r1) L(r2). VBy L1L2 là ngôn ng chính quy. Cnh lð 3.9. N2u L là các ngôn ng chính quy thì L* c|ng là ngôn ng chính quy. Ch_ng minh: T18ng tF nh1 trên. Cnh lð 3.10. N2u L là các ngôn ng chính quy thì LR c|ng là ngôn ng chính quy. 38
  39. Ch_ng minh: Chúng ta ch+ng minh b`ng cách xây NFA thAa nhBn LR tA NFA thAa nhBn L. Gi s/ NFA M = (Q, Σ, δ, q0, F) thAa nhBn L1, chúng ta xây dFng M‘ = (Q‘, Σ‘, δ‘, q0‘, F‘) thAa nhBn LR vSi ð t1>ng là: - Čo ng1@c tKt c các cung trong bi4u Ča d thành trLng thái cuNi quy nhKt trong M‘, - thêm vào M‘ m?t trLng thái Čku mSi q0‘và các d i M, thì xâu wR sj Č1@c Čoán nhBn b>i M‘. Cho L là ngôn ng gam các xâu k2t thúc b>i xâu con ab trên Σ = {a, b}, xây dFng NFA Čoán nhBn ngôn ng LR. Tr1Sc h2t, chúng ta xây dFng NFA Čoán nhBn L trong hình vj 3.10 (a), sau Čó xây dFng NFA Čoán nhBn LR trong hình vj 3.10 (b). a, b a, b a b a b ε q1 q q1 q2 q0‘ q0 2 q0 a) b) Hình vS 3.10. Xây dng NFA Čoán nh'n ngôn ng ngh.ch Č"o Trong mXc này, chúng ta sj quan tâm Č2n làm th2 nào Č4 gii quy2t các bài toán liên quan Č2n ngôn ng chính quy. Chúng ta Čã bi2t, m?t ngôn ng thông th1rng là vô hLn, nên không th4 bi4u di6n ngôn ng b`ng cách li\t kê tKt c các xâu thu?c ngôn ng . Tuy nhiên, chúng ta s/ dXng m?t trong bNn cách bi4u di6n ngôn ng chính quy Čã bi2t. Trong các phkn tr1Sc, chúng ta c|ng Čã ch• ra r`ng có th4 chuy4n Č„i gi a bNn cách bi4u di6n ČNi vSi m?t ngôn ng chính quy. Chúng ta sj xem xét m?t vài bài toán c8 bn vc ngôn ng nh1: - M?t ngôn ng có là rbng không? - M?t xâu w có thu?c ngôn ng L không? - M?t ngôn ng L có phi là Σ*? - M?t ngôn ng có là tBp con c9a ngôn ng khác? - Hai ngôn ng có —b`ng“ nhau không? 39
  40. Bài toán 1. Xác Č i m?t th9 tXc hi\u qu. ThBt vBy, L có th4 Č1@c bi4u di6n b`ng m?t ôtômát h u hLn (Č8n Č i m?t th9 tXc hi\u qu. ThBt vBy, xây dFng m?t ôtômát h u hLn Č8n Č ng ČU>ng. TA vKn Čc này, chúng ta sj tìm cách cFu ti4u hóa DFA: t+c là xây dFng DFA có tNi thi4u sN trLng thái t18ng Č18ng vSi m?t DFA cho tr1Sc. 3.7.1 SG t4:ng Č4:ng c;a các tr+ng thái MXc Čích c9a chúng ta là xác Č i m?t trLng thái duy nhKt mà có ch+c nQng nh1 p và q. Chúng ta nói r`ng, hai trLng thái p và q là tU>ng ČU>ng n2u: vSi mgi xâu w, δ*(p, w) cho k2t qu là trLng thái k2t thúc và δ*(q, w) cho k2t qu c|ng là trLng thái k2t thúc hoic δ*(p, w) cho k2t qu là trLng thái không k2t thúc và δ*(q, w) cho k2t qu c|ng là không trLng thái k2t thúc. L1u ð, chúng ta không yêu cku δ*(p, w) và δ*(q, w) cho cùng trLng thái mà ch• cho k2t qu cùng trLng thái k2t thúc hoic không k2t thúc. Ng1@c lLi, hai trLng thái không t18ng Č18ng Č1@c ggi là phân bift. NghDa là, trLng thái p phân bi\t vSi trLng thái q, n2u tan tLi ít nhKt m?t xâu w sao cho m?t trong hai d<ch chuy4n δ*(p, w) và δ*(q, w) cho trLng thái k2t thúc và d<ch chuy4n còn lLi cho trLng thái không k2t thúc. C4 xác Č<nh sF t18ng Č18ng c9a các trLng thái, chúng ta s/ dXng chúng ta s/ dXng thuBt toán xây dFng b"ng Čánh du nh1 sau:. 40
  41. 1. N2u p là trLng thái không k2t thúc và q là trLng thái k2t thúc thì {p, q} là cip trLng thái phân bi\t. 2. Cho p và q là các trLng thái sao cho vSi kí hi\u vào a, r = δ(p, a) và s = δ(q, a) là cip trLng thái phân bi\t. Khi Čó {p, q} c|ng là cip trLng thái phân bi\t. ThBt vây, b>i vì {r, s} là cip trLng thái phân bi\t, nên tan tLi xâu w phân bi\t r và s, nghDa là ch• m?t trong hai d i xâu aw. Xây dFng bng Čánh dKu c9a DFA trong hình vj 3.11. 0 0 B E 0, 1 1 0, 1 0, 1 A D G 0 1 0 C F 1 1 Hình vS 3.11. DFA cho ví dD 3.10 Trong bng Čánh dKu các trLng thái phân bi\t (hình vj 3.12), các cip trLng thái phân bi\t Č1@c Čánh dKu X, các cip trLng thái t18ng Č18ng Č1@c Č4 trNng, các ô bôi Čen không Č1@c s/ dXng. Ban Čku, không có cip nào b trên. Tr1Sc h2t, các cip trLng thái gam có m?t thái k2t thúc và m?t trLng thái không k2t thúc Č1@c Čánh dKu. ThFc hi\n b1Sc 2 c9a thuBt toán, chúng ta không tim thKy thêm cip trLng thái phân bi\t nào n a. B X C X D X X E X X F X X X G X X X A B C D E F Hình vS 3.12. B"ng Čánh du các chp trng thái phân bift cho ví dD 3.10 Nh1 th2, chúng ta có các cip trLng thái t18ng Č18ng sau: {A, C}, {A, F}, {C, F}, {B, D}, {B, E}, {B, G}, {D, E}, {D, G}. 3.7.2 SG t4:ng Č4:ng c;a các DFA TA bng Čánh dKu sF t18ng Č18ng các trLng thái, chúng ta d6 dàng xác Č ng 41
  42. 3U> g thì chp trng thái Č:u ph"i là chp trng thái tU>ng ČU>ng. Ng1@c lLi, n2u cip trLng thái Čku phi là cip trLng thái phân bi\t thì M1 và M2 là không t18ng Č18ng. Xét hai DFA trong hình vj 3.13. Hai DFA này cùng Čoán nhBn ngôn ng gam các xâu trên bng ch {0, 1} k2t thúc b>i kí hi\u 0. Chúng ta coi hai DFA nh1 là m?t DFA vSi các trLng thái là A, B, C, D và E. Bây gir xây dFng bng Čánh dKu các trLng thái phân bi\t (hình vj 3.14) c9a DFA này. 0 1 0 0 1 C D A B 1 1 1 0 0 E a) b) Hình vS 3.13. Hai DFA tU>ng ČU>ng B X C X D X E X X X A B C D Hình vS 3.14. B"ng Čánh du các chp trng thái phân bift cho ví dD 3.11 A và C là cip trLng thái t18ng Č18ng, vBy hai DFA là t18ng Č18ng, t+c là chúng cùng thAa nhBn m?t ngôn ng . 3.7.3 CGc ti7u hóa DFA CFc ti4u hóa m?t DFA nghDa là tìm m?t DFA t18ng Č18ng có sN trLng thái ít nhKt. DFA tNi thi4u là duy nhKt ČNi vSi m?t ngôn ng . Ð t1>ng c9a vi\c xây dFng DFA tNi thi4u là: - Tr1Sc h2t, loLi b[ các trLng thái không ČLt Č2n Č1@c tA trLng thái Čku, - Sau Čó, chia các trLng thái thành các nhóm, sao cho các trLng thái trong cùng m?t nhóm là t18ng Č18ng nhau và không có cip trLng thái nào trong các nhóm khác nhau là t18ng Č18ng nhau. C4 thFc hi\n công viêc này, tr1Sc h2t chúng ta xét Č<nh lð sau. Cnh lð 3.11. (Tính cht b(c c:u) Cho DFA, n2u các trLng thái p và q là t18ng Č18ng và các trLng thái q và r là t18ng Č18ng thì các trLng thái p và r c|ng t18ng Č18ng. Ch_ng minh: Ch+ng minh b`ng phn ch+ng. Gi s/ {p, q} và {q, r} là các cip trLng thái t18ng Č18ng, còn {p, r} là cip trLng thái không t18ng Č18ng. Th2 thì tan tLi ít nhKt m?t xâu w sao cho ch• có m?t trong hai d<ch chuy4n δ*(p, w) và δ*(r, w) là cho trLng thái k2t thúc. Không mKt tính t„ng quát gi s/ δ*(p, w) cho trLng thái k2t thúc và δ*(r, w) cho trLng thái không k2t thúc. Xét k2t qu c9a d<ch chuy4n δ*(q, w). N2u δ*(q, w) cho trLng thái k2t thúc, thì {p, q} là t18ng Č18ng, nh1ng {q, r} là không t18ng Č18ng. N2u δ*(q, w) cho trLng thái không k2t thúc, 42
  43. thì {p, q} là không t18ng Č18ng. VBy ta k2t luBn r`ng {p, r} phi là cip trLng thái t18ng Č18ng. TA Č trong m?t nhóm t18ng Č18ng. Bây gir thì chúng ta có th4 Č1a ra thuBt toán cX th4 Č4 xác Č i vi\c s/ dXng các nhóm trLng thái nh1 là các trLng thái c9a nó. Gi s/ δmin là hàm d i vì, m?t trLng thái k2t thúc và m?t trLng thái không k2t thúc bao gir c|ng phân bi\t nhau, nên chúng không th4 > trong cùng m?t nhóm t18ng Č18ng. Quay tr> lLi ví dX 3.10. ta xây dFng DFA cFc ti4u trong hình vj 3.11. Ta có các cip trLng thái t18ng Č18ng là: {A, C}, {A, F}, {C, F}, {B, D}, {B, E}, {B, G}, {D, E} và {D, G}. VBy các nhóm trLng thái t18ng Č18ng là: {A, C, F} và {B, D, E, G}. 1 0, 1 0 ACF BDEG Hình vS 3.15. DFA cc ti/u tU>ng ČU>ng DFA trong hình vS 3.11 3.7.4 Bài tCp 1. Xây dFng DFA cFc ti4u cho DFA trình bày trong bng d<ch chuy4n sau: δ 0 1 → A B F B G C 43
  44. * C A C D C G E H F F C G G G E H G C Chúng ta Čã xét bNn công cX khác nhau Č4 làm vi\c vSi các ngôn ng chính quy: - Ótômát h u hLn Č8n Č ng c9a Č 0). Nh1 th2, vSi mgi xâu có Č? dài lSn h8n m, vi\c thFc hi\n ôtômát trên xâu này phi v1@t qua cùng m?t trLng thái qi nào Čó ít nhKt hai lkn vSi m?t phkn khác rbng c9a xâu ngQn cách gi a hai nh m TA Čó, vSi kí hi\u các xâu nh1 trên hình vj 3.16, thì mgi xâu có dLng xu*y c|ng Č1@c thAa nhBn b>i ôtômát và thu?c ngôn ng . D1Si Čây, chúng ta sj phát bi4u và ch+ng minh m?t cách hình th+c Č m cho ngôn ng chính quy) Cho L là ngôn ng chính quy vô hLn. Nh1 th2, tan tLi m?t sN nguyên d18ng m sao cho mgi xâu w thu?c mà |w| ≥ m, xâu w có th4 Č1@c phân tích thành ba xâu, w = xuy, sao cho: 1. u ≠ ε 2. |xu| ≤ m 3. ∀k ≥ 0, xuky ∈ L x u y qi qi q0 qf NghDa là, chúng ta luôn tìm Č1@c xâu u khác rbng, mà xâu này có th4 Č1@c —b8m“, t+c là xâu u có th4 Č1@c lip nhicu lkn hoic xóa nó (k = 0) mà xâu k2t qu xuky luôn thu?c L. Ch_ng minh: Gi s/ L là ngôn ng chính quy. Nh1 th2 tan tLi DFA M =(Q, Σ, δ, q0, F) sao cho L = L(M). Gi s/ M có m trLng thái. Chúng ta xem xét xâu w, |w| = n, vSi n ≥ m. Gi s/, w = a1a2 an, ai ∈ Σ. VSi mbi i = 0,1, n, gi s/ δ(q0, a1a2 ai) = pi. NghDa là, pi là trLng thái 44
  45. c9a M sau khi Čgc kí hi\u th+ i c9a w. L1u ð, p0 = q0. B>i vì n ≥ m, nên tan tLi i và j, vSi 0 ≤ i i vì pi = pj, nên u b‚t Čku tLi pi và sau Čó quay tr> lLi pi. Quan h\ gi a các xâu và các trLng thái Č1@c minh hga trong hình vj sau: u = ai+1ai+2 aj x = a1a2 ai y = aj+1aj+2 an q0 pi qf Hình vS 3.17. M;i xâu có Č n s? trng thái Č=u lhp li trên m 0, thì ôtômát M sj Či tA q0 Č2n pi khi Čgc k k x, lip lLi trên pi k lkn khi Čgc u và tA pi Č2n qf khi Čgc y. VBy xâu xu y Č1@c thAa nhBn. Nh1 th2, ∀k ≥ 0, xuky ∈ L. 3.8.2 Wng dXng Č=nh —b:m “ Chúng sj xét m?t sN ví dX s/ dXng Č Čku xâu khác sN kí hi\u a > cuNi xâu. VBy L không phi là ngôn ng chính quy. Ch+ng minh ngôn ng L ={ak | k là sN nguyên tN} không là chính quy. Gi s/ L là ngôn ng chính quy. Th2 thì, tan tLi DFA M thAa nhBn L. Gi s/ M có m trLng thái. Ta chgn xâu w = ap sao cho p > m + 1. Cicu này hoàn toàn thFc hi\n Č1@c, vì sN các sN nguyên tN là vô hLn. Theo Č<nh lð —b8m“, tan tLi cách phân tích w thành xuy, vSi u ≠ ε và 45
  46. |xu| ≤ m. Cit |u| = k, vBy |xy| = p œ k. Theo Č 0, vBy k + 1 > 1. Ngoài ra, |u| ≤ |xu| ≤ m, vBy k ≤ m. Ta lLi có, p > m + 1, vBy p > k + 1. Hay p œ k > 1. CuNi cùng, vì k + 1 > 1 và p œ k > 1 nên |xup-ky| không phi là sN nguyên tN. VBy, xup-ky ∉ L. Th2 thì, L không phi là ngôn ng chính quy. 3.8.3 Bài tCp 1. Ch+ng minh các ngôn ng sau không là chính quy: a. {0n12n | n ≥ 0} b. {0n11n | n > 0} c. {anbmcn | m, n ≥ 0} 2. Ch+ng minh các ngôn ng sau không là chính quy: a. {an | n = m2, m ≥ 0} b. L = {ww | w ∈ {a, b}*} 46
  47. PKn ph+m và ngôn ng phi ng c nh Trong các ch18ng tr1Sc, chúng ta Čã tìm hi4u ngôn ng chính quy và các ph18ng ti\n bi4u di6n ngôn ng chính quy. Chúng ta Čã thKy r`ng ngôn ng chính quy ch• mô t m?t lSp các ngôn ng t18ng ČNi Č8n gin. Các ngôn ng nh1 {0n1n | n≥ 0} hay {wwR | w ∈ {0, 1}} không thu?c lSp các ngôn ng chính quy. Cicu này ČYn Č2n vi\c nghiên c+u lSp ngôn ng r?ng h8n, Č1@c ggi là ngôn ng phi ng c"nh (context-free languages). Các ngôn ng phi ng cnh Č1@c mô t b>i vQn phLm, ggi là vn phm phi ng c"nh (context-free grammars). VQn phLm phi ng cnh Čóng vai trò rKt quan trgng trong vi\c xây dFng b? phân tích cú pháp c9a các ch18ng trình d<ch. 4.1.1 E=nh nghFa vKn ph+m và ngôn ng phi ng c nh Cnh nghna 4.1. M?t vQn phLm phi ng cnh G = (N, Σ, R, S) có các thành phkn nh1 sau: - N tBp các bi2n hay các kí hi\u không k2t thúc. - Σ là bng ch cái vào. - S ∈ N là bi2n Čku. - R là tBp các luBt sinh/sn xuKt, mà mbi luBt sinh có dLng: A → α trong Čó: A ∈ N, α ∈ (N ∪Σ)*. Nh1 th2, chúng ta nhBn thKy r`ng, ČNi vSi vQn phLm chính quy mbi luBt sinh có v2 trái là m?t bi2n Č8n, còn v2 phi có dLng Čic bi\t. Trong khi ČNi vSi vQn phLm phi ng cnh, v2 trái c|ng là m?t bi2n Č8n, nh1ng v2 phi là bKt k~, không ch<u giSi hLn nào. VSi Č<nh nghDa này chúng ta d6 dàng nhBn thKy, m?t vQn phLm chính quy c|ng là m?t vQn phLm phi ng cnh, tuy nhiên ng1@c lLi thì không phi luôn luôn Čúng. Cnh nghna 4.2. Ngôn ng L Č1@c ggi là phi ng cnh n2u tNn tLi m?t vQn phLm phi ng cnh G sao cho L = L(G). Nh1 th2, m?t ngôn ng chính quy c|ng là ngôn ng phi ng cnh, hay nói cách khác lSp các ngôn ng chính quy là tBp con trong lSp các ngôn ng phi ng cnh. Có th4 minh hga Čicu này b`ng hình vj 4.1. 47
  48. Ngôn ng; chính quy Ngôn ng; phi ng; c`nh )* h vS 4.1. Minh h;a quan hf gia lap ngôn ng chính quy và lap ngôn ng phi ng c"nh Cho vQn phLm phi ng cnh G = ({S}, {0, 1}, R, S) có các luBt sinh nh1 sau: S → 0S1 | ε Xét m?t dYn xuKt trong vQn phLm G: S 0S100S11000S1110000S111100001111 G G G G G Chúng ta d6 dàng nhBn thKy ngôn ng phi ng cnh Č1@c sinh ra b>i vQn phLm G là: L(G) = {0n1n | n ≥ 0} Cho vQn phLm phi ng cnh G = ({S}, {0, 1}, R, S) có các luBt sinh nh1 sau: S → 0S0 S → 1S1 S → 0 S → 1 S → ε Xét m?t dYn xuKt trong vQn phLm G: S 0S001S10011S1100110S0110011010110 G G G G G Chúng ta nhBn thKy r`ng, ngôn ng phi ng cnh là: L(G) = {wwR | w ∈ {0, 1}*} VU d1 4.3. Cho vQn phLm phi ng cnh Č<nh nghDa các bi4u th+c Č8n gin G = (N, Σ, R, E), trong Čó, tBp bi2n N = {E, I}, Σ = {a, b, +, *, (, )}, E là bi2n Čku, R gam các luBt sinh sau: E → I (1) E → E + E (2) E → E * E (3) E → (E) (4) I→ a (5) I→ b (6) I→ aI (7) I→ bI (8) Chúng ta có th4 hi4u các luBt sinh trên nh1 sau. LuBt sinh (1) nói r`ng m?t bi4u th+c là m?t Č<nh danh (bi2n). LuBt sinh (2) mô t m?t bi4u th+c là k2t qu c9a phép c?ng hai bi4u th+c. LuBt sinh (3) mô t m?t bi4u th+c là k2t qu c9a phép nhân hai bi4u th+c. LuBt sinh (4) mô t 48
  49. m?t bi4u th+c Čit gi a hai dKu Čóng m> ngoic c|ng là m?t bi4u th+c. Các luBt sinh tA (5) Č2n (6) mô t m?t Č<nh danh. M?t Č<nh danh là m?t xâu các kí hi\u a và b. 4.1.2 DYn xuLt trái nhLt và dYn xuLt ph i nhLt C4 giSi hLn sF lFa chgn các luBt sinh trong quá trình dYn xuKt, n2u mbi b1Sc bi2n bên trái nhKt c9a dLng câu Č1@c thay th2 thì ta ggi là dn xut trái nht. T18ng tF, n2u mbi b1Sc bi2n bên phi nhKt c9a dLng câu Č1@c thay th2 thì ta ggi là dn xut ph"i nht. Xét vQn phLm phi ng cnh G sau: S → aAB (1) A → bBb (2) B → A (3) B → ε (4) C4 d6 dàng xác Č<nh th+ tF các luBt sinh Č1@c s/ dXng trong dYn xuKt, chúng ta Čánh sN các luBt sinh. Xét dYn xuKt trái nhKt sau: 1 2 3 2 4 4 S  aAB abBbB abAbB abbBbbB abbbbB abbbb DYn xuKt trái nhKt này cho chúng ta xâu abbbb. Xét dYn xuKt phi nhKt sau: 1 4 2 3 2 4 S  aAB aAabBb abAb abbBbb abbbb DYn xuKt phi nhKt này c|ng cho chúng ta xâu abbbb. Hai dYn xuKt trái nhKt và phi nhKt trên là t18ng Č18ng vSi nhau vì chúng sinh ra cùng m?t xâu k2t qu. 4.1.3 Cây dYn xuLt Có m?t dLng cây Č1@c s/ dXng rKt h u ích Č4 bi4u di6n các dYn xuKt. DLng cây này, Č1@c ggi là cây dn xut hay cây phân tích cú pháp (parse tree), khi Č1@c s/ dXng trong ch18ng trình d<ch, là cKu trúc d li\u Č4 bi4u di6n các ch18ng trình nguan. Trong m?t ch18ng trình d<ch, cây dYn xuKt sj làm d6 dàng vi\c d<ch các ch18ng trình nguan sang các mã thFc thi. Cnh nghna 4.3. Cho vQn phLm G = (N, Σ, R, S). Cây dYn xuKt (còn Č1@c ggi là cây cú pháp hay cây phân tích) là cây vSi các Čicu ki\n sau: 1. Nút gNc Č1@c gán nhãn là bi2n Čku S. 2. Mbi nút trong Č1@c gán nhãn là m?t bi2n trong N. 3. Mbi nút lá Č1@c gán nhãn là m?t kí hi\u k2t thúc thu?c Σ hoic là m?t kí tF rbng ε. 4. N2u mbi nút có nhãn là bi2n A ∈ N và các con c9a nó Č1@c gán nhãn theo th+ tF tA trái sang phi là X1, X2, , Xn thì phi có luBt sinh A → X1X2 Xn trong R. 5. N2u m?t nút lá Č1@c gán nhãn là m?t kí tF rbng ε thì nó phi là con duy nhKt c9a cha nó (hLn ch2 sN l1@ng nút ε trong cây dYn xuKt). 49
  50. Quay tr> lLi vSi vQn phLm sinh ra các câu ČNi x+ng trong ví dX 4.2, cây dYn xuKt sn sinh xâu 00111 là nh1 sau: S 0 S 1 0 1 1 )* h vS 4.2. Cây bi/u diCn dn xut sinh xâu 00111 N2u chúng ta Čgc các nhãn c9a các nút lá tA trái qua phi sj nhBn Č1@c m?t xâu, Č1@c ggi là kt qu" cZa cây dn xut. Nh1 th2, k2t qu c9a m?t cây dYn xuKt là m?t xâu ch• gam các kí hi\u k2t thúc Č1@c dYn xuKt ra tA nút gNc (bi2n Čku). Quay tr> lLi vSi vQn phLm trong ví dX 4.3, chúng ta xây dFng cây dYn xuKt có k2t qu là (ab + b) * bb nh1 sau: E E * E ( E ) b b I + I a b b Hình vS 4.3. Cây dn xut sinh xâu (ab + b) * bb Cnh lð 4.1. Cho vQn phLm phi ng cnh G = (N, Σ, R, S), m?t câu w Č1@c sinh ra b>i G, * t+c là S  w , thì tan tLi cây dYn xuKt có k2t qu là w. G Ch_ng minh: Chúng ta sj ch+ng minh b`ng quy nLp theo sN b1Sc dYn xuKt ra xâu w trong vQn phLm G. N2u dYn xuKt ch• là m?t b1Sc, ch• có m?t luBt sinh Č1@c s/ dXng. LuBt sinh Čó phi là S → w. Gi s/ w = a1a2 an. LuBt sinh này sj t18ng +ng vSi cây có gNc là S và mbi nút lá có nhãn là mbi kí hi\u ai (Hình vj 4.4). Cây này sj th[a mãn là cây dYn xuKt trong vQn phLm G có k2t qu là w. Trong tr1rng h@p Čic bi\t w = ε thì cây dYn xuKt ch• có m?t nút lá duy nhKt có nhãn là ε. 50
  51. S a1 a2 an )* h vS 4.4. Cây dn xut cho kt qu" a1a2 an Bây gir, gi s/ r`ng Č i vì b1Sc Čku tiên s/ dXng luBt sinh S → X1X2 Xn không th4 thu?c dYn xuKt sinh ra wi. Êp dXng gi thuy2t quy nLp sinh xâu wi vSi n b1Sc dYn xuKt, ta có cây dYn xuKt Ti vSi k2t qu là wi. Sau Čó, chúng ta có th4 xây dFng m?t cây vSi gNc là S, cho k2t qu là w nh1 hình vj 4.5. Trong Čó, các con c9a gNc là X1, X2, Xn. SF lFa chgn là có th4 b>i vì ta có dYn xuKt S → X1X2 Xn trong G. S X1 X2 Xn T1 T2 Tn w1 w2 wn Hình vS 4.5. Cây dn xut có kt qu" w Nút Xi là gNc cây dYn xuKt con vSi k2t qu là wi. B`ng cách ghép k2t qu c9a các cây con ta có Č1@c k2t qu c9a cây có gNc là S, nghDa là w = w1w2 wn. 4.1.4 Bài tCp 1. Xây dFng vQn phLm phi ng cnh sinh cac ngôn ng sau: n n a. L1 = {0 11 | n > 0} i j k b. L2 = {a b c | i ≠ j hoic j ≠ k} 2. Cho vQn phLm phi ng cnh G sau: S → aSbS | bSaS | ε Ch+ng minh G sinh ra ngôn ng L(G) gam các xâu có sN kí hi\u a b`ng sN kí hi\u b. 51
  52. VQn phLm phi ng cnh ban Čku Č1@c Čc xuKt b>i Chomsky Č4 mô t ngôn ng tF nhiên, nh1ng sau Čó mXc Čích này Čã không Č1@c phát tri4n. Tuy nhiên, vQn phLm phi ng cnh lLi Č1@c s/ dXng Č4 mô t các m?t cách Č\ quy các khái ni\m trong lDnh vFc tin hgc. M?t trong nh ng +ng dXng quan trgng Čó là mô t ngôn ng lBp trình và xây dFng b? phân tích cú pháp. 4.2.1 Mô t ngôn ng lCp trình Chúng ta Čã thKy r`ng nhicu mYu Č8n gin c9a ngôn ng lBp trình có th4 Č1@c mô t b>i bi4u th+c chính quy, chmng hLn nh1 các Č i bi4u th+c chính quy. Chúng ta sj xem xét m?t sN ví dX cX th4 d1Si Čây. Chúng ta s/ dXng vQn phLm phi ng cnh sau Č4 mô t các cKu trúc s/ dXng hai kí hi\u { và } trong ngôn ng C. S → SS | {S}| ε Hay n2u chúng ta thay th2 cip dKu { và } b>i ( và ) thì vQn phLm trên cho phép mô t cách s/ dXng dKu ngoic trong các bi4u th+c toán hgc. VQn phLm sau sj cho phép mô t cKu trúc if-then và if-then-else trong các ngôn ng lBp trình, chmng hLn nh1 ngôn ng C. S → SS | iS | iSeS | ε Trong Čó, i và e bi4u di6n t18ng +ng các m\nh Čc if và else. Xét xâu sinh ra b>i vQn phLm là iiee. Xâu này sj t18ng +ng vSi các câu l\nh sau trong ngôn ng C. if (Či.u ki n) if (Či.u ki n) câu l nh; else câu l nh; else câu l nh; VSi m?t vQn phLm G, m?t xâu w thu?c L(G) có th4 là k2t qu c9a nhicu cây dYn xuKt khác nhau. Cicu Čó có nghDa là xâu w có th4 Č1@c phân tích cú pháp b`ng nhicu cách khác nhau. Cnh nghna 4.4. M?t vQn phLm G Č1@c ggi là nhBp nh`ng (ambiguity) n2u có th4 có m?t xâu w là k2t qu c9a hai cây dYn xuKt khác nhau trong G. Xét vQn phLm cho trong ví dX 4.3. E → I | E + E | E * E | (E) I → a | b | aI | bI Các luBt sinh E → E + E | E * E cho phép sinh ra các bi4u th+c s/ dXng các toán t/ + và * trong các th+ tF khác nhau. Xét bi4u th+c I + I * I, có hai dYn xuKt khác nhau tA E nh1 sau: E  E + E  I + E  I + E * E  I + I * E  I + I * I E  E * E  E * I  E + E * I  E + I * I  I + I * I 52
  53. Hay chúng ta bi4u di6n hai cây dYn xuKt t18ng +ng vSi các dYn xuKt trên trong hình vj 4.6. E E E + E E * E I E * E E + E I I I I I a) b) )* h vS 4.6. Hai cây dn xut cho cùng kt qu" I + I * I Nh1 th2, vQn phLm trong ví dX 4.3 là nhBp nh`ng. VSi hai dYn xuKt trên, chúng ta d6 dàng nhBn thKy th+ tF thFc hi\n c9a hai toán t/ + và * là bKt k~. Tuy nhiên, trong thFc t2 th+ tF thFc hi\n c9a hai toán t/ này phi xác Č i bKt k~ toán t/ nào licn kc. M?t bi2n F sj là m?t Č i các toán t/ > bên ngoài dKu ngoic). VBy ta có luBt sinh: F → I | (E). 2. Bi2n T bi4u di6n bi4u th+c không th4 b i toán t/ + licn kc. Trong vQn phLm này, ch• có hai toán t/ * và +, nên T là m?t phép nhân c9a m?t hoic nhicu F. Nh1 th2, toán t/ * Č1@c 1u tiên h8n toán t/ +. VBy ta có luBt sinh: T → F | T * F. 3. M?t bi4u th+c E có th4 là bi4u th+c bKt k~. Nh1 th2, m?t bi4u th+c là phép c?ng c9a m?t hoic nhicu T. VBy ta có luBt sinh: E → T | T + E. CuNi cùng, chúng ta có vQn phLm không nhBp nh`ng sau: F → I | (E) 53
  54. T → F | T * F E → T | E + T I → a | b | aI | bI VSi vQn phLm này, cây dYn xuKt (hình vj 4.7) cho k2t qu I + I * I là duy nhKt. E E + T I T * F F I I )* h vS 4.7. Cây dn xut cho kt qu" I + I * I 4.3.1 Bài tCp 1. Cho vQn phLm phi ng cnh G sau: S → aS | aSbS | ε a. Hãy cho ví dX ch• ra r`ng vQn phLm trên là nhBp nh`ng. b. Hãy loLi b[ sF nhBp nh`ng c9a vQn phLm trên. Trong phkn này chúng ta sj ch• ra r`ng bKt k~ m?t phi ng cnh nào không ch+a xâu rbng ε c|ng Č1@c sinh ra b>i ch• các luBt sinh có dLng A → BC hoic A → a, vSi A, B, C là các bi2n và a là kí hi\u k2t thúc. VQn phLm vSi các luBt sinh có dLng này ggi là dng chuqn Chomsky. C4 có Č1@c vQn phLm dLng chu_n nh1 th2 chúng ta ckn phi thFc hi\n m?t sN b1Sc gin l1@c: 1. LoLi b[ các kí hifu vô ích, là các bi2n hoic kí hi\u không k2t thúc mà không xuKt hi\n trong bKt k~ dYn xuKt nào sinh ra xâu tA bi2n Čku. 2. LoLi b[ các lu't sinh ε, là các luBt sinh có dLng A → ε, vSi A là m?t bi2n. 3. LoLi b[ các lu't sinh Č>n v., là các luBt sinh có dLng A → B, vSi A và B là các bi2n. 4.4.1 Lo+i b\ kí hi]u vô ích Cho vQn phLm phi ng cnh G = (N, Σ, R, S). M?t kí hi\u X ∈ N ∪ Σ Č1@c ggi là có ích n2u có dYn xuKt: ∗ ∗ S αXβ  w , vSi α, β ∈ (N∪Σ)* và w ∈ Σ. NghDa là, m?t kí hi\u là có ích n2u nó xuKt hi\n trong ít nhKt m?t dYn xuKt sinh xâu thu?c ngôn ng . Ng1@c lLi, m?t kí hi\u không có ích Č1@c ggi là vô ích. R[ ràng, n2u chúng ta loLi b[ các kí hi\u vô ích sj không nh h1>ng Č2n ngôn ng sinh ra b>i vQn phLm, vì chúng không tham gia vào quá trình sinh các xâu thu?c ngôn ng . Chúng ta xét hai loLi kí hi\u vô ích sau: 54
  55. 1. Kí hi\u mà không th4 bi2n Č„i thành xâu các kí hi\u k2t thúc Č1@c ggi là 5 hifu vô sinh. L1u ð r`ng kí hi\u không k2t thúc không th4 là kí hi\u vô sinh, b>i vì m?t xâu có th4 ch• gam m?t kí hi\u k2t thúc. 2. Kí hi\u mà không tan tLi dYn xuKt tA bi2n Čku S nào ch+a nó Č1@c ggi là kí hifu không Čt Čn ČUrc. Xét vQn phLm: S → aSb | A | ε A → aA A là kí hi\u vô sinh, vì không th4 bi2n ČNi A thành xâu các kí hi\u k2t thúc Č1@c. Xét vQn phLm: S → A A → aA | ε B → b ∗ B là kí hi\u không ČLt Č2n Č1@c vì không th4 có Č1@c S αXβ , vSi α và β nào Čó. Chúng ta ckn xác Č i vì nó có th4 sinh ra chính nó. b. N2u có A → α mà mgi kí hi\u c9a α là không vô sinh thì A là không vô sinh. L1u ð r`ng khi α là ε thì hi4n nhiên A là không vô sinh. 2. Các kí hi\u còn lLi trong N là các kí hi\u vô sinh. T18ng tF nh1 cách xác Č<nh các kí hi\u vô sinh, Č4 xác Č<nh các kí hi\u không Č2n Č1@c, chúng ta xác Č<nh các kí hi\u Č2n Č1@c. Khi Čó các kí hi\u còn lLi sj là kí hi\u không Č2n Č1@c. Cho vQn phLm phi ng cnh G = (N, Σ, R, S). Các kí hi\u không Č2n Č1@c Č1@c xác Č<nh nh1 sau: 1. Xác Č<nh tKt c các kí hi\u ČLt Č2n Č1@c, t+c là các kí hi\u có th4 Č1@c dYn xuKt ra tA S. B1Sc này Č1@c thFc hi\n nh1 sau: a. S hi4n nhiên là kí hi\u ČLt Č2n Č1@c. b. Gi s/ A là bi2n ČLt Č2n Č1@c. VSi tKt c các luBt sinh α → β mà α ch+a A thì các kí hi\u thu?c β là các kí hi\u ČLt Č2n Č1@c. 2. Các kí hi\u còn lLi trong N ∪ Σ là không ČLt Č2n Č1@c. 55
  56. Rõ ràng chúng ta nhBn thKy r`ng các kí hi\u vô ích không tham gia vào quá trình sn sinh xâu, nên khi loLi b[ chúng sj không làm nh h1>ng Č2n ngôn ng Č1@c sn sinh ra b>i vQn phLm. Cho vQn phLm phi ng cnh G = (N, Σ, R, S), gi s/ L(G) ≠ ∅, nghDa là G sn sinh ra ít nhKt m?t xâu. Chúng ta sj thFc hi\n vi\c loLi b[ các kí hi\u vô ích trong G b>i hai b1Sc sau: 1. LoLi b[ tKt c các kí hi\u vô sinh và các luBt sinh ch+a m?t hoic nhicu kí hi\u này. 2. LoLi b[ tKt c các kí hi\u không ČLt Č2n Č1@c và các luBt sinh ch+a m?t hoic nhicu kí hi\u này. Cnh lð 4.2. Cho vQn phLm phi ng cnh G = (N, Σ, R, S), vSi L(G) ≠ ∅ thì tan tLi vQn phLm phi ng cnh t18ng Č18ng G‘ = (N‘, Σ‘, R‘, S) không ch+a các kí hi\u vô ích. Ch_ng minh: Chúng ta sj thFc hi\n hai b1Sc loLi b[ các kí hi\u vô ích trong G. Sau khi loLi b[ kí hi\u vô sinh và các luBt sinh ch+a m?t hoic nhicu kí hi\u này ta thu Č1@c vQn phLm G1 = (N1, Σ1, R1, S). L1u ð S không th4 b i b1Sc 1, nên tan tLi A w , w ∈ Σ*. Nh1 th2, các kí hi\u tham gia G vào dYn xuKt này Čcu là không vô sinh, nên A w . G' ∗ H8n n a, A không b i b1Sc 2, nên tan tLi S αAβ . Nh1 th2, tKt c các kí hi\u G1 ∗ trong dYn xuKt này Čcu ČLt Č2n Č1@c, nghDa là S αAβ . Các kí hi\u trong α và β Čcu ČLt Č2n G' Č1@c, t+c là các kí hi\u này thu?c N1 ∪ Σ1, vBy các kí hi\u này là không vô sinh. Khi Čó, ta có ∗ ∗ S αAβ  xwy . G' G' Chúng ta k2t luBn r`ng A là kí hi\u có ích. B>i vi\c chgn A là bKt k~, nghDa là tKt c các kí hi\u trong G‘ Čcu là có ích. Ckn ti2p túc ch+ng minh r`ng G và G‘ t18ng Č18ng, nghDa là L(G) = L(G‘). Hay ckn ch+ng minh: L(G‘) ⊆ L(G) và L(G) ⊆ L(G‘). - L(G‘) ⊆ L(G): Čicu này là hi4n nhiên vì G‘ nhBn Č1@c b`ng cách loLi b[ các kí hi\u và luBt sinh trong G. - L(G) ⊆ L(G‘): ckn ch+ng minh w ∈ L(G) thì w ∈ L(G‘). ThBt vBy, vì w ∈ L(G) nên ∗ tan tLi S  w. R[ ràng r`ng tKt c các kí hi\u tham gia vào dYn xuKt này Čcu là G ∗ không vô sinh và ČLt Č2n Č1@c, vBy S  w. Nh1 th2, w ∈ L(G‘). G' L1u ð, khi loLi b[ các kí hi\u vô ích, ckn phi thFc hi\n loLi b[ theo Čúng th+ tF: loLi b[ các bi2n vô sinh, sau Čó loLi b[ các bi2n không ČLt Č2n Č1@c. Xét vQn phLm phi ng cnh G: 56
  57. S → aSb | ab | A A → aAB B → b D6 dàng xác Č i khái ni\m —bi2n tri\t tiêu * Č1@c“. Bi2n A Č1@c ggi là trift tiêu ČUrc (nullable), n2u Aε . Cho vQn phLm phi ng cnh G = (N, Σ, R, S), tBp các bi2n tri\t tiêu Č1@c, Č1@c kí hi\u Nt, trong G Č1@c xác Č i thuBt toán sau: 1. VSi mgi luBt sinh A → ε trong G thì A là bi2n tri\t tiêu Č1@c, thêm A vào Nt. 2. N2u có luBt sinh B → C1C2 Cn trong G và C1, C2, Cn ∈Nt thì B là bi2n tri\t tiêu Č1@c, thêm B vào Nt. 3. Lip lLi b1Sc 2 cho Č2n khi không còn bi2n nào Č1@c thêm vào trong Nt. Bây gir, chúng ta sj thFc hi\n vi\c loLi b[ các luBt sinh-ε trong vQn phLm phi ng cnh. Cho vQn phLm phi ng cnh G = (N, Σ, R, S). Xác Č<nh tBp Nt các bi2n tri\t tiêu Č1@c trong G. Ta xây dFng vQn phLm phi ng cnh G‘ = (N, Σ, R‘, S) tA G, trong Čó tBp các luBt sinh R‘ Č1@c xác Č<nh nh1 sau: N2u A → B1B2 Bn là luBt sinh trong R thì thêm vào R‘ các luBt sinh có dLng A → x1x2 xn trong Čó mbi xi thay th2 Bi thõa mãn các Čicu ki\n sau: - N2u Bi là bi2n không tri\t tiêu Č1@c thì cho xi = Bi. - N2u Bi là bi2n tri\t tiêu Č1@c thì cho xi = ε (khi cho xi = ε nghDa là Bi sj v‚ng mit) hoic xi = Bi. - Không cho tKt c các xi = ε, nghDa là n2u A → ε thì không Č1a vào R‘. LoLi b[ các luBt sinh-ε trong vQn phLm G sau: S → AB 57
  58. A → aAB | ε B → bAB | ε Xác Č i cách xây dFng > trên thì L(G‘) = L(G) œ {ε}. Ch_ng minh: Chúng ta ckn ch• ra r`ng n2u w ≠ ε thì w ∈ L(G‘) n2u và ch• n2u w ∈ L(G). Trong tr1rng h@p t„ng quát h8n chúng ta ch+ng minh r`ng: ∗ ∗ A w n2u và ch• n2u A w , vSi w ∈ Σ*, w ≠ ε, A ∈ N. G' G ∗ ∗ • Gi s/ A w ckn ch+ng minh A w G' G Ta d6 dàng nhBn thKy w ≠ ε vì G‘ không ch+a luBt sinh-ε. Chúng ta sj ch+ng minh b`ng quy ∗ nLp trên Č? dài c9a dYn xuKt A w . G BUac c> sE: dYn xuKt ch• m?t b1Sc, nghDa là có luBt sinh A → w trong G‘. Cách xây dFng G‘ cho chúng ta bi2t r`ng tan tLi A → α trong G, vSi α là w khi thay th2 không hoic nhicu ∗ ∗ bi2n tri\t tiêu Č1@c trong α. Th2 thì trong G có Aα  w, trong Čó α  w là b1Sc thay th2 G G G các bi2n tri\t tiêu Č1@c trong α b>i ε. ∗   BUac quy np: gi s/ dYn xuKt có Č? dài là n > 1, vBy có A X 1 X 2 X k w . Theo cách G' G' xây dFng G‘, trong G phi có luBt sinh A → β mà X1X2 Xk nhBn Č1@c tA β b`ng cách thay  β  th2 các bi2n tri\t tiêu Č1@c. NghDa là ta có: A X 1 X 2 X k trong G. Ngoài ra, tA dYn xuKt G G 58
  59. ∗ ∗    B d 1 d 2 X k w trong G‘ ta có th4 chia w thành w1w2 wk, sao cho X i wi G' G' G' ∗  (i=1, 2, , k) vSi sN b1Sc ít h8n n. Theo gi thi2t quy nLp thì trong G c|ng có X i wi . VBy G  β    ta có A X 1 X 2 X k w1w2 wk wtrong G. G G ∗ ∗ • Gi s/ A w và w ≠ ε ckn ch+ng minh A w G G' BUac c> sE: dYn xuKt ch• m?t b1Sc, nghDa là có luBt sinh A → w trong G thì c|ng có luBt sinh A → w trong G‘ vì w ≠ ε. VBy A w . G' ∗   BUac quy np: gi s/ dYn xuKt có Č? dài là n > 1, vBy có A X 1 X 2 X k w . Ta có th4 G G ∗  ≠ ε chia w thành w1w2 wk, sao cho X i wi (i=1, 2, , k) vSi sN b1Sc ít h8n n. N2u wi thì G ∗  ε theo gi thi2t quy nLp ta có X i wi trong G‘. N2u wi = thì Xi là bi2n tri\t tiêu Č1@c. Nh1 th2, G' trong G‘ phi có luBt sinh A → Y1Y2 Yk mà trong Čó Yi = ε khi wi = ε và Yi = Xi khi wi ≠ ε. H8n n a, w ≠ ε nên không th4 mgi Yi Čcu b`ng ε. VBy trong G‘ có dYn xuKt: ∗     A Y1Y2 Yk X 1 X 2 X k w1w2 wk w . G' G' G' G' ∗ ∗ VBy chúng ta Čã ch+ng minh xong: A w n2u và ch• n2u A w , vSi w ∈ Σ*, w ≠ ε, G' G ∗ ∗ A ∈ N. B`ng cách thay A b>i S, ta nhBn Č1@c: A w n2u và ch• n2u A w , vSi w ≠ ε. Hay G' G L(G‘) = L(G) œ {ε}. 4.4.3 Lo+i b\ luCt sinh Č:n v= Các luât sinh có dLng A → B trong Čó A và B là các bi2n Č1@c ggi là các lu't sinh Č>n v Các luBt sinh Č8n v i 0 b1Sc. * b. N2u (A, B) là cip th[a mãn A B và B → C là luBt sinh, vSi C là bi2n thì * (A, C) là cip th[a mãn A C . 3. CNi vSi mbi cip bi2n (A, B) Č1@c xác Č trên, thêm vào R‘ các luBt sinh A → α trong Čó B → α là luBt sinh không Č8n trong R. LoLi b[ luBt sinh Č8n v< c9a vQn phLm G có tBp các luBt sinh R nh1 sau: S → aA | A 59
  60. A → B | a B → A | ab | bb Xây dFng tBp luBt sinh R‘ b`ng cách loLi b[ các luBt sinh Č8n v ng Č2n ngôn ng Č1@c sinh ra b>i vQn phLm. Cnh lð 4.4. N2u G‘ là vQn phLm Č1@c xây dFng tA vQn phLm G b>i thuBt toán loLi b[ các luBt sinh Č8n v trên, thì L(G‘) = L(G). Ch_ng minh: Chúng ta ch• ra r`ng w ∈ L(G) khi và ch• khi w ∈ L(G‘). • Gi s/ w ∈ L(G‘) ckn ch+ng minh w ∈ L(G). * Gi s/ S  w, theo cách xây dFng G‘, thì mbi luBt sinh trong G‘ t18ng +ng vSi m?t dãy tA G' không hoic nhicu luBt sinh Č8n v i m?t luBt sinh không Č8n v i các dYn xuKt G' G G' * t18ng +ng trong G thì ta có S  w, vBy w ∈ L(G). G • Gi s/ w ∈ L(G) ckn ch+ng minh w ∈ L(G‘). * Khi Čó tan tLi dYn xuKt trái nhKt trong G sinh xâu w: S  w. N2u trong dYn xuKt này có xuKt G hi\n luBt sinh Č8n v i luBt sinh không Č8n v<. Theo cách xây * dFng G‘, thì mbi b1Sc này chính là m?t luBt sinh trong G‘. VBy S  w hay w ∈ L(G‘). G' 60
  61. 4.4.4 Gi n l4Ac vKn ph+m phi ng c nh Tóm lLi, chúng ta vAa thFc hi\n m?t sN b1Sc gin l1@c m?t vQn phLm phi ng cnh G thành G‘ t18ng Č18ng sao cho G‘ không ch+a các bi2n vô ích, các luBt sinh-ε và các luBt sinh Č8n v dLng chu_n Chomsky tA G nh1 sau: 1. Cit các luBt sinh dLng A → a vào R‘ (vì Čã th[a mãn dLng chu_n). 2. CNi vSi các luBt sinh dLng A → x1x2 xn vSi n ≥ 2, xi ∈ (N ∪Σ), i = 1, 2, n, n2u xi là m?t kí hi\u k2t thúc, chmng hLn xi = a, a ∈ Σ, thì thay th2 xi b>i m?t bi2n ČLi di\n mSi Bi. Khi Čó luBt sinh A → x1x2 xn sj có dLng A → B1B2 Bn. Wng vSi mbi bi2n ČLi di\n Bi mSi thêm vào, ta thêm vào R‘ luBt sinh Bi → a. 3. Sau khi thFc hi\n xong b1Sc 2, +ng vSi mbi luBt sinh A → B1B2 Bn mà n = 2 thì ta Čit nó vào R‘ (vì Čã th[a mãn dLng chu_n). Ng1@c lLi, n2u n > 2 ta Č1a vào các bi2n mSi C1, C2, và Č1a vào R‘ các luBt sinh sau: A → B1C1 C1 → B2C2 Cn-2 → Bn-1Bn Nh1 vBy, tKt c các luBt sinh trong G‘ sj th[a mãn dLng chu_n Chomsky. Bi2n Č„i vQn phLm phi ng cnh G sau vc dLng chu_n Chomsky: S → a | ABb A → a | bbc B → b | Ac Xây dFng G‘ > dLng chu_n Chomsky t18ng Č18ng G nh1 sau: 61