Übung Akzeptor

Aufgabe 1

Entwerfen Sie jeweils einen Akzeptor mit dem Eingabealphabet X= {a,b}, der die folgende Sprache L(A) erkennt.

1. $L(A) = \lbrace \rbrace$ .......... die leere Menge
2. $L(A) = \lbrace \epsilon \rbrace$ .......... die Menge, die nur ein leeres Wort enthält
3. $L(A) = \lbrace abba \rbrace$ .......... die Menge, die genau ein nichtleeres Wort enthält (hier: abba)
4. $L(A) = \lbrace a^n \mid n \in \mathbb N \rbrace$ .......... die Menge, die alle nur aus a bestehenden Worte aus $X^*$ enthält
5. $L(A) = \lbrace w \mid w \in X^*, w\ enthaelt\ eine\ gerade\ Anzahl\ von\ a \rbrace$
6. $L(A) = \lbrace X^* \setminus \lbrace abba \rbrace \rbrace$

---

Aufgabe 2

Entwerfen Sie zur Syntaxanalyse von Zahlendarstellungen in Pascal einen endlichen Automaten, der

1. genau die vorzeichenlosen Ganzzahlen oder
2. genau die vorzeichenlosen Zahlen akzeptiert

---

Aufgabe 3

Gesucht ist ein Automat, der Dualzahlen erkennt, die

1. eine ungerade Anzahl von Einsen enthalten,
2. mindestens zwei aufeinander folgende Einsen oder zwei aufeinander folgende Nullen enthalten,
3. durch 2 (4, 8, ...) teilbar sind,
4. an vorletzter Stelle eine Null haben.

---

Aufgabe 4

Entwickeln Sie einen Automaten, der die folgende Pascal-ähnliche Deklaration für ein Feld erkennt: