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

0 Pluspunkte 0 Minuspunkte
17 Aufrufe
Hallo, ich habe eine Frage:

In der oben genannten Klausur im Aufgabenteil 3c) finden wir heraus, dass weil wir den regulären Ausdruck formuliert haben, die Grammatik vom Typ 3 ist. Jedoch haben wir davor im Teil a) wegen der letzten Produktion herausgefunden, dass es eine Typ 0 Grammatik ist.

Jetzt bin ich etwas verwirrt. Beide Grammatiken stellen ja die gleiche Sprache dar. Heißt das, dass es für die gleiche Sprache verschiedene Grammatik-Typen gibt?

Besten Dank!
in 2009-N-03 von ueyfv ueyfv Lernwillige(r) (310 Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Hallo ueyfv,

einzelne Sprachen können mithilfe unterschiedlicher Grammatiken beschrieben werden (als Beispiel kannst du im Tut 1 Nr.1b) schauen). Die Regelmenge unterscheidet sich dabei etwas, wie hier bei der Aufgabe.
Welche Sprache da beschrieben wird, muss nicht unbedingt davon abhängen bzw. es gibt unterschiedliche Ansätze, wie man sie beschreiben kann.
Und eine Sprache vom Typ 3 ist automatisch auch eine Sprache vom Typ 0, da es nur mehr Einschränkungen gibt.

Aber man kann nicht jede Sprache vom Typ 0 auch als z.B. rechtslineare Sprache schreiben, also die Grammatik von Typ 0 ist deutlich Mächtiger als die Grammatik Typ 3 (und auch als 2 oder 1).

Falls noch etwas unklar ist, kannst du gerne noch einmal nachfragen
von uvlwv uvlwv Info-Genie (9.4k Punkte)  
...