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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

2 Pluspunkte 0 Minuspunkte
325 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?
in 2009-N-03 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

2 Pluspunkte 0 Minuspunkte
 
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

 

von uafjv uafjv Tutor(in) (168k Punkte)  
1 Pluspunkt 1 Minuspunkt

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...