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

1 Pluspunkt 0 Minuspunkte
57 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)  
...