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?

  • 1
    $\begingroup$ In a CFG there is no "start rule", only a start symbol. $\endgroup$ – vonbrand Feb 3 '13 at 17:22
  • 1
    $\begingroup$ Thanks, that is what I was not sure about. $\endgroup$ – trev9065 Feb 3 '13 at 17:23

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$


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.