1
$\begingroup$

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?

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

1 Answer 1

Reset to default
3
$\begingroup$

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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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