 zeigen dass Sprache von einen deterministischen Kellerautomaten akzeptiert wird |
jenny 53
Mitglied
Dabei seit: 01.12.2013
Beiträge: 28
 |
|
| zeigen dass Sprache von einen deterministischen Kellerautomaten akzeptiert wird |
     |
Hallo!!!
Ich will zeigen,dass die Sprache ![[latex] \{ w\epsilon \left \{ a,b,c \right \}^{*}:w=xcx^{R},x \epsilon \{a,b\}^{*}\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php? \{ w\epsilon \left \{ a,b,c \right \}^{*}:w=xcx^{R},x \epsilon \{a,b\}^{*}\}) von einen deterministischen Kellerautomaten akzeptiert wird.Wie könnte ich das zeigen?Muss ich einen Kellerautomaten malen oder kann ich das auch mit einen anderen Weg machen?
|
|
13.01.2014 23:34 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
das kommt auf den Dozenten an. Es gibt potentiell drei Wege:
- verbale Beschreibung eines Kellerautomaten
- formale Spezifikation (Automat als Tupel wie in Wikipedia und Angabe der partiellen Übergangsfunktionen)
- Angabe einer kontextfreien Grammatik
Das zeichnen eines Kellerautomaten ist sicher auch mögliche, solange anhand der Zeichnung die volle und Lückenlose Spezifikation ablesbar ist.
VG,
Karlito
|
|
|
13.01.2014 23:42 |
|
|
jenny 53
Mitglied
Dabei seit: 01.12.2013
Beiträge: 28
|
|
Also,wenn ich die kontextfreie Grammatik finde,die die Sprache generiert,bedeutet das dann,dass die Sprache von einen deterministischen Kellerautomaten akzeptiert wird?
|
|
|
13.01.2014 23:46 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Im Prinzip ja. Vorraussetzung ist aber, dass ihr das auch als Fakt heranziehen dürft. Schließlich muss bewiesen werden, dass DPDAs auch kontextfreie Grammatiken akzeptieren.
Die Angabe der Grammatik wäre auch die einfachste Variante und ist in Ca 10 Minuten erledigt. Demzufolge denke ich, dass ihr eher einen Automaten angeben sollt 
VG,
Karlito
|
|
|
13.01.2014 23:51 |
|
|
jenny 53
Mitglied
Dabei seit: 01.12.2013
Beiträge: 28
|
|
Also du meinst ich soll den Kellerautomaten verbal beschreiben?Wie könnte ich das machen? 
|
|
|
13.01.2014 23:54 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
am Besten ähnlich wie hier unter der Tabelle mit den Übergänen oder gleich komplett formal.
VG,
Karlito
|
|
|
14.01.2014 00:29 |
|
|
jenny 53
Mitglied
Dabei seit: 01.12.2013
Beiträge: 28
|
|
Ich habe versucht die verbale Beschreibung des Kellerautomaten zu machen:
-Die Charaktere(entweder a oder b) der Eingabe werden gelesen,und im Keller gespeichert,bis es ein c gelesen wird.
-Nachdem ein c gelesen worden ist,müssen die Charaktere,die gelesen werden mit der Charakter vom Keller übereinstimmten.
-wenn es nicht der Fall ist,führt es nicht zum Akzeptanzzustand.
Ist es richtig oder könnte ich was verbessern?
|
|
|
14.01.2014 01:01 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
prinzipell richtig 
. Ich würde noch beschreiben, dass der FInalzustand dann erreicht wird, wenn vom Keller das Kellerstartsymbol gelesen wird und dass wenn darüber hinaus Zeichen gelesen werden, der Fehlerzustand erreicht wird.
VG,
Karlito
|
|
|
14.01.2014 07:39 |
|
|
jenny 53
Mitglied
Dabei seit: 01.12.2013
Beiträge: 28
|
|
| Zitat: |
Original von Karlito
Hallo,
prinzipell richtig
. Ich würde noch beschreiben, dass der FInalzustand dann erreicht wird, wenn vom Keller das Kellerstartsymbol gelesen wird und dass wenn darüber hinaus Zeichen gelesen werden, der Fehlerzustand erreicht wird.
VG,
Karlito |
Vielen Dank für deine Hilfe!!!!!!
|
|
|
14.01.2014 11:01 |
|
|
|
