0
$\begingroup$

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form.

Here is the language:

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

I know the first step is to make a new start symbol and thats easy enough

SO → S

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

Here is where I mess up, I know that you have to get rid of the lambda after this so it should be

SO → S

S → AA|SBBa|b|Sa

A → ABa|BS|a|Aa|S

B → BBb|a|

I know that now you have to get rid of the unit rules, but I have no idea how to start getting rid of them. A to S and So to S seem, like the only ones.

Any help would be appreciated

$\endgroup$
  • $\begingroup$ No, you do not have to get rid of empty symbol for sure not in that step and not by simply erasing it, because now it is no longer equivalent to original one. You have to add new symbols to shorten "SBBa", "ABa" and "BBb". There cannot be terminals and nonterminals in the Chomsky normal form. There will be 9 productions. Allowed productions are in form A→BC or A→a or A→λ (only if it is a part of language generated by grammar). Please try to start adding new symbols to get allowed productions and update your question. $\endgroup$ – Evil Oct 18 '16 at 4:40
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 18 '16 at 9:27
  • $\begingroup$ Converting grammars into normal forms is possible by rote-following algorithms. Why doesn't that work for you? Are you really working with such an algorithm, or are you trying to wing it? $\endgroup$ – Raphael Oct 18 '16 at 9:28
  • $\begingroup$ Ok here I believe I got it, does this look good? $\endgroup$ – Kevin Floyd Oct 18 '16 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.