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

1 Pluspunkt 0 Minuspunkte
74 Aufrufe
woran erkenne ich dass das größte i 2 ist?

und was wurde bei b) gemacht?

danke
in 2011-N-02 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

1 Pluspunkt 0 Minuspunkte

Hi,

schau dir am besten nochmal an, wie sich die verschiedenen Typen von Grammatiken unterscheiden. Am besten fängt man mit Typ 3 an, dafür gibt es die meisten Einschränkungen. Wenn dies nicht zutrifft, prüft man ob Typ 2 vorliegt, etc. Für Typ 2 gilt, dass ein Nonterminal auf ein oder mehrere Nonterminal- oder Terminalsymbole abbildet. Im Gegensatz zu Typ 1 muss immer von einem Nonterminal ausgehend abgeleitet werden. Da dies hier zutrifft, ist das größte i 2.

Bei der b) wird geschaut, von welchem Typ die von G erzeugte Sprache ist. Man kann erkennen, dass X immer zu mindestens einer 1 wird, Y immer zu einer durch 2 teilbaren Anzahl an 2en wird und Z zu einer durch 3 teilbaren Anzahl an 3en. Wenn man dazu die Grammatik aufschreibt, kann man versuchen, die Regeln für rechtslineare Grammatiken zu beachten um zu prüfen, ob L(G) vom Typ 3 ist.
Alternativ könnte man auch direkt die Grammatik aus a) umformulieren, sodass diese rechtslinear wird. Dann ist die Sprache nämlich auch vom Typ 3.

Gruß,
Jonas B. (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

Hallo,

es ist leicht zu erkennen, dass die Grammatik vom Typ 2 ist, jedoch nicht vom Typ 3. Also ist das größte i eben 2. Die Typ 2 Grammatik erlaubt Produktionen von einem Nonterminalsymbol auf beliebige Kombination von Nonterminal- und Terminalsymbole. (siehe Vorlesung)

In Aufgabenteile b wird eine Grammatik erzeugt, die vom Typ 3 ist (also rechtslinear) und die gleiche Sprache definiert. Somit ist gezeigt, dass die Sprache vom Typ 3 ist.

Grüße

Simon (Tutor)

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