Laboration 2: Språket för en DFA

Skriv ett program i Java (eller C) som accepterar en beskrivning av en deterministisk ändlig automat M = (K, , , s, F) som indata och som utdata producerar ett reguljärt utryck, som representerar språket L(M).

Programmet ska innehålla lämplig kontroll av indata, M kan begränsas på ett lämpligt sätt, till exempel genom att anta att |K|<5 , |F|<2. Det reguljära uttrycket som utgör utdata behöver inte förenklas

Programmmet skall läsa in en indatafil som definierar en dfa. Detta åstadkommes endera genom att filnamnet ges som argument till programmet vid körning, eller att programmet frågar efter filnamn. Indatafilen har följande format:

s f
a b
s
f
s a s
s b f
f a f
.
.
f b s

Där första raden representerar K (tillstånden), andra raden (alfabetet), tredje raden s (starttillståndet), fjärde raden F (måltillståndet). De resterande raderna (okänt antal) är (transduktionsreglerna).

Här är några exempel på dfa filer du kan testa ditt program med:

Exempel 1:
M1.txt bör ge följande utdata:
a*b(aUba*b)*
Där även (a*b)*(a*b)*(a*b)*(a*b)*
el motsvarande (oförenklade uttryck) är OK

Exempel 2:
M2.txt bör ge följande utdata:
a*b(aub)*
Även OK är tex här: a*b((aUb)*)*

Exempel 3:
M3.txt bör ge följande utdata:
aubaa*ba*

Exempel 4:
M4.txt bör ge följande utdata:
aubaa*b(aub)*

Hitta gärna på egna dfa'er!

För er som inte vet hur filhantering sker i java så finns här ett exempel för att läsa in en fil som man anger som argument och skriver ut den på skärmen.

Uppgiften löses individuellt och skall vara inlämnad senast den 29 maj (23:59).