Problem Detail: I’m writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:
- Can I use a single variable (a non-terminal) on the left-hand side of multiple rules?
- Can I use a single variable (a non-terminal) twice on the right-hand side of a single rule?
For instance, is the following grammar properly in Chomsky Normal Form? Is it OK that I have two rules with $S$ on the left-hand side? Is it OK that I have $X$ twice on the right-hand side of the second rule? $$S_0 to S$$ $$S to XX$$ $$S to XZ$$ $$vdots$$
Asked By : haunted85
Answered By : robyoder
The production $$S_0 to S$$ is not in CNF. CNF requires that nonterminals produce either two nonterminals or one terminal. Since the above line shows a nonterminal producing a single nonterminal, it does not fit. The CFG in CNF would be just: $$S_0 to XX$$ $$S_0 to XZ$$ $$vdots$$ To answer your original questions, though, yes, you can do the above in CNF. There are no stipulations about how many times a nonterminal may appear on the left or whether it can be duplicated on the right.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18052
