Automata, Languages and Compilers 2018/19 spring

jFlap tutvustus

JFLAPi installeerimine:

• Lae alla JFLAP.jar (9MB).
• Käivita topeltklõpsuga või java -jar JFLAP.jar
• Iseseisvaks uurimiseks soovitame http://www.jflap.org/tutorial/
• 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.)

Lahendusfaile (*.jff) saab kontrollimiseks üles laadida siin. NB! Kasuta failinimesid kujul yl<ülesande nr>.jff nt. yl1.jff. Praktikumi ülesanded saab ka enda arvuti peal testida:

• Pane kõik oma lahendused kaustas src/main/jflap/praks/ ja nimeta neid samamoodi nagu moodle'i jaoks.
• Käivitada tuleb siis src/test/java/week3/JFlapEquivalenceTester, mis võrdleb meie näidislahendustega (need on juba test/jflap kataloogis olemas. Kodutöö seega niimoodi testida ei saa.)
• Palume oma lõpptulemus igal juhul moodle'isse üles laadida. See ei anna otseselt siin punkte, aga see võib kaudselt mõjutada punktide ümmardamise kvantalgoritmi.