Theory: Your own regex engine

Match strings with an NFA you build yourself from the expression.

What to build

A program that builds a Thompson NFA for an expression and decides several words with it.

Requirements

  • Do not use the re module: build and simulate the NFA.
  • Print yes or no for each word.

Input

Line 1: the expression (letters, |, *, brackets). Line 2: n. Then n words (a word may be an empty line).

Output

n lines, each yes or no.

Constraints

The expression has at most 30 characters; at most 20 words of at most 30 symbols.

Example

Input:

(a|b)*abb
3
abb
ab
babb

Output:

yes
no
yes

Why it works

Every piece of the expression becomes a fragment, so the whole NFA accepts exactly the expression's language.

Examples

Example 1 · Input
(a|b)*abb
3
abb
ab
babb
Expected output
yes
no
yes
Example 2 · Input
a*b*
2

ba
Expected output
yes
no

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

Hints

Hint 1

Build fragments (start, end) for symbol, concatenation, union and star, with None for ε-moves.

Hint 2

Simulate with sets of states and ε-closures; accept when the end state is in the final set.

Solution

Show one correct solution (try it yourself first)
pattern = input()
edges = []
count = 0
pos = 0


def state():
    global count
    count += 1
    return count - 1


def peek():
    return pattern[pos] if pos < len(pattern) else None


def take():
    global pos
    pos += 1
    return pattern[pos - 1]


def union():
    start, end = concat()
    while peek() == "|":
        take()
        s2, e2 = concat()
        s, e = state(), state()
        edges.extend([(s, None, start), (s, None, s2), (end, None, e), (e2, None, e)])
        start, end = s, e
    return start, end


def concat():
    start = end = state()
    while peek() not in (None, "|", ")"):
        s2, e2 = star()
        edges.append((end, None, s2))
        end = e2
    return start, end


def star():
    start, end = atom()
    while peek() == "*":
        take()
        s, e = state(), state()
        edges.extend([(s, None, start), (s, None, e), (end, None, start), (end, None, e)])
        start, end = s, e
    return start, end


def atom():
    if peek() == "(":
        take()
        result = union()
        take()
        return result
    s, e = state(), state()
    edges.append((s, take(), e))
    return s, e


start, end = union()


def closure(states):
    seen, stack = set(states), list(states)
    while stack:
        s = stack.pop()
        for a, symbol, b in edges:
            if a == s and symbol is None and b not in seen:
                seen.add(b)
                stack.append(b)
    return seen


for _ in range(int(input())):
    current = closure({start})
    for c in input():
        current = closure({b for a, symbol, b in edges if a in current and symbol == c})
    print("yes" if end in current else "no")

Lesson: From regular expression to NFA: Thompson's construction →