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.
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]).
