1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – G. Bach
    Nov 15, 2013 at 16:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Nov 15, 2013 at 19:31
  • 1
    $\begingroup$ @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. $\endgroup$
    – Guy Coder
    Nov 15, 2013 at 21:42
  • $\begingroup$ @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? $\endgroup$
    – haunted85
    Nov 15, 2013 at 22:13
  • $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Nov 15, 2013 at 22:15

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.