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 Null kommt x mal vor - (DEA) Deterministischer endlicher Automat

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

  1. \( L = \{ w \in \{0,1\}^* ~:~ |w|_0 = 2 \} \)
  2. \( L = \{ w \in \{0,1\}^* ~:~ |w|_0\geq 2 \} \)
  3. \( L = \{ w \in \{0,1\}^* ~:~ |w|_0\leq 2 \} \)
  4. \( L = \{ w \in \{0,1\}^* ~:~ |w|_0 ~\text{mod}~ 2 = 0 \} \)
  5. \( L = \{ w \in \{0,1\}^* ~:~ |w|_0 ~\text{mod}~ 3 = 0 \} \)
  6. \[ L = \{ w \in \{0,1\}^* ~:~ |w|_0 ~\text{mod}~ 2 = 0 ~\text{UND}~ |w|_1 ~\text{mod}~ 2 = 0 \} \]
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\).

Lösungen

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, 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, 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, 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)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und in jedem Wort \(w\) kommt nur eine gerde Anzahl an Nullen vor. Die Sprache besteht beispielsweise aus folgenden Wörtern:13\[ L = \{\varepsilon, 1, 11, 00, 010, 110000,~... \} \]hierbei ist \(\varepsilon\) das leere Wort mit \(|\varepsilon| = 0 \).

DEA, der Wörter akzeptiert, die eine gerade Anzahl an 0en enthalten.

Es werden mindestens zwei Zustände gebraucht. Ein Zustand \(U\) für eine ungerade Anzahl an Nullen und ein Zustand \(G\) für eine gerade Anzahl an Nullen. Die Zustandsmenge ist:14\[ Z = \{ G, U \} \]mit \(G\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:15\[ \delta(G, \varepsilon) = \delta(G, 1) = \delta(U, 0) = G \] \[ \delta(U, 1) = U \]

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

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

Lösung für (e)
Dieser DEA akzeptiert Wörter, bei denen die Anzahl der 0en durch 3 teilbar ist.

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und in jedem Wort \(w\) kommt nur eine Anzahl an Nullen vor, die durch drei teilbar ist. Die Sprache besteht beispielsweise aus folgenden Wörtern:17\[ L = \{\varepsilon, 000, 101010, 000000,~... \} \]hierbei ist \(\varepsilon\) das leere Wort mit \(|\varepsilon| = 0 \).

Es werden mindestens drei Zustände gebraucht. Ein Zustand für Rest 0, Rest 1 und Rest 2. Die Zustandsmenge ist:18\[ Z = \{ z_0 \} \]mit \(z_0\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:19\[ \delta(z_0, \varepsilon) = \delta(z_0, 1) = \delta(z_2, 0) = z_0 \] \[ \delta(z_0, 0) = \delta(z_1, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_2, 1) = z_2 \]

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

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

Lösung für (f)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und in jedem Wort \(w\) kommt nur eine gerade Anzahl an Nullen UND Einsen vor. Die Sprache besteht beispielsweise aus folgenden Wörtern:21\[ L = \{\varepsilon, 00, 11, 001100,~... \} \]hierbei ist \(\varepsilon\) das leere Wort mit \(|\varepsilon| = 0 \).

DEA für Wörter, die eine gerade Anzahl an 0en und 1en haben.

Die Zustandsmenge ist:22\[ Z = \{ z_{\text{gg}}, z_{\text{gu}}, z_{\text{ug}}, z_{\text{uu}} \} \]mit \(z_{\text{gg}}\) als Anfangszustand. Der erste Buchstabe des Index bestimmt die Anzahl bereits gelesener 0en. Und der Buchstabe bestimmt die Anzahl bereits gelesener 1en. Beispielsweise im Zustand \(z_{\text{gu}}\) wurde eine gerade Anzahl an 0en und eine ungerade Anzahl an 1en gelesen.

Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:23\[ \delta(z_{\text{gg}}, \varepsilon) = \delta(z_{\text{gu}}, 1) = \delta(z_{\text{ug}}, 0) = z_{\text{gg}} \] \[ \delta(z_{\text{gg}}, 1) = \delta(z_{\text{uu}}, 0) = z_{\text{gu}} \] \[ \delta(z_{\text{gg}}, 0) = \delta(z_{\text{uu}}, 1) = z_{\text{ug}} \] \[ \delta(z_{\text{gu}}, 0) = \delta(z_{\text{ug}}, 1) = z_{\text{uu}} \]

Die Menge \(E\) der Endzustände ist:24\[ E = \{ z_{\text{gg}} \} \]

Der angegebene Automat \(A = (Z, \Sigma, \delta, z_{\text{gg}}, E) \) akzeptiert die betrachtete Sprache \(L\).

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