3.5Membership and decision problems for CFLs
The idea
The CYK algorithm decides whether a string is in a CFG's language in cubic time, using a CNF grammar and a triangular table.
Think of it like this: Building a wall bottom-up: first single bricks, then pairs, then bigger blocks.
Why it exists
It shows CFL membership is decidable and gives the O(n³) bound GATE likes to ask about.
How it works
- Fill the bottom row with variables that derive each single token.
- A cell for a longer span: for every split, combine variables from the two smaller spans using A → BC.
- Accept if the start symbol is in the top cell.
- O(n²) cells, O(n) splits each: O(n³).
Worked example: aabb with S → aSb | ab (CNF)
Row 1: T_a, T_a, T_b, T_b. Row 2: S for "ab" (positions 2–3). The top cell contains S: accepted.
Now play with it
- →Open the CYK tab, type
a a b b, then change it toa a b.
| span 4 | S | |||
|---|---|---|---|---|
| span 3 | ∅ | X | ||
| span 2 | ∅ | S | ∅ | |
| span 1 | T_a | T_a | T_b | T_b |
| a | a | b | b |
Accepted: the start symbol S is in the top cell.
Cell (i, j) holds the variables that derive tokens i..j. CYK fills O(n²) cells with O(n) splits each: O(n³) time.
Check yourself
The time complexity of CYK for a grammar of fixed size and input length n is
Exam notes (the dense version)
CYK decides membership in O(n³) time using a CNF grammar. Emptiness and finiteness are decidable. Equivalence, universality (L(G) = Σ*) and "is the intersection empty" are undecidable.
Previous year questions: Context-Free Grammars & Languages (13)
PYQs are grouped by topic, so this is the full set for Context-Free Grammars & Languages; try the ones that match this subtopic. Open all 13 on the topic page.