Hide

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.

\includegraphics[width=0.5\textwidth ]{1.png}
Figure 1: Illustration of the NFA for the first test case.

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
CPU Time limit 3 seconds
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