DEA: Einstieg, keine Vorkenntnisse, keinen Plan – Hilfe

Question

Ich brauche dringend Hilfe bei diesem AB. Ich war jetzt 2 Wochen nicht in der Schule (hatte Corona) und komme nicht mehr hinterher.

Wir machen jetzt DEA und haben ein AB bekommen. Ich bin da jetzt schon 3 Tage dran, aber bekomme es nicht hin. :( Bitte, ich kriege sonst eine 6.

DEAs.pdf

Beispiel
Wir wollen einen Automaten \( M \) diskutieren, der Dualzahlen der Form "1010010" bzw. Dualbrüche der Form "10010.01110" erkennt. Wir wollen zur Erleichterung auch leere Zahlen akzeptieren und Zahlen der Formen "xxxxx." und "xxxxx.0". Das heißt, der Automat soll alle Wörter über dem Alphabet \( \left\{0,\:1,\: .\right\}\) akzeptieren, die keinen oder genau einen Punkt enthalten.

\( M=\left(\left\{s_{0},\: s_{1},\: s_{2}\right\},\left\{0,\:1,\:.\right\},\: \mathrm{d},\: s_{0},\:\left\{s_{0},\: s_{1}\right\}\right) \)

\( \mathrm{d}\left(s_{0},\: 0\right) = s_{0},\quad \mathrm{d}\left(s_{0},\: 1\right) = s_{0},\quad \mathrm{d}\left(s_{0},\: .\right) = s_{1} \)
\(\mathrm{d}\left(s_{1},\: 0\right) = s_{1},\quad \mathrm{d}\left(s_{1},\: 1\right) = s_{1},\quad \mathrm{d}\left(s_{1},\: .\right) = s_{2} \)
\(\mathrm{d}\left(s_{2},\: 0\right) = s_{2},\quad \mathrm{d}\left(s_{2},\: 1\right) = s_{2},\quad \mathrm{d}\left(s_{2},\:.\right)=s_{2} \)

Grafisch stellt sich der oben beschriebene Automat wie folgt dar:

(siehe Abbildung)

Die Zustände sind als Kreise dargestellt und die Übergangsregeln mit den Pfeilen zwischen den Zuständen. Den Startzustand erkennt man an dem Pfeil, der aus dem Nichts auf ihn zeigt. Die Endzustände sind doppelt umkreist. Neben den Übergängen steht das Symbol, welches der Automat einlesen muss, um den Übergang durchzuführen. Beispielsweise bleibt der obige Automat im Startzustand, wenn er eine 0 oder eine 1 einliest. Trifft er im Eingabewort irgendwann auf einen Punkt, dann geht er in den Zustand \( s_{1} \). Da dies ein Endzustand ist, würde der Automat das Wort akzeptieren.

Aufgabe 1:
Zeigen Sie, dass die folgenden Zahlen/ Wörter von dem Automaten akzeptiert werden:
[a] 10101
[b] 1.11
[c] .10
[d] .
Zeigen Sie, dass die folgenden Zahlen nicht von dem Automaten akzeptiert werden:
[e] 1.1.
[f] 000111000..

Aufgabe 2:
Wollen wir dagegen leere Zahlen und Zahlen der Formen "xxxxx." und ".xxxx" nicht akzeptieren, so müsen wir den Automaten folgendermaßen modifizieren:

(siehe Abbildung)

Geben Sie das zu diesem Automaten gehörende 5-Tupel \(N\) an.

Aufgabe 3:
Wollen wir auch
a) zulassen, dass Zahlen der Form ".xxxx" möglich sind,
b) führende Nullen vor einer Eins vor dem Dualpunkt unterdrücken,
müssen wir den Automaten weiter modifizieren.

Aufgabe 4:
Beschreiben Sie die Sprachen, die durch die endlichen Automaten erkannt werden, deren Übergangsgraphen in den folgenden Abbildungen dargestell sind. (Aufgabe unvollständig)

