Theory: The complement of a DFA

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 accept or reject for 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

Example 1 · Input
E
E
4
E a O
E b E
O a E
O b O
3
ab
aab
b
Expected output
accept
reject
reject
Example 2 · Input
s
f
6
s a A
s b s
A a A
A b f
f a f
f b f
2
ba
aab
Expected output
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")

Lesson: Designing DFAs: memory, complement and product →