1

I want to change the grammar in to Chomsky Normal Form(CNF).

This is example

S--> AB | ɛ

A--> aASb | a

B--> bS

I try to solve this 

S --> [A] [B]

[A] --> [aA] [Sb] | [a]

[aA] --> [a] A

[Sb] --> s [b]

[a] --> a

[b] --> b

I am not sure about the answer. Could anybody tell me if it is right or wrong?

Brian Tompsett - 汤莱恩
  • 5,438
  • 68
  • 55
  • 126
cool
  • 89
  • 1
  • 2
  • 9

1 Answers1

1

One mistake is that you removed the S --> ɛ transition. You need that (S --> ɛ is specifically allowed in CNF, even though AnyNonTerminalOtherThanS --> ɛ is not).

Then the rule [A] --> [a], should be [A] --> a because if you have only one item on the RHS, it needs to be a terminal.

[aA] --> [a] A
[Sb] --> s [b]

These two seem like typos as A and s don't exist. You probably meant:

[aA] --> [a] [A]
[Sb] --> [S] [b]

Other than that, what you have is correct.

sepp2k
  • 353,842
  • 52
  • 662
  • 667
  • @ sepp2k- Thanks that make sense. – cool Dec 13 '10 at 17:41
  • @ sepp2k- I am sorry but I did not include [A] --> [a] rule as you mentioned earlier. Although I got your point that if on RHS there is only one item then it should be terminal. – cool Dec 13 '10 at 17:45
  • @sepp2K- Hi!. I have a request. I asked a question here http://stackoverflow.com/questions/13143186/example-of-non-linear-unambiguous-and-non-deterministic-cfl. - Can clear my doubt. – Grijesh Chauhan Nov 02 '12 at 11:03