b) genaue Erklärung?

Question

woran erkenne ich dass das größte i 2 ist?

und was wurde bei b) gemacht?

danke

Answer 1

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)

 

Answer 2

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)