Reduce PDA for a given language I drew a Push-down Automata, accepting the following language:
$$
\{ xcy : x,y \in (a+b)^*, \#_a(x) &gt; \#_{bb}(y) \}.
$$
Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with overlaps. For example, $\#_{bb}(bbb) = 2$.
My question here. Is it possible to reduce my PDA to less states? Thanks.
Yes. You can obtain a PDA with only one state by &quot;encodng&quot; the state of your PDA into the stack of the new PDA. See this document.