Giáo trình Lý thuyết ngôn ngữ hình thức và Ôtômát

Khoa Công nghꢀ Thông tin

Trꢁꢂng ꢃꢄi hꢅc Bách khoa

ꢃꢄi hꢅc ꢃà Nꢆng

GIÊO TRÏNH

LÐ THUY&T

NGÓN NG( HÏNH TH)C V ÓTÓMÊT

Nguy/n Thanh Bình

M1c l1c

1.1

1.2

Gi5i thiꢀu.................................................................................................................6

Khái niꢀm v: ngôn ng; ..........................................................................................6

1.2.1

1.2.2

1.2.3

1.2.4

1.2.5

Bꢀng chꢁ (alphabet) .........................................................................................6

Xâu (String)......................................................................................................7

Các phép toán trên xâu .....................................................................................7

Ngôn ngꢁ..........................................................................................................7

Các phép toán trên ngôn ngꢁ............................................................................8

1.3

1.4

Khái niꢀm v: v=n phꢄm .........................................................................................9

Khái niꢀm v: ôtômát ............................................................................................11

2.1

Ótômát h;u hꢄn ČBn ČCnh (deterministic finite automata - DFA) ..................12

2.1.1

2.1.2

Mô tꢀ không hình th+c ...................................................................................12

Mô tꢀ hình th+c ..............................................................................................13

DFA x/ lí xâu nh1 th2 nào.............................................................................13

Các cách bi4u di6n Č8n giꢀn h8n c9a DFA....................................................14

Hàm d<ch chuy4n m> r?ng .............................................................................14

Ngôn ngꢁ Č1@c thAa nhBn b>i DFA...............................................................16

Bài tBp.............................................................................................................17

2.1.3

2.1.4

2.1.5

2.1.6

2.1.7

2.2

2.2.1

2.2.2

2.2.3

Ótômát h;u hꢄn không ČBn ČCnh (non deterministic finite automata - NFA)17

C<nh nghDa hình th+c NFA.............................................................................17

Hàm d<ch chuy4n m> r?ng .............................................................................18

Ngôn ngꢁ Č1@c thAa nhBn b>i NFA...............................................................19

2.3

2.3.1

2.3.2

2.3.3

SP tꢁBng ČꢁBng gi;a DFA và NFA ....................................................................20

Xây dFng DFA tA NFA..................................................................................20

SF t18ng Č18ng giꢁa NFA và DFA ...............................................................23

Bài tBp.............................................................................................................24

2.4

2.4.1

2.4.2

2.4.3

)ng d1ng...............................................................................................................25

NFA cho tìm ki2m tA khóa.............................................................................25

DFA cho tìm ki2m tA khóa.............................................................................26

Bài tBp.............................................................................................................26

2

3.1

3.1.1

3.1.2

BiSu thTc chính quy (regular expresssion).........................................................27

C<nh nghDa hình th+c c9a bi4u th+c chính quy...............................................27

C? 1u tiên các phép toán trên bi4u th+c chính quy........................................28

Các tính chKt ČLi sN c9a bi4u th+c chính quy.................................................28

Bài tBp.............................................................................................................29

3.1.3

3.1.4

3.2

3.3

3.4

BiSu thTc chính quy và ngôn ng; chính quy .....................................................29

3.2.1

Bài tBp.............................................................................................................33

)ng d1ng cXa biSu thTc chính quy.....................................................................33

3.3.1

Phân tích tA vFng (lexical analysis) ...............................................................33

V=n phꢄm chính quy ............................................................................................33

3.4.1

3.4.2

3.4.3

VQn phLm tuy2n tính phꢀi và vQn phLm tuy2n tính trái..................................33

Ngôn ngꢁ chính quy và vQn phLm chính quy.................................................34

Bài tBp.............................................................................................................36

3.5

3.5.1

3.5.2

Các tính chZt Čóng cXa ngôn ng; chính quy......................................................36

Tính Čóng c9a ngôn ngꢁ chính quy d1Si các phép toán tBp h@p....................36

Tính Čóng d1Si các phép toán khác................................................................38

3.6

3.7

Các thu\t toán liên quan Č^n ngôn ng; chính quy............................................39

SP tꢁBng ČꢁBng cXa các ôtômát và cPc tiSu hóa ôtômát..................................40

3.7.1

3.7.2

3.7.3

3.7.4

SF t18ng Č18ng c9a các trLng thái.................................................................40

SF t18ng Č18ng c9a các DFA........................................................................41

CFc ti4u hóa DFA...........................................................................................42

Bài tBp.............................................................................................................43

3.8

3.8.1

3.8.2

3.8.3

Nh\n bi^t các ngôn ng; không là chính quy......................................................44

