Given G a phrase structure grammar, what is the language generated by G?

1k Views Asked by At

Given $G$, a phrase-structure grammar. Let $G = (V, T, S, P)$, where $V = \{a, b, A, B, S\}$, $T = \{a, b\}$, $S$ is the start symbol, $P = \{S \rightarrow ABb, A \rightarrow BB, Bb \rightarrow aA, B \rightarrow ab, AB \rightarrow b \}$. What is the language generated by $G$, $L(G)$, that is the set of all strings of terminals that are derivable from the start symbol $S$.

I am a little confused as to how to attempt this question but I got my answer as $$\{ (ab)^n \mid n \geq 0\} \cup \{ a^n b^m \mid m,n \geq 0 \}$$ where $n$ and $m$ are natural numbers

1

There are 1 best solutions below

0
On

For convenience of reference I recopy the set of productions:

$$\begin{align*} S&\to ABb\\ A&\to BB\\ Bb&\to aA\\ B&\to ab\\ AB&\to b \end{align*}$$

Every derivation must start $S\Rightarrow ABb$. After that we have a choice of applicable productions: we can apply any of $AB\to b$, $A\to BB$, $B\to ab$, and $Bb\to aA$.

  • Applying $AB\to b$ produces the word $bb$.

  • Applying $A\to BB$ results in $BBBb$, and at this point we have two choices: $$S\Rightarrow ABb\Rightarrow BBBb\Rightarrow BBaA\Rightarrow BBaBB\Rightarrow^4 ababaabab\;,$$ and $$S\Rightarrow ABb\Rightarrow BBBb\Rightarrow BBabb\Rightarrow ^2abababb\;.$$ Once we reach $BBaA$ or $BBabb$, the final outcome is determined, though we can change the order of the last $5$ steps in the first derivation and the last $2$ steps in the second.

  • Applying $B\to ab$ produces $Aabb$, and the only derivation is $$S\Rightarrow ABb\Rightarrow Aabb\Rightarrow BBabb\Rightarrow ^2abababb\;;$$ this is just a reordering of the previous derivation.

  • Applying $Bb\to aA$ results in $AaA$, and the derivation must proceed $$S\Rightarrow ABb\Rightarrow AaA\Rightarrow^2 BBaBB\Rightarrow^4 ababaabab\;,$$ again a reordering of an earlier derivation.

Thus, $L(G)=\{bb,abababb,ababaabab\}$.