complexity of determining whether a language given by context free grammar is empty

Question

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)?

Answer 1

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.

Answer 2

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).

Answer 3

Simplest way is to compute the generating symbols (symbols $A$ such that $A \Rightarrow^* \alpha$ for $\alpha \in \Sigma^*$), and check if the start symbol is generating. A symbol $A$ is generating if there is a production $A \to \sigma$ with all symbols in $\sigma$ generating. To compute that, start with the terminals (by definition, generating), check all non-terminals if they have productions with right hand sides only generating symbols, and repeat until no more changes.