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?
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$).
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$.
