Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

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


Where P:

  • S→A1B
  • A→0A|ε
  • B→0B|1B|ε

I have to list the first 25 strings from L(G). So far I've made the tree, but I'm not sure that it's correct.

enter image description here

share|cite|improve this question
Please specify your question? What is the strings you try to derive? – Strin Dec 27 '12 at 8:33
up vote 1 down vote accepted

"the first 25 strings" in what order? Let's assume lexicographic order. Then, go by length of the produced strings.

Length 0: only $\varepsilon$ is of length $0$. Can $\varepsilon$ be generated by the grammar? (No).

Length 1: what strings of length 1 can be generated by $G$? only the string "1" (why?)

now, proceed to length 2,3,4... until you get 25 strings. But, doing this, can you see any rules here? Can you define the language generated by $G$ and then easily infer what are then strings (of length $n$) that $G$ generates?


The regular expression is $0^*1(0+1)^*$.

Finally, for each string construct a derivation tree, like you did. It seems that the grammar is un-ambiguous, so there's only one tree anyways. The way to write it as left-side derivation is listing the sentinel phrase and replace the leftmost variable with the right-had-side of its production. For the tree you give, an equivalent derivation is: $$S\to \mathbf{A1B} \to \mathbf{0A}1B \to 0\mathbf{\varepsilon} 1B \to 01\mathbf{0B} \to 010\mathbf{1B} \to 0101\mathbf{\varepsilon} = 0101 $$

share|cite|improve this answer
Would it be 1 01 10 11 010 011 100 001 111 0011... ? – 0x6B6F77616C74 Dec 29 '12 at 22:26
@0x6B6F77616C74 Your strings are correct, but not in lexicographic order (eg. 001 should be the first among length 3 strings). That is assuming you want them in lexicographic order. – Paresh Dec 31 '12 at 4:57

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.