Checking my CFG to CNF answer

402 Views Asked by At

I attempted to transform the given CFG into CNF.

$$S → ASA|A$$

$$A→aa|ε$$

Here are my steps:

  1. $$S→X$$

    $$X→XA|AX|A$$

    $$A→aa$$

  2. $$S→X$$

    $$X→XA|AX|YY$$

    $$A→YY$$

    $$Y→a$$

  3. $$S→XA|AX|YY$$

    $$X→XA|AX|YY$$

    $$A→YY$$

    $$Y→a$$

Is that one a correct solution?

1

There are 1 best solutions below

0
On BEST ANSWER

Follow the steps in the following order

1)Remove ε production

 S→ASA|AS|SA|A( You can ignore S->S )
 A→aa

2)Remove Unit Production(Non Terminal->Single Non Terminal)

Here we have unit production S->A

S→ASA|AS|SA|aa
A->aa

3)Remove Long Production(restructure the grammar such that R.H.S. have either 2 Non Terminal or single Terminal symbol)

S→AX|AS|SA|YY

X→SA

A→YY

Y→a