# Chomsky Normalform



## b1zarRe (7. Aug 2011)

Hi,

ich schreibe bald eine Klausur und das einzige Thema was mir noch Kopfzerbrechen bereitet ist die CNF(Chomsky Normalform). Ich habe jetzt schon in 2 Bücher, Skript und Google sowie Youtube nach Erklärungen gesucht finde das aber alles sehr verwirrend, weil überall leicht veränderte Heransgehensweise beschrieben wird.

Kennt ihr vielleicht noch ein gutes (Video)tutorial was dies leicht erklärt? Ich habe mir zb.: Theoretische Informatik - Chomsky Normalform (CNF)
Eleminieren von nutzlosen Variablen Video - sevenload

sowie die Videos hiervon angesehen und versucht nachzumachen, aber bei neuen Aufgaben stoße ich immer wieder auf weitere Probleme...


----------



## XHelp (7. Aug 2011)

Der 1. Link liefert eigentlich ganz brauchbare Erklärung. Vlt lohnt es eher irgendeine Beschreibung versuchen zu verstehen, anstatt auf gut glück eine andere suchen.
Tretten denn bei dir konkrete Fragen auf, wenn du an neuen Aufgaben es durchspielst?


----------



## b1zarRe (10. Aug 2011)

Ich habe mich nun an folgende Aufgabe probiert... jedoch nach dem Java App (CNF - Chomsky-Normalform kontextfreier Grammatiken berechnen) nicht richtig... Ich verstehe einfach nicht, was ich ab Punkt 2 falsch mache?! (Kettenregel)

*Aufgabe*:

Bringen Sie mithilfe von Entfernen von Epsilon Regel, Kettenregel, Nutzloser/Nichtterminierender Zeichen und Überführung in die Chomsky Normalform:

S -> ASB
S -> epsilon
A -> aAS
A -> a
B -> SbS
B -> A
B -> bb

*1.) Epsilon Regeln*: Ich ersetze jedes Vorkommen auf der rechten Seite von S (da S -> epsilon) mit einer neuen Regel, wo dieses Nichtterminalzeichen nicht mehr vorkommt, also beispielsweise:
S -> ASB in S -> AB und S -> ASB Regel wird gelöscht. Hiernach verbleibt:

S -> ASB
S -> AB
A -> aA
A -> aAS
A -> a
B -> SbS
B -> bS
B -> Sb
B -> b
B -> A
B -> bb

*2.) Kettenregeln*: Alleinstehende Terminalzeichen auf der rechten Seite ersetze ich durch ihre Produktionregel, zb.: B -> A daraus wird B -> a | aA und B -> A wird gelöscht.
Es verbleibt:

B -> a
B -> aAS
B -> aA
S -> AB 
S -> ASB
B -> SbS
B -> bS
B -> Sb
B -> b
B -> bb
B -> A

*3.) a)* Nicht erreichbar von S: Nicht erreichbare Zustände durchlaufe ich, und gucke ob ein Nichtterminalzeichen nutzlos ist. Ist hier aber nicht der Fall
*b)* Nicht terminierend: Ich suche mir ein Terminalzeichen aus was alleine steht und laufe rückwärts die Regeln durch und markiere, welche Zustände dadurch auch termierend sein können. (hier: alle)

*4.)* Ich bringe die bisherige Form zb.: S -> ABC in S -> AX und X -> BC (gleiches für Terminalzeichen).
es verbleibt:

B -> BB
B -> b
B -> SB
B -> a
B -> BA
S -> AB 
B -> BS
B -> BZ
Z -> AS
S -> AW
W -> SB
B -> SR
R -> BS

Nun dachte ich, dass alles gut aussieht und alles die Form X -> AC und X -> b hat und somit korrekt ist... irgendwie sagt mir das Programm was anderes... drehe langsam durch ... blöde CNF :/


----------



## XHelp (10. Aug 2011)

Der 1. Schritt ist schon falsch. Die Beschreibung passt zwar, aber wie kommst du dabei auf dieses Ergebnis?


----------



## b1zarRe (10. Aug 2011)

Ok, ich habe es verbessert:

B -> SbS
Können natürlich folgendende Fälle auftreten:
B -> bS
B -> b
B -> Sb

-> Habe den Rest auch weiter editiert... sieht das nun korrekt aus???

Probleme habe ich zu verstehen ob ein Zyklus = Kettenregel ist oder ob darunter noch was anderes gemeint ist??? Und wie man genau nutzlose Nichtterminalzeichen bestimmt ist mir noch nicht verständlich... doer habe ich das schon richtig?


----------



## fastjack (11. Aug 2011)

Zur Hilfe kannst Du ein bisschen bei der Minimierung von DEA/NEA abschmumeln. Also Zustandstabelle aufbauen, bestimmte Zustände markieren, äquivalente Zustände suchen...

Sehr gut zum Thema TI ist auch das TI-Forum auf  : Matroids Matheplanet - Die Mathe Redaktion - Portal Mathematik


----------



## XHelp (11. Aug 2011)

Nein, der erste Schritt ist immer noch falsch. Das ist nicht mehr die selbe Gramatik.
Die Ketteneliminierung sieht hingegen ok aus (zumindestmal mit deinem falschen Ergebnis)


----------



## b1zarRe (11. Aug 2011)

Kannst du vllt schreiben warum das falsch ist? Komme nicht drauf


----------



## XHelp (11. Aug 2011)

Auf welchem Grund hast du die Regen S > ASB komplett gelöscht? Dadurch kannst du gar nicht AAAASBBBB produzieren.
Das gilt auch für alle anderen Übergänge


----------



## b1zarRe (11. Aug 2011)

