Laboration 2 : Implementera en DFA
Inledning
Denna laboration går ut på att implementera en Deterministisk Finit Automat (DFA) M=(K, S, d, s, F) där
K är mängden tillstånd för DFA'n
S är alfabetet för språket som DFA'n beskriver
d är övergångsfunktionen
s är starttillståndet (ett element ut K)
F är sluttillstånden (en delmängd av K)
Programmet ska ta två filer som indata. Den ena filen ska innehålla beskrivningen för DFA'n. Den andra filen ska innehålla strängen som ska kontrolleras av DFA'n. Om strängen accepteras ska svaret "Strängen 'S' accepteras" (där S är strängen som kontrolleras) skrivas ut. Om den inte accepteras ska svaret "Strängen 'S' accepteras ej" skrivas ut. Ni behöver givetvis inte skriva exakt på detta sätt, men se till att skriva ut strängen samt om den accepteras eller inte.
Indata
Indatat är exakt lika som den "gamla" labben. Dock kommer inte begränsningen på K's och F's storlekar att gälla.
Första raden innehåller mängden av tillstånd K (okänt antal tecken)
Andra raden innhåller alfabetet S (okänt antal tecken)
Tredje raden innehåller starttillståndet s (ett tecken)
Fjärde raden innehåller sluttillstånden F (okänt antal tecken, dock mindre än totala antalet tillstånd i K)
Resten av raderna innhåller reglerna för övergångsfunktionen d (för antal se Tips nedan).
Tips
För att göra det lite enklare att representera reglerna i övergångsfunktionen d kan ni begränsa dem till 10 stycken. Skapa en array med 10 element, där varje element är en array med tre tecken. Det första tecknet innhåller nuvarande tillstånd, det andra tecknet det från "bandet" inlästa tecknet och det tredje nästa tillstånd. Se dock till att få med detta i er rapport under rubriken Lösningens bergänsningar. Givetvis är det snyggare att kunna ha "oändligt" antal regler...
Se till att ha ordentligt felkontroll när ni läser in beskrivningen för DFA'n. Om det till exempel inte finns några regler med alls och ni försöker köra ert program utan att ha definierat regler i er array kan det gå snett.
Kom även ihåg att det är DFA'n som skall upptäcka om en sträng tillhör ett språk eller inte. Ha till exempel inte en separat felkontroll som undersöker om den inlästa strängen innehåller andra tecken än de som finns i alfabetet för DFA'n. Detta ska DFA'n själv upptäcka genom att se att det inte finns en regel för detta tecken.