Hide

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)}$.

\includegraphics[width=0.5\textwidth ]{1.png}
Figure 1: Illustration of the input (top) and answer (bottom) for the first test case. Other answers are possible.

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
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Greg Hamerly
Source Baylor University Introduction to Computation Theory
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in