Informatiker Board | Theoretische Informatik | Kontextsensitive und Kontextfreie Grammatiken

Informatiker Board » Themengebiete » Theoretische Informatik » Kontextsensitive und Kontextfreie Grammatiken

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Kontextsensitive und Kontextfreie Grammatiken

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Pünktchen
unregistriert

Kontextsensitive und Kontextfreie Grammatiken

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Hallo!
Ich habe bezüglich kontextsensitiven und kontextfreien Grammatiken eine Frage und zwar: Ist jede kontextfreie auch gleichzeitig eine kontextsensitive Grammatik? Oder gibt es einfache Beispiele von kontextfreien Grammatiken, die nicht kontextsensitiv sind?

Meine Ideen:
Also nach meinem Verständnis der Chomsky-Hierarchie müsste eine kontextfreie auch eine kontextsensitive Grammatik sein. Allerdings haben mich einige uneindeutige Aussagen im Internet sehr darüber verwirrt. Ich habe auch leider nirgends ein Beispiel für eine kontextfreie, nicht kontextsensitive Grammatik gefunden.

Aber so wie mein Grundverständnis ist, ist eine kontextfreie Grammatik einfach eine kontextsensitive Grammatik mit weiteren Einschränkungen, was die Regeln betrifft. Liege ich da also falsch?

07.02.2018 15:02

Anton
unregistriert

Hallo Pünktchen!

Zitat:

Ist jede kontextfreie auch gleichzeitig eine kontextsensitive Grammatik?

Ja.

Zitat:

Also nach meinem Verständnis der Chomsky-Hierarchie müsste eine kontextfreie auch eine kontextsensitive Grammatik sein.

So ist es.

Bei kontextsensitiven Grammatiken (Typ 1) ist die rechte Seite der Ableitungsregeln niemals kürzer als die linke Seite. Bei kontextfreien Grammatiken (Typ 2) steht auf der linken Seite nur eine Variable. Daraus resultiert unmittelbar die obige Einschränkung. (Für $[latex]\varepsilon[/latex]$ gibt es noch Sonderregelungen)

07.02.2018 18:04

Anton
unregistriert

Oder so:

Bei der Ableitungsregel $[latex]\alpha X \beta \to ...[/latex]$ dürfen $[latex]\alpha[/latex]$ und $[latex]\beta[/latex]$ auch leer sein, d.h. $[latex]X \to ...[/latex]$ ist ein Sonderfall der kontextsensitiven Grammatik, der zur kontextfreien Grammatik führt.

07.02.2018 18:13

Pünktchen
unregistriert

Hallo Anton, vielen Dank für die Antwort! Daumen hoch

Mittlerweile habe ich zu der Frage auch noch ein bisschen im Internet rumgestöbert und dort folgendes gefunden:

"Jede kontextfreie Grammatik ist auch kontextsensitiv. -> Falsch. Zum Beispiel: G=({S},{a},{S->aS|a|epsilon},S) ist kontextfrei aber nicht kontextsensitiv." (Ist aus den Lösungen zu einer Klausur 2011 von einer Universität.)

Jetzt bin ich mir wieder unsicher. Also ist es wahrscheinlich ja doch so, dass nicht jede kontextfreie eine kontextsensitive Grammatik ist. Aber irgendwie richtig nachvollziehen warum das so ist, kann ich nicht. verwirrt

Und wie sieht das mit Sprachen aus, verhält es sich da genauso?

07.02.2018 18:47

Anton
unregistriert

Hallo Pünktchen!

Anscheinend liegt der Schlüssel in einer, von mir oben lax erwähnten, $[latex]\varepsilon[/latex]$ -Ableitung.

Manche Autoren definieren die kontextfreien Grammatiken sinngemäß mit "eine kontextsensitive Grammatik heißt kontextfrei wenn ...". In diesem Fall ist jede kontextfreie Grammatik natürlich auch kontextsensitiv.

Wenn man die kontextfreien Grammatiken [latex](V,T,P,S)[/latex]

allerdings nur über $[latex]X \to \alpha[/latex]$ mit $[latex]X \in V[/latex]$ und $[latex]\alpha \in (V \cup T)^*[/latex]$
definiert, so ist $[latex]S \to \varepsilon[/latex]$ zugelassen (wegen der Kleeneschen Hülle).

In vielen Definitionen der kontextsensitiven Grammatiken ist $[latex]S \to \varepsilon[/latex]$ erstmal explizit nicht zugelassen. Hier muss eine Ausnahmeregelung her, wobei dann nicht mehr auf der rechten Seite auftauchen darf. In deinem Beispiel ist dies aber der Fall.

07.02.2018 19:55

Anton
unregistriert

Achso: Bei Sprachen ist das nicht mehr der Fall. Jede kontextfreie Sprache ist auch kontextsensitiv. Ich kann die kontexfreie Grammatik [latex]G[/latex]

in eine kontextsensitive Grammatik [latex]G'[/latex]

umwandeln, sodass [latex]L(G) = L(G')[/latex]

07.02.2018 20:01

Pünktchen
unregistriert

Alles klar, vielen lieben Dank für deine ausführlichen Antworten! Dank dir habe ich es jetzt glaube ich verstanden! smile

07.02.2018 20:37

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Kontextsensitive und Kontextfreie Grammatiken