# Give the context-free grammar that generates the pushdown automaton language

The pushdown automaton :

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$$

• 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)^*$. Nov 9, 2020 at 17:39
• Re. your attempt: This is not quite right because it allows the empty string ($S\Rightarrow B\Rightarrow \varepsilon$), whereas the PDA does not. Nov 10, 2020 at 2:47
• @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 ? Nov 10, 2020 at 3:54
• 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$. Nov 10, 2020 at 4:15

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.

• 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. Nov 10, 2020 at 2:44