Parikh Image of Pushdown Automata

Pierre Ganty, Elena Gutiérrez

We compare pushdown automata (PDAs for short) against other representations. First, we show that there is a family of PDAs over a unary alphabet with $n$ states and $p\ge 2n+4$…