search

knowsys / FormaleSysteme

Unterlagen zur Vorlesung "Formale Systeme", Fakultät Informatik, TU Dresden
https://iccl.inf.tu-dresden.de/web/Formale_Systeme
44 stars 14 forks source link

Kontextsensitive Grammatik? #43

Open vivienne-amm opened 3 years ago

vivienne-amm commented 3 years ago

Im Video „Abschlusseigenschaften kontextfreier Sprachen“ sagen Sie auf Folie 9 (13:40), dass aS2->c Regel einer kontextsensitive Grammatik ist, aber |aS2| > |c| .

mmarx commented 3 years ago

Das stimmt, aS_2 -> c ist keine Regel einer kontextsensitiven Grammatik, denn die Regel ist ja verkuerzend. Das Gegenbeispiel selbst funktioniert natuerlich weiterhin, nur ist G_2 nur eine Typ-0-Grammatik, keine kontextsensitive Grammatik; es laesst sich aber leicht zu einer kontextsensitiven Grammatik erweitern, etwa, in dem die Regel in aS_2 -> cc geaendert wird.