Chomsky Normal Form Details

138 Views Asked by At

I'm converting a CFG to CNF and there are some details that I'm unsure of. I know the form is

  A-->BC
  A-->a

Is a transition such as S-->AA|... acceptable? Or do they have to be two different variables?

Is something such as S-->aa|... acceptable? I don't know how to change 'aa' to something else without ending up with AA or aA one of which isn't allowed and the other I'm unsure of.

1

There are 1 best solutions below

0
On

You are right. There are only two forms of rules in a CNF grammar. Either rewrite a variable into two veriables, or replace it by a single terminal letter.

The rule $S\to AA$ is perfectly OK, the variables can be identical. The rule $S\to aa$ is not OK. You can only generate a single terminal at the time. There is nothing wrong with using an intermediate symbol $A$ and productions $S\to AA$, $A\to a$ as you suggest. It is indeed possible to generate $aA$ but it will not belong to the generated language. The language only contains those generated strings that have no variables.