0 Daumen
226 Aufrufe

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:

blob.png

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

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

Danke im Voraus.

Avatar von

1 Antwort

0 Daumen

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.

Avatar von 107 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community