Context Free grammar to Chomsky Normal Form

41 Views Asked by At

So I got:

$ S \rightarrow XY|a $

$ X \rightarrow XYb|XS|\varepsilon$

$ Y \rightarrow SY|cX|XX|a$

So I want to solve this step by step ( first seperate, avoid length $\geq$ 2, avoid $\varepsilon$, avoid chain rules ).

(i)

$ S \rightarrow XY|a $

$ X \rightarrow XYB|XS|\varepsilon$

$ Y \rightarrow SY|CX|XX|a$

$ B \rightarrow b $

$ C \rightarrow c $

(ii)

$ S \rightarrow XY|a $

$ X \rightarrow XD|XS|\varepsilon$

$ Y \rightarrow SY|CX|XX|a$

$ B \rightarrow b $

$ C \rightarrow c $

$ D \rightarrow YB $

(iii)

$ S \rightarrow XY|X|Y|a $

$ X \rightarrow XD|XS|D|S|X$ is X $\rightarrow$ X necessary ?

$ Y \rightarrow SY|CX|XX|X|Y|S|C|a$ is Y $\rightarrow$ Y necessary ?

$ B \rightarrow b $

$ C \rightarrow c $

$ D \rightarrow YB|B $

(iv) here is my problem. I had to guess at this part

$ S \rightarrow XY|a|XD|XS|YB|b|SY|CX|XX|c $

$ X \rightarrow XD|XS|YB|b|XY|a|SY|CX|XX|c$

$ Y \rightarrow SY|CX|XX|a|c|b|XD|XS|YB|XY$

$ B \rightarrow b $

$ C \rightarrow c $

$ D \rightarrow YB|b $

I know that this is heart to read. Thank you in advance.