Deterministic Finite Automaton X16856

Input

The input will consist in several rows: - 1st will come the set of states of the DFA. - 2nd the alphabet supported by the DFA. - 3rd the start state. - 4th the set of accepted states (note that there could exist more than one accepted state). - N rows, one per state and in order of appearance, defining the transition function for such state using pairs of symbol-destination. - Finally, the input string.

In sake of clarity, the input for trying to discern if M (our previous example DFA) would accept 100010 would be: q1 q2 q3 0 1 q1 q2 0 q1 1 q2 0 q3 1 q2 0 q2 1 q2 100010

Output

The output will be a single sentence depending on the evaluation’s outcome: - If the input string has symbols that aren’t from the DFA’s alphabet: "Invalid input string!" - If the input string is accepted: "Input string accepted" - If the input string is rejected: "Input string rejected" - If the definition does not correspond with a DFA: "This is not a deterministic finite automaton!"

Note that the later situation may arise when: - A transition involving a symbol not existing in the DFA’s alphabet is defined. - A transition involving a state not existing in the set of states of the DFA is defined. - There isn’t exactly a single transition defined for each pair of state-symbol. If that rule is broken we would be in front of a Nondeterministic Finite Automaton (NFA), so we better leave that topic for another year :)