Theory: Parse with CYK

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 yes or no for 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")

Lesson: Parsing with the CYK algorithm →