Diskussion:Kontextsensitive Sprache
Letzter Kommentar: vor 14 Jahren von Ri st in Abschnitt Beispiel
Frage zum Beispiel[Quelltext bearbeiten]
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[Quelltext bearbeiten]
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)