Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Unterschied kontextsensitive und monotone Grammatik?

–1 Punkt
1,748 Aufrufe

Hallo,

ich verstehe nicht ganz den Unterschied (falls es überhaupt einen gibt) zwischen kontextsensitiven und monotonen Grammatiken.

Ist jede kontextsensitive G auch monoton, aber nicht jede monotone G auch kontextsensitiv?
Wie kann man hier mit (echten) Teilmengen argumentieren? (Was ist (echte) Teilmenge von was?) Oder auch in Bezug zu Sprachen?

Gruß

 

Gefragt 22, Okt 2014 in SPR-AA von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

+1 Punkt

Hallo,

das ist eigentlich ganz einfach:

  • Kontextsensitive Grammatiken sind auch monoton (denn durch eine kontextsensitive Regel ϕAψϕγψ wird immer ein einzelnes Zeichen A durch eine nichtleere Zeichenfolge γ ersetzt, also kann das Wort durch die Ableitung nicht kleiner werden).
  • Monotone Grammatiken sind nicht unbedingt kontextsensitiv (denn eine Regel wie ABBA ist nicht kontextsensitiv).

Entsprechend sind kontextsensitive Grammatiken eine echte Teilmenge der monotonen Grammatiken, ABER:

  • Die Menge der durch monotone Grammatiken darstellbaren Sprachen ist gleich der Menge der durch kontextsensitive Grammatiken darstellbaren Sprachen. Beide Grammatiktypen können nämlich genau die Typ-1-Sprachen erzeugen.

Viele Grüße

Lukas König

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...