# Derive some strings

G=({S,A,B},{0,1},P,S)

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.

-
Please specify your question? What is the strings you try to derive? – Strin Dec 27 '12 at 8:33

"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?

HINT:

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$$

-
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