Aufgabe 4 - Endliche Automaten · Abitur NRW Informatik LK · Nachtermin 2022

Startzustand des Automaten A

Lösung: $q_0$

Menge der Endzustände des Automaten A

Lösung: $\{q_6\}$

Erläutern Sie, was der Zustand $q_2$ des Automaten A im Sachzusammenhang bedeutet.

Lösung: In diesen Zustand gelangt man, nachdem der Automat die erste Hälfte der Vokalkombination ee oder ie gelesen hat.

Entwickeln Sie den Übergangsgraphen eines deterministischen endlichen Automaten, der genau die Sprache akzeptiert, die auch der nichtdeterministische endliche Automat A akzeptiert.

Lösung: Der Übergangsgraph zu einem äquivalenten deterministischen endlichen Automaten besitzt folgende Struktur: - Startzustand $q_0$. - Nach Einlesen von Vokalen, die bereits als Einzelvokal oder als Beginn einer Kombination gültig sind, werden Zustände $q_1, q_2, q_3, q_4, q_5$ auch als Endzustände markiert (oder äquivalente Potenzmengen-Zustände). - Von $q_0$ mit 'a' nach $q_1$ (Endzustand), von $q_1$ mit 'a, i, u' nach $q_6$. - Von $q_0$ mit 'e' nach $q_2$ (Endzustand), von $q_2$ mit 'e, i, u' nach $q_6$. - Von $q_0$ mit 'i' nach $q_3$ (Endzustand), von $q_3$ mit 'e' nach $q_6$. - Von $q_0$ mit 'o' nach $q_4$ (Endzustand), von $q_4$ mit 'o' nach $q_6$. - Von $q_0$ mit 'ä' nach $q_5$ (Endzustand), von $q_5$ mit 'u' nach $q_6$. - Von $q_0$ direkt mit 'u, ö, ü' nach $q_6$ (Endzustand).