Chomsky Grammatik Theoretische Informatik?
a)
L2 ist vom Typ 1
L3 ist vom Typ 2
L1 ?
b) Man könnte zu L1 eine reguläre Grammatik angeben, z. B.
S -> aA |aS
A -> bC
C -> cC | cD
D -> d
Wie man sieht ist die Grammatik zur Sprache L1 regulär Typ 3.
Wenn man aber an dann z. B. an das Pumping Lemma für Typ 3 Sprachen denkt, dann kann man ja nur eine Stelle Pumpen. Womit das Pumping Lemma zeigen würde, das die Sprache nicht von Typ 3 bzw. regulär ist.
Welchen Typ hat L1 jetzt in der Chomsky-Hierarchie?
1 Antwort
L2 und L3 passt.
L1 ist Typ 3. Deine angegebene Grammatik sollte da funktionieren.
Das Pumping Lemma ist hier allerdings (wie es auch sein muss) erfüllt, denn es gibt zu jedem Wort eine passende Zerlegung. Man wählt z.B. v := a, und kann so die a's aufpumpen.
Nein, muss man nicht. Es reicht, einen pumpbaren Teil zu finden.
Ob da noch andere, unabhängige Teile sind, welche man theoretisch aufpumpen könnte, ist egal.
Deswegen ist das Pumping Lemma auch kein hinreichendes Kriterium für reguläre Sprachen.
Der Nutzen des Pumping Lemmas besteht darin, bei einer Sprache sinngemäß recht leicht zu zeigen: "Kein Teilwort von Wörtern in L ist durch beliebiges Aufpumpen von Zeichen entstanden. Also wird sie erst recht nicht regulär sein.
Und nicht für reguläre Sprachen zu zeigen: "Die (sehr langen) Wörter sind alle nur durch aufpumpen entstanden". Teilwörter davon jq, aber vielleicht gibt es auch noch nichtreguläre Teilwörter.
Hoffe das hilft eher als dass es verwirrt ^^
Und was ist mit den c's bei L1, die muss man doch auch pumpen können? Oder nicht? Warum pumpst du jetzt hier nur die a's beim Pumping Lemma für Typ3?