Diskussion:Kontextsensitive Sprache

Frage zum Beispiel

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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)Beantworten

Beispiel

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

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)Beantworten

Nein, die Anzahl der a, b und c sollen gleich sein. Gruß --ri st 09:59, 10. Nov. 2009 (CET)Beantworten

Abschnitt hinzufügen