0
$\begingroup$

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.

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

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

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .