Problem B
NFA Simulator
Simulate a nondeterministic finite automaton (NFA) on a list of strings to find out whether the NFA accepts or rejects each string.
An NFA is defined by:

A set of states $Q$.

One state $q_0 \in Q$ which is the start state. In this problem, the start state is always numbered $0$.

An alphabet of symbols $\Sigma $. In this problem, the alphabet is given implicitly (the set of symbols used in the NFA description).

A set of transitions $Q \times \Sigma _{\varepsilon } \longrightarrow \mathcal{P}(Q)$. Here $\Sigma _{\varepsilon }$ means that a transition may use a symbol from the alphabet $\Sigma $, or it may be an epsilon transition ($\varepsilon $ is not a symbol, but the lack of a symbol). $\mathcal{P}(Q)$ is the powerset of $Q$.

A set of final states $F \subseteq Q$.
To decide whether the NFA $N$ accepts or rejects a string $w$, it processes one symbol of the string at a time. $N$ maintains a set of current states $C$. Initially $C$ contains the epsilon expansion of the start state $q_0$. (Epsilon expansion takes a set of states and adds all other states that can be reached using only epsilon transitions.) Then for each symbol $w_i \in w$, it performs the following two steps:

Identify the set of states $C'$ that are reachable from any state in $C$ using a single transition on the symbol $w_i$.

Let $C$ be the epsilon expansion of $C'$.
Finally, if $C \bigcap F$ is not empty, then $N$ accepts $w$; otherwise $N$ rejects $w$.
Input
Input consists of two parts. The first part describes the NFA. The second part is a list of strings.
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 $n1$. 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 transition 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 $n1$.
The list of strings starts with an integer $1 \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 English characters (a–z).
Output
For each of the $s$ strings, output ‘accept’ if the NFA would accept the string, or ‘reject’ otherwise.
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 

3 3 0 a 1 1 a 2 2 a 2 1 2 3 a aa aaaaa 
reject accept accept 
Sample Input 2  Sample Output 2 

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 3  Sample Output 3 

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 4  Sample Output 4 

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 5  Sample Output 5 

3 3 0 a 1 1 eps 0 1 eps 2 1 2 5 a b aaaaa aaaaab 
reject accept reject accept reject 