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. Trans.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. DFA lahendamine
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. Relation.java
Mida nüüd teha nende neetud epsilon-servadega?? Siin on eriti oluline kõigepealt ise mõelda, sest seda ei pea nüüd tingimata õpiku moodi tegema. See on siiski lihtsam ja kui nende epsilonide pärast läheb lahendus väga käest ära, siis võib proovida transitiivset sulundit kõigepealt arvutada. Selle lahendus on ka repos olemas ja tasub vaadata loengu slaide sulundi kohta.
NB! Transitiivne sulundi arvutamine ei termineeru, kui automaadis esinevad tsüklid, aga epsilon-sulundi arvutamine töötab alati, sest epsilon-sulund kogub automaatide seisundeid ja neid ei ole lõpmatu palju. Seega võid transitiivse sulundi ülesandes eeldada, et automaadis ei esine tsükleid, aga selline kood töötab epsilon-sulundi puhul ka tsüklitega automaadis.