Rules regarding Chomsky Normal Form (CNF) grammars

Question

I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:

1. Can I use a single variable (a non-terminal) on the left-hand side of multiple rules?

2. 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$$

• G. Bach: You can write the productions for the same variable on separate lines or on one line, separated by |, whatever the convention in your context is. Otherwise, this looks correct to me.
• D.W.: This question appears to be off-topic because questions of the form: "This is the exercises problem, this is my solution. Please grade!" are not suitable for this site. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened.
• Guy Coder: @D.W. IMHO haunted85 did ask a specific question: "if a variable can be used multiple times on the left side" and "if it's allowed using the same variable twice on the right side". I know these are basic questions for grammars, but he did present his work and ask for specific help not a solution.
• haunted85: @D.W. I am not looking for a grade, just for my confusion to be cleared. I did ask two specific questions, if you want them to be more clear, I will gladly edit my post right away. But really why would this site have a check-my-proof tag indexing Questions which also contain a proof or a solution that needs to be checked for correctness and completeness if I weren't allowed for correctness and completeness of my solution?
• D.W.: @GuyCoder, right, but this site exists to generate questions and answers that will be helpful to others. This would be a better question if haunted85 extracts the general question out from his specific situation. For instance, if his question was "Can I use the same variable multiple times on the LHS? Is it OK to use the same variable twice on the RHS? Here's an example grammar that illustrates this.", that'd be a better question, because it's more likely to be helpful to others. It requires thinking in terms of what will help others rather than getting haunted85's homework answer graded.

Answer 1

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.