Decidability of Formal Languages

Overview

Formal languages sit at different levels of the Chomsky hierarchy, and each level carries its own decidability guarantees for basic questions like membership, emptiness, and equivalence. For regular languages (recognized by finite automata) and context-free languages (recognized by pushdown automata), membership is always decidable — an algorithm can always determine, in finite time, whether a given string belongs to the language. But as languages grow more expressive, familiar questions start to fail: emptiness and equivalence are decidable for regular and context-free languages, yet EQUIVALENCE of two context-free grammars is undecidable, and for general recursively enumerable languages (those recognized by an unrestricted Turing machine), even MEMBERSHIP itself can become undecidable — this is exactly the content of the halting problem. Mapping which questions remain decidable at which level of the hierarchy is one of the central organizing structures of computability theory.

Intuition

Think of the Chomsky hierarchy as a ladder of increasingly powerful 'rulebooks' for generating strings: regular languages have the simplest rulebooks (finite automata, no memory beyond a current state), context-free languages allow a stack (a pushdown automaton, useful for nested/balanced structures like parentheses), and unrestricted (recursively enumerable) languages allow the full power of a Turing machine. As the rulebook becomes more powerful, checking things ABOUT the rulebook — not just running it, but answering questions like 'does this rulebook ever produce any string at all?' or 'do these two rulebooks produce the exact same language?' — becomes harder, and eventually impossible in general. It's a recurring pattern: more expressive power to DESCRIBE languages tends to buy less power to ANALYZE or REASON ABOUT those descriptions algorithmically.

Formal Definition

Definition

Key decidability results for the language classes of the Chomsky hierarchy, contrasted:

\text{MEMBERSHIP}_{\text{REG}} = \{\langle M, w\rangle : M \text{ is a DFA and } w \in L(M)\} \in \text{decidable}

Regular language membership — decidable

\text{EMPTINESS}_{\text{CFG}} = \{\langle G \rangle : L(G) = \emptyset\} \in \text{decidable}

Context-free emptiness — decidable

\text{EQUIVALENCE}_{\text{CFG}} = \{\langle G_1, G_2\rangle : L(G_1) = L(G_2)\} \in \text{undecidable}

Context-free equivalence — undecidable

A_{TM} = \{\langle M, w\rangle : M \text{ is a TM that accepts } w\} \in \text{undecidable}

Turing machine acceptance / halting problem — undecidable

Notation

Notation	Meaning
$L(M)$	The language recognized/generated by automaton or grammar M
$A_{TM}$	The Turing-machine acceptance problem: does M accept input w?
$\le_m$	Mapping (many-one) reducibility, used to transfer undecidability between problems

Theorems

Theorem 1: Decidability of regular/context-free membership and emptiness

\text{Membership, emptiness, and finiteness are decidable for both regular languages (via DFA simulation) and context-free languages (via the CYK algorithm and grammar-emptiness propagation).}

Theorem 2: Undecidability of context-free equivalence

\text{Given two context-free grammars } G_1, G_2, \text{ deciding whether } L(G_1) = L(G_2) \text{ is undecidable (though equivalence IS decidable for the more restricted class of deterministic context-free/regular languages).}

Theorem 3: Undecidability of the halting problem / A_TM

\text{There is no Turing machine that decides, for every pair } \langle M, w \rangle, \text{ whether } M \text{ halts (accepts) on } w. \text{ Proof: diagonalization.}

Applications

Compiler front-ends rely on the decidability of context-free membership (via CYK or LL/LR parsing) to always determine, in finite time, whether source code matches the language's grammar.

Worked Examples

Mark a nonterminal as 'generating' if it has a production rule whose right-hand side consists entirely of terminals, or entirely of already-marked generating nonterminals and terminals.
$A \to \alpha \text{ is applicable if every symbol in } \alpha \text{ is a terminal or already marked generating}$
Repeat this marking process until no new nonterminals can be marked (this must terminate, since there are finitely many nonterminals and each pass either marks at least one new one or the process stops).
$\text{At most } |V| \text{ passes needed, where } V \text{ is the (finite) set of nonterminals}$
L(G) is nonempty exactly when the start symbol ends up marked as generating; otherwise L(G) = ∅.
$L(G) \ne \emptyset \iff S \text{ is marked generating}$

Answer: This fixed-point marking procedure always terminates in a bounded number of passes (at most the number of nonterminals) and correctly determines generativity, so CFG emptiness is decidable — in sharp contrast to CFG equivalence, which is undecidable despite looking like a similarly 'structural' question.

Practice Problems

Difficulty 6/10

Why is MEMBERSHIP decidable for both regular and context-free languages, but not for arbitrary recursively enumerable languages?

Difficulty 7/10

A compiler author wants to prove two different context-free grammars for their language's syntax always generate exactly the same set of valid programs (i.e. are equivalent). Can they write an algorithm that always determines this correctly?

Difficulty 6/10

Which of the following is undecidable?

Whether a given string is accepted by a given DFAWhether the language of a given context-free grammar is emptyWhether two given context-free grammars generate the same languageWhether a given context-free grammar generates at least one string

Common Mistakes

Common Mistake

Assuming that because a language class has decidable membership, every natural question about that class (like equivalence) is also decidable.

Decidability must be checked question-by-question. Context-free languages have decidable membership and emptiness, but undecidable equivalence — different questions about the same language class can land on opposite sides of the decidability boundary.

Common Mistake

Believing 'recursively enumerable' and 'decidable (recursive)' mean the same thing.

A language is recursively enumerable if some Turing machine accepts exactly its strings (but may run forever on non-members); it is decidable (recursive) only if some Turing machine both accepts members AND halts-and-rejects on non-members. Every decidable language is recursively enumerable, but not every recursively enumerable language is decidable — A_TM itself is the classic example of a recursively enumerable but undecidable language.

Quiz

Flashcards

1 / 4

Historical Background

Noam Chomsky's 1956 classification of formal grammars into regular, context-free, context-sensitive, and unrestricted (recursively enumerable) types gave computability theorists a hierarchy against which to test which decision problems remain solvable. Decidability results for regular and context-free languages (membership, emptiness, finiteness) were established through the 1950s-60s alongside the automata theory of Rabin, Scott, and Chomsky himself. In parallel, Alan Turing's 1936 proof of the undecidability of the halting problem, and later results like Emil Post's correspondence problem (1946) and Yuri Matiyasevich's resolution of Hilbert's tenth problem (1970), supplied concrete undecidable language/decision problems that anchor the top of the hierarchy, showing decidability is not a uniform property but one that depends sharply on how expressive the underlying grammar or automaton model is.

1936
Alan Turing proves the halting problem is undecidable
Alan Turing
1946
Emil Post introduces the Post correspondence problem, later shown undecidable
Emil Post
1956
Noam Chomsky introduces the Chomsky hierarchy of formal grammars
Noam Chomsky
1970
Yuri Matiyasevich proves Hilbert's tenth problem (solvability of Diophantine equations) is undecidable
Yuri Matiyasevich

Summary

Decidability of basic questions (membership, emptiness, equivalence) depends sharply on which level of the Chomsky hierarchy a language belongs to.
Regular and context-free languages have decidable membership and emptiness via DFA simulation and generating-symbol marking, respectively.
Context-free grammar EQUIVALENCE is undecidable, even though emptiness for the same class is decidable — decidability must be checked per question, not per language class.
For general recursively enumerable languages, even membership can be undecidable, as in the halting/acceptance problem A_TM, proven by diagonalization.
Recursively enumerable (Turing-recognizable) is strictly weaker than decidable (recursive): a recognizer may loop forever on non-members.