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.<ref>{{cite book|last=Sipser |first=Michael |author-link=Michael Sipser |title=Introduction to the Theory of Computation |publisher=Cengage Learning |year=2012 |isbn=9781285401065}}</ref> For an automaton having <math>n</math> states, this is a decision problem that can be solved in <math>O(n^2)</math> time,<ref>{{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}}</ref> or in time <math>O(n+m)</math> 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.<ref name="Hopcroft">{{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}}</ref> The emptiness problem in machine learning and formal languages determines if a model or automaton generates the empty language, which is undecidable for certain alternating multi-head finite automata over single-letter alphabets.<ref>{{Cite journal |last=Geidmanis |first=Dainis |date=1991-03-01 |title=Unsolvability of the emptiness problem for alternating 1-way multi-head and multi-tape finite automata over single-letter alphabet |url=https://dl.acm.org/doi/10.5555/115367.115361 |journal=Comput. Artif. Intell. |volume=10 |issue=2 |pages=133–141 |issn=0232-0274}}</ref>
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.<ref name="Hopcroft"/>
== See also ==
* Intersection non-emptiness problem
==References== {{reflist}}
{{comp-sci-stub}}
Category:Formal languages Category:Polynomial-time problems Category:PSPACE-complete problems Category:Undecidable problems