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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

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