Derivations for Context Free Grammar

1
votes

Ultimately I want to convert the following CFG into Chomsky Normal Form:

S→aSbS∣bSaS∣ε

However, I'm not sure if I'm doing the derivations correctly--here is what I have:

Replacing nonterminals with terminals

S→aabb

S→ε

Could someone tell me if this is correct/on the right track?

Thank you.

1
context-free-grammarcomputer-science-theorychomsky-normal-form
More combinations are possible than those which you have listed. - Ashalynd
en.wikipedia.org/wiki/Chomsky_normal_form - Ashalynd
@Ashalynd Is this right ? A-> a B-> b C-> AS D-> BS S-> CD|DC|ε - user3000731
No. Chomsky normal form means no epsilon, and no complex statements. - Ashalynd

1 Answers

0
votes

As @Ashalynd wrote, you should read a bit more about Chomsky Normal Form:

Chomsky normal form means no epsilon, and no complex statements.

The grammar you have contains an ε and therefore can never be transformed into a CNF as ε is a valid sentence in the language produced by S.