Informatiker Board | Theoretische Informatik | Kontextsensitive und Kontextfreie Grammatiken

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 7 Beiträge

Pünktchen

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

Anton

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]

Anton

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.

Pünktchen

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?

Anton

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.

Anton

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)

Pünktchen

Kontextsensitive und Kontextfreie Grammatiken

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?