Problem D
Regular Language Complement

We know that for any regular language $R$ over alphabet $\Sigma $, the complement $\overline{R} = \Sigma ^* - R$ is also a regular language. Thus by definition, $\overline{R}$ has a corresponding finite automaton that accepts it.

Write a program that takes as input the description of an NFA (nondeterministic finite automaton) $X$ which accepts language $L(X)$ and produces an NFA $Y$ such that $L(Y)=\overline{L(X)}$.

Figure 1: Illustration of the input (top) and answer (bottom) for the first test case. Other answers are possible.

An NFA is defined by:

• A set of states $Q$.

• One state $q_0 \in Q$ which is the start state. In this problem, the start state is always numbered $0$.

• An alphabet of symbols $\Sigma $. In this problem, the alphabet is given implicitly (the set of symbols used in the NFA description).

• A set of transitions $Q \times \Sigma _{\varepsilon } \longrightarrow Q$. Here $\Sigma _{\varepsilon }$ means that a transition may use a symbol from the alphabet $\Sigma $, or it may be an epsilon transition ($\varepsilon $ is not a symbol, but the lack of a symbol).

• A set of final states $F \subseteq Q$.

For a given NFA $X$, we can find a machine $Y$ that accepts the complement of $L(X)$ by doing the following steps:

• Read in the machine $X$ which accepts the language $L(X)$.

• Compute another machine $X'$ that is deterministic, but recognizes the same language ($L(X') = L(X)$).

• Swap the final states and the non-final states of $X'$ to get a machine $Y$ that recognizes $L(Y) = \overline{L(X)}$.

When doing these steps, remember that it may be necessary to add “sink state” to the deterministic machine $X'$.

Input

The description of the NFA $X$ begins with a line containing an integer $1 \le n \le 100$, indicating the number of states in the NFA. States are numbered $0$ through $n-1$. State $0$ is the start state. The next line contains an integer $1 \le m \le 27 n^2$ indicating the number of transitions that follow, one transitions per line. Each transition is given as three tokens $a~ b~ c$ where $0 \le a, c < n$ are the source and destination states, and $b$ is either ‘eps’ (indicating an epsilon transition) or a single lowercase character (a–z) indicating the symbol for that transition. All transitions are unique. At least one transition will have a symbol (i.e. at least one is not an epsilon transition). Following the transitions is an integer $0 \le f \le n$ indicating the number of final states. The next $f$ lines contain $f$ unique integers indicating which of the states are final. All listed final states are in the range $0$ to $n-1$.

Output

Output an NFA $Y$ which recognizes exactly the complement of the language recognized by $X$, using the same format. The alphabet $\Sigma $ used to compute the complement is considered to be all the symbols that appear in any part of the definition of $X$.

Scoring

Your program will be tested on a set of test groups, each of which is worth a number of points. Each test group contains several test cases, and to receive the points for a test group your program must solve all of the test cases in that group. The score of your program is the sum of the points received on all of the test groups.

4
5
0 a 0
0 b 0
0 a 1
1 b 2
2 a 3
1
3

4
8
0 a 1
0 b 0
1 a 1
1 b 2
2 a 3
2 b 0
3 a 1
3 b 2
3
0
1
2

4
8
0 a 0
0 b 0
0 a 1
0 b 2
1 a 3
2 b 3
3 a 3
3 b 3
1
3

5
10
0 a 1
0 b 2
1 a 4
1 b 2
2 a 1
2 b 3
3 a 4
3 b 3
4 a 4
4 b 3
3
0
1
2

4
5
0 a 1
1 a 1
0 a 2
2 b 3
3 a 2
3
0
1
3

6
12
0 a 1
0 b 2
1 a 3
1 b 4
2 a 2
2 b 2
3 a 3
3 b 2
4 a 5
4 b 2
5 a 2
5 b 4
2
2
5

3
3
0 a 1
1 eps 0
1 eps 2
1
2

2
2
0 a 1
1 a 1
1
0