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

Kategorien

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