WINAK

S -> ABC | a
A -> aAaa | (eps)
B -> bBbb | (eps)
C -> cCc | c

Dit moet je omzetten naar chomsky normal form, maar is hetgeen ik hier doe en uitkom juist? (eps) = epsilon

1) Eliminate eps-producties

S -> ABC | AC | BC | C | a
A -> aAaa | aaa
B -> bBbb | bbb
C -> cCc | c

2) Unit producties
Enige unit production is van S->C

S-> ABC | AC | BC | cCc | c | a
A -> aAaa | aaa
B -> bBbb | bbb
C -> cCc | c

3) Eliminating useless symbols.
S -> c | a (Generating)
A -> aaa (Generating)
B -> bbb (Generating)
C -> c (Generating)

en allemaal reachable

CNF is :
S-> ABC | AC | BC | cCc | c | a
A -> aAaa | aaa
B -> bBbb | bbb
C -> cCc | c

Is mijn werkwijze juist ?

Dit kan al geen CNF zijn omdat

S-> ABC | AC | BC | cCc | c | a niet mag

(alleen X -> YZ en X -> t) mogen (Y en Z variabele, t terminal)

de andere 3 stappen lijken me wel ok

nasam wrote:Dit kan al geen CNF zijn omdat

S-> ABC | AC | BC | cCc | c | a niet mag

(alleen X -> YZ en X -> t) mogen (Y en Z variabele, t terminal)

de andere 3 stappen lijken me wel ok

Hoe maakte daar dan CNF van ? en in welke stap moet je dat bijvoegen ?

Als laatste stap moet je die zaken opsplitsen:

Bv: S -> ABC wordt
S -> AD
D -> BC

A -> aAaa | aaa
wordt
A -> XY | XZ
X -> a
Y -> AZ
Z -> XX

bBbb | bbb analoog
cCc ook

aja just, thx kheb het door nu.