Struggling to describe the language that this pushdown automaton represents

automatacomputer sciencecontext-free-grammarformal-languages

Given this pushdown automaton :
enter image description here

I am trying to describe the language that this represents.

My analyze yet:

the numbers of a at the start will need to be the same that as the end.

Also, the starting letter if there's no a, will be one b.

Also, the last letter before the ending a's will be a b

Now I struggle with the middle loop ( state 3 and 4 ) I am not sure on how to analyze and represent it.

For now i have something that looks like this:

$a^n b(b^*aa^*bb^*)^*a^n :n \in\mathbb{N}$

But I am pretty sure it's not good since I think I need to have a relaiton between the exponent ( just like the $a^n$) the other exponent should also be represented by a letter but I can't seem to understand the pattern and relations here.
Just to give you an example i need something that could look like this :
$$
L=\left\{a^{m} b^{m} c^{n}: m, n \in \mathbb{N} \wedge m \geq n\right\}
$$

If this can help I figured some words that can be accepted : babb , aabaaababaa

Could anyone help me figure this out and how to approach it.

Thanks a lot.

Best Answer

The language L is , L = { a^n b (a* b)* a^n , n ≥ 0 }

We can see how the number of as at begging and end of the string must match from the transitions a,ε,c and a,c,ε , this is why we have a^n at begging and end

After the first a^n , the transition b,ε,ε shows that there comes a b

Now we arrive arrive at state 3 , we consider states 3 and 4 , once you enter 3 you are left with 2 options :

  1. go from 3 to 3 , which is b , the same as a^0 b

  2. go from 3 to 4 , loop on 4 if you want , then go back to 3 , which is a^+ b

now you can do 1 or 2 , hopefully you can see that 1 U 2 is a^0 b U a^+ b = a* b (this is why we wrote b as a^0 b) , and this can be repeated as many times as we want since after 1 or 2 we return back to 3 so we arrive at (a* b)*

Related Question