Theory: Run any pushdown automaton

Simulate a nondeterministic PDA from its description.

What to build

A program that decides words for a PDA that accepts in an accepting state after reading all the input.

Requirements

  • Explore every reachable configuration; ignore configurations whose stack grows beyond the word's length plus 2.
  • Print yes or no for each word.

Input

Line 1: start state. Line 2: accepting states. Line 3: the start stack symbol. Line 4: t, then t lines from input pop to push. Then n and n words (a word may be an empty line).

Output

n lines.

Constraints

At most 10 states, 30 moves and 10 words of at most 12 symbols.

Example

Input:

p
f
Z
6
p a Z p AZ
p a A p AA
p b A q eps
q b A q eps
p eps Z f Z
q eps Z f Z
3
aabb

aab

Output:

yes
yes
no

Why it works

Each configuration is one possible situation of the machine; if any reachable configuration has read everything and is accepting, some path accepts.

Examples

Example 1 · Input
p
f
Z
6
p a Z p AZ
p a A p AA
p b A q eps
q b A q eps
p eps Z f Z
q eps Z f Z
3
aabb

aab
Expected output
yes
yes
no
Example 2 · Input
p
f
Z
6
p a eps p a
p b eps p b
p eps eps q eps
q a a q eps
q b b q eps
q eps Z f Z
2
abba
abab
Expected output
yes
no

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

Hints

Hint 1

A configuration is (position, state, stack); explore them with a queue and a visited set.

Hint 2

A move `p x X q push`: x or X may be `eps` (read nothing, pop nothing); push is written top first, or `eps`.

Solution

Show one correct solution (try it yourself first)
from collections import deque

start = input().strip()
accepting = set(input().split())
bottom = input().strip()
moves = []
for _ in range(int(input())):
    p, x, top, q, push = input().split()
    moves.append((p, "" if x == "eps" else x, "" if top == "eps" else top, q, "" if push == "eps" else push))


def accepts(word):
    limit = len(word) + 2
    first = (0, start, bottom)
    seen = {first}
    queue = deque([first])
    while queue:
        pos, state, stack = queue.popleft()
        if pos == len(word) and state in accepting:
            return True
        for p, x, top, q, push in moves:
            if p != state:
                continue
            if x and (pos >= len(word) or word[pos] != x):
                continue
            if top and not stack.startswith(top):
                continue
            rest = stack[len(top):] if top else stack
            nxt = (pos + (1 if x else 0), q, push + rest)
            if len(nxt[2]) <= limit and nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return False


for _ in range(int(input())):
    print("yes" if accepts(input()) else "no")

Lesson: Pushdown automata →