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

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)?
• 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}$. Oct 22 '15 at 8:12
• 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/… Oct 22 '15 at 8:14
• See here for an improvement to the length $2^{n^2}$ upper bound: cstheory.stackexchange.com/questions/45915/… Sep 1 '20 at 0:46

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.

• Could you show reduction from HORNSAT to this problem ? Aug 16 '17 at 12:27

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

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.