Endlicher Automat helfe bei 3 Aufgaben

Question

Frage:

Kann mir jemand bitte bitte der Azfgabe helfen, ich schreibe meine Ansätze hin aber habe echt keine Ahnung IV das so stimmt und wie es weiter geht.

Das Bild ist der endliche Automat um den es sich in der Aufgabe handelt.

Text erkannt:

Fig. 1

Also bei Aufgabe A sollen wir gucken welcher der folgenden Nummern akzeptiert werden...

Meine Lösung:

Akzeptiert wird: 1111;  1001; 0010100

Nicht akzeptiert wird: 10101; 001101; 0101010

Stimmt das?

Aufgabe B lautet: formuliert allgemein, welche Wörter hier erkannt werden. Tipp: Betrachte die Endzustände und untersucht, wie die drei letzten Zeichen der akzeptierten Wörter aussehen.

Keine Ahnung. Meine Lösung wäre :

001 ; 10001; 11; 10011001

Keine Ahnung stimmt das? Habe ich das falsch verstanden ? Hier brauche ich aufjedenfall Hilfe. Ich denke wichtig ist, dass am Ende eine 1 muss oder ? Ich verstehe die nicht.

Letze Aufgabe: in eine Tabelle Formen

Meine Tabelle:

Aktueller Zustand  Eingabe:0     Eingabe: 1

z1                                     z3                  z5

z2                                      z2                z4

...

z5                                      z3                  z6

Stimmt das so?

Vielen Dank für eure Hilfe

Comments

zu A: Nach Abarbeiten von 0010100 befindet sich der Automat im Zustand z2. Das ist kein Endzustand.

---

Oh stimmt, ok

Aber stimmt der Rest? Und ich brauche hauptsächlich Hilfe bei Aufgabe B bitte

Answer 1

A) 0010100 wird nicht akzeptiert:

        \(z_{1}\stackrel{0}{\rightarrow}z_{3}\stackrel{0}{\rightarrow}z_{2}\stackrel{1}{\rightarrow}z_{4}\stackrel{0}{\rightarrow}z_{3}\stackrel{1}{\rightarrow}z_{6}\stackrel{0}{\rightarrow}z_{3}\stackrel{0}{\rightarrow}z_{2}\)

Die anderen Wörter hast du richtig eingeordnet.

B) Am Ende muss eine 1 stehen. Das reicht aber nicht, wie du an den Wörtern 01, 101, 0101, 00101, 000101, 0000101, 00000101, 000000101 und 0000000101 feststellen kannst.

Comments

Ah ok danke:), aber wie kann ich denn jetzt B lösen? Also es reicht ja nicht hinzuschreiben, dass am Ende eine 1 sein muss. Da muss es doch irgendwie eine Formel oder sowas geben..oderbwi soll ich allgemein alle Wörter aufzählen die akzeptiert werden? Tut mir leid

---

Da muss es doch irgendwie eine Formel oder sowas geben

Es gibt keine Formel mit der man mathematische Sprache in leicht verständliche Sprache übersetzen kann.

Betrachte die Endzustände und untersucht, wie die drei letzten Zeichen der akzeptierten Wörter aussehen.

Konzentriere dich dabei auf den Endzustand \(z_4\).

Der Endzustand \(z_5\) akzeptiert offensichtlich genau die Wörter, in denen keine 0 vorkommt.

---

Danke, aber verstehe das dennoch nicht, also wenn ich bei z5 bin akzeptier es alles ohne 0 das verstehe ich noch, aber was ist mkt z4 was soll ich da hin schreiben.

Oder soll man schreiben ,, alle Wörter in denen keine 0 vorkommt werden von z5 akzeptiert und alle die mit 1 enden von z4? Aber das macht doch irgendwie keinen Sinn

---

Stimmt das so?

---

Ich habs: alle Wörter die auf 001 enden werden von z4 erkannt und alle ohne 0 von z5

---

Man muss dich halt nur lange genug denken lassen ...

---

Hahahah ja, aber stimmt das denn jetzt?

---

Ja, das stimmt.

---

Cool, vielen vielen Dank bist der beste

---

Und was akzepiert der Automat nun insgesamt?

---

Die Vereinigung der beiden Mengen.

---

Wie? Das verstehe ich nicht muss ich jetzt 111001 Vereinen oder woe?

---

Die Menge der akzeptierent Wörter ist

        \(\{w\in \{0,1\}^* |\ |w|_0 = 0\} \cup \{w\in \{0,1\}^*|\exists w'\in \{0,1\}^*:\ w = w'001\}\).

Das ist mit Vereinigung gemeint.

---

Könntest du vielleicht kurz erläutern, was du gemacht hast? Also was sind die W Dinger und so? So kann ich das nicht nachvollziehen

Aber danke

---

\(\{w\in \{0,1\}^* |\ |w|_0 = 0\}\)

Das ist die Menge aller Wörter \(w\) über dem Alphabet \(\{0,1\}\), für die gilt, dass die Anzahl der Nullen in \(w\) null ist.

Schau dir mal beschreibende Darstellung von Mengen an. Zum Beispiel ist

        \(\{x\in M | A(x)\}\)

die Menge aller Elmente aus \(M\), die die Eigenschaft \(A\) haben.

\(\{w\in \{0,1\}^*|\exists w'\in \{0,1\}^*:\ w = w'001\}\)

Das ist die Menge aller Wörter \(w\) über dem Alphabet \(\{0,1\}\), für die gilt, dass Es ein Wort \(w'\) gibt, so dass \(w = w'001\) ist.

---

Der Automat akzeptiert kein leeres Wort.

---

Also wie, er akzeptiert alles was 1 hat und keine 0 oder alles was auf 001 endet.

Das zusammentragen der Wörter verstehe ich immer noch nicht

---

Was ist mit Vereinigung der beiden Mengen gemeint?