chương trình trợ giúp học một số

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

TRÖÔØNG ÑAÏI HOÏC KYÕ THUAÄT TP.HOÀ CHÍ MINH

KHOA COÂNG NGHEÄ THOÂNG TIN

LUAÄN VAÊN TOÁT NGHIEÄP

Ñeà taøi

Chöông trình trôï giuùp hoïc moät soá

giaûi thuaät trong moân hoïc

Thaày höôùng daãn :

HOÀ VAÊN QUAÂN

QUAÛN THAØNH THÔ

Sinh vieân thöïc hieän :

NGUYEÃN COÂNG MINH

LÖU THÒ TOÁT

Lôùp KS2 – K6

7/99

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 89

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

MUÏC LUÏC

1 .Phaàn moät

Lyù thuyeát ngoân ngöõ hình thöùc vaø OÂtoâmaùt phaàn ngoân ngöõ chính qui

1.1 Chöông 1: Moät soá kieán thöùc lyù thuyeát cô baûn cuûa moân hoïc .........................2

1.1.1 Töø (word).............................................................................................2

1.1.2 Ngoân ngöõ ............................................................................................3

1.1.3 Automata (maùy töï ñoäng ).....................................................................3

1.1.4 Bieåu thöùc chính qui vaø ngoân ngöõ chính qui..........................................4

1.1.5 Vaên phaïm chính qui ............................................................................5

1.2 Chöông 2 : Moät soá giaûi thuaät lieân quan ........................................................7

1.2.1 Chuyeån Nfa sang DFA.........................................................................7

1.2.2 Xaây döïng NFA töø Bieåu thöùc chính qui...............................................12

1.2.3 Xaây döïng NFA töø Vaên phaïm chính qui..............................................18

1.2.4 Giaûi thuaät ruùt goïn soá traïng thaùi cuûa DFA...........................................19

1.3 Chöông 3 :Borland Delphi 3.0.....................................................................21

1.3.1 Giôùi thieäu...........................................................................................21

1.3.2 Phaàn chuû yeáu söû duïng trong chöông trình..........................................22

2. Phaàn hai

Phaân tích vaø thieát keá toång quaùt

2.1 Chöông 1: Lyù thuyeát veà phaàn meàm giaûng daïy............................................26

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 90

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

2.1.1 Phaàn meàm giaûng daïy ........................................................................26

2.1.1.1 Phaàn meàm daïy hoïc......................................................................26

2.1.1.2 Caùc loaïi phaàn meàm giaûng daïy hieän taïi.......................................27

2.1.1.3 ÖÙng duïng lyù thuyeát CDT trong thieát keá phaàn meàm giaûng daïy....28

2.1.2 Chöông trình trôï giuùp giaûng daïy moân ngoân ngöõ lyù thuyeát vaø Automat

hình thöùc.....................................................................................................28

2.1.2.1 Phaân tích caùc ñieàu kieän giaûng daïy..............................................28

2.1.2.2 Phöông phaùp giaûng daïy. Chieán löôïc phaùt trieån caùc moâ hình cho

moân hoïc..................................................................................................29

2.2 Chöông 2 : Chöông trình trôï giuùp giaûng daïy Lyù thuyeát ngoân ngöõ hình thöùc

vaø Automat. Phaân tích vaø thieát keá toång quaùt.....................................................35

2.2.1 Chöông trình naøy laøm gì.....................................................................35

2.2.2 Nhaän daïng vaø xaây döïng caùc ñoái töôïng cuûa phaàn meàm......................36

3.Phaàn ba

Laäp trình cuï theå xaây döïng caùc ñoái töôïng

3.1 Chöông 1: Phaân tích vaø thieát keá xaây döïng caùc ñoái töôïng............................43

3.1.1Caùc ñoái töôïng caàn xaây döïng ..............................................................44

3.1.1.1 Caùc ñoái töôïng ñoà hoïa..................................................................44

3.1.1.2 Caùc ñoái töôïng lyù thuyeát...............................................................44

3.1.1.3 Caùc ñoái töôïng lieân keát.................................................................44

3.1.2 Sô ñoà toång quaùt_ Höôùng ñi cuûa chöông trình.....................................47

