# How to show that pda accepts empty language?

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.

• Are you asking for a proof of $L(A) = \phi$? where $A$ is your PDA May 29 at 7:57

I am not aware of any straightforward algorithms. One roundabout way I can think of is:

1. 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)
2. 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:

1. Mark all terminals in $$G$$ (or delete them from the rules)
2. While no new variables are marked:
1. For each rule $$A \to \alpha_1 \ldots \alpha_k$$, if $$\alpha_1, \ldots, \alpha_k$$ are all marked then mark $$A$$.
3. 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