Säännöllisen lausekkeen muuntaminen automaatiksi

Näytämme, miten mikä tahansa säännöllinen lauseke muunnetaan epädeterministiseksi äärelliseksi automaatiksi.

Esimerkki

Ennen kuin kuvaamme itse algoritmin, näytämme esimerkillä, mistä oikeastaan on kyse. Olkoon meillä tämä säännöllinen lauseke: a(b|c)x^∗. Sanoin kuvaisimme säännöllisen lausekkeen tuottaman kielen sanoiksi, jotka alkavat kirjaimella ”a”, sen jälkeen tulee joko kirjain ”b” tai ”c” ja sitten mikä tahansa määrä kirjaimia ”x”. Osaisimmeko rakentaa automaatin, joka hyväksyisi tämän kielen? Kyllä vain, katso:

Tämä automaatti hyväksyy selvästi saman kielen. Herää kysymys, onko jokaiselle säännölliselle lausekkeelle olemassa automaatti, joka hyväksyy kyseisen kielen. No, on.

Säännöllisen lausekkeen muuntaminen automaatiksi: algoritmin kuvaus

Oletamme, että syötteenä on säännöllinen lauseke R. Aiemmasta säännöllisiä lausekkeita käsittelevästä osasta tiedämme, että säännöllisellä lausekkeella voi olla yhteensä kuusi eri muotoa. Erotamme siis kuusi eri tapausta:

1. R = a jollekin symbolille a ∈ Σ. Eli säännöllinen lauseke on vain yksi aakkoston Σ symboli, jonka yllä työskentelemme. Automaatti, joka hyväksyisi yhden symbolin a, näyttäisi tältä:

   

2. R = ϵ, tyhjä sana. Automaatti, joka hyväksyisi tyhjän sanan, näyttäisi tältä:

   

3. R = ∅, säännöllinen lauseke, joka tuottaa tyhjän kielen. Automaatti, joka tunnistaisi tällaisen kielen, on tämä:

   

4. R = R₁ ∪ R₂, jossa R₁, R₂ ovat säännöllisiä lausekkeita. Tiedämme jo, että säännöllisten kielten yhdiste on jälleen säännöllinen kieli ja että pystymme rakentamaan automaatin, joka hyväksyy sellaisen kielen. Toisin sanoen oletamme, että meillä on automaatit, jotka tunnistavat lausekkeiden R₁ ja R₂ tuottamat kielet, ja niiden avulla rakennamme automaatin, joka hyväksyy lausekkeen R₁ ∪ R₂ tuottaman kielen. Esimerkki: jos R₁ = a ja R₂ = ϵ, saamme menetelmän mukaan tämän automaatin:

   

5. R = R₁ ∘ R₂, jossa R₁, R₂ ovat säännöllisiä lausekkeita. Sama tapaus kuin edellisessä kohdassa. Säännöllisten kielten konkatenaatio on säännöllinen kieli, ja pystymme siis rakentamaan automaatin, joka hyväksyy sellaisen kielen. Jos siis R₁ = a, R₂ = b, konkatenaatio näyttäisi tältä:

   

6. $R=(R_1^{\ast })$, jossa R₁ on säännöllinen lauseke. Tiedämme taas, että säännöllisen kielen Kleenen tähti on säännöllinen kieli. Jos siis R = a^∗, automaatti näyttäisi tältä:

   

Soveltamalla näitä kohtia vähitellen muunnamme koko säännöllisen lausekkeen äärelliseksi automaatiksi.

Kokonainen esimerkki

Yritetään muuntaa säännöllinen lauseke (a|bc)^∗. Saamme vähitellen nämä automaatit:

Tämä tuloksena syntyvä automaatti hyväksyy kielen, jonka säännöllinen lauseke (a|bc)^∗ tuottaa. Automaatti on tietenkin hirvittävän monimutkainen, ja varmasti on olemassa paljon yksinkertaisempi automaatti, joka hyväksyy saman kielen. Voimme käyttää NFA:n muuntamisen DFA:ksi algoritmia ja sen jälkeen tehdä automaatin minimoinnin.

Lähteet

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools