[M&B] Chomsky Normal Form

Forum van 2de Bachelor Informatica.

Moderator: Praesidium

User avatar
Sebastiaan
Posts: 1184

[M&B] Chomsky Normal Form

Post#1 » Wed Jan 27, 2010 1:08 pm

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 ?
WINAK Schacht 2007-2008
WINAK Commiliton 2008-2009
ASK-Stuwer Snelkrant 2009-2010
ASK-Stuwer Vice-Praeses 2010-2011
ASK-Stuwer Praesidium 2011-2012
ASK-Stuwer IT 2012-2013

User avatar
nasam
Posts: 233
Contact:

Post#2 » Wed Jan 27, 2010 2:49 pm

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
http://www.nathansamson.be" onclick="window.open(this.href);return false; Flattr me!Image

User avatar
Sebastiaan
Posts: 1184

Post#3 » Wed Jan 27, 2010 3:55 pm

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 ?
WINAK Schacht 2007-2008
WINAK Commiliton 2008-2009
ASK-Stuwer Snelkrant 2009-2010
ASK-Stuwer Vice-Praeses 2010-2011
ASK-Stuwer Praesidium 2011-2012
ASK-Stuwer IT 2012-2013

User avatar
nasam
Posts: 233
Contact:

Post#4 » Wed Jan 27, 2010 4:19 pm

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
http://www.nathansamson.be" onclick="window.open(this.href);return false; Flattr me!Image

User avatar
Sebastiaan
Posts: 1184

Post#5 » Wed Jan 27, 2010 5:01 pm

aja just, thx kheb het door nu.
WINAK Schacht 2007-2008
WINAK Commiliton 2008-2009
ASK-Stuwer Snelkrant 2009-2010
ASK-Stuwer Vice-Praeses 2010-2011
ASK-Stuwer Praesidium 2011-2012
ASK-Stuwer IT 2012-2013

Return to “2de Bachelor”

Who is online

Users browsing this forum: No registered users and 4 guests

cron