Direkt zum Inhalt
  1. Startort
  2. Quests
  3. 📖
Level 3
Level 3 setzt die Grundlagen der Vektorrechnung, Differential- und Integralrechnung voraus. Geeignet für Studenten und zum Teil Abiturienten.

Aufgabe mit Lösung Wörter bestimmter Länge - DEA (deterministischer endlicher Automat)

Konstruiere jeweils einen deterministischen endlichen Automaten (DEA), der die folgenden Sprachen \(L\) akzeptiert:

  1. \( L = \{ w \in \{a,b\}^* ~:~ |w| = 2 \} \)
  2. \( L = \{ w \in \{a,b\}^* ~:~ |w| \geq 2 \} \)
  3. \( L = \{ w \in \{a,b\}^* ~:~ |w| \leq 2 \} \)
Lösungstipps

Zähle zuerst ein paar Beispielwörter \(w\) auf, die von der jeweilgen Sprache \(L\) akzeptiert werden.

Zur Erinnerung: Ein DEA \(A\) ist ein 5-Tupel \(A = (Z, \Sigma, \delta, z_0, E) \). Gib diesen 5-Tupel an. Für die Überführungsfunktion \( \delta \) kann auch ein Graph angefertigt werden.

Lösung

Lösung zu (a) anzeigen

Die Sprache \(L\) ist eine endliche Sprache, deren Wörter \(w\) aus den Buchstaben \(a\) und \(b\) bestehen und genau die Länge \(|w|=2\) haben. Die Sprache besteht also aus vier Wörtern:1\[ L = \{aa, ab, ba, bb \} \]

DEA für Wörter, deren Wortlänge genau zwei ist.

Für einen minimalen deterministischen endlichen Automaten werden \(n+2\) (mit \(|w|=n\)) Zustände gebraucht, also 4 Zustände. Die Zustandsmenge ist damit:2\[ Z = \{ z_0, z_1, z_2, z_3 \} \]mit \(z_0\) als Anfangszustand. Der Index \(k\) in \(z_k\) kann als Anzahl der Zeichen interpretiert werden, die bereits gelesen wurden. Im Zustand \(z_0\) wurden 0 Zeichen gelesen. Im Zustand \(z_1\) wurde 1 Zeichen gelesen. Im Zustand \(z_2\) wurden 2 Zeichen gelesen.

Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:3\[ \delta(z_0, a) = \delta(z_0, b) = z_1 \] \[ \delta(z_1, a) = \delta(z_1, b) = z_2 \] \[ \delta(z_2, a) = \delta(z_2, b) = z_3 \] \[ \delta(z_3, a) = \delta(z_3, b) = z_3 \]

Die Menge \(E\) der Endzustände ist:4\[ E = \{ z_2 \} \]

Der angegebene Automat \(A = (Z, \Sigma, \delta, z_0, E) \) akzeptiert die betrachtete Sprache \(L\).

Lösung zu (b) anzeigen

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Buchstaben \(a\) und \(b\) bestehen und größer oder gleich die Länge \(|w|=2\) haben. Die Sprache besteht beispielsweise aus folgenden Wörtern:5\[ L = \{aa, bb, ab, aaa..., bbb..., ~... \} \]

DEA für Wörter, deren Wortlänge größer oder gleich zwei ist.

Für einen minimalen deterministischen endlichen Automaten werden \(n+1\) (mit \(|w| \geq n\)) Zustände gebraucht, also 3 Zustände. Die Zustandsmenge ist damit:6\[ Z = \{ z_0, z_1, z_2 \} \]mit \(z_0\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:7\[ \delta(z_0, a) = \delta(z_0, b) = z_1 \] \[ \delta(z_1, a) = \delta(z_1, b) = z_2 \] \[ \delta(z_2, a) = \delta(z_2, b) = z_2 \]

Die Menge \(E\) der Endzustände ist:8\[ E = \{ z_2 \} \]

Der angegebene Automat \(A = (Z, \Sigma, \delta, z_0, E) \) akzeptiert die betrachtete Sprache \(L\).

Lösung zu (c) anzeigen

Die Sprache \(L\) ist eine endliche Sprache, deren Wörter \(w\) aus den Buchstaben \(a\) und \(b\) bestehen und kleiner oder gleich die Länge \(|w|=2\) haben. Die Sprache besteht aus folgenden Wörtern:9\[ L = \{\varepsilon, a, b, ab, ba, aa, bb \} \]hierbei ist \(\varepsilon\) das leere Wort mit der Länge \(|\varepsilon|=0\).

DEA für Wörter, deren Wortlänge kleiner oder gleich zwei ist.

Für einen minimalen deterministischen endlichen Automaten werden \(n+2\) (mit \(|w| \leq n\)) Zustände gebraucht, also 4 Zustände. Die Zustandsmenge ist damit:10\[ Z = \{ z_0, z_1, z_2, z_3 \} \]mit \(z_0\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:11\[ \delta(z_0, \varepsilon) = z_0 \] \[ \delta(z_0, a) = \delta(z_0, b) = z_1 \] \[ \delta(z_1, a) = \delta(z_1, b) = z_2 \] \[ \delta(z_2, a) = \delta(z_2, b) = z_3 \] \[ \delta(z_3, a) = \delta(z_3, b) = z_3 \]

Die Menge \(E\) der Endzustände ist:12\[ E = \{ z_0, z_1, z_2 \} \]

Der angegebene Automat \(A = (Z, \Sigma, \delta, z_0, E) \) akzeptiert die betrachtete Sprache \(L\).

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .