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
5 S -> AB S -> AC C -> SB A -> a B -> b aabb
length 1: {A} {A} {B} {B}
length 2: {} {S} {}
length 3: {} {C}
length 4: {S}
accepted
5 S -> AB S -> AC C -> SB A -> a B -> b ab
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")