3.1.3 Chieán löôïc xaây döïng caùc Module ñoäc laäp..........................................48

3.1.4 Chæ daãn baûng thieát keá ........................................................................49

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 91

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

3.2 Chöông 2 : Caáu truùc döõ lieäu cuûa caùc doái töôïng............................................50

3.2.1.Ñoái töïôïng Nfa Baèng hình veõ..............................................................50

3.2.1.1Toå chöùc döõ lieäu vaø caây phaân caáp caùc ñoái töôïng hình ..................51

3.2.2.2 Döõ lieäu vaø thuaät giaûi...................................................................58

3.2.2 Ñoái töôïng DFA baèng hình veõ.............................................................63

3.2.3 Ñoái töôïng NFA lyù thuyeát boä 5............................................................63

3.2.4 Ñoái töôïng DFA lyù thuyeát boä 5...........................................................66

3.2.5 Ñoái töôïng Bieåu thöùc chính qui ..........................................................67

3.2.6 Ñoái töôïng Vaên phaïm chính qui..........................................................68

3.3 Chöông 3 : Caùc giaûi thuaät ...........................................................................70

3.3.1 Trình bieân dòch cho bieåu thöùc chính qui.............................................71

3.3.2 Kieåm tra loãi cho Vaên phaïm chính qui................................................74

3.3.3 Giaûi thuaät xaây döïng DFA töø NFA .....................................................75

3.3.4 Giaûi thuaät ruùt goïn soá traïng thaùi cuûa DFA...........................................76

3.3.4 Giaûi thuaät sinh ra NFA töø Bieåu thöùc chính qui...................................77

3.3.5 Giaûi thuaät sinh ra NFA töø Vaên phaïm chính qui..................................78

3.4 Chöông 4 :Giao dieän chöông trình ..............................................................84

3.4 Chöông 5 :Tìm hieåu Winhelp .Xaây döïng Help- cho öùng duïng....................84

3.5.1 Tìm hieåu Winhelp..............................................................................84

3.5.2 Xaây döïng Help cho öùng duïng ...........................................................85

4 Phaàn boán

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 92

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

Chöông trình nguoàn.....................................................................................89

Heát............................................................................................................198

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 93

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

Lôøi noùi ñaàu

Lyù thuyeát ngoân ngöõ hình thöùc vaø automat laø moân lyù thuyeát baét nguoàn töø

nhöõng nhu caàu moâ phoûng ngoân ngöõ töï nhieân söû duïng trong maùy tính. Ta khoù coù

theå noùi heát nhöõng öùng duïng cuûa moân hoïc lyù thuyeát ngoân ngöõ hình thöùc vaø

automata treân caùc lónh vöïc khaùc nhau cuûa khoa hoïc maùy tính nhö trình bieân

dòch, trong kyõ thuaät nhaän daïng vaø chuyeån ñoåi giöõa caùc ngoân ngöõ khaùc nhau.

Chính vì vieäc nghieân cöùu vaø öùng duïng Lyù thuyeát ngoân ngöõ hình thöùc vaø

automata coù moät vai troø quan troïng nhö theá, neân vieäc xaây döïng moät chöông

trình trôï giuùp hoïc cho moân hoïc naøy seõ coù moät vai troø tích cöïc nhaát ñònh, nhaát laø

ñoái vôùi caùc sinh vieân thuoäc khoa Coâng ngheä thoâng tin. Ngay caû khi chöông trình

ñöôïc xaây döïng vôùi nhieàu haïn cheá, thì noù cuõng seõ ñeå laïi nhöõng kinh nghieäm ñeå

coù theå caûi thieän vaø xaây döïng laïi moät chöông trình toát hôn. Vì nhö ñaõ noùi, vôùi

taàm quan troïng cuûa Lyù thuyeát ngoân ngöõ hình thöùc vaø automata, vôùi söï phaùt

trieån nhö vuõ baõo cuûa lónh vöïc coâng ngheä thoâng tin ngaøy nay, moät chöông trình

höôùng daãn trôï giuùp hoïc moân Lyù thuyeát ngoân ngöõ hình thöùc vaø automata nhaát

ñònh phaûi ñöôïc ra ñôøi vaø seõ lieân tuïc ñöôïc phaùt trieån, naâng caáp cuõng nhö ñöôïc söû

