Endlicher Automat erkennt Mengen

Question

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 ? :)

Answer 1

(1) Vier Zustände:

• q₀ Es wurde noch kein Teil der Zeichenkette abba gelesen.
• q_a Es wurde das erste a der Zeichenkette abba gelesen.
• q_ab Es wurde das erste b der Zeichenkette abba gelesen.
• q_abb Es wurde das zweite b der Zeichenkette abba gelesen.
• q_abba Es wurde das zweite a der Zeichenkette abba gelesen.

(2) Drei Zustände:

• q₀ Die Anzahl der Einsen ergibt beim Teilen durch 3 den Rest 0.
• q₁ Die Anzahl der Einsen ergibt beim Teilen durch 3 den Rest 1.
• q₂ Die Anzahl der Einsen ergibt beim Teilen durch 3 den Rest 2.

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