Simulation of Non-deterministic finite state automata using backtracking feature of prolog.

Let us now see how the features of prolog can be used to simulate a non-deterministic automata which would have been a cumbersome task using other programming languages.

A nondeterministic finite automaton is an abstract machine that reads a string of symbols as input and decides whether to accept or to reject the input string. An automaton has a number of states and it is always in one of the states. The automata can change from one state to another upon encountering some input symbols. In a non deterministic automata the transitions can be non deterministic meaning that the transition may take place with a NULL character or the same character may result in different transitions

A non deterministic automaton decides which of the possible moves to execute, and it chooses a move that leads to the acceptance of the string if such a move is available.

Let us simulate the given automata.