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

Question

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$

Answer 1

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 )

Answer 2

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.