Turn a DFA into the machine for "every string it does not accept".
What to build
A program that reads a complete DFA and decides each word for the complement language.
Requirements
- Use the same moves; accept when the run ends in a state that is NOT accepting.
- Print
acceptorrejectfor each word.
Input
Line 1: start state. Line 2: accepting states. Line 3: t, then t lines from symbol to. Then n and n words (a word may be an empty line).
Output
n lines, each accept or reject, for the complement.
Constraints
The DFA is complete: it has a move for every state and symbol used. At most 20 states and 20 words.
Example
Input:
E
E
4
E a O
E b E
O a E
O b O
3
ab
aab
b
Output:
accept
reject
reject
Why it works
Swapping accepting and non-accepting states of a complete DFA accepts exactly the strings the original rejects.
Examples
E E 4 E a O E b E O a E O b O 3 ab aab b
accept reject reject
s f 6 s a A s b s A a A A b f f a f f b f 2 ba aab
accept reject
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep every move; accept exactly when the original DFA would not.
Hint 2
The DFA given is complete, so every word ends in some state.
Solution
Show one correct solution (try it yourself first)
start = input().strip()
accepting = set(input().split())
delta = {}
for _ in range(int(input())):
a, symbol, b = input().split()
delta[(a, symbol)] = b
for _ in range(int(input())):
state = start
for symbol in input():
state = delta[(state, symbol)]
print("reject" if state in accepting else "accept")