Aufgaben: Endliche Automaten und reguläre Grammatiken

Ein Automat hat die Zustände $q_0$ (Start), $q_1$ (akzeptierend) und das Alphabet $\{a, b\}$. Übergänge: $q_0 \xrightarrow{a} q_1$, $q_0 \xrightarrow{b} q_0$, $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_0$.

1. a) Prüfen Sie, ob die Wörter ba, ab und bb akzeptiert werden.

1. b) Beschreiben Sie die akzeptierte Sprache in Worten.

Ein Getränkeautomat in einem Bahnhof in Hannover akzeptiert 1-€- und 2-€-Münzen; ein Getränk kostet 2 €. Wird zu viel eingezahlt, gibt der Automat das Getränk aus und das überzahlte Geld als Wechselgeld zurück.

1. a) Geben Sie die Zustände (eingezahlter Betrag) an.

1. b) Stellen Sie das Zustandsdiagramm in Textform (als Übergangstabelle) dar.

Gegeben ist die Grammatik $G$ mit $S \to aS \mid b$.

1. a) Leiten Sie die Wörter b, ab und aab ab.

1. b) Beschreiben Sie die erzeugte Sprache durch einen regulären Ausdruck.

Entwerfen Sie einen deterministischen endlichen Automaten über $\{0, 1\}$, der genau die Wörter mit einer geraden Anzahl von Einsen akzeptiert.

1. a) Geben Sie Zustände, Startzustand, akzeptierende Zustände und Übergangstabelle an.

1. b) Testen Sie 1011 und 0110.

Ein Automat soll Wörter über $\{a, b\}$ akzeptieren, die auf ab enden.

1. a) Entwerfen Sie einen Automaten und geben Sie die Übergangstabelle an.

1. b) Geben Sie eine reguläre Grammatik für diese Sprache an.

Eine Ampelsteuerung an einer Kreuzung in Bochum durchläuft die Zustände Rot, Rot-Gelb, Grün, Gelb. Ein Signal takt löst den Wechsel aus.

1. a) Modellieren Sie die Steuerung als endlichen Automaten (Zustände, Übergänge).

1. b) Welche Zustandsfolge entsteht nach fünf Takten, wenn der Start bei Rot liegt?

Ein Passwortprüfer soll Zeichenfolgen über $\{L, Z\}$ (Buchstabe, Ziffer) akzeptieren, die mit einem Buchstaben beginnen und mindestens eine Ziffer enthalten.

1. a) Entwerfen Sie einen DFA und begründen Sie die Zustände.

1. b) Geben Sie einen regulären Ausdruck und eine reguläre Grammatik an.

1. c) Wandeln Sie Ihren Automaten so um, dass zusätzlich genau drei Zeichen gefordert sind, und beschreiben Sie die Änderung.

Gegeben ist die Sprache $L = \{a^n b^n \mid n \ge 0\}$.

1. a) Begründen Sie anschaulich, warum kein endlicher Automat $L$ erkennen kann (Zählen unbeschränkt).

1. b) Beschreiben Sie, welches zusätzliche Speichermodell (Stack) ausreicht.

1. c) Erläutern Sie die Bedeutung für Grenzen regulärer Ausdrücke, z. B. beim Prüfen beliebig tiefer Klammerung.

Gegeben ist die Grammatik $S \to aA$, $A \to bA \mid cS \mid c$.

1. a) Geben Sie drei Wörter der Sprache mit Ableitung an.

1. b) Konstruieren Sie den zugehörigen Automaten.

1. c) Entscheiden Sie mit Begründung, ob abbcac zur Sprache gehört.