Decide membership for a context-free grammar with dynamic programming.
What to build
A program that runs CYK for a grammar in Chomsky normal form on several words.
Requirements
- The start variable is S.
- Print
yesornofor each word.
Input
Line 1: r. Then r lines A -> body (two capitals, or one terminal). Then n and n non-empty words.
Output
n lines, each yes or no.
Constraints
r ≤ 20; at most 10 words of at most 20 symbols.
Example
Input:
5
S -> AB
S -> AC
C -> SB
A -> a
B -> b
3
aabb
aab
ab
Output:
yes
no
yes
Why it works
Filling the table shortest substrings first finds every variable that generates every substring, so S in the top cell decides membership.
Examples
Example 1 · Input
5 S -> AB S -> AC C -> SB A -> a B -> b 3 aabb aab ab
Expected output
yes no yes
Example 2 · Input
6 S -> LR S -> LT S -> SS T -> SR L -> ( R -> ) 3 () (() ()()
Expected output
yes no yes
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Cell (i, 1) holds every A with a rule A → word[i].
Hint 2
For longer substrings, try every split and every rule A → BC; the start variable is S.
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]
for _ in range(int(input())):
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
print("yes" if "S" in table[(0, n)] else "no")