Problem C
Regular Language Complement
We know that for any regular language $L$ over alphabet $\Sigma $, the complement $\overline{L} = \Sigma ^* - L$ is also a regular language. Thus by definition, $\overline{L}$ 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)}$.
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$.
Sample Input 1 | Sample Output 1 |
---|---|
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 |
Sample Input 2 | Sample Output 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 |
Sample Input 3 | Sample Output 3 |
---|---|
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 |
Sample Input 4 | Sample Output 4 |
---|---|
3 3 0 a 1 1 eps 0 1 eps 2 1 2 |
2 2 0 a 1 1 a 1 1 0 |