Decidability of Emptiness and Finiteness for CFLs

1. The Emptiness Problem

A decision problem is a question with a "yes" or "no" answer. The emptiness problem for CFLs is formally stated as:

• Given a CFG $G$, is $L(G)=\varnothing$?

A naive approach, such as trying to generate strings to see if we find one, is not a valid algorithm. If the language is indeed empty, this process would run forever. We need an algorithm that is guaranteed to halt.

The solution lies in working backward from the terminals. A grammar generates a non-empty language if and only if the start symbol is capable of deriving at least one string of terminals. We can determine this by identifying all the variables that can generate terminal strings.

The Marking Algorithm

The core idea is to find all the "generating" variables—those that can eventually produce a string of only terminals. We can do this iteratively:

1. Base Case: Any terminal symbol is, by definition, "generated".
2. Inductive Step: A variable $A$ is "generating" if there is a production $A\to \alpha$ where all symbols in the string $\alpha$ (which can be terminals or other variables) are already known to be "generating".

We repeat this process until no new generating variables can be found. If the start symbol $S$ is marked as generating by the end of this process, the language is not empty. Otherwise, it is empty.

The following video provides an excellent intuitive explanation of this marking procedure.

Formalizing the Algorithm

Let's formalize this procedure, as described in the lecture notes from St. Francis Xavier University. This frames the algorithm as a proof that the emptiness problem is decidable.

As the notes detail, the algorithm is:
Given a CFG $G=(V,\Sigma ,R,S)$:

1. Mark all terminal symbols in $\Sigma$.
2. Repeat until no new variables are marked in an iteration:
   • For each rule $A\to {\alpha }_1{\alpha }_2...{\alpha }_k$ in $R$, if all symbols ${\alpha }_1,...,{\alpha }_k$ have already been marked, then mark the variable $A$.
3. If the start symbol $S$ is marked, then $L(G)$ is not empty.
4. If $S$ is not marked, then $L(G)$ is empty.

This algorithm is guaranteed to terminate because in each step of the loop, we can only mark more variables, and there are a finite number of variables in the grammar.

To see this algorithm applied to concrete examples, the next video walks through several grammars.

2. The Finiteness Problem

Next, we ask whether a grammar's language is finite or infinite.

• Given a CFG $G$, is $L(G)$ finite?

The source of infinite strings in a CFL is recursion. Specifically, if a variable can be part of a derivation that expands to include itself, it may be possible to repeat this derivation an arbitrary number of times, generating infinitely many strings.

For example, a rule like $A\to aAb$ allows $A$ to generate $ab,aabb,aaabb,...$. This happens if $A$ can derive a string containing itself, formally written as $A{\Rightarrow }^{+}\alpha A\beta$, where $\alpha$ or $\beta$ contains at least one terminal.

The Graph-Based Algorithm

We can detect this kind of useful recursion by modeling the grammar as a directed graph.

The algorithm is as follows:

1. Simplify the Grammar: First, eliminate all non-generating and unreachable variables from the grammar. This is crucial. A recursive variable only contributes to an infinite language if it is useful—that is, it can be reached from the start symbol AND it can generate a string of terminals. Simplifying the grammar ensures we only consider such variables.

2. Construct a Dependency Graph: Create a directed graph where the nodes are the variables of the (simplified) grammar. For every production $A\to \alpha B\beta$ in the grammar, draw a directed edge from variable $A$ to variable $B$.

3. Check for Cycles: Determine if the graph contains any cycles. Standard graph traversal algorithms like Depth-First Search (DFS) can do this.

4. Decision:

   • If the graph contains a cycle, the language $L(G)$ is infinite.
   • If the graph does not contain a cycle, the language $L(G)$ is finite.

Why does this work? A cycle in the graph, say $A\to B\to ...\to A$, signifies that the variable $A$ is recursive ($A{\Rightarrow }^{+}\alpha A\beta$). Since we already removed all non-generating variables, we know that this $A$ can also be part of a derivation that produces a terminal string. Combining these facts, we can construct infinitely many distinct strings, proving the language is infinite.

Let's look at the first example from the article.

Problem-01:
$S\to AB|a$
$A\to BC|b$
$B\to CC|c$
(Assume C has a rule like $C\to c$, which is missing but implied by the problem being well-formed. Let's add $C\to c$.)

The grammar is already simplified. The dependency graph has nodes $\{S,A,B,C\}$.

• $S\to AB$ gives edges $S\to A$ and $S\to B$.
• $A\to BC$ gives edges $A\to B$ and $A\to C$.
• $B\to CC$ gives an edge $B\to C$.

The resulting graph is acyclic. Therefore, the language is finite.

Now consider the second example.

Problem-02:
$S\to XS|b$
$X\to YZ$
$Y\to ab$
$Z\to XY$

The graph has nodes $\{S,X,Y,Z\}$.

• $S\to XS$ gives edges $S\to X$ and a self-loop $S\to S$.
• $X\to YZ$ gives edges $X\to Y$ and $X\to Z$.
• $Z\to XY$ gives edges $Z\to X$ and $Z\to Y$.

This graph contains multiple cycles (e.g., the self-loop $S\to S$ and the mutual recursion $X\to Z\to X$). Therefore, the language is infinite.

Conclusion

In this lesson, we have added two more powerful tools to our analytical toolkit for Context-Free Languages. We've shown that we can algorithmically decide fundamental properties of the entire language generated by a grammar, not just its individual strings.

Key Takeaways:

• The emptiness problem for CFLs is decidable. The algorithm works by iteratively marking all "generating" variables that can produce terminal strings and checking if the start symbol gets marked.
• The finiteness problem for CFLs is also decidable. The algorithm involves constructing a dependency graph from a simplified grammar and checking for cycles. A cycle implies the language is infinite; no cycles means it is finite.
• These algorithms are efficient and rely on analyzing the grammar's structure, a common theme in formal language theory and compiler construction.
• Unlike regular languages, however, not all decision problems for CFLs are decidable. For instance, the equivalence problem (is $L(G_1)=L(G_2)$?) and the universality problem (is $L(G)={\Sigma }^{\ast }$? ) are undecidable for CFLs. This is a crucial distinction and a hint at the limits of computation we will soon explore.

Preview of the Next Lesson:
We have reached the limits of what pushdown automata and context-free grammars can do. To model more complex computational tasks and to formally define what "computation" itself means, we need a more powerful model. In the next lesson, we will be introduced to the Turing Machine, the foundational model for all of modern computer science and the final step up in the Chomsky Hierarchy we will study.