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 esitada üleminekurelatsiooni on 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 f1 ja f(2) funktsiooni f2, mis kirjeldavad, mis nendes seisundites toimub iga tähe jaoks:
| Üleminekute hulk | Funktsioonina |
|---|---|
| (1, a, 2) | f(1) = f1 ja f1(a) = 2 |
| (1, b, 3) | f(1) = f1 ja f1(b) = 3 |
| (2, c, 3) | f(2) = f2 ja f2(c) = 3 |
Implementeerige funktsioon makeTransitionMap, mis teisendab üleminekute hulga selliseks funktsiooniks (Map).
2. FiniteAutomaton.java
Nüüd võib kätte võtta ja FiniteAutomaton.java failis hakkata kodutööd lahendama. Soovitame alustada kõigepealt täiesti korrektse deterministliku automaatiga. Implementeerime siin abstraktse klassi AbstractAutomaton kõik meetodid. Piilumeetodid (getterid) ei ole otseselt vaja selle nädala kodutöö lahendamiseks, aga nende kaudu saab automaati joonistada. See võib olla väga suureks abiks vigade avastamiseks!
Abstraktses klassis on implementeeritud meetod, mis nende piilumeetodite abil joonistab automaati. FiniteAutomaton klassis on main meetodis väike näide, kuidas seda kasutada. Kui kõik töötab, siis automaat joonistatakse faili "auto.png" 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);
// Joonistame automaati:
fa.createDotFile("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 proovida NFA peale kodus ü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 hakkama DFA-ga, 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 allolev teek meie jaoks ära teeb. Mõistlik on seega Person.java ülesandes ise ka puhta Javaga kõigepealt ära lahendada.
4. TransitionUtils.java
NFA realiseerimise kõige keerulisem osa on epsilon-servadega automaate, et epsilon-tsüklite korral mitte lõpmatult mööda tsüklit liikuda. Siin on oluline kõigepealt ise mõelda oma lahenduse, sest seda ei pea nüüd tingimata õpiku moodi tegema. Sulundi arvutimine 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 arvatada. 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.