Structuur van computer programma's II
Opgave project ``fsm''

Dirk Vermeir
Departement Informatica
Faculteit Wetenschappen
Vrije Universiteit Brussel

Mei 2001

Contents

1  Inleiding: fsm

Fsm is een programma waarmee eindige automaten kunnen gesimuleerd worden. Fsm kan ook gebruikt worden om de volgende transformaties uit te voeren:

• Omzetten van een niet-deterministische (verder NFA genoemd) automaat naar een deterministische (DFA) automaat.

• Optimalisatie van een DFA.

De input van fsm bevat steeds een (bestand met een) beschrijving van een automaat. Optioneel wordt ook een bestand met een specificatie van een input string meegegeven. In dat geval wordt ook een ``execution trace'' aangemaakt dat een weergave bevat van de uitvoering van de (getransformeerde) deterministische automaat met de gegeven input. Een schematische voorstelling is terug te vinden in Figuur 1.

Figure 1: Fsm

2  Achtergrond

Hiervoor wordt verwezen naar de cursus ``Grondslagen van de Informatica II'', in het bijzonder naar:

• De definitie van deterministische en niet-deterministische automaten.

• Het algoritme om een niet-deterministische automaat om te zetten in een equivalente deterministische automaat.

• Het algoritme om een deterministische automaat te optimaliseren (met betrekking tot het aantal staten).

3  Opgave: fsm

1. Maak een programma ``fsm'' dat voldoet aan de onderstaande functionele<sup>1</sup> en niet-functionele<sup>2</sup> eisen (``requirements'').

2. Beschrijf kort uw ontwerp in een apart document; waarvan u een afdruk bezorgt aan het secretariaat van de vakgroep vóór de uiterste indiendatum.

4  Functionele eisen

Het programma kan op de volgende manier opgeroepen worden

fsm [-o] input-automaat output-automaat [input-string trace]

• De optionele vlag -o duidt aan dat de input automaat moet geoptimaliseerd worden;

• Input-automaat is de naam van een bestand dat de specificatie van een automaat (NFA of DFA) bevat;

• Output-automaat is de naam van een bestand waarop de specificatie van de getransformeerde automaat wordt geschreven. Indien er geen transformatie werd toegepast, dan zal dit bestand de specificatie van de input automaat bevatten;

• Input-string is optioneel. Indien aanwezig geeft het de naam van een bestand dat een rij van input symbolen bevat; in dat geval zal deze rij aan de automaat (na transformatie) als input gegeven worden;

• Trace is optioneel en kan alleen voorkomen als ook input-string voorkomt. De output van de simulatie van de automaat met de input uit input-string zal geschreven worden op een bestand met die naam.

De werking van fsm kan als volgt beschreven worden:

1. Het input-automaat bestand wordt gelezen, wat resulteert in een automaat M₁.
2. Indien M₁ deterministisch is en de -o vlag niet aanwezig is wordt M₁ weggeschreven op output-automaat. Indien input-string en trace aanwezig zijn wordt M₁ gesimuleerd met de rij van symbolen uit input-string.
3. Indien M₁ deterministisch is en de -o is aanwezig, dan wordt het optimalisatie algoritme toegepast op M₁, wat resulteert in een nieuwe DFA M₂. M₂ wordt weggeschreven op output-automaat. Indien input-string en trace aanwezig zijn wordt M₂ gesimuleerd met de rij van symbolen uit input-string.
4. Indien M₁ niet deterministisch is, wordt eerst een equivalente DFA D₁ geconstrueerd waarmee verder gewerkt wordt zoals in (2) en (3) hierboven.

4.1  Formaat van de specificatie van een automaat

Dit formaat wordt beschreven door de grammatica in Tabel 1. Een specificatie kan ook commentaar bevatten: een teken # en alle tekens op dezelfde lijn worden niet in aanmerking genomen.

Normaal gedrukte woorden zijn niet-terminale symbolen. Andere symbolen zijn terminaal. Een naam is een rij van tekens, waarbij enkel letters, cijfers en ``underscore'' (``_'') toegelaten tekens zijn. ``White space'' (' ', '\t', '\n') tekens kunnen willekeurig voorkomen tussen ``tokens''. De tekens ``{'' en ``}'' die een lijst van namen begrenzen moeten gescheiden zijn van de rest van de input d.m.v. ``white space''. Dus

