Kellerautomaten(PDA)
2005-07-11 16:36
Anonymer User
Kann jemand mir sagen was ist ein PDA und ein DPDA und der Unterschied?Danke!!
Kellerautomaten(PDA)
Re: Kellerautomaten(PDA)
2005-07-11 17:03
Calamari
PDAs sind sog. Push Down Automates (das letzte Wort ist garantiert Falsch geschrieben, den ich glaube da müsste irgendwo noch ein "o" hin). DPDAs sind halt die deterministische Varianten der PDAs. Auf Deutsch Kellerautomaten.
Wozu dienen Sie? Ganz einfach. Ähnlich der Endlichen Automaten, beschreiben die PDAs auch eine Sprache, in dem Fall die Sprache der Kontextfreien Grammatiken. Wobei anzumerken ist, das DPDAs nur eine echte Teilmenge der Kontextfreien Sprache beschreibt.
Funktionsweise ist hier, das sie mit einem Keller arbeiten. Ein Stack im Grunde, wo man Zeichen des Kelleralphabets rein legt, und LILO-like das letzte reingelegte auch zuerst rausnimmt. Hierbei kann ein Kellerautomat ein Wort auf zwei Arten akzeptieren: Mit endzustand wie bei den FAs und mit leerem Keller, hierbei muss der Keller komplett leer sein, nichtmal ein Boden darf drin sein. [img]http://www.fb18.de/gfx/23.gif[/img]
Wie die genau aussehen, kann man im Skript nachsehen, oder nochmal die Musterlösungen der Übungsaufgaben überfliegen.
Wozu dienen Sie? Ganz einfach. Ähnlich der Endlichen Automaten, beschreiben die PDAs auch eine Sprache, in dem Fall die Sprache der Kontextfreien Grammatiken. Wobei anzumerken ist, das DPDAs nur eine echte Teilmenge der Kontextfreien Sprache beschreibt.
Funktionsweise ist hier, das sie mit einem Keller arbeiten. Ein Stack im Grunde, wo man Zeichen des Kelleralphabets rein legt, und LILO-like das letzte reingelegte auch zuerst rausnimmt. Hierbei kann ein Kellerautomat ein Wort auf zwei Arten akzeptieren: Mit endzustand wie bei den FAs und mit leerem Keller, hierbei muss der Keller komplett leer sein, nichtmal ein Boden darf drin sein. [img]http://www.fb18.de/gfx/23.gif[/img]
Wie die genau aussehen, kann man im Skript nachsehen, oder nochmal die Musterlösungen der Übungsaufgaben überfliegen.
Re: Kellerautomaten(PDA)
2005-07-11 18:18
Anonymer User
PDAs sind sog. Push Down Automates (das letzte Wort ist garantiert Falsch geschrieben, den ich glaube da müsste irgendwo noch ein "o" hin).
push down automaton [img]http://www.fb18.de/gfx/25.gif[/img]
Re: Kellerautomaten(PDA)
2005-07-11 22:53
korelstar
… und LILO-like das letzte reingelegte auch zuerst rausnimmt.Du meinst LIFO. [img]http://www.fb18.de/gfx/25.gif[/img]
Re: Kellerautomaten(PDA)
2005-07-12 00:59
Brokkoli
… und LILO-like das letzte reingelegte auch zuerst rausnimmt.Du meinst LIFO. [img]http://www.fb18.de/gfx/25.gif[/img]
nicht FILO ? [img]http://www.fb18.de/gfx/24.gif[/img]
Re: Kellerautomaten(PDA)
2005-07-12 11:56
Calamari
hmm, stimmt meinte LIFO. Sonst gäbe das ganze ja noch einen anderen kranken Sinn ;)
Re: Kellerautomaten(PDA)
2005-07-12 20:25
Anonymer User
hmm, stimmt meinte LIFO. Sonst gäbe das ganze ja noch einen anderen kranken Sinn ;)Welchen? [img]http://www.fb18.de/gfx/3.gif[/img] Sag ihn mir! [img]http://www.fb18.de/gfx/28.gif[/img]
Re: Kellerautomaten(PDA)
2005-07-13 20:02
Anonymer User
Bemerkenswert wäre auch noch, dass man nicht weiß, ob LBAs und DLBAs die selbe Klasse von Sprachen akzeptieren. Das ist das sogenannte LBA-Problem.
Re: Kellerautomaten(PDA)
2005-07-13 21:51
georg
Bemerkenswert wäre auch noch, dass man nicht weiß, ob LBAs und DLBAs die selbe Klasse von Sprachen akzeptieren. Das ist das sogenannte LBA-Problem.
Das ist richtig, aber hier ging es um PDA bzw. DPDA (LBA und
DLBA kommen erst in F3 [img]http://www.fb18.de/gfx/28.gif[/img]). Um also Verwirrung vorzubeugen:
Von DPDAs weiß man natürlich, dass sie nicht die gleiche Klasse
von Sprachen akzeptieren wie PDAs.