04.09. endlicher Automat

Gegeben sei der folgende endliche Automat:

Dieser Automat akzeptiert die Sprache aller Sequenzen über dem Alphabet {a,b}, die eine gerade Anzahl von a’s beinhalten.

Repräsentiere diesen Automaten in Prolog und schreibe ein Prädikat fsa_accept/1, das als Argument eine Liste nimmt und gelingt, wenn die Liste eine von dem Automaten akzeptierte Sequenz ist.

?- fsa_accept([a,b,a,a,b,b,a]).
true.
?- fsa_accept([a,a,c]).
false.
?- fsa_accept([a,b]).
false.

Was ist noch mal ein endlicher Automat?

Teil dieser Aufgabe ist auch, sich das Datenformat, in dem der Automat in Prolog repräsentiert wird, auszudenken! fsa_accept ruft also andere Prädikate auf, die man auch selbst implementieren muss.

Das Prädikat fsa_accept soll wirklich den gezeigten Automaten modellieren. Lösungen, die z.B. alle b’s aus der Eingabeliste löschen und prüfen, ob die übrig gebliebene Liste eine gerade Länge hat, zählen NICHT.

Falls Du Hilfe brauchst, bearbeite die Unteraufgaben als Hilfestellung!

Wenn du schon einige Ideen hast kannst du unten auch direkt Programmieren!