Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2011-N-02

Beantwortet: Rechtslineare Grammatik in Greibach-NF

Fri, 04 Feb 2022 19:26:39 +0000

Hallo ueyfv,

da hast du recht, die rechtslineare Grammatik muss lambdafrei sein, damit man 'nichts' machen muss. Ansonsten muss man sie lambdafrei machen.

Die einzige Sonderregel bei der Greibach-Normalform mit Lambda ist, dass das Startsymbol auf Lambda abgebildet werden darf, wenn es auf keiner rechten Seite auftaucht (und zwar genau dann, wenn das leere Wort zur Sprache gehört)

Viele Grüße

Anne (Tutorin)

Beantwortet: Umwandlung einer kontextfreien Grammatik in eine CNF ?

Mon, 12 Feb 2018 14:32:53 +0000

Hallo,

wenn sich durch einen Schritt keine Änderung ergeben, muss dieser nicht explizit aufgeschrieben werden. (Außer es wird in der Aufgabenstellung verlangt.)
Allerdings ist es grundsätzlich von Vorteil, wenn Zwischenschritte mit angegeben werden, damit wir eventuelle Fehler nachvollziehen und Teilpunkte vergeben können.

Viele Grüße
Julia (Tutorin)

Beantwortet: alternative Argumentation PPL?

Tue, 29 Sep 2015 08:58:05 +0000

Ich vermute, du gehst davon aus, dass die Anzahl der 2er doppelt so groß wie die der 1er sein muss und die der 3er dreimal so groß. Die Sprache schreibt aber nur vor, dass die Anzahl der 2er gerade und die der 3er durch drei teilbar sein muss.

Beispiel an der ursprünglichen Grammatik:

S -> XYZ -> 1XYZ -> 1X 22 Z -> 11X 22 Z -> 11X 22 333 -> 111X 22 333 -> 1111 22 333

Deshalb liegt \(1(n-j+5j)2^{2n}3^{3n}\) innerhalb der Sprache. (Über X -> 1X | 1 kann man beliebig viele 1en erzeugen, ohne Auswirkungen auf den 2er bzw. 3er Block ...)

Die Sprache der Wörter der Bauart \( 1^n 2^{2n} 3^{3n} \) ist nicht vom Typ 3 (siehe dein Pumping-Lemma-Beweis)

Gruß,

Tobias (Tutor)

Beantwortet: d): N --> Lamda bei Greibach-Normalform?

Tue, 29 Sep 2015 08:54:42 +0000

Sie haben recht, dass die Regel N --> lambda natürlich bei der Greibach Normalform nicht erlaubt ist.

Die Lösung in der Klausur ist das minimal geforderte (und streng genommen auch nicht ganz korrekt), wenn Sie an dieser Stelle geschrieben hätten, dass n--> zu viel ist, dann hätten Sie natürlich auch die volle Punktzahl erhalten.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Nonterminal- und Terminalzeichen in falscher Reihenfolge ?

Tue, 29 Sep 2015 08:52:05 +0000

Hallo,

du hast recht. Bisher war eine Grammatik wie folgt definiert: G = (N, T, P, S). Somit müsste man die Mengen vertauschen, also so: G =({S,X,Y,Z},{1,2,3},P,S). Die Reihenfolge innerhalb der Klammern macht keinen Unterschied, da es Mengenklammern sind. In der Klausur ist die Reihenfolge der Elemente des Tupels "prinzipiell" nicht egal.

Grüße

Simon( Tutor)

Beantwortet: b) genaue Erklärung?

Tue, 29 Sep 2015 08:50:51 +0000

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)