Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have a context free grammar described:

$S \rightarrow 0SS1$
$S \rightarrow 1$
$S \rightarrow \epsilon$

Because the first rule is considered the start rule does that mean that this grammar could never generate a string that starts with 1 or can you apply the second $S$ rule first to generate the string?

share|cite|improve this question
In a CFG there is no "start rule", only a start symbol. – vonbrand Feb 3 '13 at 17:22
Thanks, that is what I was not sure about. – trev9065 Feb 3 '13 at 17:23
up vote 3 down vote accepted

Yes you can apply the second rule you have written if you'd like. Since $S$ is your start symbol, you can apply any of its productions when you begin. It might be clearer if you wrote it as follows (where $|$ denotes or):

$S \rightarrow 0SS1 \; |\; 1 \; | \; \epsilon$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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