duïng roäng raõi.

Ñaáy cuõng laø muïc ñích cuûa luaän vaên naøy. Coù theå chöông trình ñöôïc xaây

döïng trong luaän vaên chöa phaûi laø moät moâ hình trôï giuùp cho vieäc hoïc toái öu nhaát.

Nhöng vôùi noù chuùng toâi hy voïng raèng caùc baïn seõ ñôõ vaát vaõ nhieàu trong quaù

trình tìm hieåu vaø hoïc hoûi moät soá giaûi thuaät cô baûn cuûa moân Lyù thuyeát ngoân ngöõ

hình thöùc vaø automata. Chöông trình ñöôïc hình thaønh töø nhöõng yù töôûng hoã trôï

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 94

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

vieäc hoïc giuùp caùc baïn hoïc vieân thoâng qua noù ñeå tìm hieåu nhöõng vaán ñeà veà lyù

thuyeát (cuï theå laø söû duïng Help cuûa chöông trình) ; cuõng nhö tham khaûo quaù

trình chaïy giaûi thuaät cuûa maùy tính theo kieåu töøng böôùc ñeå nhaèm naém ñöôïc saâu

hôn noäi dung maø saùch hay giaùo trình cuûa moân hoïc ñöa ra. Chuùng toâi hy voïng

chöông trình trôû thaønh moät coâng cuï kieåm tra baøi taäp vaø töï hoïc caùc giaûi thuaät

trong moân hoïc naøy moät caùch sinh ñoäng nhaàm naâng cao hieäu quaû tieáp thu kieán

thöùc.

Ngoõ haàu ñaït ñöôïc keát quaû mong muoán chuùng toâi ñaõ coá gaéng phaân tích vaø

ñeà ra caùc phöông phaùp thöïc hieän phaàn meàm söû duïng sao cho gaàn guõi vaø thaân

thieän vôùi ngöôøi hoïc. Vôùi söï coá vaán taän tình cuûa Thaày Hoà Vaên Quaân vaø Thaày

Quaûn Thaønh Thô, chuùng toâi coá gaéng taïo ñaày ñuû caùc coâng cuï hoå trôï cho ngöôøi söû

duïng trong khaû naêng cho pheùp cuûa mình. Tuy vaäy, chaéc chaén chöông trình seõ coù

phaàn haïn cheá do nhöõng yeáu toá chuû quan cuûa caùc taùc giaû, nhöng chöông trình coù

theå phaùt trieån thaønh moät chöông trình giaûng daïy hoaøn chænh cuõng nhö coù theå

ñöôïc nghieân cöùu ñeå phaùt trieån vieäc xaây döïng caùc chöông trình trôï giuùp giaûng

daïy cho caùc moân hoïc khaùc.

Thaønh phoá Hoà Chí Minh, 7/99.

Hoïc vieân KS2-K6

Nguyeãn Coâng Minh

Löu Thò Toát

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 95

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

Chöông 1

Moät soá kieán thöùc lyù thuyeát cô baûn cuûa moân hoïc.

1.1.1.Töø ø(word):

♦ Cho ∑ laø baûng chöõ caùi (alphabet) , moät töø w treân ∑ laø 1 chuoãi höõu haïn

caùc chöõ caùi. Ví duï u = aabba , v = ababaa... laø caùc töø treân baûng chöõ caùi

∑ = {a,b}.

♦ Chuoãi roãng cuõng laø 1 töø treân baûng chöõ caùi ∑ , kyù hieäu λ

♦ Toaùn töû keát noái (concatenation) : cho 2 töø u ,v treân baûng chöõ caùi ∑ , keát

noái cuûa u vaø v , kyù hieäu uv laø 1 töø treân baûng chöõ caùi ∑ bao goàm caùc kyù töï

thuoäc u theo sau laø caùc kyù töï thuoäc v .

♦ Moät töø u ñöôïc goïi laø töø con (subword) cuûa töø w neáu w = v1uv2 .Neáu

v1 = λ thì u ñöôïc goïi laø ñoaïn baét ñaàu (initial segment) hay tieàn toá (prefix)

cuûa w.

