5
$\begingroup$

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word of length $\leq 2^n$ (or maybe $\leq 2^{n+1}$, I'm not sure) belongs to the language, where $n$ is IIRC the number of nonterminals in CNF. If not, then no longer words belong either and the grammar is empty.

The above algorithm has the unpleasant property of having exponential complexity. The questions that interest me are:

  • Is there a polynomial algorithm to check whether given CFG represents empty language?
  • What's the (asymptotically) best known algorithm for that?
  • What's the simplest polynomial algorithm for that (not necessarily having best known complexity)?
$\endgroup$
  • $\begingroup$ For an $n$ state PDA, the shortest path from a start state to a final state has length at most $2^{n^2}$. We believe it to be an open problem to determine if this upper bound can be improved to $2^{n}$. As a result, for $n$ state PDA's, the naive (and inefficient) approach may require you to check all strings of length $2^{n^2}$. $\endgroup$ – Michael Wehar Oct 22 '15 at 8:12
  • $\begingroup$ The faster approach (that runs in polynomial time) for checking if a PDA's language is non-empty is described here: cstheory.stackexchange.com/questions/32053/… $\endgroup$ – Michael Wehar Oct 22 '15 at 8:14
8
$\begingroup$

First, omit all terminal symbols. Then the language is empty iff the grammar does not generate the empty string.

An algorithm to check acceptance of the empty string is straightforward. A non-terminal $A$ is nullable, i.e., $A\Rightarrow^* \lambda$ iff $A \to w$ where each symbol in $w$ is nullable.

Determine the symbols nullable with a derivation tree of depth $k$, $k=0,1,\dots$. First find all $A$ such that $A\to \lambda$. Remove these $A$ from the right-hand side of productions and repeat. Axiom $S$ is nullable iff the language is non-empty.
This can be implemented in linear time, making lists of all productions that contain a certain letter at their right-hand side.

Seems to be equivalent to HORN-SAT.

$\endgroup$
  • $\begingroup$ Could you show reduction from HORNSAT to this problem ? $\endgroup$ – Haskell Fun Aug 16 '17 at 12:27
5
$\begingroup$

Let $G=(V,\Sigma, P,S)$ be your context-free grammar, and define $$ W = \{ A \in V |\, \exists w \in \Sigma^* : A \Rightarrow_G^* w \} $$ It's clear that $L_G \neq \emptyset \Leftrightarrow S \in W$.

You could use this algorithm to determine whether $W$ is empty:

while( $W' \neq W$) do
$ \quad W' = W$
$ \quad W = W \cup \{ A \in V \,|\, \exists w \in (\Sigma \cup W)^*: (A \to w) \in P \} $
endwhile

Since a nonterminal doesn't need to be added more than once it should be able to do this in linear time (linear in the number of nonterminals).

$\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.