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.)

b) genaue Erklärung?

+1 Punkt
28 Aufrufe
woran erkenne ich dass das größte i 2 ist?

und was wurde bei b) gemacht?

danke
Gefragt 29, Sep 2015 in 2011-N-02 von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

0 Punkte

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)

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
+1 Punkt

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)

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...