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
remodule: build and simulate the NFA. - Print
yesornofor 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
(a|b)*abb 3 abb ab babb
yes no yes
a*b* 2 ba
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 →