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!
 

 

a): Typ 1 Grammatik - monoton und kontextsensitiv?

+2 Punkte
135 Aufrufe
Meine Frage (bezieht sich auf Aufgabenteil a) ) ist nun, ob eine monotone Grammatik vom Typ 1 ist oder ob eine Typ 1 Grammatik monoton und kontextsensitiv sein muss und deshalb die in der Aufgabenstellung beschriebene Grammatik nicht vom Typ 1 ist, da sie nur monoton aber nicht kontextsensitiv ist?
Gefragt 29, Sep 2015 in 2009-N-03 von uafjv uafjv Tutor(in) (166,490 Punkte)  

2 Antworten

+2 Punkte
 
Beste Antwort

Hallo,

hier eine kurze Korrektur von unserer Seite:

Jede kontextsensitive Grammatik ist monoton, aber nicht jede monotone Grammatik ist kontextsensitiv. Jedoch ist es genau so, wie Tobias geschrieben hat, jede monotone Grammatik kann auch in eine kontextsensitive Grammatik umgewandelt werden.

Viele Grüße

Friederike Pfeiffer-Bohnen, Micaela Wünsche und Lukas König

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (166,490 Punkte)  
0 Punkte

Grundsätzlich: man muss zwischen dem Typ der Grammatik und dem Typ der Sprache unterscheiden, die die Grammatik erzeugt. Eine Grammatik kann von einem allgemeineren Typ sein als die Sprache, die sie erzeugt (man kann die Grammatik komplizierter machen als nötig)

Eine Grammatik vom Typ 1 muss kontextsensitiv sein (aber nicht unbedingt monoton). Eine Grammatik, die "nur" monoton, aber nicht kontextsensitiv ist, ist daher nicht vom Typ 1.

Laut Vorlesungsfolien kann man jedoch jede monotone Grammatik in eine kontextsensitive Grammatik umwandeln, d.h. jede monotone Grammatik erzeugt eine Sprache vom Typ 1.

Gruß,

Tobias (Tutor)

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (166,490 Punkte)  
...