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