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!