Ist ein AB kein Buch!! Also bitte nicht löschen

Answer 1

Aufgabe 1:
Zeigen Sie, dass die folgenden Zahlen/ Wörter von dem Automaten akzeptiert werden:
[a] 10101
[b] 1.11
[c] .10
[d] .
Zeigen Sie, dass die folgenden Zahlen nicht von dem Automaten akzeptiert werden:
[e] 1.1.
[f] 000111000..

Diese Zustandsfolgen führen zum Akzepieren des jeweiligen Wortes: $$ \textrm{[a]}\quad\xrightarrow{}s_0\xrightarrow{1}s_0\xrightarrow{0}s_0\xrightarrow{1}s_0\xrightarrow{0}s_0\xrightarrow{1}s_0\\ \textrm{[b]}\quad\xrightarrow{}s_0\xrightarrow{1}s_0\xrightarrow{.}s_1\xrightarrow{1}s_1\xrightarrow{1}s_1\\ \textrm{[c]}\quad\xrightarrow{}s_0\xrightarrow{.}s_1\xrightarrow{1}s_1\xrightarrow{0}s_1\\ \textrm{[d]}\quad\xrightarrow{}s_0\xrightarrow{.}s_1 $$ Diese Zustandsfolgen führen zum Nichtakzeptieren des jeweiligen Wortes: $$ \textrm{[e]}\quad\xrightarrow{}s_0\xrightarrow{1}s_0\xrightarrow{.}s_1\xrightarrow{1}s_1\xrightarrow{.}s_2\\ \textrm{[f]}\quad\xrightarrow{}s_0\xrightarrow[\textrm{3 mal}]{0}s_0\xrightarrow[\textrm{3 mal}]{1}s_0\xrightarrow[\textrm{3 mal}]{0}s_0\xrightarrow{.}s_1\xrightarrow{.}s_2$$ Eine abkürzende Schreibweise fasst Teilpfade ohne Zustandsänderung zusammen, etwa so: $$\textrm{[c]}\quad\xrightarrow{}s_0\xrightarrow{.}s_1\xrightarrow{10}s_1 $$

Comments

Dankeschön

Ok, das hatte ich jetzt auch so ungefähr raus. Könntest du mir vielleicht bei dem rest helfen?

---

Na ja, meine Zeit ist ein wenig beschränkt. Mach mal ein paar Vorschläge und dann sehen wir weiter.

---

