Hi,

ich bin mir nicht ganz sicher, ob die definition von kontextsensitiven grammatiken richtig verstanden habe.
bei wiki wird kontextsensitiv folgendermaßen definiert: http://de.wikipedia.org/wiki/Kontextsensitive_Grammatik
also eine grammatik ist kontextsensitiv, wenn alle produktionen folgende form haben:
aCb -> awb, wobei C ein nonterminal ist und a, b, w aus V*, w nicht leer.
also darf C nur ersetzt werden, wenn es in einem bestimmten kontext steht. ich versteh die definition so, dass w aber auch in demselben kontext sein muss wie C, stimmt das?
also aCb -> aeb wäre kontextsensitiv, aber
aCb -> eb wäre doch nicht kontextsensitv, weil das a fehlt, oder?
ich hab im internet ein paar beispiele für kontextsensitive grammatiken gefunden und die enthalten teilweise produktionen wie:
CD -> DC
so eine produktion widerspricht doch der definition, weil sich der kontext durch das ersetzen ändert, oder?

(Edit: Topictitel)

da musst du dich in den Beispielen verguckt haben oder diese sind falsch,
hast du noch die Links darauf?

CD -> DC geht nicht, siehe dazu auch:
http://3773.rapidforum.com/topic=101679783480

schön, dann hab ich die definition wohl richtig verstanden ;-)

einer der links ist:
http://www.cs.fhm.edu/~vogt/gdi/Formale_Sprachen_2.pdf (folie 60)
bei diesem links gibt es zwei definitionen von kontextfrei, bei der einen wird nur die monotonie der grammatik gefordert und bei der anderen der gleiche kontext. ist dann wohl definitionssache.

also aCb -> aeb w�re kontextsensitiv, aber
aCb -> eb w�re doch nicht kontextsensitv, weil das a fehlt, oder?

Wenn das e ein Symbol ist und keine Variable, die f�r ein
Wort steht (sonst k�nnte ja e=ax sein), dann ist aCb -> eb
nach der Definition im Skript in kontextsensitiven Grammatiken
nicht erlaubt.

ich hab im internet ein paar beispiele f�r kontextsensitive grammatiken gefunden und die enthalten teilweise produktionen wie:
CD -> DC
so eine produktion widerspricht doch der definition, weil sich der kontext durch das ersetzen �ndert, oder?

Nach der Definition im Skript ist es nicht erlaubt. Aber im
Skript wird ja auch gezeigt, dass die monotonen Grammatiken
dieselbe Klasse von Sprachen erzeugen wie die kontextsensitiven.
Deshalb werden in manchen B�chern kontextsensitiven Grammatiken
so definiert wie bei uns die monotonen. Das erspart dann
den Nachweis, dass beide Arten dieselbe Klasse erzeugen
(den man f�r den LBA-Beweis braucht), hat aber den Nachteil,
dass dann niemand wei�, warum die Dinger "kontextsensitiv" hei�en.
Im Buch von Sch�ning ist das zum Beispiel so.

Ich vermute mal, dass das auf der Seite mit dem Beispiel
so gemacht wird, denn diese Produktion ist ja monoton.

Nach der Definition im Skript ist es nicht erlaubt. Aber im
Skript wird ja auch gezeigt, dass die monotonen Grammatiken
dieselbe Klasse von Sprachen erzeugen wie die kontextsensitiven.
Deshalb werden in manchen B�chern kontextsensitiven Grammatiken
so definiert wie bei uns die monotonen. Das erspart dann
den Nachweis, dass beide Arten dieselbe Klasse erzeugen
(den man f�r den LBA-Beweis braucht), hat aber den Nachteil,
dass dann niemand wei�, warum die Dinger "kontextsensitiv" hei�en.
Im Buch von Sch�ning ist das zum Beispiel so.

Ich vermute mal, dass das auf der Seite mit dem Beispiel
so gemacht wird, denn diese Produktion ist ja monoton.

jo, stimmt. hab nochmal nachgesehen, da wird gesagt, dass monoton äquivalent zu kontextsensitiv ist.