Course contentsShow
← Computer Science
Lesson 1873 of 2,87242. Turing Machines and ComputabilityFree lesson

Decidability of CFG Membership

Prove that determining if a CFG generates a given string is decidable using the CYK algorithm.

Decidability of CFG Membership

You'll learn: How to prove that checking whether a context-free grammar generates a specific string is a decidable problem.

The Core Question

Given a context-free grammar (CFG) and a string, can we algorithmically determine whether the grammar produces that string? This is called the membership problem for CFGs. Unlike some problems in computer science that have no algorithmic solution, this one does—it's decidable.

Why It's Decidable: The CYK Algorithm

The CYK (Cocke-Younger-Kasami) algorithm provides a definitive answer. You already learned about CYK as a parsing technique; here's why it proves decidability:

  1. Finite input: The grammar is finite, and the string has finite length n.

  2. Guaranteed termination: CYK runs in O(n³) time—it always finishes in a predictable number of steps.

  3. Definitive answer: CYK either finds a parse (the string is in the language) or exhaustively proves no parse exists (the string is not in the language).

The Proof Sketch

To prove decidability, we construct a Turing machine that:

  • Converts the input CFG to Chomsky Normal Form (always possible)
  • Runs the CYK algorithm on the input string
  • Accepts if CYK finds a derivation, rejects otherwise

Since CYK always halts and gives a yes/no answer, the membership problem is decidable.

Analogy

Think of it like checking if a recipe can produce a specific cake. The recipe (grammar) has finite steps, the cake description (string) is concrete, and you can systematically try all valid combinations of ingredients and steps. Eventually, you'll either produce the exact cake or prove it's impossible with that recipe.

Key Takeaway: The CFG membership problem is decidable because the CYK algorithm provides a terminating procedure that always correctly determines whether a grammar generates a given string.