Theory: Unreachable states

The first step of minimisation: find the states no input can reach.

What to build

A program that lists the states of a DFA that cannot be reached from the start state.

Requirements

  • Print the unreachable states sorted alphabetically and separated by spaces, or none.

Input

Line 1: the alphabet. Line 2: start state. Line 3: accepting states. Line 4: t, then t lines from symbol to.

Output

One line.

Constraints

At most 30 states and 80 transitions.

Example

Input:

0 1
q0
q2 q3
10
q0 0 q1
q0 1 q2
q1 0 q1
q1 1 q3
q2 0 q1
q2 1 q3
q3 0 q1
q3 1 q2
q4 0 q4
q4 1 q4

Output:

q4

Why it works

A state is useful only if some input leads to it; a graph search from the start finds exactly those.

Examples

Example 1 · Input
0 1
q0
q2 q3
10
q0 0 q1
q0 1 q2
q1 0 q1
q1 1 q3
q2 0 q1
q2 1 q3
q3 0 q1
q3 1 q2
q4 0 q4
q4 1 q4
Expected output
q4
Example 2 · Input
a b
E
E
4
E a O
E b E
O a E
O b O
Expected output
none

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

Hints

Hint 1

Search from the start state with a stack, following every move.

Hint 2

Every state named in a transition line belongs to the DFA.

Solution

Show one correct solution (try it yourself first)
alphabet = input().split()
start = input().strip()
accepting = set(input().split())
moves = {}
states = {start}
for _ in range(int(input())):
    a, symbol, b = input().split()
    moves.setdefault(a, []).append(b)
    states.update((a, b))
reach = {start}
stack = [start]
while stack:
    s = stack.pop()
    for t in moves.get(s, []):
        if t not in reach:
            reach.add(t)
            stack.append(t)
lost = sorted(states - reach)
print(" ".join(lost) if lost else "none")

Lesson: Minimising a DFA →