Legal Sentences

Introduction

Natural language processing is an area of artificial intelligence. In very simple natural language processing systems, nondeterministic finite state automata are used to check whether sentences are grammatically formed or not.

To solve this problem, you must write a nondeterministic finite state automaton that checks whether a series of proposed inputs are grammatically correct or not.

Input File (sentences.in)

Each input file begins with the number n. n gives the number of states in the nondeterministic finite state automaton. The states are numbered from 0 to n-1 and the start state is always state 0. n is followed by a blank line.

There are now an unknown number of lines that contain an integer, state1, followed by a space, followed by an integer, state2, followed by a space, followed by a string, message, that contains no more than 20 uppercase alphabetical characters. There are three possibilities:

  1. If the two integers are different from one another, there is a transition from state1 to state2 when message is encountered. If message is EPSILON, that means that one can go from state1 to state2 with no input at all.
  2. If the two integers are the same and are non-negative, then message is always FINAL and this indicates that the state is an accepting state.
  3. Finally, if the two integers are each -1, then the message is always END and this indicates the end of this portion of the input file.

After another blank line, there is an unknown number of lines. Each line contains an unknown number of symbols where each symbol is separated from another symbol by a blank space. This portion of the file is terminated by the end of file marker.

Sample Input File

4

0 1 DET
0 1 EPSILON
1 1 ADJ
1 2 N
2 3 V
3 3 FINAL
-1 -1 END

DET N V
N V
DET ADJ N V
DET ADJ ADJ ADJ N V
ADJ V

Output (sentences.out)

Each line of symbols that is read in should be evaluated by the non-deterministic finite state automaton. If there is any way to reach an accepting state, the message Accept: should precede the line of symbols. Otherwise the message Reject: should precede the line of symbols.

Match the format of the sample output below exactly.

Sample Output

Accept: DET N V
Accept: N V
Accept: DET ADJ N V
Accept: DET ADJ ADJ ADJ N V
Reject: ADJ V