C<nh lð —b8m“ cho ngôn ngꢁ chính quy ........................................................44

Wng dXng Č<nh —b8m“....................................................................................45

Bài tBp.............................................................................................................46

4.1

4.1.1

4.1.2

V=n phꢄm phi ng; c`nh.......................................................................................47

C<nh nghDa vQn phLm và ngôn ngꢁ phi ngꢁ cꢀnh...........................................47

DYn xuKt trái nhKt và dYn xuKt phꢀi nhKt........................................................49

Cây dYn xuKt...................................................................................................49

Bài tBp.............................................................................................................51

4.1.3

4.1.4

4.2

4.3

4.4

)ng d1ng cXa v=n phꢄm phi ng; c`nh...............................................................52

4.2.1

Mô tꢀ ngôn ngꢁ lBp trình................................................................................52

SP nh\p nhang trong v=n phꢄm phi ng; c`nh ..................................................52

4.3.1

Bài tBp.............................................................................................................54

Dꢄng chubn cXa v=n phꢄm phi ng; c`nh...........................................................54

4.4.1

4.4.2

4.4.3

4.4.4

4.4.5

4.4.6

LoLi b[ kí hi\u vô ích.....................................................................................54

LoLi b[ luBt sinh-ε..........................................................................................57

LoLi b[ luBt sinh Č8n v<..................................................................................59

Giꢀn l1@c vQn phLm phi ngꢁ cꢀnh..................................................................61

DLng chu_n Chomsky ....................................................................................61

Bài tBp.............................................................................................................63

3

5.1

5.1.1

5.1.2

Ótômát Čby xucng (PushDown Automata - PDA) ............................................64

Mô tꢀ không hình th+c ...................................................................................64

C<nh nghDa hình th+c......................................................................................65

Bi4u di6n PDA b`ng bi4u Ča..........................................................................66

CKu hình c9a PDA..........................................................................................67

5.1.3

5.1.4

5.2

5.2.1

5.2.2

5.2.3

thái cuNi

5.2.4

Ngôn ng; Čꢁfc Čoán nh\n bgi PDA...................................................................67

Coán nhBn b>i trLng thái cuNi ........................................................................67

Coán nhBn b>i ngQn x2p rbng ........................................................................68

Chuy4n tA PDA Čoán nhBn b>i ngQn x2p rbng vc PDA Čoán nhBn b>i trLng

69

Chuy4n PDA Čoán nhBn b>i trLng thái cuNi vc PDA Čoán nhBn b>i ngQn x2p

71

rbng

5.2.5

Bài tBp.............................................................................................................72

5.3

5.3.1

5.3.2

5.3.3

SP tꢁBng ČꢁBng gi;a PDA và v=n phꢄm phi ng; c`nh....................................72

Chuy4n vQn phLm phi ngꢁ cꢀnh thành PDA ..................................................72

Chuy4n PDA thành vQn phLm phi ngꢁ cꢀnh ..................................................73

Bài tBp.............................................................................................................76

5.4

Ótômát Čby xucng ČBn ČCnh................................................................................76

5.4.1

Bài tBp.............................................................................................................77

Các tính chZt cXa ngôn ng; phi ng; c`nh..........................................................77

Các thu\t toán liên quan Č^n ngôn ng; phi ng; c`nh ......................................79

Nh\n bi^t các ngôn ng; không phi ng; c`nh.....................................................79

5.5

5.6

5.7

5.7.1

5.7.2

5.7.3

5.7.4

Kích th1Sc cây dYn xuKt.................................................................................80

C<nh lð b8m cho ngôn ngꢁ phi ngꢁ cꢀnh.......................................................80

Wng dXng Č<nh lð b8m cho ngôn ngꢁ phi ngꢁ cꢀnh.......................................82

Bài tBp.............................................................................................................83

6.1

6.1.1

6.1.2

Máy Turing ...........................................................................................................84

C<nh nghDa máy Turing ..................................................................................84

Bi4u di6n máy Turing b`ng bi4u Ča ...............................................................86

CKu hình c9a máy Turing ...............................................................................87

Ngôn ngꢁ Č1@c Čoán nhBn b>i máy Turing ...................................................88

Bài tBp.............................................................................................................88

6.1.3

6.1.4

6.1.5

6.2

Tính toán bgi máy Turing ...................................................................................88

6.2.1

Bài tBp.............................................................................................................89

Lu\n Č: Church-Turing (Church Turing thesis) ..............................................89

Các kh thu\t xây dPng máy Turing....................................................................90

6.3

6.4

6.4.1

6.4.2

6.4.3

NhS > b? Čicu khi4n hꢁu hLn .........................................................................90

BQng nhicu rãnh..............................................................................................90

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

6.5.2

Máy Turing không Č8n Č<nh...........................................................................92

Tài liꢀu tham kh`o… … … … … … … … … … … … … … … … … … … … … … … … … … … … 93

5

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 giꢀn h8n, mà chúng ta ggi là ôtômát

hꢀu hꢁn, Čã Č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

vꢂn phꢁm 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 tꢀng 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 bꢀn.

Ba khái ni\m c8 bꢀn 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 giꢀn Č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)

Bꢀng chꢁ hay còn ggi là b? kí tF là m?t bꢀng hꢁu hLn các kí hi\u (symbol). Bꢀng chꢁ

th1rng Č1@c kí hi\u là Σ.

Cho các bꢀng chꢁ sau:

{a, b, c, …, z}: bꢀng chꢁ cái Latin

{0, 1, …, 9} : bꢀng chꢁ sN thBp phân

{0, 1}

: bꢀng chꢁ sN nh< phân

6

1.2.2 Xâu (String)

Xâu (tA, chubi) là m?t dãy hꢁu hLn các kí hi\u tA bꢀng 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 bꢀng

chꢁ và các chꢁ cái w, u, v, … bi4u di6n các xâu.

Cho bꢀng 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 phꢀi c9a xâu u, t+c là:

u = a₁a₂… a_nvà v = b₁b₂… b_mthì k2t nNi c9a u và v là xâu uv = a₁a₂… a_nb₁b₂… b_m

ꢃ`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à

w = a₁a₂… a_nthì xâu Čꢀo nhBn Č1@c là w^R= a_na_n-1… a₁

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ì wⁿlà xâu nhBn Č1@c b`ng cách k2t nNi w vSi

chính nó n lkn.

wⁿ= ww…w (n lkn)

L1u ð, w⁰= ε vSi mgi w.

1.2.4 Ngôn ngꢃ

Ngôn ngꢁ là m?t tBp h@p các xâu trên bꢀng chꢁ Σ. Ngôn ngꢁ th1rng Č1@c kí hi\u là L.

TBp tKt cꢀ các xâu trên bꢀng 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 bꢀng 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 >0} là m?t ngôn ngꢁ trên Σ.

Còn Σ^*= {ε, 0, 1, 00, 01, 10, 11, 000, …}

L₁= {a, ab, abb, bba, bbb} là ngôn ngꢀ hꢀu hꢁn trên {a, b}.

L₂= {(ab)ⁿ| n > 0} là ngôn ngꢀ vô hꢁn trên {a, b}.

7

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, L₁và L₂trên bꢀng chꢁ Σ.

L₁L₂= {w | w L₁hoic w L₂}

L₁∩ L₂= {w | w L₁và w L₂}

L₁œ L₂= {w | w L₁và w L₂}

L = {w | w L} hoic L = Σ^*- L

L₁L₂= = {w | w = uv, u L₁và v L₂}

Cho L₁= {0, 1} và L₂= {00, 11}

L₁L₂= {000, 011, 100, 111}

L^R= {w | w^RL}

Lⁿ= LL…L (n lkn)

Hay L⁰= {ε}, Lⁱ= LL^i-1

L^*= L⁰L¹

…

Lⁿ

L⁺= L¹L²

…

L1u ð:

L^*= L⁺{ε}

L⁺= LL^*= L^*L

Cho L = {a, b}

L²= {aa, ab, bb, ba}

L³= {aaaa, aaab, aabb, aaba, abaa, abab, abbb, abba, bbaa, bbab, bbbb, bbba,

baaa, baab, babb, baba}

8

Khi nghiên c+u ngôn ngꢁ ckn m?t c8 ch2 mô tꢀ ngôn ngꢁ Čó là vꢂn phꢁm (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<nh nghDa m?t câu ti2ng Vi\t Č8n giꢀn b>i vQn phLm sau:

<Câu>

→

<V< ngꢁ>

<B„ ngꢁ>

<C?ng tA> | <C?ng tA> <B„ ngꢁ>

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 Č<nh nghDa nh1 là b? bNn:

G = (N, Σ, R, S)

trong Čó:

-

N là tBp h@p hꢁu hLn các kí hi\u không k2t thúc (non terminal symbol) hay

còn Č1@c ggi là các bi2n;

-

Σ là bꢀng chꢁ, tBp các kí hi\u k2t thúc (terminal symbol), N ∩ Σ =

N là kí hi\u Čku hay bi2n kh>i Čku;

;

S

R là tBp các quy t‚c (rule) hoic các sꢀn 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 G₁= ({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 G₂= ({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

Cho vQn phLm G = (N, Σ, R, S) và hai xâu u (N Σ)⁺và v (N Σ)^*

•

Dꢃn xuꢄt trꢅc tiꢆp (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

•

Dꢃn xuꢄt gián tiꢆp (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Ω w₁Ω w₂Ω ... Ω v

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à phꢀi tan tLi: S Ωw₁Ω w₂Ω ... Ω w , các w₁, w₂, …Č1@c ggi là các dꢁng câu c9a

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 G₁= ({S}, {0, 1}, {S → 0S1 | ε}, S)

thì S Ω 0S1 Ω 00S11 Ω 000S111 Ω 000111 là m?t dYn xuKt ra câu.

Ngôn ngꢁ t18ng +ng c9a vQn phLm G₁là: L(G₁) = {0ⁿ1ⁿ| n ≥ 0}.

Cho vQn phLm G₂= ({S, A}, {a, b}, {S → aA, A → aA, A → b}, S)

Ngôn ngꢁ t18ng +ng c9a vQn phLm G₂là: L(G₂) = {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à vꢂn phꢁm 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à vꢂn

phꢁm 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à vꢂn phꢁm 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à vꢂn phꢁm ngꢀ

cꢄu (tꢅ do) hay vQn phLm loLi 0.

10

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<ch s/ c9a h\ thNng. ThuBn l@i c9a vi\c ch• có sN hꢁu hLn các trLng thái là m?t h\ thNng có th4

Č1@c cài Čit vSi tBp h@p hꢁu hLn tài nguyên.

M?t cách không hình th+c, m?t ôtômát gam m?t tBp h@p các trLng thái và các Čicu khi4n

d<ch chuy4n tA trLng thái này sang trLng thái khác khi nhBn dꢁ li\u vào.

Ótômát Č8n giꢀn nhKt là mô tꢀ các trLng thái c9a m?t chuy4n mLch (switch). Thi2t

b< ckn ghi nhS trLng thái c9a nó là b't hay t(t, cho phép ng1ri s/ dXng Kn nút thì hi\u +ng nó

phX thu?c vào trLng thái hi\n tLi c9a thi2t b<. Khi thi2t b< > 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< Čang > 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 hꢀu hꢁn mô t" thiꢆt b. chuy/n mꢁch

Ó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 hꢀu hꢁn Č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

Ótômát hꢃu 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 Č<nh là ôtômát mà tLi m?t thri Či4m nó ch• có th4 > trong m?t trLng thái nhKt Č<nh,

trong khi ôtômát hꢁu hLn không Č8n Č<nh (bKt Č<nh) là ôtômát mà tLi mbi thri Či4m có th4 >

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 bꢂng 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 bꢀng 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< Či=u khi/n Q, gam m?t sN hꢁu hLn các trLng thái, tLi mbi thri Či4m nó có

m?t trLng thái.

BQng vào

0

1

0

1

0

1

0

Cku Čgc

B? Čicu khi4n

q

Hình 2.1 Mô t" ôtômát hꢀu hꢁn Č>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<ch chuy4n sang phꢀi m?t ô.

Quy luBt chuy4n trLng thái c9a ôtômát hꢁa hLn Č8n Č<nh Č1@c mô tꢀ b>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 trꢁng thái Č:u, th1rng kí hi\u q₀và m?t tBp h@p các trꢁng 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 q₀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

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 hꢀu hꢁn Č>n Č.nh (DFA) Č1@c Č<nh nghDa nh1 là m?t b? nQm:

M = (Q, Σ, δ, q₀, F)

Trong Čó:

-

Q là tBp hꢁu hLn các trLng thái, Q = {q₀, q₁, …, q_n}.

Σ là bꢀng chꢁ vào.

δ : Q x Σ → Q là hàm d<ch chuy4n, δ có th4 Č1@c vi2t d1Si dLng δ(q, a) = q‘,

nghDa là ôtômát Čang > trLng thái q và Čgc kí hi\u a thì nó sj chuy4n sang trLng

thái q‘.

-

q₀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 = a₀a₁...a_nlà xâu vào. DFA sj b‚t Čku vSi trLng thái q₀, nó sj thFc hi\n d<ch

chuy4n δ(q₀, a₁) giꢀ s/ cho q₁. DFA bây gir > trLng thái q₁và kí tF ti2p theo sj Čgc là a₂, nó

thFc hi\n d<ch chuy4n δ(q₁, a₂) giꢀ s/ cho q₂. Nó c+ ti2p tXc nh1 th2, cho Č2n khi Čgc a_nthì sj

chuy4n sang trLng thái q_nnào Čó, n2u q_nthu?c tBp F thì DFA thAa nhBn xâu vào w, ng1@c lLi

thì xâu vào sj không Č1@c thAa nhBn.

Xây dFng DFA thAa nhBn các xâu gam ch• các kí hi\u 0, 1 và ch+a ít nhKt m?t lkn

xâu 01, nghDa là chúng ta có th4 mô tꢀ ngôn ngꢁ L này nh1 sau:

L = {x01y | x và y gam các kí hi\u 0 và 1 bKt kì}

C4 xây dFng DFA thAa nhBn L, DFA M ckn ghi nhS các khꢀ nQng sau:

1. DFA Čã Čgc xâu 01, nh1 th2 sau Čó nó có th4 thAa nhBn xâu vào.

2. DFA ch1a bao gir Čgc kí tF 0, nh1ng nó Čã Čgc ít nhKt kí tF 1, trong tr1rng h@p này

nó có th4 ti2p tXc Čgc các kí tF 1 cho Č2n khi nào Čgc m?t kí tF 0 Čku tiên, thì nó có

th4 sau Čó Čgc m?t kí tF 1 Či licn sau.

3. DFA ch1a Čgc xâu 01, nh1ng ngay tr1Sc Čó nó Čgc ít nhKt m?t kí tF 0, nh1 th2 nó có

th4 ti2p tXc Čgc kí tF 0 cho Č2n khi gip m?t kí tF 1 thì có th4 chuy4n sang thAa nhBn

xâu vào.

VSi nhBn xét trên, chúng ta d6 dàng nhBn thKy mbi tr1rng h@p trên sj +ng vSi m?t trLng thái

ghi nhS c9a DFA. Tr1rng h@p (1) sj t18ng +ng vSi trLng thái thAa nhBn, kí hi\u trLng thái q₂,

> trLng thái này, DFA có th4 ti2p tXc Čgc bKt k~ kí hi\u nào. Nh1 th2, δ(q₂, 0) = δ(q₂, 1) = q₂.

Tr1rng h@p (2) sj t18ng +ng vSi trLng thái Čku q₀, 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, δ(q₀, 1) = q₀,

δ(q₀, 0) = q₁.

Tr1rng h@p (3) sj t18ng +ng vSi trLng thái q₁, khi Čã Čgc tr1Sc Čó ít nhKt m?t kí tF 0,

nh1ng ch1a bao gir Čgc xâu 01. ‰ trLng thái q₁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 q₂. Nh1 th2, δ(q₁, 0) = q₁, δ(q₁, 1) = q₂.

13

VBy, cuNi cùng chúng ta có DFA nh1 sau:

M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀, {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 giꢀn 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<ch chuy4n cho m?t DFA M = (Q, Σ, δ, q₀, F) là m?t Ča th< Č1@c Č<nh nghDa

nh1 sau:

1. Mbi trLng thái trong Q là m?t nút.

2. VSi mbi trLng thái q Q và mbi kí hi\u a Σ, có δ(q, a) = p Q. Nh1 th2, bi4u Ča

d<ch chuy4n có m?t cung Či tA nút p Č2n nút q mang nhãn a, n2u có nhicu kí hi\u tLo

ra d<ch chuy4n tA q Č2n p thì ch• ckn bi4u di6n m?t cung mang nhãn là danh sách các

kí hi\u Čó.

3. Có m?t m|i tên Či vào nút q₀Č4 kí hi\u trLng thái Čku.

4. Các trLng thái k2t thúc F là các nút Č1@c bi4u di6n b>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<ch chuy4n trLng thái Č4 bi4u di6n DFA Č1@c xây dFng trong ví

dX 2.1.

1

0

0, 1

0

1

q₀

q₁

q₂

Hình 2.1. DFA bi/u diCn ngôn ngꢀ trong ví dD 2.1

Bꢀng d<ch chuy4n cho m?t DFA là m?t quy 1Sc bi4u di6n dLng bꢀng c9a m?t hàm, mà >

Čây là d<ch chuy4n vSi hai tham sN: các trLng thái và các kí hi\u vào. TrLng thái Čku Č1@c Čánh

dKu b>i dKu ”→‘, các trLng thái cuNi sj Č1@c Čánh dKu b>i các dKu ”*‘.

Bꢀng d<ch chuy4n c9a DFA xây dFng trong ví dX 2.1 là nh1 sau:

δ

→ q₀

q₁

0

1

q₁

q₂

q₀

q₂

*q₂

2.1.5 Hàm d=ch chuy7n mꢀ r?ng

M?t cách không hình th+c chúng ta có th4 nhBn thKy r`ng, m?t DFA Č<nh nghDa ngôn ngꢁ

gam các xâu là k2t quꢀ c9a quá trình d<ch chuy4n tA trLng thái Čku Č2n m?t trong các trLng thái

thAa nhBn. C4 xác Č<nh ngôn ngꢁ Č1@c thAa nhBn b>i m?t DFA, chúng ta sj Č<nh nghDa hàm

d.ch chuy/n mE r<ng (extended transition function).

14

Hàm d<ch chuy4n m> 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<ch chuy4n m> r?ng Č1@c Č<nh nghDa Č\ quy trên Č? dài c9a xâu w

nh1 sau:

1. δ^*(q, ε) = q, vSi mgi trLng thái q, n2u DFA không Čgc kí hi\u vào nào thì sj > 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 phꢀi 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à phꢀi Č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 = ({q₀, q₁}, {0, 1}, δ, q₀, {q1})

Trong Čó, hàm δ nh1 sau:

1

0

1

q₀

q₁

0

Hình 2.2. DFA cho ví dD 2.4

Hay chúng ta có th4 bi4u di6n hàm δ b>i bꢀng d<ch chuy4n nh1 sau:

δ

→ q₀

* q₁

0

q₀

1

q₁

Bây gir, chúng ta s/ dXng hàm d<ch chuy4n m> r?ng Č4 Čoán nhBn xâu w=101101 c9a ngôn

ngꢁ L.

δ^*(q₀, ε) = q₀

δ^*(q₀, 1) = δ(δ^*(q₀, ε), 1) = δ(q₀, 1) = q₁

δ^*(q₀, 10) = δ(δ^*(q₀, 1), 0) = δ(q₁, 0) = q₀

δ^*(q₀, 101) = δ(δ^*(q₀, 10), 1) = δ(q₀, 1) = q₁

δ^*(q₀, 1011) = δ(δ^*(q₀, 101), 1) = δ(q₁, 1) = q₁

δ^*(q₀, 10110) = δ(δ^*(q₀, 1011), 0) = δ(q₁, 0) = q₀

δ^*(q₀, 101101) = δ(δ^*(q₀, 10110), 1) = δ(q₀, 1) = q₁

Nh1 th2, xâu vào w = 101101 Č1@c thAa nhBn b>i DFA.

15

Chúng ta có th4 bi4u di6n quá trình Čoán nhBn Č8n giꢀn h8n nh1 sau:

q₀101101 Ω q₁01101 Ω q₀1101 Ω q₁101 Ω q₁01 Ω q₀1 Ω q₁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 bꢀi DFA

ꢃCnh nghna 2.3. Cho DFA M = (Q, Σ, δ, q₀, F), ngôn ngꢁ Č1@c thAa nhBn b>i M, Č1@c kí

hi\u là L(M), Č1@c Č<nh nghDa nh1 sau:

L(M) = {w Σ^*| δ^*(q₀, w) = q_f, q_fF}

NghDa là, ngôn ngꢁ L(M) gam các xâu w sao cho M xuKt phát tA trLng thái Čku q₀, sau khi

Čgc h2t xâu w thì ČLt Č2n m?t trong các trLng thái q_fthu?c F.

ꢃCnh nghna 2.4. Cho DFA M, m?t ngôn ngꢁ L = L(M) Č1@c ggi là ngôn ngꢀ chính qui

(regular language). Hay nói cách khác, ngôn ngꢁ Č1@c thAa nhBn b>i m?t ôtômát hꢁu hLn Č8n

Č<nh là ngôn ngꢁ chính qui.

Xây dFng ôtômát thAa nhBn ngôn ngꢁ L gam các xâu trên bꢀng chꢁ Σ = {a, b}

Č1@c b‚t Čku b>i xâu aa.

a, b

a

q₀

q₃

q₂

b

q₁

a, b

Hình 2.3. DFA cho ví dD 2.5

Chúng ta có th4 d6 dàng nhBn thKy r`ng q₁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 = { abaⁿb^m| 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

q₁

a

q₂

q₃

q₀

q₄

a

b

a

q₅

a, b

Hình 2.4. DFA th4a nh'n L = { abaⁿb^m| m,n >0 }

Nh'n xét: CNi vSi m?t DFA M = (Q, Σ, δ, q₀, 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 δ phꢀi 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

2.1.7 Bài tCp

1. Hãy xác Č<nh các DFA Čoán nhBn các ngôn ngꢁ trên bꢀng chꢁ {0, 1} sau:

a. TBp các xâu có Č? dài chia h2t cho 3.

b. TBp các xâu k2t thúc b>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 = {abⁿab^m| 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:

δ

→ q₀

* q₁

q₂

0

1

q₁

q₂

q₀

q₂

M?t ôtômát hꢁu hLn không Č8n Č<nh có khꢀ nQng > 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 (bꢀng

chꢁ vào). NFA c|ng có m?t hàm d<ch chuy4n, Č1@c kí hi\u là δ. SF khác nhau c8 bꢀn giꢁa

NFA và DFA là Č<nh nghDa c9a hàm d<ch chuy4n. CNi vSi NFA, hàm d<ch chuy4n nhBn m?t

trLng thái và m?t kí hi\u vào (c|ng nh1 ČNi vSi DFA) và trꢀ vc m?t tBp h@p, có th4 rbng, các

trLng thái (thay vì ch• trꢀ vc Čúng m?t trLng thái ČNi vSi DFA).

2.2.1 E=nh nghFa hình th.c NFA

ꢃCnh nghna 2.5. M?t ôtômát hꢀu hꢁn không Č>n Č.nh (NFA) Č1@c Č<nh nghDa nh1 là m?t b?

nQm:

M = (Q, Σ, δ, q₀, F)

Trong Čó:

-

Q là tBp hꢁu hLn các trLng thái, Q = {q₀, q₁, …, q_n}.

Σ là bꢀng chꢁ vào.

q₀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 bꢀn 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

•

m?t NFA có th4 có d<ch chuy4n khi Čgc ε, t+c là Čgc xâu rbng, trong khi DFA thì

không Čgc xâu rbng. Nh1 vBy, NFA cho phép thFc hi\n sF chuy4n trLng thái mà

không Čgc kí hi\u vào nào cꢀ.

M?t NFA c|ng có th4 Č1@c mô tꢀ b>i bi4u Ča d<ch chuy4n hay bꢀng d<ch chuy4n nh1 DFA.

Xây dFng NFA thAa nhBn ngôn ngꢁ gam các xâu trên bꢀng chꢁ {0, 1}, b‚t Čku

b>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.

q₁

0

1

q₀

q₂

0, 1

Hình 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:

q₀0101101 Ω q₁101101 Ω q₁01101 Ω q₁1101 Ω q₁101 Ω q₁01 Ω q₁1 Ω q₂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 bꢀng chuy4n d<ch nh1 sau:

δ

→ q₀

q₁

0

{q₁}

1

{q₁, q₂}

* q₂

LUu ð: K2t quꢀ c9a hàm d<ch chuy4n là m?t tBp các trLng thái và có th4 là tBp rbng khi NFA

> m?t trLng thái nào Čó, Čgc kí hi\u vào, không tan tLi d<ch chuy4n t18ng +ng. Khi Čó, ta nói

NFA —b< hóc“, không hoLt Č?ng nꢁa.

Xây dFng ôtômát nhBn bi2t ngôn ngꢁ gam các xâu có Č? dài ch‹n trên bꢀng

chꢁ {0, 1}. NFA Č1@c xây dFng trong hình vj 2.6.

ε

q₁

0, 1

q₀

q₂

Hình vS 2.6. NFA cho ví dD 2.8

2.2.2 Hàm d=ch chuy7n mꢀ r?ng

C|ng nh1 ČNi vSi DFA, chúng ta Č<nh nghDa hàm d<ch chuy4n m> 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

ꢃCnh nghna 2.6. Hàm d<ch chuy4n m> r?ng Č1@c Č<nh nghDa Č\ quy trên Č? dài c9a xâu w

nh1 sau:

1. δ^*(q, ε) = {q}, vSi mgi trLng thái q, n2u NFA không Čgc kí hi\u vào nào thì sj > lLi

trLng thái Čó.

2. VSi w = xa, x Σ^*và a Σ, giꢀ s/ δ^*(q, x) = {p₁, p₂, …, p_k} và

k

δ ( p ,a) = {r ,r , ..., r } thì δ^*(q, w) = {r₁, r₂, …, r_n}.

8

i

1

2

n

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 δ^*(q₀, a).

ε

q₁

Hình vS 2.7. NFA cho ví dD 2.9

a

ε

q₀

q₂

Ta có: δ^*(q₀, a) = {q₀, q₁, q₂}.

S/ dXng hàm d<ch chuy4n m> r?ng trong hình vj 2.5 Č4 x/ lð xâu w = 0101101.

Các b1Sc Čoán nhBn nh1 sau:

1. δ^*(q₀, ε) = {q₀}

2. δ^*(q₀, 0) = δ(q₀, 0) = {q₁}

3. δ^*(q₀, 01) = δ(q₁, 1) = {q₁, q₂}

4. δ^*(q₀, 010) = δ(q₁, 0) δ(q₂, 0) = {q₁}

5. δ^*(q₀, 0101) = δ(q₁, 1) = {q₁, q₂}

6. δ^*(q₀, 0101) = δ(q₁, 1) δ(q₂, 1) = {q₁, q₂}

7. δ^*(q₀, 01011) = δ(q₁, 1) δ(q₂, 1) = {q₁, q₂}

8. δ^*(q₀, 010110) = δ(q₁, 0) δ(q₂, 0) = {q₁}

9. δ^*(q₀, 0101101) = δ(q₁, 1) = {q₁, q₂}

= {q₁}

= {q₁, q₂}

= {q₁}

2.2.3 Ngôn ngꢃ Č4Ac thBa nhCn bꢀi NFA

ꢃCnh nghna 2.7. Cho NFA M = (Q, Σ, δ, q₀, F), ngôn ngꢁ Č1@c thAa nhBn b>i M, Č1@c kí

hi\u là L(M), Č1@c Č<nh nghDa nh1 sau:

L(M) = {w Σ^*| δ^*(q₀, w) ∩ F ≠

}

NghDa là, ngôn ngꢁ L(M) gam các xâu w thu?c Σ^*sao cho M xuKt phát tA trLng thái Čku q₀,

thì δ^*(q₀, w) ch+a ít nhKt m?t trong các trLng thái thAa nhBn.

Xác Č<nh ngôn ngꢁ Č1@c thAa nhBn b>i ôtômát trong hình vj d1Si Čây:

19

q₁

0

1

q₀

q₂

0, 1

Hình 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 Č<nh nghDa DFA và NFA là khác nhau: th4 hi\n > hàm d<ch

chuy4n. Ngoài ra, ČNi vSi m?t ngôn ngꢁ, NFA là d6 dàng xây dFng h8n DFA. H8n nꢁa, sN

trLng thái c9a m?t DFA th1rng là rKt lSn, trong khi sN trLng thái NFA th1rng là ít h8n. Tuy

nhiên, chúng ta sj thKy r`ng NFA và DFA có vai trò nh1 nhau trong Čoán nhBn ngôn ngꢁ. ThBt

vBy, chúng ta sj ch• ra r`ng DFA thFc hi\n nhꢁng gì mà NFA thFc hi\n.

2.3.1 Xây dGng DFA tB NFA

TA m?t NFA N = (Q_N, Σ, δ_N, q₀, F_N) chúng ta có th4 xây dFng m?t DFA D = (Q_D, Σ, δ_D,

{q₀}, F_D) sao cho L(N) = L(D). Trong Čó, bꢀng chꢁ vào c9a NFA và DFA giNng nhau, trLng

thái Čku c9a DFA là tBp h@p {q₀} ch• gam trLng thái Čku q₀c9a NFA. Các thành phkn khác

Č1@c xây dFng nh1 sau:

•

Q_Dlà tBp h@p các tBp con c9a Q_N. L1u ð r`ng, n2u Q_Ncó n trLng thái thì Q_Dsj có 2ⁿ

trLng thái. Tuy nhiên, th1rng có các trLng thái không ČLt Č2n Č1@c trong Q_D, các

trLng thái này có th4 loLi b[. Nh1 vBy, Q_Dth1rng có sN trLng thái nh[ h8n 2ⁿ.

F_Dlà tBp h@p các tBp con S c9a Q_Nsao cho S ∩ F_N≠ . NghDa là, F_DtBp h@p các

trLng thái trong Q_Dsao cho mbi trLng thái Čó có ch+a ít nhKt m?t trLng thái thAa

nhBn thu?c F_N.

CNi vSi mbi tBp T Q_Nvà mbi kí hi\u a Σ,

δ _D

(

T, a

)

=

δ (q, a)

8

N

q trong T

Cho NFA N trong hình vj 2.8 chKp nhBn ngôn ngꢁ gam các xâu trên {0, 1} k2t

thúc b>i 01. B>i vì tBp các trLng thái c9a N là {q₀, q₁, q₂}, sN tBp h@p các tBp con các trLng thái

c9a N là 2³. Nh1 th2, chúng ta có th4 xây dFng bꢀng d<ch chuy4n cho DFA nh1 sau:

δ

0

1

→ {q₀}

{q₁}

{q₀, q₁}

{q₀}

{q₂}

* {q₂}

{q₀, q₁}

{q₀, q₂}

{q₀}

{q₂}

* {q₀, q₂}

* {q₁, q₂}

*{q₀, q₁, q₂}

{q₀, q₁}

{q₀, q₂}

L1u ð r`ng, mbi trLng thái c9a DFA là m?t tBp h@p các trLng thái c9a NFA. Chúng ta có th4

Čit tên lLi cho các trLng thái này, chmng hLn {q₀} Č1@c thay b>i p₀, {q₁} Č1@c thay b>i p₁, …

Ta có bꢀng d<ch chuy4n nh1 sau:

20