Hallo, 

ich wollte Fragen ob ich folgende Grammatik richtig in CNF umgeformt habe.

Gegeben:
G=({a,b}, {A,B,S}, R, S) 

mit R: 

S->ASB \or\ \epsilon
A->bS
B->Sa 

In CNF: 

S'->S \or\ \epsilon
S->CB 
A->DS
B->SE
C->AS 
D->b
E->a

Kann ich das so lassen oder ist es falsch? 

\
S' -> S | epsilon 
S->ASB 
A->bS
B->Sa 

S' -> S \or\  epsilon 
S->ASB 
A->bS
B->Sa 

--------------- 

S' -> S \or\   epsilon 
S -> C_1 B 
A->C_b S
B->S C_a 
C_1 -> AS
C_b -> b
C_a -> a

Das ist jetzt zwar in CNF , allerdings bekomme ich nach wie vor bei der Bildung eines Wortes das S nicht weg. Davor konnte ich ja ein S mittels Epsilon ersetzen. 

Ich finde dazu auch keine Lösung im Wikipedia (oder ich war zu blöd und habs nicht verstanden)

\
S-> ab 

in CNF wäre ja : 

S -> C_a C_b
C_a -> a
C_b -> b

Ich verstehe allerdings nicht, wieso du S->ab gewählt hast. Wie kommst du denn darauf? Wenn ich S->ASB ableite, dann wäre ja quasi mein kleinstes entstehendes wort S->ba. 

Ich habe mir den Wikipedia Artikel durchgelesen, werde daraus allerdings nicht schlau. 

Wenn man strikt nach der Wikipedia-Anleitung vorgehen will, muss man zu Beginn die Regel S -> \epsilon stehen lassen, sonst verändert man die erzeugte Sprache. Diese Regel wird in Schritt 4 entfernt.

Nach den Schritten 2 und 3 hat man dann die Grammatik, die du in Post 6 angegeben hast, allerdings mit der zusätzlichen Regel S -> \epsilon \(Womit man das S auch wieder wegbekommt\). Diese Regel kann man jetzt eliminieren, Siehe Wikipedia. Diesen Eliminierungsschritt muss man bei manchen Grammatiken \(hier nicht\) öfter durchführen, bis wirklich alle \epsilon-Produktionen ausser S' -> \epsilon weg sind.

\
S -> C_1 B \or\ epsilon 
A->C_b S
B->S C_a 
C_1 -> AS
C_b -> b
C_a -> a

------------------------------------------
Entfernung der Epsilon Regel :

S' -> S \or\ epsilon 
S -> C_1 B 
A->C_b S
B->S C_a 
C_1 -> AS
C_b -> b
C_a -> a

Musterlösung sagt allerdings was anderes... intuitiv würde ich aber sagen, es gibt mehr als eine Lösung von daher poste ich es einfach mal. Bestimmt falsch gemacht :D 

Die Grammatik aus #6 mit S -> eps drin sieht so aus:

S' -> S \or \epsilon
S -> C_1 B \or \epsilon 
A->C_b S
B->S C_a 
C_1 -> AS
C_b -> b
C_a -> a

--------------------------------

Bei Eliminieren von S -> \epsilon wird jedes Vorkommen von S \(ausser in S' -> S, das ist eine Sonderregel\) einmal durch \epsilon ersetzt und die entstehende Regel zusätzlich eingefügt. Danach kann S -> \epsilon raus. Du kriegst

S' -> S \or \epsilon
S -> C_1 B \(S -> \epsilon weg\)
A->C_b S
B->S C_a 
C_1 -> AS
C_b -> b
C_a -> a

und zusätzlich

A -> C_b
B -> C_a
C_1 -> A.

\
Jetzt hab ich's bis dahin aufjedenfall verstanden. Danke für das anschauliche Beispiel! 

Letzter Schritt wäre doch Kettenregeln entfernen. 

Offensichtlich haben wir folgende Kettenregeln :

A->C_b
B->C_a
C_1 ->  A

Laut Wiki muss ich diese ersetzen nach dem Motto : A->B und B->w . Dann packe A->w rein.

D.h.

A->C_b wird ersetzt durch : A->b  { da C_b -> b. Die Indizes haben endlich einen Sinn :D 
B->C_a  wird ersetzt durch: B->a
C_1->A wird ersetzt durch: C_1 -> C_b S

CNF: 

S' -> S \or \epsilon
S -> C_1 B 
A->C_b S \or \ b
B->S C_a \or \ a
C_1 -> AS \or \ C_b S
C_b -> b
C_a -> a