NFA angeben der die folgende Sprache akzeptiert: L1 := {w ∈ {0, 1}^∗| w

Question

Aufgabe:

Ich muss einen NFA angeben der die folgende Sprache akzeptiert:

L1 := {w ∈ {0, 1}^∗| w enthält die Zeichenkette 000 oder die Zeichenkette 111}

Hat jemand vielleicht ein Lösungsansatz für ein NFA der Sprache L1?

Answer 1

\(\begin{aligned}q & \stackrel{0,1}{\longrightarrow} q\\q_{F} & \stackrel{0,1}{\longrightarrow} q_{F}\\\\q & \stackrel{0}{\longrightarrow} q_0\\q_0 & \stackrel{0}{\longrightarrow} q_{00}\\q_{00} & \stackrel{0}{\longrightarrow} q_{F}\\\\q & \stackrel{1}{\longrightarrow} q_1\\q_1 & \stackrel{1}{\longrightarrow} q_{11}\\q_{11} & \stackrel{1}{\longrightarrow} q_{F}\\\end{aligned}\)

Answer 2

Ein Nondeterministic Finite Automaton (NFA), der die oben genannte Sprache akzeptiert, könnte wie folgt aussehen:

• Es gibt drei Zustände: q0, q1, q2, die für die Überprüfung der jeweils ersten, zweiten und dritten Stelle der Eingabe verwendet werden.
• Der Anfangszustand ist q0.
• Der Endzustand ist q2.
• Es gibt Übergänge von q0 nach q0, q1 und q2 bei Eingabe von 0 oder 1.
• Es gibt Übergänge von q1 nach q1, q2 bei Eingabe von 0 oder 1.
• Es gibt Übergänge von q2 nach q2 bei Eingabe von 0 oder 1.

So akzeptiert der NFA jede Eingabe die enthält 000 oder 111, da er sich bei der Eingabe der dritten Null oder eins im Zustand q2 befindet, und dieser Zustand ist ein Endzustand.

Comments

Der Automat akzeptiert auch das Wort 0 mittels des Übergangs vom Startzustand q0 zum Endzustand q2 bei Eingabe von 0.

Das Wort 0 ist nicht in L1 enthalten, weil es weder die Zeichenkette 000, noch die Zeichenkette 111 enthält.

Deshalb akzeptiert der Automat nicht die Sprache L1.