0

I'm working on converting this grammar to CNF (Chomsky Normal Form). 

S-> abAB
A-> bAB | lambda
B-> BAa | A | lambda

So I started off by eliminating the lambda productions, and in doing so I got this:

S-> abAB | abB | abA | ab
A-> bAB  | bA  | bB  | b
B-> BAa  | A   | Ba  | Aa  | a

I went a little bit further into the conversion process and ran into an issue of adding more unit productions than necessary, so I went and checked the answer key to see what I missed and it turns out that when we remove the lambdas, the following productions are not correct:

S-> ab
A-> b
B-> a

I would like to know why because it is not obvious to me yet. If we are looking at the production:

A-> bAB

and A and B can produce lambda, then we are just simply left with b correct? So why is it not a part of our production after eliminating lambda?

After the $\lambda$ eliminination the key has the following grammar:

S-> abAB | abA | abB
A-> bAB  | bA  | bB
B-> BAa  | A   | Ba  | Aa
Talen Kylon
  • 563
  • Is "lambda" the empty string in your notation? If so, then something has gone wrong in your first transformation, because A and B can be empty in the first grammar but not in the second. – Rob Arthan Nov 04 '15 at 23:34
  • @RobArthan Yes "lambda" is the empty string, I just wasn't sure how to insert the symbol. – Talen Kylon Nov 04 '15 at 23:56
  • The MSE help system when you are composing a question should give you some tips on how to format mathematical symbols like $\lambda$. As for your problem, compare what you have done with the process described here https://en.wikipedia.org/wiki/Chomsky_normal_form – Rob Arthan Nov 05 '15 at 00:42
  • They look fine to me. Does the key give a complete list of the productions that are supposed to remain after $\lambda$-elimination? – Brian M. Scott Nov 05 '15 at 04:39
  • I included the productions after the $\lambda$ elimination in the key. @BrianM.Scott – Talen Kylon Nov 05 '15 at 09:58
  • @Talen: I agree with your results, not those of the key. – Brian M. Scott Nov 05 '15 at 18:01

0 Answers0