I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski or Thompson, but they are for DFA, so I don't know if it would work.
I am not aware of any straightforward algorithms. One roundabout way I can think of is:
- Convert the PDA to a CFG (there is a standard construction for this covered in introductory automata classes, the resulting CFG has $O(|Q|^2)$ variables where $Q$ is the size of the PDA)
- Check if the CFG's language is empty.
We can check if the language of a CFG $G$ is empty using an iterative algorithm that marks a variable if it can derive a string:
- Mark all terminals in $G$ (or delete them from the rules)
- While no new variables are marked:
- For each rule $A \to \alpha_1 \ldots \alpha_k$, if $\alpha_1, \ldots, \alpha_k$ are all marked then mark $A$.
- If the start variable is marked then $L(G)$ is nonempty, otherwise $L(G)$ is empty.
The algorithm above can be optimized with a worklist that skips re-visiting a same variable's rules after it's marked, and doing some processing to allow checking rules affected by the previous pass