Hallo, hab da ein paar Fragen.
Wird jede formale Sprache von einer geeigneten Grammatik erzeugt?
Wird jede von einem NFA erkannte Sprache auch von einer geeigneten kontextfreien Grammatik erzeugt?
CNF:
S->Tb|b|aSU
T->TU|U|aa
U->bU|a
1.)
\(S->TX_b|b|X_aSU\)
\(T->TU|U|X_aX_a\)
\(U->X_bU|a\)
\(X_a->a\)
\(X_b->b\)
2.)
\(S->TX_b|b|X_aX_c\)
\(T->TU|U|X_aX_a\)
\(U->X_bU|a\)
\(X_a->a\)
\(X_b->b\)
\(X_c->SU\)
3.)
Kann man jetzt hier T->U löschen, da T->TU?
also
\(S->TX_b|b|X_aX_c\)
\(T->TU|X_aX_a\)
\(U->X_bU|a\)
\(X_a->a\)
\(X_b->b\)
\(X_c->SU\)
?
Klausurvorbereitung
Re: Klausurvorbereitung
Ja, das lässt sich exemplarisch auch mit dem CYK-Algo nachprüfen. (Die Frage ist dieselbe.)kain hat geschrieben: Wird jede formale Sprache von einer geeigneten Grammatik erzeugt?
Wird jede von einem NFA erkannte Sprache auch von einer geeigneten kontextfreien Grammatik erzeugt?
Warum willst du das tun? Ookain hat geschrieben: Kann man jetzt hier T->U löschen, da T->TU?
T -> U \(\not \leftrightarrow\) T -> TU ... das ist nicht dasselbe!
Gruß domac
Extend my dropbox space (here).
Thanks!
Thanks!
Re: Klausurvorbereitung
Warum willst du das tun?
Weil man ja nicht die Produktion T->U haben darf. Und eine neue Produktion einzufügen, würde nichts ändern.
Wie würde denn CNF aussehen?
Re: Klausurvorbereitung
Hey,
um es kurz zu fassen:
Man nehme folgende Produktionen:
X -> Z | a | yK
Z -> b | eG |wA
um das Z in der Produktion X zu entfernen musst du einfach das Z aus der Produktion, in der es vor (alleine) vorkommt (in diesem Fall in Produktion X) streichen und dafür in die selbe Produktion mit neuen Produktionen erweitern, für die das Z stand:
1.
X -> | a | yZ
Z -> b | eG |WA
G-> ....
W-> ...
A->...
2. X -> b | eG |WA | a | yZ
Z -> b | eG |WA
G-> ....
W-> ...
A->...
Somit könntest du mit deiner neuen Produktion X auch das ableiten, was du vorher mit dem enizelnen Z abgeleitest hast. Jetzt musst du halt nicht mehr den Weg über Z gehen, sondern alle Z-Produktionen sind jetzt auch in deiner neuen und erweiterten X Produktion.
Gruß
onbes
um es kurz zu fassen:
Man nehme folgende Produktionen:
X -> Z | a | yK
Z -> b | eG |wA
um das Z in der Produktion X zu entfernen musst du einfach das Z aus der Produktion, in der es vor (alleine) vorkommt (in diesem Fall in Produktion X) streichen und dafür in die selbe Produktion mit neuen Produktionen erweitern, für die das Z stand:
1.
X -> | a | yZ
Z -> b | eG |WA
G-> ....
W-> ...
A->...
2. X -> b | eG |WA | a | yZ
Z -> b | eG |WA
G-> ....
W-> ...
A->...
Somit könntest du mit deiner neuen Produktion X auch das ableiten, was du vorher mit dem enizelnen Z abgeleitest hast. Jetzt musst du halt nicht mehr den Weg über Z gehen, sondern alle Z-Produktionen sind jetzt auch in deiner neuen und erweiterten X Produktion.
Gruß
onbes
Re: Klausurvorbereitung
Du musst die Produktion von U mit in T nehmen also \(T ... | X_bU | a\).kain hat geschrieben:Warum willst du das tun?
Weil man ja nicht die Produktion T->U haben darf. Und eine neue Produktion einzufügen, würde nichts ändern.
Wie würde denn CNF aussehen?
Gruß Thomas
Extend my dropbox space (here).
Thanks!
Thanks!
Re: Klausurvorbereitung
Nein, denn es gibt in der Chomsky-Hierarchie die Klasse/Menge der allgemeinen (also aller) formalen Sprachen, die noch weiter außen (also echt größer) ist als die der Typ-0-Sprachen. Solche Sprachen kann man zwar durch eine bestimmte Eigenschaft aller Wörter darin spezifizieren, aber man kann keine Grammatik dafür angeben, sie sind also quasi zu kompliziert, um mit den beschränkten Möglichkeiten einer Grammatik eine Regel zur Erzeugung aller ihrer Wörter anzugeben.kain hat geschrieben:Wird jede formale Sprache von einer geeigneten Grammatik erzeugt?
Ja, denn die von NFAs erkannten Sprachen sind gerade die regulären Sprachen, und jede reguläre Sprache ist auch eine kontextfreie Sprache (da Typ 3 in der Chomsky-Hierarchie unter Typ 2, also eine Teilmenge ist), somit gibt es für jede solche Sprache eine kontextfreie Grammatik.kain hat geschrieben:Wird jede von einem NFA erkannte Sprache auch von einer geeigneten kontextfreien Grammatik erzeugt?
Die beiden Fragen sind im Übrigen ganz und gar nicht dasselbe, und mit dem CYK-Alhorithmus hat keine der beiden zu tun.
Nein, das kannst du nicht ohne weiteres. Wie schon erwähnt musst du den normalen Schritt des Normalisierungsalgorithmus zur Eliminierung von Produktionen mit nur einem Nicht-Terminal auf der rechten Seite durchführen.kain hat geschrieben:Kann man jetzt hier T->U löschen, da T->TU?
Re: Klausurvorbereitung
Danke an alle, die umfangreichen Antworten zu den beiden Fragen haben bei mir das "aha" ausgelöst. 
Ebenso die Hinweise zum CNF.
Ebenso die Hinweise zum CNF.
Re: Klausurvorbereitung
1.)
Für zwei Sigma-Wörter w, v gilt w ~L v genau dann, wenn x € Sigma* gilt, dass wx € L <-> vx € L.
a) Seien L1, L2 Teilmenge Sigma* regulär. Man soll jetzt mit Myhill-Nerode nachweisen, dass L := L1 Durchschnitt L2 regulär ist. Als Hinweis ist gegeben, dass man zeigen kann, in wie viele (Äquivalenzklassen) ~L2-Klassen eine ~L1-Klasse höchstens zerfallen kann.
Wie geht man hier vor?
b) Sei L die Sprache aller Wörter über dem Alphabet Sigma = {a, b, c}, die genauso oft "ac" wie "ab" enthalten. Man soll jetzt zeigen, dass L nicht regulär ist, indem man unendlich viele paarweise nicht ~L-äquivalente Wörter angibt und man soll begründen warum diese Wörter nicht äquivalent sind.
Lösung:
Sprache = (ac)^n(ab)^n
acab | epsilon
acacab | ab
acacacab | abab
...
Stimmt das soweit und wie sieht die Begründung aus?
2.)
P: Xo -> aX|aY
X -> aXY|aYY
Y -> b
Lösung:
Sprache L(G) = (a^nb^n | n >= 1)
CNF:
Xo -> XaX | XaY (a wurde durch Xa ersetzt)
X -> X1Y | X2Y (XaX und XaY wurde durch X1 und X2 ersetzt)
Y -> b
Xa -> a
X1 -> XaX
X2 -> XaY
Kellerautomat:
(q, #, €, Xo, q)
(q, Xo, €, aX, q)
(q, Xo, €, aY, q)
(q, X, €, aXY, q)
(q, X, €, aYY, q)
(q, Y, €, b, q)
(q, a, a, €, q)
(q, b, b, €, q)
Richtig so?
Danke.
Für zwei Sigma-Wörter w, v gilt w ~L v genau dann, wenn x € Sigma* gilt, dass wx € L <-> vx € L.
a) Seien L1, L2 Teilmenge Sigma* regulär. Man soll jetzt mit Myhill-Nerode nachweisen, dass L := L1 Durchschnitt L2 regulär ist. Als Hinweis ist gegeben, dass man zeigen kann, in wie viele (Äquivalenzklassen) ~L2-Klassen eine ~L1-Klasse höchstens zerfallen kann.
Wie geht man hier vor?
b) Sei L die Sprache aller Wörter über dem Alphabet Sigma = {a, b, c}, die genauso oft "ac" wie "ab" enthalten. Man soll jetzt zeigen, dass L nicht regulär ist, indem man unendlich viele paarweise nicht ~L-äquivalente Wörter angibt und man soll begründen warum diese Wörter nicht äquivalent sind.
Lösung:
Sprache = (ac)^n(ab)^n
acab | epsilon
acacab | ab
acacacab | abab
...
Stimmt das soweit und wie sieht die Begründung aus?
2.)
P: Xo -> aX|aY
X -> aXY|aYY
Y -> b
Lösung:
Sprache L(G) = (a^nb^n | n >= 1)
CNF:
Xo -> XaX | XaY (a wurde durch Xa ersetzt)
X -> X1Y | X2Y (XaX und XaY wurde durch X1 und X2 ersetzt)
Y -> b
Xa -> a
X1 -> XaX
X2 -> XaY
Kellerautomat:
(q, #, €, Xo, q)
(q, Xo, €, aX, q)
(q, Xo, €, aY, q)
(q, X, €, aXY, q)
(q, X, €, aYY, q)
(q, Y, €, b, q)
(q, a, a, €, q)
(q, b, b, €, q)
Richtig so?
Danke.
Re: Klausurvorbereitung
1. b) Die Sprache stimmt so eher nicht, denn du schließt alles aus, was in de Reihenfolge anders ist, z.B. abac
Das ist quasi ein Beweis über Myhill-Nerode, würde ich mal behaupten. Allerdings sollten die Wörter auch in der Sprache liegen, deine Beispiele tun das großteils nicht:
abac , acab
ababacac, abacabac
\((ab)^n (ac)^n\)
...
Die Begründung geht über die Definition der Äquivalenzrelation (2.4.1), da nie 2 Wörter aus L in der gleichen Äquivalenzklasse liegen können. Und damit folgen aus unendlich vielen Wörtern unendlich viele Äquivalenzklassen.
2. Die Sprache stimmt meiner Meinung nach
CNF: Es wird übersichtlicher wenn du statt Xa z.B. \(X_a\) oder A verwendest.Für Sonderzeichen generell würde ich die Tex-Formatierung verwenden.
Aber sonst sollte die CNF stimmen
Der Kellerautomat ist allerdings so nicht richtig:
- Kein akzeptierender Zustand
- Deine Zustände der Grammatik haben sich irgendwie im Kelleralphabet verheddert
- Das leere Wort wird irgendwie sehr oft gelesen^^
Das sollte ein akzeptierender PDA sein, mit #(Anfang), + für a gelesen im Kelleralphabet, Akzeptierender Zustand ist \(q_2\)
\((q_0, \#, a, +\#, q_0)\)
\((q_0, +, a, ++, q_0)\)
\((q_0, +, b, \epsilon, q_1)\)
\((q_1, +, b, \epsilon, q_1)\)
\((q_1, \#, \epsilon, \epsilon, q_2)\)
Das ist quasi ein Beweis über Myhill-Nerode, würde ich mal behaupten. Allerdings sollten die Wörter auch in der Sprache liegen, deine Beispiele tun das großteils nicht:
abac , acab
ababacac, abacabac
\((ab)^n (ac)^n\)
...
Die Begründung geht über die Definition der Äquivalenzrelation (2.4.1), da nie 2 Wörter aus L in der gleichen Äquivalenzklasse liegen können. Und damit folgen aus unendlich vielen Wörtern unendlich viele Äquivalenzklassen.
2. Die Sprache stimmt meiner Meinung nach
CNF: Es wird übersichtlicher wenn du statt Xa z.B. \(X_a\) oder A verwendest.Für Sonderzeichen generell würde ich die Tex-Formatierung verwenden.
Aber sonst sollte die CNF stimmen
Der Kellerautomat ist allerdings so nicht richtig:
- Kein akzeptierender Zustand
- Deine Zustände der Grammatik haben sich irgendwie im Kelleralphabet verheddert
- Das leere Wort wird irgendwie sehr oft gelesen^^
Das sollte ein akzeptierender PDA sein, mit #(Anfang), + für a gelesen im Kelleralphabet, Akzeptierender Zustand ist \(q_2\)
\((q_0, \#, a, +\#, q_0)\)
\((q_0, +, a, ++, q_0)\)
\((q_0, +, b, \epsilon, q_1)\)
\((q_1, +, b, \epsilon, q_1)\)
\((q_1, \#, \epsilon, \epsilon, q_2)\)