♦ λ laø töø con cuûa w vaø w laø töø con cuûa chính noù.

♦ Chieàu daøi cuûa 1 töø u kyù hieäu u hay l(u) : laø soá phaàn töû trong chuoãi caùc

kyù töï cuûa noù.

♦ Vôùi moïi töø u,v treân ∑ :

 uv = u + v

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 96

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

 uv = vu

♦ Cho F laø taäp caùc töø treân baûng chöõ caùi ∑ , thì F laø semigroup vôùi toaùn töû

keát noái vaø identity element laø λ. F coøn ñöôïc goïi laø free semigroup treân

∑.

1.1.2. Ngoân ngöõ (language) :

♦ Baát kyø 1 taäp L caùc töø treân baûng chöõ caùi ∑ , hay taäp con L cuûa ∑

*

ñöôïc goïi

laø 1 ngoân ngöõ.

♦ Cho K vaø L laø 2 ngoân ngöõ treân baûng chöõ caùi ∑ :

 KL laø 1 ngoân ngöõ treân ∑ chöùa caùc töø coù ñöôïc baèng caùch noái caùc töø

trong K vôùi caùc töø trong L.

KL = {w : w = uv , u∈ K vaø v∈L}

 L

0

={λ} , L1

= L vaø Ln

= Ln-1L vôùi n>0

 L

*

chöùa taát caû caùc töø maø caùc kyù töï laø thuoäc caùc töø trong L : L

*

L

k

k 0

=

=

∞



1.1.3.Automata (maùy töï ñoäng)

Moät Automata laø moät moâ hình tröøu töôïng cuûa moät maùy tính soá.Automata

coù moät ñôn vò ñieàu khieån (control unit) doø tìm kieåm tra chuoãi nhaäp .

1.1.3.1. Automata höõu haïn ñôn ñònh (dfa or deterministic finite accepter)

1.1.3.1.1. Ñònh nghóa 1:

Moät dfa ñöôïc ñònh nghóa bôûi boä naêm:

M= (Q, ∑ ,δ, q0 ,F)

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 97

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

trong ñoù:

 Q: Taäp höõu haïn caùc traïng thaùi trong.

 ∑: Taäp höõu haïn caùc kyù hieäu nhaäp.

 δ: Q×∑ --> Q laø haøm chuyeån traïng thaùi.

 q0∈ Q: Traïng thaùi khôûi ñaàu.

 F ⊆ Q: Taäp caùc traïng thaùi keát thuùc.

1.1.3.1.2. Hoaït ñoäng cuûa dfa:

Ñoïc caùc kyù töï cuûa chuoãi töø traùi sang phaûi ñoàng thôøi thay ñoåi traïng thaùi ôû

kyù töï cuoái, neáu traïng thaùi trong ∈ F thì chaáp nhaän chuoãi, ngöôïc laïi thì

khoâng.

1.1.3.1.3. Ñònh nghóa 2:

Ngoân ngöõ chaáp nhaän bôûi dfa M= (Q, ∑ ,δ, q0 ,F) laø taäp taát caû caùc chuoãi

treân ∑ ñöôïc chaáp nhaän bôûi M. Bieåu dieãn chính thöùc baèng kí hieäu:

L(M) = {w ∈ ∑

* : δ

*

(q0 ,w) ∈ F }

1.1.3.1.4. Ñònh nghóa 3:

Moät ngoân ngöõ L ñöôïc goïi laø chính qui neáu vaø chæ neáu toàn taïi moät dfa M

naøo ñoù sau cho L = L(M).

1.1.3.2. Automata höõu haïn khoâng ñôn ñònh (nfa or nondeterministic finite

accepter)

1.1.3.2.1.Ñònh nghóa:

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 98

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

Moät nfa ñöôïc ñònh nghóa bôûi boä naêm:

M= (Q, ∑ ,δ, q0,F)

trong ñoù:

 Q: Taäp höõu haïn caùc traïng thaùi trong.

 ∑: Taäp höõu haïn caùc kyù hieäu nhaäp.

 δ: Q×(∑ ∪{λ}) --> 2Q

laø haøm chuyeån traïng thaùi.

 q0∈ Q: Traïng thaùi khôûi ñaàu.

 F ⊆ Q: Taäp caùc traïng thaùi keát thuùc.

