Klausurvorbereitung

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Klausurvorbereitung

Beitrag von kain » 22. Aug 2011 11:09

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

?

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Klausurvorbereitung

Beitrag von Domac » 22. Aug 2011 12:46

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?
Ja, das lässt sich exemplarisch auch mit dem CYK-Algo nachprüfen. (Die Frage ist dieselbe.)
kain hat geschrieben: Kann man jetzt hier T->U löschen, da T->TU?
Warum willst du das tun? Oo
T -> U \(\not \leftrightarrow\) T -> TU ... das ist nicht dasselbe!

Gruß domac
Extend my dropbox space (here).
Thanks!

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Klausurvorbereitung

Beitrag von kain » 22. Aug 2011 16:44

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?

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Klausurvorbereitung

Beitrag von onbes » 23. Aug 2011 09:40

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

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Klausurvorbereitung

Beitrag von Domac » 23. Aug 2011 11:33

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?
Du musst die Produktion von U mit in T nehmen also \(T ... | X_bU | a\).
Gruß Thomas
Extend my dropbox space (here).
Thanks!

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Klausurvorbereitung

Beitrag von dschneid » 23. Aug 2011 19:01

kain hat geschrieben:Wird jede formale Sprache von einer geeigneten Grammatik erzeugt?
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 von einem NFA erkannte Sprache auch von einer geeigneten kontextfreien 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.

Die beiden Fragen sind im Übrigen ganz und gar nicht dasselbe, und mit dem CYK-Alhorithmus hat keine der beiden zu tun.
kain hat geschrieben:Kann man jetzt hier T->U löschen, da T->TU?
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
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Klausurvorbereitung

Beitrag von kain » 23. Aug 2011 20:32

Danke an alle, die umfangreichen Antworten zu den beiden Fragen haben bei mir das "aha" ausgelöst. :)
Ebenso die Hinweise zum CNF.

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Klausurvorbereitung

Beitrag von kain » 29. Aug 2011 11:08

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.

Tobio
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 4. Okt 2010 15:47

Re: Klausurvorbereitung

Beitrag von Tobio » 31. Aug 2011 15:44

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

Antworten

Zurück zu „Archiv“