Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- zeigen dass Sprache von einen deterministischen Kellerautomaten akzeptiert wird (http://www.informatikerboard.de/board/thread.php?threadid=1778)

Geschrieben von jenny 53 am 13.01.2014 um 23:34:

  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] 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?


Geschrieben von Karlito am 13.01.2014 um 23:42:

 

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


Geschrieben von jenny 53 am 13.01.2014 um 23:46:

 

Also,wenn ich die kontextfreie Grammatik finde,die die Sprache generiert,bedeutet das dann,dass die Sprache von einen deterministischen Kellerautomaten akzeptiert wird?


Geschrieben von Karlito am 13.01.2014 um 23:51:

 

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 Augenzwinkern

VG,

Karlito


Geschrieben von jenny 53 am 13.01.2014 um 23:54:

 

Also du meinst ich soll den Kellerautomaten verbal beschreiben?Wie könnte ich das machen? verwirrt


Geschrieben von Karlito am 14.01.2014 um 00:29:

 

Hallo,

am Besten ähnlich wie hier unter der Tabelle mit den Übergänen oder gleich komplett formal.

VG,

Karlito


Geschrieben von jenny 53 am 14.01.2014 um 01:01:

 

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? verwirrt


Geschrieben von Karlito am 14.01.2014 um 07:39:

 

Hallo,

prinzipell richtig Daumen hoch . 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


Geschrieben von jenny 53 am 14.01.2014 um 11:01:

 

Zitat:
Original von Karlito
Hallo,

prinzipell richtig Daumen hoch . 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!!!!!! Daumen hoch


Forensoftware: Burning Board, entwickelt von WoltLab GmbH