Kursuse kodulehekülg Viimati muudetud: 12.3.2003 kell 11.00

Loeng 2 - Regulaaravaldistega otsimine

  1. Mis on regulaaravaldised
  2. Kordus automaatide kohta
  3. Mittedeterministlikud automaadid (NFA)
  4. NFA Determiniseerimine
  5. Automaadi minimiseerimine
  6. Deterministlikud automaadid (DFA)
  7. Teisenduskaugus

Lisamaterjale

Tagasi

Mis on regulaaravaldised

Esimeses loengus kirjeldasime täpset otsimist olukorras kus otsitav oli kas üks konkreetne sõne või sõnede hulk. Nüüd üldistame otsmist nii et otsitav on esitatud regulaaravaldisena.

Definitsioon Regulaaravaldised (RE) on

  1. ∅ on RE; ∅ on tühi sõnede hulk
  2. ε on RE; ε esitab hulka {ε}, ε on tühi sõne
  3. Iga a ∈ Σ on RE, a esitab hulka {a}
  4. Kui A ja B on RE ja L(A) ja L(B) on keeled mida need esindavad, siis on regulaaravaldised ka:
    1. (A + B), ühend, L(A + B) = L(A) ∪ L(B)
    2. (AB), konkatenatsioon, L(AB) = L(A)L(B)
    3. (A*), sulund, L(A*) = L(A)*
Ülesandepüstitus

P1 lahendus: moodusta mittedeterministlik automaat MA nii et L(MA) = L(Σ* A) ja otsi sellega S-is. Alati kui MA on lõppolekus on leitud üks keele L(A) alamsõne lõpp-positsioon S-is.

P2 lahendus: moodusta MA nii et L(MA) = L(A). Sobita MA S peale.

P1 on P2 erijuht. Edaspidi vaatame vaid P2-e.

(A+B) võib esitada ka (A ∪ B) või (A|B)
Tagasi

Kordus automaatide kohta

Lõplikud automaadid (finite automaton) leiavad kasutust olukordades kus arvutusprobleemid saavad olla vaid teatud lõplikus arvus olekutes. Lõplikke automaate võib esitada mitmel eri kujul millest olekudiagrammid (transition state diagrams).

DFA = Deterministic Finite Automaton

Definitsioon (DFA) Lõplik automaat (ingl. finite automaton) on viisik M=( Q, Σ, δ, q0, F ), kus

Automaadi kasutamine:

Näide: märgiga täisarvu äratundmine

Tagasi

Mittedeterministlikud automaadid (NFA)

NFA = Nondeterministic Finite Automaton

Definitsioon (NFA) Mittedeterministlik lõplik automaat (ingl. nondeterministic finite automaton) on viisik M=( Q, Σ, δ, q0, F ), kus

Automaadi kasutamine:

Automaadi konstruktsioon: Regulaarsest avaldisest mittedetermineeritud automaadi moodustamine (Meelis Roos) (kohalik)

Tsitaat:

Kasutame Thompsoni konstruktsiooni. Selle konstruktsiooni idee on seada igale regulaaravaldises esineda võivale operatsioonile vastavusse primitiivne automaat. Kogu avaldisele vastab primitiivsete automaatide lihtne kompositsioon. Korduvatele alamavaldistele seatakse vastavusse mitu vastavalt mitu primitiivset automaati, mingit optimiseerimist siin ei toimu.

Nii saadud lõplik automaat pole determineeritud, kuna me kasutame juba primitiivsetes automaatides mittedetermineeritust. Lõpliku automaadi võib hiljem muidugi eraldi determineerida.

Primitiivsed automaadid.

Igal primitiivsel automaadil on oma algolek i ja lõppolek f. Iga uue primitiivse automaadi koostamisel võtame kasutusele uue alg- ja lõppoleku. Hiljem kompositsiooni juures võivad mõned neist seisunditest osutuda üleliigseks, siis viskame nad lihtsalt minema.
  1. Tühjale sümbolile e seame vastavusse järgmise automaadi:
    Joonis 1
  2. Igale kasutatavale terminaalsele sümbolile a seame vastavusse automaadi
    Joonis 2
  3. Avaldises r esinevatele valikutele s|t seame vastavusse järgmised automaadid (kus N(s) ja N(t) on s ja t vastavad lõplikud automaadid):
    Joonis 3
  4. Avaldises r esinevatele konkatenatsioonidele st seame vastavusse järgmised automaadid:
    Joonis 4
  5. Avaldises r esinevate korduste s* seame vastavusse sellised automaadid:
    Joonis 5
  6. Alamavaldistele kujul (s) seame vastavusse sama automaadi, mis s-le, s.t. N(s).

Näide.

