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.

**Source Code:**

DOMAINS

Symb_list=symbol*

PREDICATES

Trans(symbol,symbol,symbol)

Silent(symbol,symbol)

Final(symbol)

accepts(symbol,Symb_list)

CLAUSES

final(s3).

trans(s1,a,s1).

trans(s1,a,s2).

trans(s1,b,s1).

trans(s2,b,s3).

trans(s3,b,s4).

silent(s2,s4).

silent(s3,s1).

accepts(S,[]):-

final(S).

accepts(S,[H|T]):-

trans(S,H,S1),

accepts(S1,T).

accepts(S,X):-

silent(S,S1),

accepts(S1,X).

GOAL

Accepts(S,[a,b]).

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