Automaadid, keeled ja translaatorid - Kursused

NFA esitamise ehitusklotsid

NFA on defineeritud kui viisik, milles on meie jaoks kõige tähtsam see üleminekurelatsioon. Esimene samm on seega otsustada, kuidas seda esitada. Siin vaatame ainult kaht esitust, aga tegelikult on palju teisi võimalusi, mida võiksite ise mõelda ja praktikumis võib seda arutada...

1. Transition.java

Kõige otsesem viis on üleminekurelatsiooni esitada lihtsalt üleminekute hulgana. Sealt asju üles otsida võib aga pärast olla natuke tüütu. Kui oletada, et automaat on deterministlik, siis võib seda relatsiooni esitada funktsioonina.

Mõtleme näite peale. Kui üleminekurelatsioon on { (1, a, 2), (1, b, 3), (2, c, 3) }, siis seda saab ka esitada funktsioonina f, millel kehtib näiteks f(1,a) = 2, aga sellist kahe argumendiga funktsiooni esitame Javas nii, et f(1) tagastab uue funktsiooni f₁ ja f(2) funktsiooni f₂, mis kirjeldavad, mis nendes seisundites toimub iga tähe jaoks:

Üleminekute hulk	Funktsioonina
(1, a, 2)	f(1) = f₁ ja f₁(a) = 2
(1, b, 3)	f(1) = f₁ ja f₁(b) = 3
(2, c, 3)	f(2) = f₂ ja f₂(c) = 3

Implementeerige funktsioon makeTransitionMap, mis teisendab üleminekute hulga selliseks funktsiooniks (Map).

2. FiniteAutomaton.java

Nüüd võib kätte võtta ja hakata FiniteAutomaton.java failis kodutööd lahendama. Soovitame alustada kõigepealt täiesti korrektse deterministliku automaatiga. Implementeerime siin abstraktse klassi AbstractAutomaton kõik meetodid. Piilumeetodeid (gettereid) ei ole selle nädala kodutöö lahendamiseks otseselt vaja, aga nende kaudu saab automaati joonistada. See võib olla vigade avastamiseks väga suureks abiks!

Abstraktses klassis on implementeeritud meetod, mis nende piilumeetodite abil automaadi joonistab. FiniteAutomaton klassis on main meetodis väike näide, kuidas seda kasutada. Kui kõik töötab, siis automaat joonistatakse faili "auto.png" kataloogis "graphs" (mis asub projekti juurkataloogis).

    public static void main(String[] args) {
        FiniteAutomaton fa = new FiniteAutomaton();
        fa.addState(0, false);
        fa.addState(1, true);
        fa.addState(2, false);
        fa.addTransition(0, 'b', 0);
        fa.addTransition(0, 'c', 2);
        fa.addTransition(2, 'a', 1);
        fa.addTransition(1, 'd', 0);
        fa.addTransition(0, null, 1);
        fa.setStartState(0);
        fa.addAcceptingState(1);
        // Joonistame automaadi:
        fa.renderPngFile(Paths.get("graphs", "auto.png"));
    }

Plaani järgi jõuame praktikumides selle ülesande enam-vähem nii kaugele, et DFA testid lähevad läbi. Edasi võiksid nüüd kodus proovida lahenduse NFA peale üldistada. Kui jääd sellega hätta, siis on meil siin lehel mõned abistavad ülesanded veel. Nende lahendused paneme "sols" kataloogi!

3. Person.java

Kui said DFA-ga hakkama, siis jääb see mure, et tegelikult võib ju ühest olekust sama tähega välja minna mitu serva... Ma kardan, et see on ületamatu probleem, mistõttu repos on hoopis teine ülesanne, kus tuleb mingite inimeste hulkadest map teha. (Tegelikult on muidugi täpselt sama probleem siin ja loodetavasti saad selle põhjal ka oma DFA teisendada NFAks.)

Siin võib olla abiks ka guava teegi kasutamine. Guava on ka moodle'is olemas ja seda võib kodutöös julgelt kasutada, aga reeglina on väga hea kui endal on ettekujutus, mis see teek meie jaoks ära teeb. Mõistlik on seega Person.java ülesanne kõigepealt ise ka puhta Javaga ära lahendada.

4. TransitionUtils.java

NFA realiseerimise kõige keerulisem osa on epsilon-servadega automaadid, et epsilon-tsüklite korral mitte lõpmatult mööda tsüklit liikuda. Siin on oluline kõigepealt ise mõelda oma lahendus, sest seda ei pea nüüd tingimata õpiku moodi tegema. Sulundi arvutamine on aga lihtsam ja kui nende epsilonide pärast läheb Sinu lahendus väga käest ära, siis võib proovida ühe teise sulundi arvutada. Loengus mainiti, et automaadi keel on tema üleminekurelatsiooni refleksiivne transitiivne sulund. Võime proovida sellist sulundit kõigepealt arvutada. Selle lahendus on ka repos olemas ja tasub vaadata loengu slaide sulundi kohta.

NB! Üleminekurelatsiooni transitiivse sulundi arvutamine ei termineeru, kui automaadis esinevad tsüklid. Me arvutame siin sisuliselt relatsioonina terve lõpmatu keele. Epsilon-sulundi arvutamine töötab alati, sest see kogub ainult automaatide seisundeid ja neid ei ole lõpmata palju. Seega võid siinses transitiivse sulundi ülesandes eeldada, et automaadis ei esine tsükleid, aga samasugune kood töötab epsilon-sulundi puhul ka tsüklitega automaadis.