3. kodutöö: Lõpliku automaadi realiseerimine
Ülesanne on kirjutada lõpuni järgnev klass, mis kujutab endast lõplikku automaati. Selle mõiste definitsioon anti loengus, vt. 27. ja 30. slaidi või Wikipeedia.
See kodutöö on eelnevaga võrreldes raskem ning ei kuulu ka aine põhioskuste hulka, mida me eksamil nõuame. Ühtlasi on see aga ka üks harivamaid kodutöid selles aines. Vähemalt kunagi oli väga hariv, aga nüüd olen selle ära rikkunud igasuguste abimaterjalidega ja Simmo on raamistikkoodi dokumenteerinud...
Kõige esimesed sammud on aga siin kõige olulisemad:
- Mida peab tegema? Kust peab alustama?
- Kuhu peab oma koodi kirjutama???
- Kuidas peaks seda automaati esitama?
Nendega me aitame praktikumides, aga veelkord palun, et prooviksid kõigepealt ise. Lõpp läheb ka algoritmiliselt päris keeruliseks. Ma arvan, et seda on üsna huvitav lõpuni teha, aga need esimesed sammud on kindlasti olulisemad 21. sajandil!
Praktikumides alustame tööd selle kodutööga ja implementeerime AbstractAutomaton klassi alamklassi, mis võimaldab siis automaate ka joonistada. Järgmises kodutöös on meil neid meetodeid ka testimiseks vaja, aga see nädal võib ka lihtsalt järgmiste meetoditega moodle'is üles laadida:
package week3;
public class FiniteAutomaton {
/**
* Selle meetodiga annab automaadi koostaja teada, millised olekud automaadis
* esinevad.
*/
public void addState(int state) {
}
/**
* Selle meetodiga määratakse algolek. Võib eeldada, et eelnevalt on see olek
* automaati lisatud.
*/
public void setStartState(int state) {
}
/**
* Selle meetodiga märgitakse olek lõppolekuks.
*/
public void addAcceptingState(int state) {
}
/**
* Selle meetodiga lisatakse uus üleminek. Epsilon-ülemineku korral on label==null.
* Võib eeldada, et olekud fromState ja toState on juba eelnevalt lisatud.
*/
public void addTransition(int fromState, Character label, int toState) {
}
/**
* See meetod peab ütlema, kas automaat tunneb ära näidatud sisendi.
*/
public boolean accepts(String input) {
return false;
}
}
Kuidas seda klassi peaks saama kasutada?
Kui me tahame kontrollida, kas selline automaat
tunneb ära sõna "cadbbbca", siis võiksime seda teha umbes sellise koodiga:
FiniteAutomaton fa = new FiniteAutomaton();
fa.addState(0);
fa.addState(1);
fa.addState(2);
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);
System.out.println(fa.accepts("cadbbbca"));
Testimine
Selleks, et oma lahendust kontrollida, saate muidugi kasutada avaliku repo teste, aga need testid on mõeldud lahenduse hindamiseks, mitte testimiseks. Oma koodi testimiseks peab ise teste kirjutama! Näiteks saab ülaloleva automaadi testina kirja panna:
@Test
public void testAccepts() {
FiniteAutomaton fa = new FiniteAutomaton();
fa.addState(0);
fa.addState(1);
fa.addState(2);
fa.setStartState(0);
fa.addAcceptingState(1);
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);
assertTrue(fa.accepts(""));
assertTrue(fa.accepts("cadbbbca"));
assertTrue(fa.accepts("bddbcad"));
assertFalse(fa.accepts("bc"));
assertFalse(fa.accepts("kala"));
}
|
|
Väga oluline on jälgida, et olulised üleminekud oleksid testitud. Alati peab proovima tühja sõnega, aga selle konkreetse automaadi puhul on huvitav vaadata, kas automaat algseisundist saab "d"-ga minna lõppseisundisse? Saab küll, sest mitte-deterministliku automaadi korral piisab, kui leidub üks tee lõppseisundisse: 0 → 1 → 0 → 1. Seega, üks hea test on lihtsalt assertTrue(fa.accepts("d")), aga sobib ka "bddbcad".
Kas toString annab oodatud tulemuse?
Kuna loodud automaat väljastatakse oma defineeritud toString() meetodiga, peate olema väga ettevaatlikud, et toString annaks ikkagi oodatud tulemuse. Proovige igaks juhuks paari erineva automaadiga ja kontrollige, et tulemus on õige. Ma olen mitut kodutööd pidanud üle vaatama, kus viga oli selles, et automaat neelab mõne serva ära. Seega, kui üritate epsilon-servadega testidest läbi saada, proovige kõigepealt, et järgmisel automaadil ikkagi oleks neli serva:
FiniteAutomaton fa = new FiniteAutomaton(); fa.addState(0); fa.addState(1); fa.addState(2); fa.addTransition(0, 'a', 0); fa.addTransition(0, 'a', 1); fa.addTransition(0, null, 1); fa.addTransition(0, null, 2); System.out.println(fa.toString());
Märkused ja vihjed
- Esitamise koht: moodle.
- Kui soovid oma lahenduses kasutada nt. Transition klassi, siis lae see samuti ise Moodlesse.
- Deterministlikke automaate saab vaadata kui mittedeterministliku automaadi erijuhte (kui see idee tundub imelik, siis uuri vastavaid definitsioone).
- Osad testid on sellised, kus koostatakse deterministlik lõplik automaat
- Kui sa ei oska kohe kirjutada klassi, mis suudaks esitada kõiki mittedeterministlikke automaate, siis arvesta esialgu ainult deterministlikega.
- Nagu ikka, testime ka selle kodutöö lahendust automaatselt, seega ära muuda meetodite signatuure!
- Te saate eeldada ainult seda, mida on üleval välja toodud. Näiteks ei saa eeldada, et seisundid lisame järjekorras 0,1,2 või seda, et on ainult üks lõppolek. Automaadi seisundid võivad olla näiteks 17, 3 ja 0, kusjuures 3 on algolek ja kõik kolm on lõppolekud.
- Testime ainult automaadi välist käitumist. Kõigepealt loome automaadi ja testime, et nende käskudega loodud automaat käitub nii nagu ta peab. Kõik meie testid on ülal oleva näite kujul: loome selle liidese kaudu automaadi ja seejärel testime ainult, et automaat õigeid sõnu ära tunneks.
- Meil on üks test, kus sisendiks on natuke pikem tekst. See on täpselt piisavalt pikk, et rekursiivne lahendus, kus rekursiooni sügavus kasvab sisendi pikkusega, viskab meie viimase testi juures StackOverflowException või OutOfMemoryError. Täiuslikkuseks saamiseks peab ülesande lahendus olema nii implementeeritud, et rekursiooni sügavus ei sõltuks sisendi pikkusest.
- Kui tekib probleeme, siis küsi Zulipis!