Theory: Print the CYK table

Show the whole dynamic-programming table, not just the answer.

What to build

A program that prints the CYK table of a word, one row per substring length, then the verdict.

Requirements

  • Rows go from length 1 to the word's length; each row lists its cells from left to right.
  • A cell is written {V,W} with its variables sorted, or {} when empty.

Input

Line 1: r. Then r lines A -> body in Chomsky normal form. Last line: a non-empty word.

Output

One row per length, then accepted or rejected.

Constraints

r ≤ 20; the word has at most 10 symbols.

Example

Input:

5
S -> AB
S -> AC
C -> SB
A -> a
B -> b
aabb

Output:

length 1: {A} {A} {B} {B}
length 2: {} {S} {}
length 3: {} {C}
length 4: {S}
accepted

Why it works

Each cell holds exactly the variables that generate that substring, so the table explains every step of the decision.

Examples

Example 1 · Input
5
S -> AB
S -> AC
C -> SB
A -> a
B -> b
aabb
Expected output
length 1: {A} {A} {B} {B}
length 2: {} {S} {}
length 3: {} {C}
length 4: {S}
accepted
Example 2 · Input
5
S -> AB
S -> AC
C -> SB
A -> a
B -> b
ab
Expected output
length 1: {A} {B}
length 2: {S}
accepted

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Print row `length L:` with one cell per starting position, each as {A,B} with sorted variables, or {} when empty.

Hint 2

After the rows, print `accepted` if S is in the top cell, otherwise `rejected`.

Solution

Show one correct solution (try it yourself first)
rules = [tuple(input().strip().split(" -> ")) for _ in range(int(input()))]
pairs = [(a, b[0], b[1]) for a, b in rules if len(b) == 2]
units = [(a, b) for a, b in rules if len(b) == 1]
word = input().strip()
n = len(word)
table = {(i, 1): {a for a, b in units if b == c} for i, c in enumerate(word)}
for length in range(2, n + 1):
    for i in range(n - length + 1):
        cell = set()
        for split in range(1, length):
            left, right = table[(i, split)], table[(i + split, length - split)]
            cell |= {a for a, b, c in pairs if b in left and c in right}
        table[(i, length)] = cell
for length in range(1, n + 1):
    row = ["{" + ",".join(sorted(table[(i, length)])) + "}" for i in range(n - length + 1)]
    print(f"length {length}:", " ".join(row))
print("accepted" if "S" in table[(0, n)] else "rejected")

Lesson: Parsing with the CYK algorithm →