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

3 Answers 3


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.

  • $\begingroup$ Could you show reduction from HORNSAT to this problem ? $\endgroup$ Commented Aug 16, 2017 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 \} $

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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