Danke für deine Mühe, ich habe jetzt im Schulbuch mir die 5 Seiten über DEA und NEA durchgelesen und im Internet studyfy Seiten über das Thema plus Videos angeguckt und ich verstehe es einfach nicht, das erste konnte ich ja noch verstehen, dass z.B. wenn der Fogezustand mit dem aktuellen Zustand übereinstimmt nichts verändert wird etc...aber den rest, obwohl es bestimmt simpel ist kriege ich nicht hin. Ich habe auf dem Zeignus in Info eine 2, also dumm bin ich nicht oder so hahaha aber ich muss sowas einfach nachvollziehen können und das kann ich einfach gerade nicht, obwohl ich jetzt bestimmt locker 3h daran sitze( mache jetzt zur Abwechslung Mathe Ha) Ich denke meine Abwesenheit durch Corona war zu groß und deshalb komme ich nicht mit, aber der Leher erwartet das eknfach:( also bitte nicht denken, dass ich euch ausnutze oder so. Aufjedenfall vielen dank ich probiere es weiter, aber ka ich krieg das nicjt hin. Durch deine Erklärung und weiteren Recherchen konnte ich Aufgabe 1 (erste Hälfte) gut nachvollziehen.

---

Guten Abend liebe Leute, also ich sitze wieder seit 1h an den Aufgaben und Knobel rum aber keine Chance ich verstehe es einfach nicht, ich wäre euch sehr verbunden wenn ihr mir helfen könntet. Ich habe nächste Woche wieder Info und bin sonst am Arsch

---

So, ich habe den Fragenstart etwas leserlicher gestaltet und meine Antwort zu Aufgabe 1 vervollständigt. Du müsstest mal mitteilen, was genau du nicht verstehst und welche Fragen du dazu im einzelnen hast.

---

Danke Danke Danke . Das ist mega lieb von dir. Ich verstehe glaub ich das Prinzip nicht, also kann es nicht nachvollziehen. Also bei [a] hat man da einfach auf diese übergangsdinger geguckt und da die Folgezustand mit dem aktuellen übereinstimmt musste man nix ändern an S0 oder wie? Und es von [a] - [d] auch keiner km Endzustand S2, werden dann alle verworfen oder wie? Ich hab so viel gelesen aber verstehe es nicht. Und bei [e] warum wird es nicht akzeptiert? Es fängt doch mit dem Startzustand S0 an und endet am endzustand S2, das verstehe ich einfach nicht. Echt sry, ich versuchs wenigstens. Und was sind 5 Tupel N? Ich hab das zwar auch gegoogelt aber ich werde daraus nicht schlau.

Und was bedeutet bei [f] das ,,3mal", muss ich das also dreimal machen oder reicht das so? Weil das ja z.B. 3 Nullen sind.

Echt ich verstehe es nicht. Ich versuche jetzt auch mal die anderen Aufgaben habe bis Montag Zeit (also morgen) und dann naja ist halt so.

Aber echt mega von dir

---

Ist das die Lösung von Aufgabe 2? M=({So,S1,S2,S3,S4}, {0,1,.}, d ,S1, {S1,S2})

Keine Ahnung ob das für Aufgabe 2 stimmt

---

Wie nennt man nochmal die Zahlen hinter d= ?

---

Wie modifiziert man denn den Automaten? Die erste Aufgabe habe ich nach längerem betrachten jetzt verstanden, bis auf den Fakt das bei dein ersten der Endzustand nicht da ist aber er akzeptiert wird und bei der anderen Aufgabe der Endzustand da ist aber es nicht akzeptiert wird. Bei 3..soll och das Bild verändern oder was? Oder muss ich wieder was mit Pfeilen oder etwas an dem 5 tupel n ändern?

Sry, für die Fragen

---

Ein DEA verarbeitet das Wort zeichenweise von links nach rechts. Ist das Wort zu Ende, allso keine Zeichen mehr vorhanden, dann stoppt der Automat. Befindet er sich dann in einem der festgelegten Endzustände, gilt das Wort als akzeptiert, sonst eben nicht. Die Menge der Endzustände sind der letzte Eintrag in dem Fünftupel bzw. die doppelt umkreisten Knoten im Übergangsgraphen. In Aufgabe 1, also dem Beispiel, sind es die Zustände \(s_0\) und \(s_1\).

---

Ah ok, ist meine Aufgabe 2 richtig?

---

Nein, richtig wäre $$M=\left(\left\{s_0,\:s_1,\:s_2,\:s_3,\:s_4\right\},\: \left\{0,\:1,\:.\right\},\: \mathrm{d},\: s_0,\: \left\{s_1,\: s_3\right\}\right),$$ das heißt, der Anfangszustand und die Endzustandsmenge waren falsch. Außerdem fehlt noch die Beschreibung von d, etwa durch Aufzählen der Funktionswerte wie im Beispiel. Natürlich tut es auch eine entsprechende Tabelle.

---

Oh ok danke,

Dass muss ich doch auch nur bei Aufgabe 3a machen oder? Nur das ich noch bei den übergangswerten eine x erweitere oder ist das falsch

---

Bei Aufgabe 3 sollen auch Zahlen über { 0, 1, . } akzeptiert werden, die mit einem Dualpunkt beginnen. Desweiteren sollen Zahlen mit führenden Nullen ausgeschlossen werden. Beispiele:

".1" wird akzeptiert,
".10" wird auch akzeptiert (warum eigentlich?),
"0.10" wird akzeptiert,
"01.1" wird nicht akzeptiert usw.