A context-free grammar can describe nested expressions, structured commands and simplified fragments of language, but one string may have many possible derivations. Trying every derivation can repeat enormous amounts of work. The Cocke–Younger–Kasami algorithm, commonly CYK or CKY, stores which nonterminal symbols can generate each contiguous substring. Short spans are solved first; longer spans combine two already-solved pieces across every split. Mathematics matters because grammar normal form, induction on span length and dynamic programming convert an open-ended derivation search into a finite triangular table with a clear cubic-time bound.
The practical search question is not simply “what is this named method?” but “which mathematical structure makes the method work, what does it guarantee, and what evidence would show that it is a poor choice?” This article keeps those questions together so students can connect mathematics education with computing, engineering, data reasoning and careful everyday decisions without turning one technique into a career promise.
Quick navigation: Why it matters · Mechanism · Worked example · Deeper ideas · Investigations · Limits · Learning route · Parent guidance · FAQs · Sources
Why this mathematics matters
Mathematics is important here because it turns an apparently visual or computational trick into a chain of reasons. The representation tells us what information is kept. The equation or invariant explains each legal step. The complexity analysis describes the work. The boundary conditions say when a conclusion should not be trusted. That combination is a practical form of problem-solving literacy.
A strong learner should be able to move in both directions: from a real task to a mathematical model, and from a formal guarantee back to its real meaning. Naming an algorithm is not enough. The useful achievement is to explain why the next operation is valid, check a small instance independently, and notice which assumptions the implementation has added.
Source: Daniel Younger’s 1967 cubic-time recognition paper.
Primary or implementation reference: University of Illinois record for Tadao Kasami’s recognition and syntax-analysis report.
How the mechanism works
Convert the grammar to Chomsky normal form, where ordinary productions have form A→BC or A→a, with a stated convention for the empty string. For each input position, place every nonterminal A with A→that terminal into the length-one cell. Then process span lengths 2 through n. For a span beginning at i and ending at j, try every split k. If a rule A→BC has B in cell (i,k) and C in cell (k+1,j), add A to (i,j). The string belongs to the language exactly when the start symbol appears in the cell for the full span. Store rule-and-split backpointers to recover parse trees rather than only recognition.
Let V[i,ℓ] be the set of nonterminals deriving the substring of length ℓ starting at i. The base rule is V[i,1]={A:A→w_i}. For ℓ>1, V[i,ℓ] contains A when there exist a split s with 1≤s<ℓ and a rule A→BC such that B∈V[i,s] and C∈V[i+s,ℓ−s]. Induction on ℓ proves soundness and completeness: each table insertion joins two valid derivations, and every binary parse tree has a root split captured by the recurrence. A direct implementation examines O(n²) spans, O(n) splits and grammar rules, commonly stated as O(n³|G|) time with O(n²|N|) set storage.
Keep a four-column notebook labelled object, rule, guarantee and caveat. In the first column name the inputs and stored state. In the second write one update precisely. In the third state what remains true after the update. In the fourth record a tie, approximation, domain restriction or hardware assumption. This routine prevents symbols from drifting away from their meaning.
Worked example and core calculations
Use the Chomsky-normal-form grammar S→AB, A→AA|a and B→BB|b. It generates one or more a symbols followed by one or more b symbols. For input aabb, the length-one row is {A},{A},{B},{B}. The length-two cells are {A} for aa, {S} for ab and {B} for bb. At length three, aab contains S because the split aa|b gives A and B; abb also contains S because a|bb gives A and B. For the full span aabb, the split aa|bb again combines A and B, so S enters the top cell and the string is accepted. Backpointers recover S⇒AB, A⇒AA and B⇒BB.
How to audit the calculation
- Recompute every intermediate value directly from the definition.
- Keep labels, indices, signs, units and normalisation visible.
- Test a case with a known exact answer.
- State tie rules, random seeds, tolerances and boundary conventions.
- Compare with a slower transparent baseline or trusted implementation.
- Separate agreement of numbers from suitability of the real-world model.
Small examples are not childish; they are diagnostic instruments. A five-line trace can reveal a reversed inequality, a missing scale factor or an inconsistent label convention before a large dataset hides the same error behind plausible output.
Four deeper ideas
The table is a proof chart
A nonterminal is entered only with a rule and a split that witness a derivation. Backpointers turn yes/no recognition into an inspectable proof tree.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Did you know? The triangle mirrors binary tree structure
Every internal node of a Chomsky-normal-form parse joins two adjacent spans, so every possible root split appears along one dimension of the table.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Normal form changes representation, not the intended nonempty language
Conversion introduces helper symbols and can make trees less readable. Map results back to the original grammar when explanation matters.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Ambiguity is information, not an implementation accident
If several rule-and-split backpointers reach the same cell entry, the string can have multiple parse trees; storing only one hides that fact.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Twelve practical investigations
1. Accepted four-symbol input
Repeat the aabb table. Fill cells by increasing span length.
What the mathematics reveals: Subproblems support longer derivations. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not skip alternative splits. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. Rejected ordering
Test abab with the same grammar. Inspect the top cell.
What the mathematics reveals: Local matches need not form a full derivation. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Acceptance depends on the start symbol. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. Ambiguous grammar
Use a grammar with two decompositions. Keep all backpointers.
What the mathematics reveals: One table entry can represent multiple trees. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not overwrite earlier evidence. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. Empty string
Ask whether ε is in the language. Handle the start-symbol convention explicitly.
What the mathematics reveals: CNF needs a stated exception. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: A zero-size table cannot decide policy itself. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Single token
Use input a. Apply only terminal productions.
What the mathematics reveals: The base case anchors induction. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: The start symbol may differ from A. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. Unknown token
Use a terminal absent from the grammar. Leave its base cell empty.
What the mathematics reveals: No larger span using it can be derived. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Tokenisation errors can look like grammar rejection. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Parse recovery
Store one backpointer per insertion. Walk from the top cell downward.
What the mathematics reveals: Dynamic programming can retain witnesses. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: One pointer suppresses ambiguity. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Parse counting
Store counts instead of trees. Sum products across rules and splits.
What the mathematics reveals: Semirings change what the table computes. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Counts can grow very large. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. Probabilistic variant
Attach rule probabilities. Use best-score or inside recurrences.
What the mathematics reveals: The same span geometry supports inference. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Probabilities need a trained model. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Grammar conversion
Convert a small non-CNF rule. Map helper symbols back.
What the mathematics reveals: Normal form enables the recurrence. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Conversion can change tree shape. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Complexity profile
Increase input length. Count spans and split checks.
What the mathematics reveals: The cubic dimension comes from boundaries and splits. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Grammar indexing changes constants. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Property testing
Enumerate short derivations. Compare table membership.
What the mathematics reveals: Exhaustive small cases provide an oracle. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Bound recursion depth carefully. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
CYK’s standard recurrence assumes Chomsky normal form and usually treats the empty string separately. Grammar conversion can add symbols and obscure the original structure. The cubic factor becomes expensive for long inputs or large grammars, and specialised deterministic parsers can be much faster for restricted programming-language grammars. Recognition alone says only that at least one derivation exists; it does not choose the most plausible interpretation. Storing every parse tree may require exponential output because an ambiguous grammar can have exponentially many parses, so packed forests or counts are preferable. Natural language requires tokenisation, probabilities and richer linguistic models. A grammar recognises the formal language it encodes, not automatically all valid human usage.
Five misconceptions to challenge
- Every context-free grammar can be used unchanged: The standard algorithm expects Chomsky normal form.
- The top cell stores one parse tree: It stores symbols; backpointers may encode many trees.
- Cubic recognition means cubic output: An ambiguous grammar can represent exponentially many parse trees.
- Acceptance proves the interpretation is sensible: It proves membership in the specified formal language.
- CYK is the usual fastest parser for every language: Restricted grammars often admit more efficient specialised methods.
Another broad misconception is that advanced mathematics automatically creates intelligence, admission, income or employment. It does not. Deliberate study can strengthen modelling, abstraction, calculation and explanation, while real pathways also depend on interests, communication, domain knowledge, opportunities and circumstances outside one topic.
A learning route for students
Move from a visible trace to a symbolic rule, then to code and critique. For every step below, prepare three pieces of evidence: a correct hand example, a boundary or failure case, and a short explanation using the relevant invariant. Do not advance merely because software returned a number.
Step 1: Identify chomsky normal form
Begin with the smallest non-trivial instance that lets you identify Chomsky normal form. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 2: Build base table cells
Begin with the smallest non-trivial instance that lets you build base table cells. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 3: Combine spans across splits
Begin with the smallest non-trivial instance that lets you combine spans across splits. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 4: State the recurrence
Begin with the smallest non-trivial instance that lets you state the recurrence. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 5: Prove soundness by induction
Begin with the smallest non-trivial instance that lets you prove soundness by induction. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 6: Prove completeness by tree decomposition
Begin with the smallest non-trivial instance that lets you prove completeness by tree decomposition. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 7: Store parse backpointers
Begin with the smallest non-trivial instance that lets you store parse backpointers. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 8: Detect ambiguity
Begin with the smallest non-trivial instance that lets you detect ambiguity. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 9: Analyse cubic complexity
Begin with the smallest non-trivial instance that lets you analyse cubic complexity. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 10: Separate tokenisation from parsing
Begin with the smallest non-trivial instance that lets you separate tokenisation from parsing. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
A four-week practice plan
- Week 1 — vocabulary and diagrams: define each object, redraw the mechanism and reproduce the worked example.
- Week 2 — equations and manufactured tests: derive the key relation and test inputs with known answers.
- Week 3 — implementation and evidence: use a trusted library, record parameters and compare with a transparent baseline.
- Week 4 — transfer and critique: apply the method to a new context, report limits and identify when a different method is better.
Guidance for parents and educators
Ask “what stays true?” and “what could make this conclusion fail?” before asking for speed. Invite the student to draw the input and output, estimate the result and locate the first step that disagrees with a reference. These prompts reveal conceptual understanding more clearly than memorised terminology.
Advanced enrichment should sit beside secure school foundations in algebra, functions, geometry, statistics and computational thinking. It need not accelerate a student into a fixed career identity. A healthy goal is curiosity with discipline: the learner becomes comfortable reading unfamiliar notation, checking an example, revising a model and communicating uncertainty.
Evidence prompts for a useful conversation
- Which quantity is observed and which is inferred?
- Which step saves work, and why is it allowed?
- Is the claim exact, approximate, probabilistic or empirical?
- What units and conventions are in use?
- Which input makes the method struggle?
- What simple baseline could check the answer?
- What would count as evidence that the parameters are poor?
Mini-project assessment
A strong mini-project contains the original question, a small reproducible dataset, a hand-worked example, code or a spreadsheet trace, at least one boundary test, a comparison with a baseline, and a paragraph on limits. Assess the reasoning trail as well as the final output. Repairing a model after a surprising result is valuable mathematical progress.
Six evidence checks for a finished project
Check 1: Identify chomsky normal form
Ask the student to demonstrate how to identify Chomsky normal form without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 2: Build base table cells
Ask the student to demonstrate how to build base table cells without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 3: Combine spans across splits
Ask the student to demonstrate how to combine spans across splits without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 4: State the recurrence
Ask the student to demonstrate how to state the recurrence without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 5: Prove soundness by induction
Ask the student to demonstrate how to prove soundness by induction without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 6: Prove completeness by tree decomposition
Ask the student to demonstrate how to prove completeness by tree decomposition without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Frequently asked questions
What does CYK decide?
Whether a string is generated by a context-free grammar in the required normal form.
Why is the table triangular?
It contains all contiguous substrings, grouped by start and length.
What goes in a cell?
Nonterminals that can derive that substring.
Why try every split?
A binary grammar rule can divide a span at any internal boundary.
What is the usual runtime?
O(n³|G|) for a direct grammar-dependent implementation.
Can it return a parse tree?
Yes, when rule-and-split backpointers are stored.
What if the grammar is ambiguous?
Multiple backpointers can represent multiple parses.
How is the empty string handled?
With an explicit grammar and algorithm convention.
Is CYK only for natural language?
No; it is a general context-free recognition method.
What should students know first?
Grammars, sets, substrings, recursion and dynamic programming.
Useful next reading and sources
Source: Daniel Younger’s 1967 cubic-time recognition paper.
Source: University of Illinois record for Tadao Kasami’s recognition and syntax-analysis report.
Related eduKateSG reading: Shunting-yard parsing and expression trees.
Related eduKateSG reading: Viterbi decoding and trellis paths.
Related eduKateSG reading: Hirschberg divide-and-conquer alignment.
Read sources with a question in mind: which definition, theorem, default or limitation is being supported? An authoritative link is useful evidence, but it does not replace a worked calculation or a clear statement of how the source applies to the example.
A cheerful final thought
Mathematics becomes friendlier when every symbol has a job and every claim has a boundary. Start small, make the state visible, test the awkward case, and celebrate the moment when a pattern becomes explainable. That is the practical benefit of learning mathematics: not certainty about every future, but a growing ability to ask better questions and build trustworthy answers.