Automaadid, keeled ja translaatorid

jFlap tutvustus

JFLAPi installeerimine:

• Lae alla JFLAP.jar (9MB).
• Käivita topeltklõpsuga või java -jar JFLAP.jar
• Iseseisvaks uurimiseks soovitame nende tutorial ja videod.
• NB! JFLAP kasutab regulaaravaldistes | asemel + ja epsiloni tähis on ! (hüüumärk)

Automaadi koostamine ja käivitamine

• Vajuta algusaknas nuppu "Finite Automaton".
• Joonistame mitte-deterministliku automaadi, mis tunneb ära kõik 'a' ja 'b'-dest koosnevad sõnad, mille eelviimane täht on 'a' ehk regulaaravaldis "(a|b)*a(a|b)".
• Käivitame selle valides menüüst "Input" → "Step with Closure..." ja proovi käivitada sisendiga abbab
• Joonistame mõne epsilon-üleminekuga automaadi. Kõige loomulikum viis selleks on jFlap'i abil see genereerida. Seega, võtame algusmenüüst hoopis "Regular Expression" (alt kolmas nupp) ja sisestame (a+b)*b ja siis valime menüüst "Convert" → "Convert to NFA".
• Proovime käivitada nii "Step by State..." kui ka "Step with Closure..." abil. Esimesel juhul ei pea lõpuni tegema, sest tähtis on siin peamiselt nende erinevusest aru saada.

Automaatide harjutused

Proovime nüüd disainida mõned automaadid.

1. Sõnad üle tähestiku {a,b}, mis sisaldavad alamsõnena "aba" ehk regulaaravaldis "(a|b)*aba(a|b)*".
2. Sõnad üle tähestiku {a,b}, mis sisaldavad täpselt ühe 'a'.
3. Sõnad üle tähestiku {a,b}, kus igale 'a'-le järgneb varem või hiljem vähemalt üks 'b'. Selline lause, nagu matemaatikas ikka, ei välista seda, et sõnes ei esine ühtegi 'a'. Keelde kuulub seega ka tühi sõne ja lihtsalt 'b'.
4. Sõnad üle tähestiku {a,b,x}, kus iga 'b' kõrval on 'a', s.t. kas vahetult enne või järel.
5. Sõnad üle tähestiku {a,b}, kus 'a' ega 'b' ei kordu, s.t. sõne on tühi või 'a' ja 'b'-d tulevad vaheldumisi.
6. Sõnad üle tähestiku {a,b}, mis ei sisalda alamsõne "aba". (NB! Selle lahendamine on lihtne, kui teisendada automaat deterministlikuks.)
7. Sõnad üle tähestiku {a,b}, mis sisaldavad alamsõnena "aba" ja kus igale 'a'-le järgneb varem või hiljem vähemalt üks 'b'.
   (Automaatide 1. ja 3. keelte ühisosa.)

Kontrolltöö/eksami automaatide ülesannete näidiskomplekt:

8. Sõnad üle tähestiku {a,b}, mis sisaldavad alamsõne "bb".
9. Sõnad üle tähestiku {a,b}, mis sobituvad regulaaravaldisega "(a*b)*".
10. Sõnad üle tähestiku {a,b}, milles on mõlemat tähte vähemalt üks.
11. Sõnad üle tähestiku {a,b}, mis sobituvad regulaaravaldisega "(a*b)*" või milles on mõlemat tähte vähemalt üks.
    (Automaatide 9. ja 10. keelte ühend.)
12. Sõnad üle tähestiku {a,b}, mis sisaldavad alamsõne "bb" ja sobituvad regulaaravaldisega "(a*b)*".
    (Automaatide 8. ja 9. keelte ühisosa.)

NB! Kasuta failinimesid kujul yl<ülesande nr>.jff nt. yl1.jff. Praktikumi ülesanded saab ka enda arvuti peal testida:

• Pane kõik oma lahendused kausta src/main/jflap/week3/praks/.
• Käivitada tuleb siis src/test/java/week3/JFlapEquivalenceTester, mis võrdleb meie näidislahendustega (need on juba src/test/jflap kataloogis olemas.)

JFlap lisatöö (eksamiks harjutamine)

Koosta JFLAP-is järgenevatele kirjeldustele vastavad lõplikud automaadid ja lae failid Moodle'isse. Nende lahendused ei ole meil repos, seega peab seda moodle'is testima. Eksamil on identne olukord. Automaatide eest võib eksamil saada kuni 10 punkti, mistõttu soovitame juba praegu seda harjutada!

NB! JFlap lubab teha ka üleminekuid, mis loevad sisendist korraga mitu tähte, aga automaatkontroll ei saa selliste üleminekutega hakkama. Seepärast ärge oma lahendustes sellist võimalust kasutage.

Kasuta failinimesid kujul yl<ülesande nr>.jff nt. yl1.jff.

1. Sõnad üle tähestiku {a,b}, mis algavad või lõppevad tähega 'a'.
2. Sõnad üle tähestiku {a,b}, mis algavad ja lõppevad tähega 'a', muuhulgas "a" ise.
3. Sõnad üle tähestiku {a,b}, mis sisaldavad vähemalt üks 'a'.
4. Sõnad üle tähestiku {a,b}, mis sisaldavad vähemalt üks 'a' ja täpselt üks 'b'.
5. Sõnad üle tähestiku {a,b}, mis sisaldavad vähemalt üks 'a' ja paaritu arv 'b'-sid.

Viimane ülesanne on selline, kus on vaja leida kahe keele ühisosa. Konkreetse ülesanne puhul saab seda intuitiivselt lahendada, aga on olemas ka kindel konstruktsioon. Selle idee on tegelikult üsna elementaarne: tuleb simuleerida kahe automaadi samaaegset käivitamist!

• Kõige parem oleks, kui prooviksid ise seda konstruktsiooni välja nuputada.
• Siis võib vaadata loengu video. Kes soovib formaalsemalt, võib vaadata definitsiooni, aga see võib jätta mulje nagu see oleks keeruline... see on tegelikult lihtne ja loomulik!
• Ühisosa saab ka ühendi ja eituse kaudu väljendada. Sel juhul peab kindlasti iga eituse jaoks automaadi deterministlikuks täielikuks automaadiks teisendada! Kuna JFLAP oskab seda pool-autoomaatselt teha, siis see protsess vajab natuke vähem mõtlemist. Selge kokkuvõtte nende mõlema lähenemise kohta on selles videos.