0 Daumen
40 Aufrufe

Frage:

Geben Sie für die nachfolgenden Mengen jeweils einen endlichen Automaten A = (Σ, Q, δ, q0, F)
an, der diese Menge erkennt.


(1) Die Menge der Wörter, die die Zeichenkette abba enthalten (z.B. aaabba, babaabbabba).


(2)  Die Menge der Wörter, die eine durch 3 teilbare Zahl von Einsen enthalten (z.B.
0111, 0101011101). Hinweis: 0 ist durch 3 teilbar.


Kann mir jemand helfen ? :)

von

1 Antwort

0 Daumen
 
Beste Antwort

(1) Vier Zustände:

  • q0 Es wurde noch kein Teil der Zeichenkette abba gelesen.
  • qa Es wurde das erste a der Zeichenkette abba gelesen.
  • qab Es wurde das erste b der Zeichenkette abba gelesen.
  • qabb Es wurde das zweite b der Zeichenkette abba gelesen.
  • qabba Es wurde das zweite a der Zeichenkette abba gelesen.

(2) Drei Zustände:

  • q0 Die Anzahl der Einsen ergibt beim Teilen durch 3 den Rest 0.
  • q1 Die Anzahl der Einsen ergibt beim Teilen durch 3 den Rest 1.
  • q2 Die Anzahl der Einsen ergibt beim Teilen durch 3 den Rest 2.

Anfangszustand, Übergänge und Endzustände musst du selbst herausfinden.

von 2,4 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community