Paralleles simulieren zweier Kellerautomaten

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Paralleles simulieren zweier Kellerautomaten

Beitrag von patrix » 31. Aug 2010 10:47

Hallo zusammen,
ich habe eine Frage mit einer Idee und wollte wissen, ob das richtig ist:
Warum kann man keine zwei Kellerautomaten nicht parallel simulieren?

Idee: Weil ein Kellerautomat im Gegensatz zu einer TM keine feste Speichergröße hat kann nicht wissen ab welchen Speicherbereich der 2. Kellerautomat starten kann. Von daher kann man 2 Kellerautomaten nicht parallel simulieren.

Zusatzfrage: Damit wäre ja zwei Kontextfreie Sprachen unter Vereinigung und Durchschnit nicht entscheidbar, oder?

Danke und viele Grüße Patrick

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Paralleles simulieren zweier Kellerautomaten

Beitrag von bruse » 31. Aug 2010 11:47

patrix hat geschrieben:Zusatzfrage: Damit wäre ja zwei Kontextfreie Sprachen unter Vereinigung und Durchschnit nicht entscheidbar, oder?
Was meinst Du damit? Der Schnitt zweier kontextfreier Sprachen ist im allgemeinen nicht unbedingt kontextfrei. Die Vereinigung schon, überleg Dir mal warum.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Paralleles simulieren zweier Kellerautomaten

Beitrag von patrix » 31. Aug 2010 12:48

o.k. hab mich jetzt noch mal schlau gemacht und nachgelesen, mit Vereinigung und durchschnitt. Jetzt aber nochmal zu meiner ersten Frage: die des Parallelen Simulieren zweier Kellerautomaten sind die korrekt?

Vielen Dank (besonderst an Bruse für die tolle Unterstützung in den letzten Tagen)

Patrick

Antworten

Zurück zu „Archiv“