Problem B
NFA Simulator
Simulate a nondeterministic finite automaton (NFA) on a list of strings to find out whether the NFA accepts or rejects them.
Input
Input consists of two parts. The first part describes the NFA. The second part is a list of strings to determine whether they are accepted by the described NFA.
The NFA description 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 $0 \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. 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$.
The list of strings starts with an integer $0 \le s \le 100$ indicating the number of lines that follow. Each of the next $s$ lines contains a string (possibly empty) of up to $100$ lowercase characters (a–z).
Output
For each of the $s$ strings, output ‘accept’ if the NFA would accept the string, or ‘reject’ otherwise.
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 7 aba bab baba aaabaaaaa bbbbbbbbbb aaaaaaaaa aaaaaabbbbaba |
accept reject accept reject reject reject accept |
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 7 aa bb abababababab babababababa bababaababab babababbabab aaaaabbbbb |
accept accept reject reject accept accept accept |
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 a aaaaa abababab abababa aab |
accept accept accept accept reject reject |
Sample Input 4 | Sample Output 4 |
---|---|
3 3 0 a 1 1 eps 0 1 eps 2 1 2 5 a b aaaaa aaaaab |
reject accept reject accept reject |