Võtame regulaarse avaldise a*(ba|c) ja konstrueerime sellele avaldisele vastava mitteetermineeritud lõpliku automaadi.

Kõigepealt moodustame 2. reegli järgi primitiivsed automaadid lihtsamatele osalausetele a ja c. 4. reegli abil saame a ja b jaoks konkatenatsioonile vastava automaadi. Igaühe jaoks võtame kasutusele uued olekud, mis omavahel ei kattu:

Näide, joonis 1
5. reegli abil saab esimese a arendada edasi a*-ks:
Näide, joonis 2
Nüüd ühendame ba ja c automaadid 3. reegli abil:
Näide, joonis 3
Ja lõpuks võimegi kõik vajalikud jupid 4. reegli abil kokku kombineerida. Saam järgmise automaadi:
Näide, joonis 4
See ongi üks võimalik mittedetermineeritud lõplik automaat, mis vastab meie poolt uuritud avaldisele.

Tekstist otsimine automaadiga MA 

 
NFA simuleerimine


Sisend:  NFA MA=( Q, Σ, δ, q0, F ), Tekst S = s[1..n]
Väljund: Olekute jada Q0, Q1, ... Qn
NB: S ∈ L(MA) ainult kui F ⊆ Qn. 
    Jada queue ja hulgad Qi on alguses tühjad

1. for i = 0 to n do 
2.     märgi kõik q ∈ Q saavutamatuks
3.     if i == 0 then   Q0 = { q0 };  queue = { q0 };  märgi q0 saavutatuks
4.     else
5.          for q ∈ Qi-1 		// Päris siirded s[i]-ga
6.               for p ∈ δ(q, s[i])
7. 			if p pole veel saavutatud
8. 			 	Qi = Qi ∪ { p } 
9.				push( queue, p )
10. 				märgi p saavutatuks
11.    while queue ≠ ∅ 
12. 	   q = take( queue ) 
13.        for p ∈ δ(q, ε ) 		// ε - siirded 
14. 	 	if p pole veel saavutatud
15.		     Qi = Qi ∪ { p }
16.		     push( queue, p )
17.		     märgi p saavutatuks
Teoreem NFA simuleerimise ajaline keerukus on O( || MA || ⋅ n ) kus ||MA|| on MA olekute ja siirete kogusumma ja ||MA|| ≤ 6 |A|.

Tõestus - ühe sammu jooksul käsitletakse kõiki olekuid ja siirdeid vaid üks kord, sest nad märgitakse kohe saavutatuks. Kokku sooritatakse samme n tk. Automaadi suurus on varasemat konstruktsiooni kasutades ≤ 6 |A| kus |A| on regulaaravaldise A pikkus.
Tagasi

NFA Determiniseerimine

Eesmärk on korvata ε-siirded ning jätta igast olekust iga märgiga vaid üks võimalik siire.

Esita kõikide algse automaadi mingil hetkel saavutatavate olekute hulgad uue automaadi olekutena. Iga erinev hulgakombinatsioon defineerib uue oleku deterministlikus automaadis.

Automata for Matching Patterns Handbook of Formal Languages (kohalik)

Vt. ka soomekeelne konspekt
Tagasi

Automaadi minimiseerimine

Automaadi minimiseerimine (koopia)
Tagasi

Deterministlikud automaadid (DFA)

Tavaliselt konstrueeritakse kõigepealt regulaaravaldisest NFA ja siis see determiniseeritakse.

Saab ka otse - kasutades McNaughtoni ja Yamada konstruktsiooni et teha regulaaravaldisest otse DFA.

Näide: Vaatame avaldise re = (a &cup b)*aba teisendamist.

Tagasi

Teisenduskaugus

Teisenduskaugus on eraldi loengu teema. Olgu vaid öeldud, et stringide y ja z vaheline teisenduskaugus on minimaalne arv teisendusi mis tuleks teha ühele stringile (näiteks y) et saada teist (z). teisendused on ühe tähe välja viskamine, ühe tähe juurde panemine, või he tähe asendamine teisega.

ABC -> ABBC saadakse ühe B lisamisega,

ABC -> AC saadakse B eemaldamisega

ABC -> ABB saadakse C asendamisega B-ga.

Kõik stringid mis on genereeritavad näiteks ABC-st ühe teisendusoperatsiooniga võiks üles lugeda ning nendest moodustada lõpliku automaadi:

ABC => AB, AC, BC, AB[AB], A[AC]C, [BC]BC, AABC, ABAC, ABCA, BABC, ABBC, ABCB, CABC, ACBC, ABCC

Järgmistes loengutes vaatleme teisenduskauguse arvutamise meetodeid ja ligikaudset otsimist (vastavalt ette antud teisenduskauguse limiidile).
Tagasi
EOF