1. Welt
  2. Quests
  3. #1454
Alexander Fufaev

Null kommt x mal vor - (DEA) Deterministischer endlicher Automat

aus dem Bereich: Quests
Mehr dazu

Deine Aufgabe ist...

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

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

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

Lösung zu (a) anzeigen

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, 000,~... \} \]

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 zu (b) anzeigen

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,~... \} \]

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 zu (c) anzeigen

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 \).

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_3 \] \[ \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 zu (d) anzeigen

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 \).

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

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

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

Lösung zu (e) anzeigen

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 zu (f) anzeigen

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 \).

Die Zustandsmenge ist: 22 \[ Z = \{ GG, GU, UG, UU \} \] mit \(GG\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus: 23 \[ \delta(GG, \varepsilon) = \delta(GU, 1) = \delta(UG, 0) = GG \] \[ \delta(GG, 1) = \delta(UU, 0) = GU \] \[ \delta(GG, 0) = \delta(UU, 1) = UG \] \[ \delta(GU, 0) = \delta(UG, 1) = UU \]

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

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

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 1
Gäste online: 1
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.