Автоматы на прологе

Question

Как найти слово длины k которое принимает недетерминированный конечный автомат в прологе(если их много, достаточно будет одного)? Автомат записываю вот так:

states([q0, q1, q2]).
symbols([a, b]).
transition(q0, a, q1).
transition(q0, b, q2).
transition(q1, a, q2).
transition(q1, b, q0).
transition(q2, a, q1).
transition(q2, b, q2).
startState(q0).
finalStates([q2]).

Answer 1

В вашей нотации решение будет такое:

states([q0, q1, q2]).
symbols([a, b]).
transition(q0, a, q1).
transition(q0, b, q2).
transition(q1, a, q2).
transition(q1, b, q0).
transition(q2, a, q1).
transition(q2, b, q2).
startState(q0).
finalStates([q2]).

search(0, S, []) :-
    finalStates(FinalStates),
    member(S, FinalStates).
search(N, S1, [Head|Tail]) :-
    N > 0,
    transition(S1, Head, S2),
    M is N - 1,
    search(M, S2, Tail).

test(N, Transitions) :-
    startState(S),
    search(N, S, Transitions).

$ swipl -s automata.pl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.2.3)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- test(4, X).
X = [a, a, a, a] ;
X = [a, a, b, b] ;
X = [a, b, a, a] ;
X = [a, b, b, b] ;
X = [b, a, a, b] ;
X = [b, a, b, b] ;
X = [b, b, a, a] ;
X = [b, b, b, b] ;
false.

БЛОГ НА HUSL

Автоматы на прологе

Ответы (1 шт):