/* File: dfa6.pl System: SWI-Prolog 5.2.8 Author: Mihaela Malita Date: 10/02/2003 Title: Check if a DFA accepts any words of certain length. DFA accepts words like a(a+b)*b Alphabet={a,b}, States={0,1,2,3} Favorable={2} start is state 0. t(0,a,1). t(0,b,3). t(1,a,1). t(1,b,2). t(2,a,1). t(2,b,2). t(3,a,3). t(3,b,3). favorable(2). % declare state 3 as favorable start(0). % declare state 0 as start state ?- start. Check if DFA accepts any words Yes Load your file: ?- ['C://swimm/dfa6.pl']. Yes ?- start. Check if DFA accepts any words of length 3 [a, a, b] Yes *************************************************/ % Definition of our DFA that accepts a(a+b)*b t(0,a,1). t(0,b,3). t(1,a,1). t(1,b,2). t(2,a,1). t(2,b,2). t(3,a,3). t(3,b,3). start(0). % 0 is the starting state favorable(2). % 2 is a favorable state % Check if a word is accepted. check_word(S,[]):- favorable(S). check_word(S,[H|T]) :- t(S,H,Q),check_word(Q,T). % Ask for a word see if it is accepted (yes/no). start:- write('Check if DFA accepts any words of length 3\n'), start(Q),check_word(Q,[X,Y,Z]),write([X,Y,Z]).