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,753
  • 72
  • 57
  • 129
cool
  • 89
  • 1
  • 2
  • 9

3 Answers3

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
  • 363,768
  • 54
  • 674
  • 675
  • @ 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
0

To write Chomsky normal form to the above question.. Get the form to either S->AB (or) S->aB

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

Perikala Spandana
  • 1
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Vikram Parimi Sep 07 '22 at 12:15
0

[Chomsky normal form][1]

Click on this to see the example of chomsky normal form [1]: https://i.stack.imgur.com/F44H0.jpg

Satyanarayana mareedu
  • 1
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Aug 30 '22 at 23:18