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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.