4. 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. teine ja kolmas slide või Wikipeedia.
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 ülesse laadida:
package week4;
public class FiniteAutomaton {
/**
* Selle meetodiga annab automaadi koostaja teada, millised olekud automaadis
* esinevad. isAcceptingState ütleb, kas tegemist on lõppolekuga.
*/
public void addState(Integer stateId, boolean isAcceptingState) {
}
/**
* Selle meetodiga määratakse algolek. Võib eeldada, et eelnevalt on see olek
* automaati lisatud.
*/
public void setStartState(Integer id) {
}
/**
* 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(Integer fromState, Character label, Integer toState) {
}
/**
* See meetod peab ütlema, kas automaat tunneb ära näidatud sisendi.
*/
public boolean accepts(String input) {
return false;
}
/**
* Seda meetodit ei hinnata ja seda ei pea muutma, aga läbikukkunud testide korral
* antakse sulle automaadi kirjelduseks just selle meetodi tagastusväärtus.
*/
@Override
public String toString() {
return super.toString();
}
}
Kuidas seda klassi peaks saama kasutada?
Kui me tahame kontrollida, kas selline automaat
tunneb ära sõna "cadbbbca", siis võiks me seda teha umbes sellise koodiga:
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);
boolean result1 = fa.accepts("cadbbbca");
boolean result2 = fa.accepts("abc")
Testimine
Selleks, et kontrollida oma lahendust, 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, false);
fa.addState(1, true);
fa.addState(2, false);
fa.setStartState(0);
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 ikkagi toString annaks 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, false); fa.addState(1, true); fa.addState(2, true); 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
Testid on ainult indikatiivsed. Me üritame võimalikult head testid välja panna, aga testimine ei ole kunagi täielik ja lõpliku hinde paneb praktikumijuhendaja. Me üldiselt ei hinda stiili, aga koodi loetavus on oluline ja võime punkte maha võtta, kui lahendus on meile täiesti arusaamatu.
- Esitamise koht: moodle.
- 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 ainult deterministlikega -- kui see töötab korralikult, siis saab juba selle eest osa punkte.
- 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.
- Me testime ainult automaadi välist käitumist. Me 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äispunktide saamiseks peab ülesande lahendus olema nii implementeeritud, et rekursiooni sügavus ei sõltuks sisendi pikkusest.
- Kui tekib probleeme, või kui pead vajalikuks lahenduse kirjutamisel kasutada mingit kolmanda osapoole teeki, siis küsi fleepis!