Problem D
Labb S3: Automatanalys

I den här labben ska du skriva kod för att analysera en ändlig automat (deterministic finite automaton, DFA). Mer specifikt ska du skriva ett program som genererar “alla” (upp till en övre gräns) strängar som accepteras av en given automat.

Labben är primärt avsedd att utföras i Java. Det är möjligt att använda något annat språk men i detta fall kommer du behöva göra lite mer saker själv (se avsnittet “Använda annat språk” nedan).

Du ska implementera en klass DFA som representerar en automat. Klassen ska ha följande metoder:

• public DFA(int stateCount, int startState);
  Konstruktor som skapar en automat med stateCount antal tillstånd, där tillstånd nummer startState är starttillstånd. Tillstånden numreras från $0$ till $\texttt{stateCount}-1$.

• public void setAccepting(int state);
  Anger att tillståndet state är ett accepterande tillstånd.

• public void addTransition(int from, int to, char sym);
  Anger att det finns en övergång från from till to med tecknet sym.

• public List<String> getAcceptingStrings(int maxCount);
  Metod som returnerar upp till maxCount olika strängar som automaten accepterar. Om automaten accepterar färre (eller lika med) maxCount strängar ska alla strängar som automaten accepterar returneras. Om automaten accepterar fler strängar ska exakt maxCount olika strängar returneras. I det senare fallet får metoden i princip returnera vilka accepterande strängar som helst (det behöver t.ex. inte vara de första i alfabetisk ordning, eller något sådant), men av tekniska skäl får de returnerade strängarna inte vara allt för långa (se “Begränsningar” nedan). Listan som returneras behöver inte vara sorterad, strängarna kan returneras i godtycklig ordning.

Testkod

För att komma igång tillhandahålls ett kodskelett, inklusive en main-klass och några testfall, som du kan använda för att provköra din lösning. Mer information finns i den medföljande README-filen.

Till Kattis ska du bara skicka in din lösning DFA.java, inte main-klassen Main.java eller inläsningsrutinerna i Kattio.java (som main-klassen använder sig av).

Använda annat språk

Om du väldigt gärna vill använda något annat språk än Java så är det tillåtet (men det måste vara ett språk som finns på Kattis). I detta fall behöver du själv hantera inläsning av automaten och utskrift av svaret genom att konvertera Main.java från Java-skelettet till det språk du vill använda.

Begränsningar

I Kattis-testerna kommer automaten inte att ha mer än 50 tillstånd, och parametern maxCount kommer inte överstiga $1000$. De tecken som kommer användas i Kattis-testerna är a-z, A-Z, och 0-9. (Dessa begränsningar är inte något ni ska hård-koda i er lösning, utan en vägledning om ni har problem att bli godkända i Kattis och vill begränsa vad ni testar.)

Strängarna som getAcceptingStrings returnerar får vara högst $5000$ tecken långa (detta kommer alltid vara tillräckligt med väldigt god marginal).

Du kan anta att alla anrop till din klass är korrekta och behöver inte skriva någon speciell felhantering. T.ex. kommer alltså parametrarna from eller to i addTransition alltid ges värden som är mellan $0$ och $\texttt{stateCount}-1$, och från varje tillstånd och tecken kommer det finnas högst en övergång från tillståndet för det tecknet.

Redovisning

När du är klar och vill redovisa, skicka ett e-brev till kurs-mailen. Brevet ska innehålla följande:

• Subject/ärende ska vara “progp: redovisning S3”

• Submission ID på Kattis för din godkända lösning.

• Ditt/era namn och kth.se-mail-adresser

Du/Ni kommer sedan bli inbokade på en redovisningstid och få info om detta via mail.