Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.