The pushdown automaton :

enter image description here

From Here i figured out that having an idea of the language is a good first step so i came to the conclusion that the language represented by this pushdown automaton is something that looks like this : $a^n b(b^*aa^*bb^*)^*a^n :n \in\mathbb{N}$ (correct me if i am wrong)

But from there i am kinda lost on how to approach the problem to figure out the CFG, in class were not really told a precise technique to do this so i would like to know how someone would proceed to solve this problem.

Thanks a lot.

EDIT my attempt: could someone validate if it's good or what i am missing thanks

$S \Rightarrow aSa$

$S \Rightarrow B$

$S \Rightarrow bB$

$B \Rightarrow aC$

$C \Rightarrow \epsilon$

$C \Rightarrow bB$

$B \Rightarrow b$

  • $\begingroup$ Your description of the language is not quite right. From state $3$, the you can either have $b$ or $aa^*b$, any number of times. So the middle part should be $(b + aa^*b)^*$. $\endgroup$
    – marcelgoh
    Nov 9, 2020 at 17:39
  • $\begingroup$ Re. your attempt: This is not quite right because it allows the empty string ($S\Rightarrow B\Rightarrow \varepsilon$), whereas the PDA does not. $\endgroup$
    – marcelgoh
    Nov 10, 2020 at 2:47
  • $\begingroup$ @marcelgoh Makes sens but if this is not accepted, is it normal that in your frist answer if we do aYa then use $Y \Rightarrow \epsilon$ it gives aa which is not in the language so $Y \Rightarrow \epsilon$ is not good right ? $\endgroup$
    – codetime
    Nov 10, 2020 at 3:54
  • $\begingroup$ I gave you three separate examples.The $Y$ in the first example is not the $Y$ in the second example. I'm just trying to demonstrate how to deal with $^*$ and $a^nLa^n$. $\endgroup$
    – marcelgoh
    Nov 10, 2020 at 4:15

2 Answers 2


We have shown (link in comment) that the language of this PDA is L = { a^n b (a* b)* a^n , n ≥ 0 } , now let's build the grammer ,

S --> aSa | bT

T --> AbT | ε

Α --> aA | ε

The first rule generates a^n b T a^n accounting for n = 0 , T generates (a* b)* , note how A generates a* , Ab is the same as a* b , and adding T , AbT allows for repeating ( you can form AbAbT , AbAbAbT and so on , or use T --> ε ) which is analogous to the *

As for your grammer , comparing it to the language you provided ( which is not the language for the PDA ) , it doesn't describe the language correctly , it doesn't also describe the correct language of the PDA

If we use the rules S --> aSa , then S --> B , we arrive at aBa , now use B --> ε ,and you get the string aa , which doesn't belong to the language you provided or that of the PDA ( note how the languages require at least one b to be in any string )


I won't give a full solution, but I will give some pointers towards the answer. Note that if $X$ is a grammar for a language, and we want to wrap it with the same number of $a$s on either side (possibly none), then the rule $$Y\to X\;|\;aYa$$ will do that for us.

Also if $X$ is a grammar for a language $L$, the grammar for $L^*$ is $$Y\to \varepsilon \;|\; XY.$$

Dealing with a $+$ in the language is easy. If $B$ and $C$ are grammars for $L$ and $M$, then the grammar for $L+M$ is $$A\to B\;|\; C.$$

You should assign variables that build small parts of your language, like $a^*$ and $b^*$ and piece them together to make the full grammar. I hope this helps.

  • $\begingroup$ Thanks for reply, i made an attempt could you tell me if it makes sens or not ? Also i am not sure why XY is required in your solution ? Thanks. $\endgroup$
    – codetime
    Nov 10, 2020 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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