Programmering för språkteknologer II. HT 2009.

Laboration: ändliga automater och reguljära uttryck

• Kod att börja med. (Tänk på det där med paket. Pröva lösningen av del (a) med TestFSA.java, som förutsätter att den är löst)
• Relevanta overheadbilder

Utgå från given klass FSA (för Finite State Automaton). Konstruktorn FSA(String file) skapar en FSA genom att läsa in en textfil (file är filnamnet) som definierar en deterministisk FSA enligt OH-bildernas syntax och lagrar informationen på ett användbart sätt.

(a) Skriv en metod som säger om automaten accepterar en sträng eller inte:

public boolean accepts(String input)

Relativt lätt.

(b) Skriv en metod som givet en LinkedList av strängar returnerar en LinkedList med dem av strängarna som automaten accepterar.

public LinkedList<String> filter(LinkedList<String> strings)

Lättare?

(c) Uppgiften handlar om datumangivelser av typen 090917. Låt oss glömma skottåren och anta att februari alltid har 28 dagar och låt oss kräva att dagssiffrorna skall stämma med månaden. T.ex. är 100431 fel. (De två första siffrorna kan vara godtyckliga.) Nedan har vi en lista med acceptabla sådana och en med oacceptabla. Skriv en automat som skiljer de acceptabla från de oacceptabla. Skriv även ett reguljärt uttryck som gör precis samma klassificering som automaten.

090131
090228
090917
090930
091231

090100
090132
090230
090431
091301

Lite mer spaghettiartat?

(d) Skriv ett program som givet en automat (hanterad som ovan), ett reguljärt uttryck, och en godtycklig fil med ord (textfil, ett ord per rad), kontrollerar att automaten och uttrycket är överens om vartenda av dessa ord. Om de inte är det skall programmet skriva ut en "protest".

Lite pyssligt.

VG-uppgifter, en räcker för VG på labmomentet

(e1) Gör som uppgift (a) men modifiera programmet så att det kan hantera automater som är icke-deterministiska på så sätt att det kan finnas övergångar till flera tillstånd från ett givet tillstånd och en given symbol.

Mer krävande.

(e2) Skriv en metod som givet en heltal int returnerar en LinkedList<String> med alla de strängar som automaten accepterar och vars längd är lika med det givna heltalet eller mindre (kortare).

public LinkedList<String> generate(int length)

Mer krävande.