Friday, June 22, 2012

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

No comments:

Post a Comment