Endliche Automaten: Zeichenkette 101

Question

Aufgabe:

Seien $L_{1}$ und $L_{2}$ die folgenden Sprachen über dem Alphabet $\Sigma=\{0,1\}$.

- $L_{1}=\left\{s \in \Sigma^{*} \mid s\right.$ enthält die Zeichenkette 101$\}$
- $L_{2}=\left\{s \in \Sigma^{*} \mid s\right.$ hat den Präfix 10 und den Suffix 01 $\}$

Geben Sie für jede der beiden Sprachen einen endlichen Automaten an, der sie akzeptiert.

Problem/Ansatz:

Was ich zu der Aufgabe nicht verstehe, ist, woher weiß man, dass Zustand q₂ eine 0 zu Zustand q₀ geben muss? Oder dass die Zustände q₀ und q₁ sich 0 und 1 geben ? Wie kommt man drauf?

Bei q₃ habe ich verstanden, da es eine "101" ist. Endet es mit 0,1 oder ?

Danke im Voraus.

Answer 1

Der Zustand $q_0$ bedeutet, von dem Teilwort 101 wurde bis jetzt noch nichts gelesen.

Der Zustand $q_1$ bedeutet, von dem Teilwort 101 wurde bis jetzt die erste 1 gelesen. Jede weitere 1, die unmittelbar folgt, kann wiederum die erste 1 des Teilwortes 101 sein. Desahlb bleibt der Automat im Zustand $q_1$, wenn eine 1 gelesen wird.

Der Zustand $q_2$ bedeutet, von dem Teilwort 101 wurde bis jetzt die erste 1 und die 0 gelesen.

Der Zustand $q_3$ bedeutet: Das ganze Teilwort 101 wurde gelesen.

Angenommen du hast bis jetzt 10 gelesen und liest nun eine 0, welcher Teil von 101 wurde dann gelesen?

Sobal 101 komplett gelesen wurde, ist es für die Etnscheidung, ob das Wort in $L_1$ liegt, irrelevant, welche Zeichen noch kommen. Deshalb bleibt der Automat im Endzustand $q_3$, egal welche Zeichen noch folgen.

Comments

Also ist es egal was man in q0 oder q1 selbst hineinschiebt? und verstehe immer noch nicht wieso q2 eine 0 an Zustand q0 gibt.

---

In die Zustände schiebt man nichts hinein. Und die Zusände übergeben auch nichts an andere Zustände.

Stattdessen geht der Automat beim Lesen eines Zeichens von einem Zustand in einen Folgezustand über.