Language of Grammar

Question

Let $G = (V,T,S,P)$ be the phrase structure grammar with $V = \{0,1,A,S\}$, $T=\{0,1\}$, and a set of productions $P$ consisting of:
$S \to 1S$
$S \to 00A$
$A \to 0A$
$A \to 0$

What is the language generated by G?

I know how to start it by creating a derivative tree. And I have also created it. My only problem is that I don't know how to use that information to answer the question. Can someone help?

Answer 1

It looks like the language is $1^{*}000(0)^{*}$. Notice we can have no $1$'s present; and if we do, we can keep revisiting $S$. To terminate, we need to visit the $S \to 00A$ rule to get to the $A$ rules. Then we can keep tacking on $0$'s or terminate with one additional $0$.

Answer 2

Here’s a fairly systematic way to approach such problems, at least when the grammar is relatively simple. Note first that you must begin with $S\to 1S$ or $S\to 00A$. Once you apply the latter production, however, you can never apply the first. Thus, any derivation must start with some number $m\ge 0$ of applications of $S\to 1S$ followed by an application of $S\to 00A$:

$$S\overset{m}\Longrightarrow 1^mS\Longrightarrow 1^m00A\;.$$

From this point on the only productions that can be applied are $A\to 0A$ and $A\to 0$. The derivation won’t terminate until you apply $A\to 0$, but before that you can apply $A\to 0A$ any number $n\ge 0$ times (and that’s all that you can do):

$$S\overset{m}\Longrightarrow 1^mS\Longrightarrow 1^m00A\overset{n}\Longrightarrow 1^m000^nA\Longrightarrow 1^m000^n0\;.$$

Thus, $G$ generates $\{1^m0^{n+3}:m,n\ge 0\}$. You can easily write a regular expression for this language: $1^*0000^*$ (or $1^*0^*000$, or $1^*00^*00$, or $1^*000^*0$).