Chomsky Normalform

B

b1zarRe

Bekanntes Mitglied
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... :(
 
X

XHelp

Top Contributor
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?
 
B

b1zarRe

Bekanntes Mitglied
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 :/
 
Zuletzt bearbeitet:
B

b1zarRe

Bekanntes Mitglied
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?
 
Zuletzt bearbeitet:
X

XHelp

Top Contributor
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)
 
X

XHelp

Top Contributor
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
 
X

XHelp

Top Contributor
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
 
X

XHelp

Top Contributor
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:
 
B

b1zarRe

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

XHelp

Top Contributor
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:
 
B

b1zarRe

Bekanntes Mitglied
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..) ?!
 


Schreibe deine Antwort... und nutze den </> Button, wenn du Code posten möchtest...

Aktuelle Jobs

Neue Themen


Oben