Problem C
Regular Language Complement
We know that for any regular language
Write a program that takes as input the description of an
NFA (nondeterministic finite automaton)
![\includegraphics[width=0.5\textwidth ]{1.png}](/problems/baylor.rlcomplement/file/statement/en/img-0001.png)
An NFA is defined by:
-
A set of states
. -
One state
which is the start state. In this problem, the start state is always numbered . -
An alphabet of symbols
. In this problem, the alphabet is given implicitly (the set of symbols used in the NFA description). -
A set of transitions
. Here means that a transition may use a symbol from the alphabet , or it may be an epsilon transition ( is not a symbol, but the lack of a symbol). -
A set of final states
.
For a given NFA
-
Read in the machine
which accepts the language . -
Compute another machine
that is deterministic, but recognizes the same language ( ). -
Swap the final states and the non-final states of
to get a machine that recognizes .
When doing these steps, remember that it may be necessary to
add “sink state” to the deterministic machine
Input
The description of the NFA
Output
Output an NFA
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.
Group |
Points |
Constraints |
1 |
55 |
The machine is deterministic and complete (there are no epsilon transitions and every state has exactly one outgoing transition for every symbol). |
2 |
15 |
The machine is nondeterministic but there are no epsilon transitions. |
3 |
15 |
The machine is nondeterministic with epsilon transitions, but no state has both an incoming and outgoing epsilon transition. |
4 |
15 |
No other restrictions. |
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 |