Direkt zum Inhalt

Aufgabe mit Lösung Null kommt x mal vor - (DEA) Deterministischer endlicher Automat

Wörter enden nicht auf 000 - DEA
Level 3 (mit höherer Mathematik)
Level 3 setzt Kenntnisse der Vektorrechnung, Differential- und Integralrechnung voraus. Geeignet für Studenten und zum Teil Abiturienten.

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

  1. Sprache 1
    Anker zu dieser Formel
  2. Sprache 2
    Anker zu dieser Formel
  3. Sprache 3
    Anker zu dieser Formel
  4. Sprache 4
    Anker zu dieser Formel
  5. Sprache 5
    Anker zu dieser Formel
  6. Sprache 6
    Anker zu dieser Formel
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.

\(|w|_x\) bedeutet die Anzahl der Vorkomnisse von \(x\) im Wort \(w\).

Alle Inhalte der Website sind kostenlos. Da aber dieses Projekt nicht von Luft und Liebe leben kann, ist es auf die Werbeeinnahmen angewiesen. Möchtest du die Lösungen sehen? Deaktiviere bitte deinen AdBlocker!
Lösung für (a)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und in jedem Wort \(w\) kommt 0 genau zwei Mal vor. Die Sprache besteht beispielsweise aus folgenden Wörtern:1\[ L = \{00, 001, 010, 001,~... \} \]

DEA - nur zwei 0en im Wort
DEA, der Wörter akzeptiert, die genau zwei 0en haben.

Die Zustandsmenge ist:2\[ 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:3\[ \delta(z_0, 1) = z_0 \] \[ \delta(z_0, 0) = \delta(z_1, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_2, 1) = z_2 \] \[ \delta(z_2, 0) = \delta(z_3, 0) = \delta(z_3, 1) = 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 für (b)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und in jedem Wort \(w\) kommt 0 genau zwei oder mehr als zwei Mal vor (aber niemals weniger als zwei). Die Sprache besteht beispielsweise aus folgenden Wörtern:5\[ L = \{00, 001, 010, 000,~... \} \]

DEA - zwei oder mehr 0en im Wort
DEA, der Wörter akzeptiert, die zwei oder mehr 0en haben.

Die Zustandsmenge ist: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, 1) = z_0 \] \[ \delta(z_0, 0) = \delta(z_1, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_2, 0) = \delta(z_2, 1) = 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 für (c)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und in jedem Wort \(w\) kommt 0 genau zwei oder weniger als zwei Mal vor (aber niemals mehr als zwei). Die Sprache besteht beispielsweise aus folgenden Wörtern:9\[ L = \{\varepsilon, 0, 00, 001, 010, 110,~... \} \]hierbei ist \(\varepsilon\) das leere Wort mit \(|\varepsilon| = 0 \).

DEA - zwei oder weniger 0en im Wort
DEA, der Wörter akzeptiert, die zwei oder weniger 0en enthalten.

Die Zustandsmenge ist: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, 1) = z_0 \] \[ \delta(z_0, 0) = \delta(z_1, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_2, 1) = z_2 \] \[ \delta(z_2, 0) = \delta(z_3, 0) = \delta(z_3, 1) = 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\).

Lösung für (d)

Um eine ausführliche Lösung zu sehen, musst du zuerst diese Funktion freischalten.

  • Alle Aufgabenlösungen freischalten
  • Alle Videos freischalten
  • Alle Illustrationen freischalten
  • Formeln umstellen
  • Keine Werbung
Mehr erfahren
Lösung für (e)

Um eine ausführliche Lösung zu sehen, musst du zuerst diese Funktion freischalten.

  • Alle Aufgabenlösungen freischalten
  • Alle Videos freischalten
  • Alle Illustrationen freischalten
  • Formeln umstellen
  • Keine Werbung
Mehr erfahren
Lösung für (f)

Um eine ausführliche Lösung zu sehen, musst du zuerst diese Funktion freischalten.

  • Alle Aufgabenlösungen freischalten
  • Alle Videos freischalten
  • Alle Illustrationen freischalten
  • Formeln umstellen
  • Keine Werbung
Mehr erfahren