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 Wortlänge durch 2, 3, n teilbar (mit und ohne Rest) - DEA

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

  1. \( L = \{ w \in \{0,1\}^* ~:~ |w| ~\text{mod}~ 2 = 0 \} \)
  2. \( L = \{ w \in \{0,1\}^* ~:~ |w| ~\text{mod}~ 2 = 1 \} \)
  3. \( L = \{ w \in \{0,1\}^* ~:~ |w| ~\text{mod}~ 3 = 0 \} \)
  4. \( L = \{ w \in \{0,1\}^* ~:~ |w| ~\text{mod}~ 3 = 1 \} \)
  5. \( L = \{ w \in \{0,1\}^* ~:~ |w| ~\text{mod}~ n = 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.

Bei (e) besteht \(L\) aus allen Binärwörtern, deren Länge durch \(n\) teilbar ist.

Lösungen

Lösung für (a)
DEA, der Wörter akzeptiert, deren Länge durch zwei teilbar ist.

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und die Länge der Wörter \(|w|\) = gerade ist. Die Sprache besteht beispielsweise aus folgenden Wörtern:1\[ L = \{\varepsilon, 00, 01, 11, 0101,~... \} \]

Hierbei ist \(\varepsilon\) das leere Wort mit der Länge Null (denn Null ist durch zwei teilbar - also gerade). Für einen minimalen deterministischen endlichen Automaten werden mindestens zwei Zustände gebraucht. Der eine Zustand \(G\), der die Wörter gerader Länge und der andere Zustand \(U\), der die Wörter ungerader Länge annimmt. Die Zustandsmenge ist damit:2\[ Z = \{ G, U \} \]mit \(G\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:3\[ \delta(G, \varepsilon) = G \] \[ \delta(G, 0) = \delta(G, 1) = U \] \[ \delta(U, 0) = \delta(U, 1) = G \]

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

Der angegebene Automat \(A = (Z, \Sigma, \delta, G, 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 deren Länge \(|w|\) = ungerade ist. Die Sprache besteht beispielsweise aus folgenden Wörtern:5\[ L = \{0, 1, 000, 111, 010, ~... \} \]

Für einen minimalen deterministischen endlichen Automaten werden ebenfalls wie bei Teilaufgabe (a) zwei Zustände gebraucht. Die Zustandsmenge ist damit:6\[ Z = \{ G, U \} \]mit \(G\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:7\[ \delta(G, 0) = \delta(G, 1) = U \] \[ \delta(U, 0) = \delta(U, 1) = G \]

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

Der angegebene Automat \(A = (Z, \Sigma, \delta, G, E) \) akzeptiert die betrachtete Sprache \(L\). Dieser unterscheidet sich von dem DEA aus (a) nur durch den Endzustand.

Lösung für (c)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und deren Länge durch drei teilbar ist. Die Sprache besteht beispielsweise aus folgenden Wörtern:9\[ L = \{\varepsilon, 000, 111, 010, ~... \} \]hierbei ist \(\varepsilon\) das leere Wort mit der Länge \(|\varepsilon|=0\). Null ist durch drei teilbar.

DEA für Wörter, deren Wortlänge durch 3 teilbar ist.

Für einen minimalen deterministischen endlichen Automaten werden mindestens drei Zustände gebraucht. Beim Teilen durch drei können drei Reste entstehen: Rest 1, Rest 2 und Rest 3. Die Zustandsmenge ist damit:10\[ 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:11\[ \delta(z_0, \varepsilon) = z_0 \] \[ \delta(z_0, 0) = \delta(z_0, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_1, 1) = z_2 \] \[ \delta(z_2, 0) = \delta(z_2, 1) = z_0 \]

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

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. Wenn die Wortlänge durch 3 geteilt wird, dann ist der Rest stets 1. Die Sprache besteht beispielsweise aus folgenden Wörtern:13\[ L = \{0, 1, 0000, 1111, 0101, ~... \} \]

DEA für Wörter, deren Wortlänge durch 3 teilbar mit Rest 1 ist.

Für einen minimalen deterministischen endlichen Automaten werden wie bei (c) mindestens drei Zustände gebraucht. Die Zustandsmenge ist:14\[ 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:15\[ \delta(z_0, 0) = \delta(z_0, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_1, 1) = z_2 \] \[ \delta(z_2, 0) = \delta(z_2, 1) = z_0 \]

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

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

Lösung für (e)

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Zahlen \(0\) und \(1\) bestehen und deren Länge durch \(n\) teilbar ist.

Für einen minimalen deterministischen endlichen Automaten werden mindestens \(n\) Zustände gebraucht. Die Zustandsmenge ist:17\[ Z = \{ z_0, z_2, ~...,~ z_{n-1} \} \]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 Null Zeichen gelesen. Im Zustand \(z_{n-1}\) wurden \(n-1\) Zeichen gelesen. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:18\[ \delta(z_0, \varepsilon) = z_0 \] \[ \delta(z_0, 0) = \delta(z_0, 1) = z_1 \] \[ \delta(z_1, 0) = \delta(z_1, 1) = z_2 \] \[...\] \[ \delta(z_{n-1}, 0) = \delta(z_{n-1}, 1) = z_0 \]

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

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 .