u/123xxx7

Pushdown automatas (PDAs) with size of stack alphabet equal to 1

I am stuck on this problem: What class of languages do pushdown automatas with size of stack alphabet equal to 1 recognize? In other words, stack is always A^k, k>=0, where A is the only stack symbol. They are clearly not as expressive as all PDAs with no constrains.  I tried to prove that they have equal expressive power to NFAs, but failed (NFAs subset PDAs is easy, we just ignore stack, but the other way i have no clue what to do with the stack, it clearly gives us some information, but idk how to use it). maybe there are not equal to NFAs, im lost. Could you please help me with how to tackle this problem?

reddit.com
u/123xxx7 — 4 days ago