1.1.4. Bieåu thöùc chính qui vaø ngoân ngöõ chính qui :

♦ Cho baûng chöõ caùi ∑ vaø 5 kyù töï ñaëc bieät : “(” ,” )” , “+” ,”*” , “λ” . Bieåu

thöùc chính qui r vaø ngoân ngöõ L(r) treân taäp ∑ ñöôïc ñònh nghóa nhö sau :

1. Khoâng coù bieåu thöùc chính qui coù chieàu daøi laø 0

2. Bieåu thöùc chính qui coù chieàu daøi laø1laøλ vaø moïi a∈∑,L(λ) ={λ}

vaø L(a)={a}.

3. Chæ coù 1 bieåu thöùc chính qui coù chieàu daøi laø 2 laø ( ) , vaø ngoân

ngöõ maø noù ñònh nghóa laø taäp roãng.

4. Giaû söû r laø 1 bieåu thöùc chính qui ñònh nghóa ngoân ngöõ L(r) , thì

(r) laø bieåu thöùc chính qui vaø L((r)) = L(r) , vaø (r*) laø bieåu thöùc

chính qui ñònh nghóa ngoân ngöõ L*

5. Giaû söû r1 vaø r2 laø 2 bieåu thöùc chính qui ñònh nghóa ngoân ngöõ L1

vaø L2 , thì (r1+r2) laø bieåu thöùc chính qui ñònh nghóa ngoân ngöõ

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 99

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

L1∪L2 , vaø (r1r2) laø bieåu thöùc chính qui ñònh nghóa ngoân ngöõ

L1L2

♦ Taäp chính qui hay ngoân ngöõ chính qui L:L ñöôïc goïi laø chính qui neáu L

laø ngoân ngöõ ñöôïc ñònh nghóa bôûi bieåu thöùc chính qui r. Nghóa laø toàn taïi

moät bieåu thöùc chính qui r sao cho L =L(r) .

1.1.5.Vaên phaïm chính qui vaø ngoân ngöõ chính qui:

Ñeå nghieân cöùu ngoân ngöõ ,chuùng ta caàn moät cô cheá moâ taû noù. Ngoân ngöõ

haèng ngaøy thöôøng laø khoâng chính xaùc (vì coù theå hieåu theo nhieàu nghóa

tuøy hoaøn caûnh vaø tuøy moãi ngöôøi) vaø nhaäp nhaèng khoâng roõ raøng (caâu coù

theå khoâng xaùc ñònh ñöôïc yù nghóa chính xaùc), vì vaäy chuùng ta seõ hoïc veà

moät vaøi cô cheá ñònh nghóa ngoân ngöõ maø raát höõu hieäu trong caùc tröôøng

hôïp khaùc nhau ñoù laø vaên phaïm.

1.1.5.1.Vaên phaïm:

1.1.5.1.1.Ñònh nghóa 1:

Moät vaên phaïm G ñöôïc ñònh nghóa nhö laø moät boä boán:

G = (V,T,S,P)

trong ñoù:

 V laø moät taäp höõu haïn caùc ñoái töôïng ñöôïc goïi laø caùc bieán

(variable)

 T laø taäp höõu haïn caùc ñoái töôïng ñöôïc goïi laø caùc kí hieäu keát thuùc

(terminal symbol)

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 100

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

 S ∈ V laø moät kí hieäu ñaëc bieät ñöôïc goïi laø bieán khôûi ñaàu (start

variable)

 P laø taäp höõu haïn caùc luaät sinh (production)

Caùc luaät sinh laø traùi tim cuûa vaên phaïm, chuùng chæ ra laøm theá naøo vaên

phaïm bieán ñoåi moät chuoãi thaønh moät chuoãi khaùc , vaø thoâng qua caùch naøy

chuùng (caùc luaät sinh ) ñònh nghóa moät ngoân ngöõ lieân keát vôùi vaên phaïm.

1.1.5.1.2.Vaên phaïm tuyeán tính – Phaûi vaø – Traùi :

1.1.5.1.2.1.Ñònh nghóa 2:

Moät vaên phaïm G = (V,T,S,P) ñöôïc goïi laø tuyeán tính – phaûi neáu taát caû

