Diskussion:Kontextsensitive Sprache
aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 8. Februar 2012 um 21:00 Uhr durch imported>MartinThoma(38851).
Frage zum Beispiel
Das Beispiel verstehe ich nicht. Sieht fuer mich aus wie eine Menge, nicht wie eine Grammatik.
Warum sind Kontextsensitive Sprachen unter Logarithmisch Platzbeschränkte Reduktion sowohl abgeschlossen als auch nicht abgeschlossen? Könnte mir jemand die dahinterstehenden quantenphysikalischen Effekte näher erläutern?
______________________________
Sehr gute und richtige Bemerkung! In polynomieller Zeit kann man linearen Platz verlassen, mit logarithmischem Platz nicht... Daher ist CSL unter erstem nicht abgeschlossen unter zweitem schon.
Grüße --Gerhard Buntrock 09:34, 20. Apr. 2007 (CEST)
Beispiel
Das Beispiel ist außerdem Kontextfrei, oder?
S -> ABC
A -> aA
B -> bB
C -> cC
A -> a
B -> b
C -> c
Gruß, Mario
--Mpmario 15:36, 9. Nov. 2009 (CET)
- Nein, die Anzahl der a, b und c sollen gleich sein. Gruß --ri st 09:59, 10. Nov. 2009 (CET)
