emptiness problem

In theoretical computer science and formal language theory, a formal language is empty if its set of valid sentences is the empty set. The emptiness problem is the question of determining whether a language is empty given some representation of it, such as a finite-state automaton.{{cite book|last=Sipser |first=Michael |author-link=Michael Sipser |title=Introduction to the Theory of Computation |publisher=Cengage Learning |year=2012 |isbn=9781285401065}} For an automaton having $n$ states, this is a decision problem that can be solved in $O(n^2)$ time,{{cite web |url=https://www.cs.columbia.edu/~aho/cs3261/Lectures/L6-Properties_of_Regular_Languages_II.html |title=Lecture 6: Properties of Regular Languages - II |website=COMS W3261 CS Theory |publisher=Department of Computer Science, Columbia University |access-date=2019-08-22 |archive-url=https://web.archive.org/web/20191031220228/https://www.cs.columbia.edu/~aho/cs3261/Lectures/L6-Properties_of_Regular_Languages_II.html |archive-date=2019-10-31 |url-status=dead}} or in time $O(n+m)$ if the automaton has n states and m transitions. However, variants of that question, such as the emptiness problem for non-erasing stack automata, are PSPACE-complete.{{cite book|last1=Hopcroft |first1=J. E. |authorlink1=John Hopcroft |last2=Ullman |first2=J. D |authorlink2=Jeffrey Ullman |title=Introduction to Automata Theory, Languages, and Computation |year=1979 |edition=first |isbn=81-7808-347-7 |publisher=Addison-Wesley}}

The emptiness problem is undecidable for context-sensitive grammars, a fact that follows from the undecidability of the halting problem. It is, however, decidable for context-free grammars.