luaät sinh coù daïng

A → xB,

A → x.

Trong ñoù A,B ∈ V , x ∈ T*

. Moät vaên phaïm laø tuyeán tính – traùi neáu taát caû

caùc luaät sinh laø coù daïng

A → Bx,

A → x.

Moät vaên phaïm chính qui laø vaên phaïm maø hoaëc laø tuyeán tính – phaûi hoaëc

laø tuyeán tính – traùi.

1.1.5.1.2.2.Ñònh lyù:

Moät ngoân ngöõ L laø chính qui neáu vaø chæ neáu toàn taïi moät vaên phaïm chính

qui G sao cho L = L(G).

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 101

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

Chöông 2

Moät soá giaûi thuaät lieân quan.

1.2.1.Chuyeån NFA sang DFA töông ñöông:

1.2.1.1.Giaûi thuaät taäp con (taïo DFA vaø NFA)

 Nhaäp:

Moät automaton höõu haïn khoâng ñôn ñònh nfa goïi taét laø N

 Xuaát:

Moät automaton höõu haïn ñôn ñònh dfa goïi taét laø D nhaän daïng cuøng

moät ngoân ngöõ nhö nfa.

 Phöông phaùp:

Giaûi thuaät naøy laø xaây döïng baûng truyeàn cho dfa. Moãi traïng thaùi

cuûa dfa laø taäp traïng thaùi cuûa nfa vaø ta xaây döïng baûng truyeàn sao

cho dfa moâ phoûng ñoàng thôøi taát caû caùc chuyeån ñoäng cuûa nfa treân

chuoãi nhaäp cho tröôùc.

Chuùng ta duøng caùc taùc vuï sau ñeå löu giöõ caùc taäp trang thaùi cuûa nfa:

Taùc vuï Giaûi thích

-closure(qo) Laø taäp traïng thaùi cuûa nfa, nfa ñaït ñöôïc chuùng töø

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 102

Luaän vaên toát nghieäp KS2 – K6 :

Chöông trình trôï giuùp hoïc moät soá giaûi thuaät trong moân hoïc Lyù thuyeát ngoân ngöõ hình thöùc & OÂtoâmaùt

traïng thaùi qo treân söï truyeàn roãng.

-closure(T) Laø taäp traïng thaùi cuûa nfa , nfa ñaït tôùi chuùng töø

moät traïng thaùi q naøo ñoù cuûa nfa thuoäc T treân söï

truyeàn roãng .

Move(T,a) Taäp caùc traïng thaùi nfa, nfa ñaït ñöôïc chuùng khi

coù söï truyeàn treân kí hieäu nhaäp.

 Phaân tích:

Tröôùc khi ñoïc moät kí töï nhaäp, nfa coù theå ôû moät traïng thaùi baát kyø

trong caùc traïng thaùi thuoäc -closure(q0). q0 laø traïng thaùi baét ñaàu

cuûa nfa. Giaû söû caùc traïng thaùi cuûa T laø caùc traïng thaùi ñaït ñöôïc töø

q0 treân caùc kí töï nhaäp vaø giaû söû a laø kí töï nhaäp keá tieáp. Khi ñoïc a,

nfa coù theå chuyeån ñeán moät traïng thaùi baát kyø trong taäp traïng thaùi

move(T,a). Khi chuùng ta cho pheùp söï truyeàn roãng, nfa coù theå ôû baát

kyø traïng thaùi naøo trong taäp -closure (move(T,a)) sau khi ñaõ ñoïc a.

 Giaûi thuaät: Xaây döïng taäp con

Baét ñaàu -closure(q0) chæ laø moät traïng thaùi trong caùc traïng thaùi

cuûa dfa, chöa ñöôïc ñaùnh daáu.

while coù moät traïng thaùi T. chöa ñöôïc ñaùnh daáu trong dfa do

Begin

Ñaùnh daáu T; {ñaùnh daáu coù nghóa laø ñem T ra xeùt}.

For vôùi moãi kí töï nhaäp a do

SVTH : Nguyeãn Coâng Minh -– Löu Thò Toát GVHD : Quaûn Thaønh Thô - Hoà Vaên Quaân

Trang 103