Question

Convert the simple algebra below into Chomsky Normal Form (CNF), and then create a parse tree showing how the converted grammar could derive: x + y * z

E → E + T | T

T → T * F | F

F → (E) | x | y | z

Answer 1

Remove Units

»Remove E T , add E T * F |F

»Remove E F , add E (E) | x | y | z

»Remove T F , add T (E) | x | y | z

»The result:

»E E + T | T * F | (E) | x | y | z

»T T * F | (E) | x | y | z

»F (E) | x | y | z

Remove Mixed

»E E T₊ T | T T_* F | T₍E T₎| id

»T T T_* F | T₍E T₎|  x | y | z

»F T₍E T₎| x | y | z

»T( (

» T) )

» T+ +

» T* *

Remove Long

»E E M2 | T M3 | T( M4 |x | y | z

»T T M3 | T(M4 | x | y | z

»F T( M4 | x | y | z

»M2 T+ T

»M3 T* F

»M4 E T)

» T( (

» T) )

» T+ +

» T* *

Add Epsilon:N/A

»E E M2 | T M3 | T( M4 | x | y | z

»T T M3 | T(M4 | x | y | z

»F T( M4 | x | y | z

»M2 T+ T

»M3 T* F

»M4 E T)

» T( (

» T))

» T+ +

» T* *

It derives expression 4+2*3 i.e. X+Y*Z