Decision problems for CFLs

Why it exists

For regular languages every natural question has an algorithm: is the language empty, finite, all of $\Sigma^*$, equal to another one, contained in another one. For context-free languages the picture splits. Some questions (is a string generated, is the language empty or finite) have algorithms; many others (are two grammars equivalent, is the grammar ambiguous) have none. GATE asks: which of these problems about grammars and automata is decidable? The task is to classify, not to run the algorithms, but the algorithms explain the classification.

Prerequisites

You need the closure properties of context-free languages (CFL closure): in particular that the intersection of a context-free language and a regular language is context-free while the intersection of two context-free languages need not be. You also need the Chomsky normal form (normal forms) and the notion of decidability (decidable and recognisable languages).

Precise definitions

A decision problem about grammars is a language of encodings, for example $E_{CFG} = \{\langle G \rangle : L(G) = \emptyset\}$. It is decidable if some Turing machine halts on every input and accepts exactly the encodings with answer yes. The problems of this page:

Everything is the same for pushdown automata, since a grammar and a pushdown automaton can be converted into each other (PDA and CFG).

How it works

The decidable problems

Membership ($A_{CFG}$). Convert $G$ to Chomsky normal form and run CYK: the table of variables that derive each substring is filled in $O(n^3)$ steps for a string of length $n$ (normal forms). (The empty string is handled separately: it is generated exactly when the start variable is nullable.)

Emptiness ($E_{CFG}$). Mark the generating variables: first those with a production whose right side has only terminals, then repeatedly those with a production whose right side uses only terminals and variables already marked. The language is empty exactly when the start variable is never marked. The table shows the rounds for two grammars:

(In $G_1$ the variables $C$ and $D$ never become generating, but $S$ does through $S \to AB$.) The same fixpoint, keeping the shortest string found for each variable, produces a shortest string of the language.

Finiteness ($FIN_{CFG}$). First remove the epsilon productions, the unit productions and the useless symbols (normal forms). Draw a graph with an edge $A \to B$ when $B$ occurs on the right side of a production of $A$. In the reduced grammar every variable is reachable and generating, and every production makes the derived form at least as long as the variable; so the language is infinite exactly when the graph has a cycle. (A cycle $A \Rightarrow^{+} xAy$ with $xy \neq \varepsilon$ can be repeated; with no cycle the depth of every derivation is bounded, so there are finitely many.) Test the grammars of the table:

Rows 4 and 5 show why the reduction must come first: a cycle made only of unit productions ($A \to B \to A$) adds no strings, and a cycle among variables that can never produce a terminal string is useless.

A grammar and a regular language. The intersection of a context-free language with a regular language is context-free: run a pushdown automaton and a DFA in parallel, or build a grammar whose variables $[p\, A\, q]$ mean "$A$ derives a string that takes the DFA from $p$ to $q$". Then two questions are decidable:

• $L(G) \cap L(R) = \emptyset$: build the product grammar and test it for emptiness.
• $L(G) \subseteq L(R)$: this is $L(G) \cap \overline{L(R)} = \emptyset$, and the complement of a regular language is regular (swap accepting states of a complete DFA).

Both are decided by the same code; the table lists six cases, with the shortest witness string (a string in the intersection, or in $L(G)$ but not in $L(R)$):

The reverse direction, $L(R) \subseteq L(G)$, is not decidable: it contains universality as the special case $R = \Sigma^*$.

The undecidable problems

None of the following has an algorithm. They all come from the Post correspondence problem (PCP): given tiles $(t_1, b_1), \dots, (t_k, b_k)$ of strings, is there a sequence of tile numbers $i_1, \dots, i_m$ (with $m \ge 1$, repetition allowed) such that $t_{i_1} \cdots t_{i_m} = b_{i_1} \cdots b_{i_m}$? That PCP is undecidable is a standard theorem (quoted). To see the connection, build two grammars over the tile letters, a marker $c$ and the tile numbers:

where $w_i$ is the top and $v_i$ the bottom of tile $i$. A string of $L(G_A)$ looks like $t_{i_1} \cdots t_{i_m}\, c\, i_m \cdots i_1$ (the tile numbers come out in reverse order, because the innermost rule is applied last). The same string lies in $L(G_B)$ exactly when the bottoms spell the same word for the same sequence of tiles. So

If "is $L(G_1) \cap L(G_2)$ empty?" had an algorithm, PCP would have one. Hence disjointness of two context-free grammars is undecidable. The same instances give the other results, with a variation of the encoding that makes the two languages deterministic (so that their complements are context-free); the proofs are in the textbooks and are quoted here:

• Universality $L(G) = \Sigma^*$: with the deterministic variant of the encoding, the complements of the two languages are context-free, their union is a context-free language, and it is all of $\Sigma^*$ exactly when the PCP instance has no solution.
• Equivalence $L(G_1) = L(G_2)$ and containment $L(G_1) \subseteq L(G_2)$: universality is the special case where $G_2$ generates $\Sigma^*$.
• Ambiguity: a grammar built from the PCP instance is ambiguous exactly when there is a solution.
• Regularity: given $G$, "is $L(G)$ regular?" is undecidable (a variation of the same argument).

Bounded search shows the limit of the reduction: running through all tile sequences up to some length finds solutions that exist, but its failure to find one proves nothing. The unsolvable instances in the table are proved so by an argument (every top is longer than its bottom; every pair starts with different letters), not by the search.

Summary

The row of Turing machines follows from Rice's theorem (Rice's theorem). One notable exception to "equivalence is undecidable": equivalence of deterministic pushdown automata is decidable (Senizergues, 1997; quoted), while equivalence of nondeterministic pushdown automata is not.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The decidable questions use constructions from other pages: CYK and the removal of useless symbols (normal forms), the product of a pushdown automaton with a DFA (CFL closure). The undecidable ones extend the decidability results of decidable and recognisable languages and the reductions of the halting problem. The corresponding questions for grammars, automata and expressions of regular languages all have algorithms (closure of regular languages). Ambiguity in practice is handled by grammar transformations, since no algorithm can decide it in general.

PYQs

Let G1, G2 be Context Free Grammars (CFGs) and R be a
regular expression. For a grammar G, let L(G) denote the
language generated by G.

Which ONE among the following questions is decidable?

Let <M> denote an encoding of an automaton M. Suppose
that Σ = {0, 1}. Which of the following languages is/are
NOT recursive?

Let L(R) be the language represented by regular
expression R. Let L(G) be the language generated by a
context free grammar G. Let L(M) be the language
accepted by a Turing machine M.
Which of the following decision problems are
undecidable?
I. Given a regular expression R and a string w, is w ∈
L(R)?
II. Given a context-free grammar G, is L(G) = ∅?
III. Given a context-free grammar G, is L(G) = Σ* for
some alphabet Σ?
IV. Given a Turing machine M and a string w, is w
∈L(M)?

Which of the following are decidable?
I. Whether the intersection of two regular languages is
infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same
language
IV. Whether a given grammar is context-free

Which of the following problems is undecidable?

Self-check

Revision card

References