building FSA in prolog

I am asked to represent a FSA in prolog.

An fsa is a list of states.

A state is a structure with the functor state and 3 arguments: a name, a list of transitions, and either yes or no to indicate whether the state is accepting or not.

A transition is a structure with the functor transition and 2 arguments: from, a character, and to, a state name.

Our FSAs do not have epsilon moves.

nondfsa(FSA) is true if FSA is non-deterministic. Finish nondfsa. Hint: use a helper predicate, nondstate(State) , that is true if State has non-deterministic transitions. You can add clauses for the predicates.`

I am given the answer as follows:

nondfsa([Hstate | _ ])
    :- nondstate(Hstate).
nondfsa([ _ | Tailstates]) :-
    nondfsa(Tailstates).

nondstate(state( _ , Transitions, _ )):-
    member(transition(Char, To1), Transitions),
    member(transition(Char, To2), Transitions),
    not(To1 = To2).

can anyone help explain to me what each predicate is doing? I am very confused on what exactly these lines are translating to.

I understand An fsa without epsilon moves is non-deterministic if at least one state has more than one transition with the same character. I just don't understand what is going on in this code.

---

The presented code is very straightforward and it would be good to learn to "read through" a Prolog predicate.

nondfsa([Hstate | _ ]) :-
    nondstate(Hstate).
nondfsa([ _ | Tailstates]) :-
    nondfsa(Tailstates).

This is a very common Prolog pattern which recursively checks every element of a list for something. nondfsa/1 checks each element of the list. If any of them is a non-deterministic state (according to nondstate/1 ), then nondfsa/1 succeeds, meaning the FSA is non-deterministic. If nondstate/1 does not succeed for any element in the given list, then nondfsa/1 will fail. The first clause checks the head of the list. The second clause skips the head and checks the rest of the list. In the recursive call, Prolog starts back at the first clause again, so it simply checks the next element via nondstate/1 .

nondstate(state( _ , Transitions, _ )):-
    member(transition(Char, To1), Transitions),
    member(transition(Char, To2), Transitions),
    not(To1 = To2).

nondstate/1 succeeds if the given state/3 is found to be non-deterministic per some definition which depends only upon the transitions of that state. If you read through your nondstate/1 predicate, you can see what this is. The predicate succeeds if:

I can obtain a member of the list of transitions

I can obtain another member of the list of transitions using the same character (this will always succeed at least once, using the same member as in #1)

The destination state for each of the two members are different

In other words, a state is non-deterministic if there's one character that has transition to at least two different states.

链接地址: http://www.djcxy.com/p/66942.html

上一篇: Prolog中的简单主谓词示例

下一篇: 在prolog建设FSA