Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$

What is $L(G)$?

So far I've derived the following regular expressions:

$ S \rightarrow (a^*ba^*)^*c \mid (b^*ab^*)^*c$

So far I've come up with this $L(G)$:

$L(G) = \{ (a^nba^n)^qc \mid (b^nab^n)^*q : n,q \geq 0 \}$

When you approach the second $S_1$ do you include the $c$ ( As in, finish $S_1c$ and the go recursive)?

  • 2
    $\begingroup$ Please ask only one question per question. I count about five questions in your question, which is about four too many. Please read cs.stackexchange.com/q/11315/755 and cs.stackexchange.com/q/50456/755, see what you can learn from them, try applying them to your situation, then edit your post to ask a single question and show us what you tried and where you got stuck and what progress you made. $\endgroup$
    – D.W.
    Jun 28, 2016 at 21:02
  • 2
    $\begingroup$ If you are confused about multiple things, I recommend you ask one question now about the logically "first" thing you're confused about and wait a few days for answers. One of two things will happen. You might get an answer that answers the question you asked, and enables you to finish off everything else on your own. Or, you might still be confused about the other issues after reading the answers; at that point, you can ask another question about the next thing you're confused about. $\endgroup$
    – D.W.
    Jun 28, 2016 at 21:03
  • 1
    $\begingroup$ 1) "What is L(G)?" -- that question is incomplete. In what form should we answer? 2) Why do you set up with a regular expression? Is the generated language regular? $\endgroup$
    – Raphael
    Jul 1, 2016 at 12:21
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Jul 1, 2016 at 12:22

2 Answers 2


To find the language for the grammar,

You need to understand how does the recursiveness in production rules work.

In solving A->Aa|epsilon , you need to know that epsilon works as a stopper for a recursive production, and determine the number of times the recursive production occurred for the given production rule.

In solving A->Aa|epsilon to get the expression for A made up of terminals , one of the ways is to keep doing with the production rule. After you do that you consider the epsilon which determines the number of times the production rule have occurred, and use that result to express the A concisely.

A->Aa->Aaa->Aaaa ... you see that the a is produced recursively and epsilon makes A to stop at any right arrow, so you can substitute A with a*. As asterisk is defined as n>=0 and n is an integer.

It is same for solving S1 and S2.

First you use the conclusion that A can be substituted with a* as they are same expressions, then AbA(S1)c is same as (a*)b(a*)(S1)(c) keep doing that production rule again and again until you find the regularity in them. S1->(a*)b(a*)S1c->(a*)b(a*)(a*)b(a*)S1cc->(a*)b(a*)(a*)b(a*)(a*)b(a*)S1ccc (You know that c occurs every time the production rule occurs)

Then you see that there is (a*)(a*) going on here and you can substitute this with just a* because they are exactly the same expression. let the left asterisk's number of recurrence time as L and right asterisk's number of recurrence time as R. We already know that L and R both satisfy the condition L>=0 , R>=0 and L,R are both integers. Then let S=L+R, then the minimum value for S is 0 because L and R has the minimum value that are both equal to zero, and since the +operator is closed on the integer set, we conclude that S>=0 which means minimum value for S is equal to zero. And S is integer, which is exactly equal to the asterisk's definition. since L+R for the expression (a*)(a*) is equal to the T which is the number of recurrence time for a in (a*). so (a*) is exactly the same expression as (a*)(a*).

Then S1->(a*)b(a*)S1c->(a*)b(a*)(a*)b(a*)S1cc->(a*)b(a*)(a*)b(a*)(a*)b(a*)S1ccc

(You now know that c is produced every time you apply the rule so this also answers your second question.)

becomes S1->(a*)b(a*)S1c->(a*)b(a*)b(a*)S1cc->(a*)b(a*)b(a*)b(a*)S1ccc->(a*)b(a*)b(a*)b(a*)b(a*)S1cccc....

You find the expression of S1 is ((a*)b)^n(a*)c^n since ((a*)b) and c keeps recurring every time you apply production rule for S1. or you can write (a*)(b(a*))^nc^n as (b(a*)) and c keeps recurring.

you can do this same for the S2. and the result should look like this. ((b*)a)^n(b*)c^n or (b*)(a(b*))^nc^n

Since S->S1|S2 you finally get L(G)

L(G)={(a*)(b(a*))^nc^n | ((b*)a)^n(b*)c^n | epsilon : n>=1 and n is an integer}

  • $\begingroup$ Excellent comment. Thank you so much. The part which made it very clear was " S1->(a*)b(a*)S1c->(a*)b(a*)(a*)b(a*)S1cc->(a*)b(a*)(a*)b(a*)(a*)b(a*)S1ccc (You know that c occurs every time the production rule occurs)"; as I didn't know how the S1 and c's worked in recursion. Once again thanks so much! $\endgroup$
    – marcusvb
    Jun 29, 2016 at 5:33
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    Jul 1, 2016 at 12:22

Let's consider "half" of your problem: $S\to AbASc \mid \epsilon$, and $A\to aA \mid \epsilon$. It is important to realize that the number of $b$'s and $c$'s generated is equal. Try to express that in your solution.

At the same time, when two $A$'s are generated, they will generate an arbitrary number of $a$'s. One of your solutions claims these numbers are always the same, but they are not.

Personally I would prefer to write this language as $L(G_{\frac12}) = \{ wc^k \mid w\in\{a,b\}^*, k\ge1, \#_b(w) = k\} \cup \{\epsilon\}$, where $\#_b(w)$ is the notation for the number of occurrences of letter $b$ in the string $w$. Alternatively, if you want to avoid that notation perhaps $L(G_{\frac12}) = \{ a^{n_0}ba^{n_1}b\dots ba^{n_k}c^k \mid k\ge1, n_0,\dots,n_k\ge 0\}\cup \{\epsilon\}$.

It is not immediate how to write this using "regular expressions" as the equality of the number of $b$'s and $c$'s is not regular property itself. Also we cannot put the star-operator inside set brackets, as the star yields a language itself, so it would be proper to write $L(G_{\frac12}) = \bigcup_{k\ge1} (a^*b)^ka^*c^k \cup \{\epsilon\} = \bigcup_{k\ge0} (a^*ba^*)^kc^k $ .

Sorry about the $\dots \cup \{\epsilon\}$ in several of these solutions. Allowing $k=0$ would not give the right answer, as that would add $a^*$ to the language, which is not generated by the grammar.

  • $\begingroup$ I understand what you mean. So a language for the half a problem you described would be something like this? $L(G) = \{ (a^n b a^x)^qc : n,x,q \geq 0 \}$ $\endgroup$
    – marcusvb
    Jun 28, 2016 at 22:44
  • $\begingroup$ Correction on the above, I think it should be $ L(G) = \{ (a^nba^x)^qc^q :n, x, q \geq 0\} $ because you reach the a^x, and if it's called again you repeat, and then at the end you add the c's from the recursion calls. $\endgroup$
    – marcusvb
    Jun 28, 2016 at 23:08
  • $\begingroup$ @marcusvbb please edit your post if you have changed / checked / resolved something. If you are sure this is proper as the comment but it changed please avoid consecutive comments saying that the previous one is obsolete - delete the previous one and write new one. But also please avoid asking another questions in the comments. And the last thing - do you use some structured way in your translation? $\endgroup$
    – Evil
    Jun 28, 2016 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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