{ q1 q2 }

is goed maar

{q1 q2}

is fout. Er is één speciaal symbool: ``-'' staat voor e, de lege string (nodig om NFAs te kunnen specifiëren).

De interpretatie is duidelijk: de specificatie bevat

1. De naam van de begintoestand van de automaat.
2. De namen van de eindtoestanden van de automaat.
3. De transities. Merk op dat lijsten van namen kunnen dienen als afkortingen bij het specifiëren van transities;

   { p q } { a b c } r

   is een afkorting voor de volgende transities.

   p a r
   p b r
   p c r
   q a r
   q b r
   q c r

De inhoud van het output-automaat bestand heeft dezelfde syntax als het input-automaat bestand. Dit laat toe dat het output bestand kan herbruikt worden als input bestand. Merk op dat de algoritmen nieuwe toestanden kunnen aanmaken, waarvoor het programma dan een redelijke naam moet verzinnen.

De bestanden dfa1.txt en dfa2.txt bevatten voorbeelden van specificaties voor automaten (waarbij de tweede automaat de geoptimaliseerde versie van de eerste is). De formele syntax is terug te vinden in Tabel 1.

4.2  Formaat van de input string

Het input-string bestand bevat een rij van symbolen (namen in de bovenstaande syntax), gescheiden door ``White space'' (' ', '\t', '\n').

Het bestand dfa1.input bevat een voorbeeld input-string bestand.

4.3  Formaat van het trace bestand

Is vrij, maar in elk geval moet het bestand normale tekst bevatten en moet uit de inhoud duidelijk blijken welke toestanden de automaat heeft doorlopen (als reactie op welke input symbolen).

5  Niet-functionele eisen

1. Het programma moet volledig en uitsluitend in C++ geschreven worden.
2. Het programma moet gebaseerd zijn op een object-georienteerd ontwerp. Functies die langer zijn dan 30 lijnen zullen met argwaan worden bekeken.

3. Het ontwerp moet zodanig zijn dat delen zonder moeite herbruikbaar zijn. Daartoe moeten de input/output en de kern (de automaten en bijhorende algoritmen) gescheiden zijn zodat bvb. een klasse voor automaten in een ander project kan gebruikt worden.

4. Het programma moet correct werken op wendy.
5. Enkel de C++ (of C) standaard library mag gebruikt worden.
6. Eigen implementaties van containers zijn niet toegestaan, enkel standaard library containers zoals map, set, vector, mogen gebruikt worden.
7. De source (C++) bestanden dienen de suffix ``.cc'', ``.C'' of ``.cpp'' te gebruiken. De ``header files'' met declaraties dienen de suffix ``.h'' te gebruiken.
8. Alle source bestanden, samen met een ``Makefile'', dienen zich in een directory ``structuur2/project2000b'' te bevinden. De volgende reeks van bevelen zal resulteren in een correct uitvoerbaar programma ``fsm'' in dit directory:

   	make clean
   	rm -f fsm *.o
   	make fsm
   	

9. Eventuele hulpbestanden mogen enkel in het werkdirectory (waar het programma wordt uitgevoerd) worden aangemaakt.
10. Het programma moet robuust zijn. Dit wil zeggen dat het ook een redelijke actie moet ondernemen indien de input extreem (bvb. geen transities in een input automaat specificatie) of foutief is (bvb. een niet bestaand input bestand, een fout in de specificatie van de automaat).

6  Vragen

• Zoals steeds kan je vragen en opmerkingen sturen naar o4556@elvas.vub.ac.be.
• Indien je zeker wil zijn van een goede aanpak, dan kan je het ontwerp (welke klassen die welke functies ondersteunen) naar stru2@tinf.vub.ac.be sturen voor commentaar.

7  Indienen

Footnotes:

¹ Functionele eisen leggen vast wat het programma moet doen.

² Niet-functionele eisen leggen vast aan welke andere voorwaarden het programma moet voldoen, bvb. onder welk operating system het moet werken, welke programmeertalen of bibliotheken mogen gebruikt worden, etc.