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.
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:
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.
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
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.
Accept: DET N V Accept: N V Accept: DET ADJ N V Accept: DET ADJ ADJ ADJ N V Reject: ADJ V