Wir betrachten das Alphabet Σ = {a, b}. Definieren Sie jeweils einen DEA mit folgenden Eigenschaften.

• a1: Akzeptiert alle Worte, die als zweites Zeichen ein b besitzen.
• a2: Akzeptiert die drei Worte baa, ab, und abb.
• a3: Akzeptiert alle Worte, die nicht mit ba enden.
• a4: Akzeptiert alle Worte, die mit zwei gleichen Zeichen enden oder beginnen.
• a5: Akzeptiert alle Worte, die eine ungerade Anzahl von a’s enthalten.

Sie können Ihre Lösungen hier testen. Hierzu ist das Haskellmodul Auto gegeben, mit dem Sie endliche Automaten definieren können. Ein neuer leerer Automat entsteht mit newAuto. Sie haben vier Funktionen, um die Zustände des Automaten zu definieren: node, startNode, terminalNode und startTerminalNode. Mit diesen Funktionen lassen sich Zustände, ein Startzustand, Endzustände oder ein Zustand, der gleichzeitig Startzustand und Endzustand ist, erzeugen. Allen diesen Funktionen ist ein String nachzustellen, der der Name des Zustands repräsentiert.

Einem Automaten kann ein Zustandsübergang mit dem Operator <: hinzugefügt werden. Ein Zustandsübergang lässt sich mit folgender Syntax beschreiben:
zustand1-//string/->zustand2
Für jedes Zeichen des Strings in der Mitte wird definiert, dass der Automat aus Zustand zustand1 in zustand2 übergeht.

Als Beispiel ist der Automat aus der Vorlesung in Haskell notiert.

Geben Sie Ihre Automaten a1 bis a5 entsprechend ein. Berücksichtigen Sie dabei, dass Einrückungen in Haskell relevant sind.

Zum lokalen Testen. Installieren Sie ghc.

Dann Auto.hs und A1.hs herunterladen.

Auf Kommandozeile:
:~$ ghci A1.hs
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Auto             ( Auto.hs, interpreted )
[2 of 2] Compiling A1               ( A1.hs, interpreted )
Ok, modules loaded: A1, Auto.

Jetzt können Sie Automaten testen. Der Beispielautomat:

*A1> accept example "111100110101"
True
*A1> accept example "11111110000"
False
*A1>


Wenn Sie nun a1 bis a5 in A1.hs definieren, können Sie mit

:reload

in der ghci Session das Programm neu laden.