# Context free grammar to language

Suppose we have $G(V,Σ, R, S)$ where $$\begin{array}{ll} V & = \{a,b,A,B,S\}\\ Σ & = \{a,b\}\\ R &= \left\{ \begin{array}{rl} S &→ abA,\\ S&→B,\\ S&→baB,\\ S&→e,\\ A&→bS,\\ B& →aS,\\ A&→b \end{array}\right\}\end{array}$$

What is language $L(G)$ ? thanks in advance

-
Is this homework? First try listing several examples from L(G). –  Memming Apr 16 '13 at 1:40
In fact a solution to this question exemplifies a simple but useful technique, and closing it after only five hours with almost no feedback to the OP is petty. –  Brian M. Scott Apr 16 '13 at 10:18
@Brian: You're right. Alihuseyn, I apologize. –  MJD Apr 16 '13 at 12:51

Notice that the only production with $B$ on the left is $B\to aS$, so we can remove that production if we replace every $B$ on the righthand side of a production by $aS$. We then have the following productions:

\begin{align*} &S\to abA\mid aS\mid baaS\mid \epsilon\\ &A\to bS\mid b \end{align*}

We can repeat the procedure to eliminate the non-terminal symbol $A$:

$$S\to abbS\mid abb\mid aS\mid baaS\mid\epsilon\;.$$

Now it’s easy to see what language is being generated: it’s actually a regular language, which you can describe either in words or by a fairly simple regular expression.

-