/* File: dfa1.pl System: SWI-Prolog 5.2.8
Author: MM
Date: 10/02/2003
Title: Explore if the DFA defined is well defined.
DFA accepts words that start with a.
Alphabet={a,b}, States={0,1,2} Favorable={1} start is state 0.
Transition function is:
delta(0,a)=1 delta(0,b)=2
delta(1,a)=1 delta(1,b)=1
delta(2,a)=2 delta(2,b)=2
Load your file:
?- ['C://swimm/dfa21.pl'].
Yes
Is there a start state.
?- start(_).
Yes
Is there one or more favorable states?
?- favorable(_).
Yes
List the delta/3 describing the transition function?
?- listing(delta).
Is there any trap state (for any words goes into itself)?
?- delta(S,a,S),delta(S,b,S).
S = 1 % You type
Yes
Is there any trap state that is not favorable (final)?
?- delta(S,a,S),delta(S,b,S), not favorable(S).
No
Find the alphabet and put it in a list. Use findall/3
Means: take all X with the property delta(_,X,_) and put them in list L.
?- findall(X,delta(_,X,_),L).
Take the list and sort it.
?- findall(X,delta(_,X,_),L), sort(L,Res).
Find the list of all favorable states.
?- findall(Q,favorable(Q),L).
For a certain state print the list of all the states where you can go from it.
?- findall(X,delta(0,_,X),L),sort(L,Res).
Check if from a state Q there are more than 2 arrows for the same letter
(Check if our automaton is deterministic for a certain state)
?- findall(X,delta(0,a,X),L).
L=
I have to find if L has the length =1. Use predicate length/2. See example:
?- length([a,[b,c],d],Len).
Len=3
How many states are there?
?- findall(X,delta(X,a,_),L),sort(L,R),length(R,N).
After I found L let's see how big(long) it is.
?- findall(X,delta(0,a,X),L),length(L,Res).
Res=1
Let's check if it exaclty one arrow from letter a from state 0.
I cannot have two definitions for a from one state.
?- findall(X,delta(0,a,X),L),length(L,Res),Res=1.
Same idea, but easier.
?- findall(X,delta(0,a,X),L),length(L,1).
Let's check if it exaclty two arrows point put of a certain state.
I cannot have two definitions for a from one state.
?- findall(X,delta(0,_,X),L),length(L,2).
*************************************************/
/* This is the definition of your DFA in Prolog.
*/
delta(0,a,1).
delta(0,b,2).
delta(1,a,1).
delta(1,b,1).
delta(2,a,2).
delta(2,b,2).
start(0).
favorable(1).