Take the 2-minute tour ×
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.

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|improve this question
1  
In a CFG there is no "start rule", only a start symbol. –  vonbrand Feb 3 '13 at 17:22
1  
Thanks, that is what I was not sure about. –  trev9065 Feb 3 '13 at 17:23
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.