theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

and

formal language theory In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet". The alphabet of a formal language consists of symbol ...

, a formal language is empty if its set of valid sentences is the

empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

. The emptiness problem is the question of determining whether a language is empty given some representation of it, such as a

finite-state automaton A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

. For an automaton having

n

states, this is a

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

that can be solved in

O(n^2)

time, 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 In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...

. The emptiness problem is undecidable for

context-sensitive grammar A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any Production (computer science), production rules may be surrounded by a context of terminal symbol, terminal and nonterminal symbols. Cont ...

s, a fact that follows from the undecidability of the

halting problem In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...

. It is, however, decidable for

context-free grammar In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the fo ...

References

{{comp-sci-stub Formal languages Polynomial-time problems PSPACE-complete problems Undecidable problems

See also

References