How to use the CYK Algorithm (CNF membership) Calculator
- 1. Type a CNF grammarRules must be A → B C or A → a. The first rule's left side is the start symbol.
- 2. Enter the stringWithout spaces, each character is one terminal.
- 3. Read the tableRow l holds substrings of length l. If the start symbol is in the top cell, the string is in the language.
How CYK works
CYK (Cocke–Younger–Kasami) decides whether a string w = a1…an is generated by a grammar in Chomsky Normal Form. X(i, j) is the set of variables that derive ai…aj.
- Length 1: X(i, i) = { A : A → ai }.
- Longer: A is in X(i, j) if there is a rule A → B C and a split k with B in X(i, k) and C in X(k + 1, j).
w is accepted when the start symbol is in X(1, n). The algorithm takes O(n³ · |G|) time.
Worked example (Hopcroft–Ullman)
Grammar S → AB | BC, A → BA | a, B → CC | b, C → AB | a and w = baaba.
- l = 1: {B}, {A, C}, {A, C}, {B}, {A, C}.
- l = 2: {S, A}, {B}, {S, C}, {S, A}. For example X(1, 2) = {B} · {A, C} gives BA → A and BC → S.
- l = 3: ∅, {B}, {B}.
- l = 4: ∅, {S, A, C}.
- l = 5: {S, A, C}.
S is in the top cell, so baaba is accepted.
Frequently asked questions
What if my grammar is not in CNF?
The tool lists the rules that break CNF. Remove ε-rules, unit rules and useless symbols, then replace long or mixed right sides with new variables.
Can CYK test the empty string?
A CNF grammar can only have S → ε when S is never on a right side. Leave the string blank and the tool checks for that rule.
Why is CYK called dynamic programming?
Each cell is built only from smaller cells that are already filled, so no substring is solved twice.