Aus drm grund weil s eh nur zu epsilon fuehrt und ich dachte das sei der sinn der epsilon regeln loeschen.. oO


----------



## XHelp (11. Aug 2011)

Du löschst die Regel *S* -> ASB, weil S *nur* zu Epsilon führt?


----------



## b1zarRe (11. Aug 2011)

Nein, auch zu AB deswegen dachte ich : S - AB


----------



## XHelp (11. Aug 2011)

Aber die S>ABS Regel besagt, dass du auch AAAAAASBBBBBB erstellen kannst. Wenn du diese Regel löschst, dann hast du eine völlig andere Sprache. Es sollte wohl sowas wie:
aus:
S>epsilon
S>ASB
wird:
S>ASB
S>AB


----------



## b1zarRe (11. Aug 2011)

Ok verstehe, habe es nochmal verbessert.


----------



## XHelp (11. Aug 2011)

1. hör auf immer wieder den selben Post zu editieren. Der ganze Thread verliert dadurch an Sinn
2. warum spielst du nicht einfach das ganze schrittweise auf der von dir geposteten Seite durch?

Kettenregel ist falsch... ob sie vorher schon falsch war oder nicht oder wasauchimemr sehe ich ja jetzt nicht mehr.
Aber in der Beschreibung ist die Rege von Terminalsymbolen und als Beispiel gibst du A > B an... da ist kein einziges Terminalsymbol dabei...
Warum guckst du dir nicht einfach nochmal eine richtige Beschreibung des ganzen. Das sind ja einfach nur klare kleine Schritte, die man nacheinander machen muss :bahnhof:


----------



## b1zarRe (11. Aug 2011)

Hast Du vielleicht ein gutes Beispiel / Erklärung welches alle Schritte durchgeht??? Irgendwie finde ich nur Beispiele, wo hier und da Schritte übersprungen werden :/


----------



## XHelp (11. Aug 2011)

Aber du hast doch selber eine Seite gepostet, die dir das Schritt für Schritt mit Erklärungen durchspielt und zwar an den Werten, die du einträgst :bahnhof:


----------



## b1zarRe (15. Aug 2011)

Ok, habe es noch paar mal probiert, hier nochmal neu:

Aufgabe:

Bringen Sie mithilfe von Entfernen von Epsilon Regel, Kettenregel, Nutzloser/Nichtterminierender Zeichen und Überführung in die Chomsky Normalform:

Grammatik a:

S -> ASB
S -> epsilon
A -> aAS
A -> a
B -> SbS
B -> A
B -> bb

1.) Epsilon Regeln: Ich suche nach Form A -> epsilon (entferne diese nachher auch) und schaue zudem, ob es die weitere Form B -> A gibt, und falls ja, dann ist somit auch B -> epsilon. Ich sammele alle epsilon Variablen und (wie gesagt nachher löschen) und gehe alle Formen der Grammatik damit durch.

Gefundene Form: S -> epsilon. (sonst keine mehr) Also:
Ok, habe es noch paar mal probiert, hier nochmal neu:

Aufgabe:

Bringen Sie mithilfe von Entfernen von Epsilon Regel, Kettenregel, Nutzloser/Nichtterminierender Zeichen und Überführung in die Chomsky Normalform:

S -> ASB
S -> AB
A -> aAS
A -> aA
A -> a
B -> SbS
B -> bS
B -> Sb
B -> b
B -> A
B -> bb
Beachte: diese Grammatik entspricht nun Grammatik a - S -> epsilon = Grammatik b

2.) Kettenregeln: Nun schaue ich nach Zyklen der Form A -> B, B -> C, C -> D, D -> A:
hier: keine, als nächstes schaue ich mir alleinstehende Nichtterminale an und ersetze
diese durch die entsprechendes Produktion.

S -> ASB
S -> AB
A -> aAS
A -> aA
A -> a
B -> SbS
B -> bS
B -> Sb
B -> b
B -> a
B -> aA
B -> aAS
B -> bb

3.)

S -> ASB
S -> AB
A -> aAS
A -> aA
A -> a
B -> SbS
B -> bS
B -> Sb
B -> b
B -> a
B -> aA
B -> aAS
B -> bb

 a) Nicht erreichbar von S: Nicht erreichbare Zustände durchlaufe ich, und gucke ob ein Nichtterminalzeichen nutzlos ist. Ist hier aber nicht der Fall
b) Nicht terminierend: Ich suche mir ein Terminalzeichen aus was alleine steht und laufe rückwärts die Regeln durch und markiere, welche Zustände dadurch auch termierend sein können. (hier: alle)

4.) Ich bringe die bisherige Form zb.: S -> ABC in S -> AX und X -> BC (gleiches für Terminalzeichen).
es verbleibt:

S -> AN
N -> SB
S -> AB
A -> LM
L -> a
M -> AS
A -> KA
K -> a
A -> a
B -> SJ
J -> IS
I -> b
B -> SH
H -> b
B -> b
B -> a
B -> CC
C -> b
B -> DE
D -> a
E -> AS
B -> GS
G -> b
B -> FA
F -> a

Nun ist alles in Chomsky Normalform A -> AB und A -> a und kann mit dem CYK Algorithmus angewandt werden... korrekt?

Habe hierzu noch kleinere Fragen: 
Im allerletzten Schritt habe ich zb F -> a und D -> a kann man die zusammenfassen in X -> a? oder darf man das nicht? 

Was wäre passiert, wenn ich bei der Kettenregel die Form A -> B, B -> C, D -> E , E -> A hätte? Also ein Zyklus? alles zusammenfassen zu einem Buchstaben?

 AUch hatte ich mal gelesen, dass man S -> epsilon nicht entfernen darf(im ersten Schritt..) ?!


----------

