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.

states, this is a decision problem that can be solved in

However, variants of that question, such as the emptiness problem for non-erasing stack automata, are PSPACE-complete.

[3] The emptiness problem is undecidable for context-sensitive grammars, a fact that follows from the undecidability of the halting problem.

[3] This computer science article is a stub.