What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?

Question

I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's entire input, have an empty stack, and be in an accept state in order to accept. I am also working with the convention that a PDA always pushes a \$ onto the stack in the first transition and pops it off on the last transition to an accept state to ensure stack-emptiness (this comes from Sipser's Intro to Theory of Computation textbook). Given a PDA $A$ where $L(A)=\Sigma^*$, what properties would $A$ have that we would be able to determine by just looking at its definition? Currently these are my potential guesses for said properties:

• Every single state has a transition for every symbol $s \in \Sigma$
• Nothing is ever pushed onto the stack (i.e. symbols are only read)
• Every state is an accept state (less sure about this one)

I would appreciate any insight, corrections, or additions to what I have already. Thanks!

Answer 1

None of the above, I am afraid. There is nothing that distinguishes a PDA for $\Sigma^*$, except that it has an accepting computation for every string.

Of course a PDA may have all those properties, just build a deterministic finite state automaton and convert it to a PDA by ignoring the stack. But we can avoid all these properties and still accept $\Sigma^*$.

The stack can be used. Otherwise the PDA turns into a mere finite state automaton. For FSA we know that accepting $\Sigma^*$ is decidable.

PDA are allowed to be non-deterministic, meaning that in the same configuration two different computational steps are possible. We do not necessarily handle every input symbol at every state. On the other hand handling every input symbol is not a restriction. One may just add non-accepting computations for missing symbols. Again, for deterministic DPDA accepting $\Sigma^*$ is decidable, so non-determinism is one feature for undecidability.