Confirming an Answer for Phrase Structure Grammar

Question

I just want to confirm that I have a valid and good understanding of Phrase Grammar Structures by working one of the problems in the presence of you fellow mathematicians.

Let's assume the following:

Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, B, S}, T={0, 1} and set of productions P consisting of S->0A, S->1A, A->0B, B->1A, B->1

Select all of the following that belong to this language.

A. 11001

B. 0000

C. 10101

D. 001011

When I worked out the problem, I was only able to manage C. I could not get the rest from the provided language.

So For C, I derived it with the following rules:

S-> 1A-> 10B-> 101A-> 1010B->10101

I believe that is the only correct answer, please correct me if I'm wrong

Answer 1

You are correct. Any derivation must start either $S\Rightarrow 0A\Rightarrow 00B$ or $S\Rightarrow 1A\Rightarrow 10B$, so the second character must be $0$; this rules out $11001$. The only terminal production is $B\to 1$, so every word in the language must contain a $1$; this rules out $0000$. Your derivation of $10101$ is fine, so we have only to rule out $001011$.

Notice that once we have $B$, our choices are limited: we can either apply $B\to 1$ and stop, or apply $B\to 1A$ followed by $A\to 0B$, at which point the original $B$ has grown to $10B$, and we have the same choice. In other words, we can generate any number of copies of $10$, but eventually we must apply $B\to 1$ to get a final $1$. Putting the pieces together, we see that every derivation looks like this for some non-negative integer $n$ and $b\in\{0,1\}$:

$$S\Rightarrow bA\Rightarrow b0B\Rightarrow b01A\Rightarrow b010B\Rightarrow \ldots\Rightarrow b0\underbrace{1010\ldots10}_{n\, 10\text{s}}1=b0(10)^n1$$

Here $n$ is the number of times that we apply the production $B\to 1A$. And a closer look at that final form shows that we can rewrite it as $b(01)^{n+1}$. Thus, a word in the language can start with either $0$ or $1$, but after that it must repeat $01$ some positive number of times. The string $001011$ does not fit this pattern: it has two $1$s in a row.