PROLOG

Here is a DFA and its transitions:

startnode(s1). finalnode(s4). transition(s1, a, s2). transition(s2, a, s2). transition(s3, a, s1). transition(s2, b, s1). transition(s3, b, s4). transition(s2, c, s4). transition(s4, d, s3).

Create a predicate in Prolog, states(X), where X is a list of symbols, that shows the states it traverses from. Before that it should be checked that we have the correct input symbols (only a, b, c, d). That's why I provide you the following predicate parse(L):

parse(L) :- startnode(S), trans(S,L). trans(X,[A|B]) :- transition(X,A,Y), trans(Y,B). trans(X,[]) :- finalnode(X).

I am giving some examples:

?-states([a,a,c]).

S1

S2

S2

S4

true

?-states([a,c,c]).

false

I hope it is clear. The answer should be as above and not just check if the list with the input symbols are accepted by the dfa. Be careful!!

a a Si S2 b a b S3 S4 d