Задача на автоматы Prolog

Question

Мне нужно написать предикат, который проверяет принимает ли конечный детерминированный автомат слово длины k(в моем случае number). Если да - возвращает первое слово, если нет - false. Написал вот такую реализацию, но она не работает. Может кто-то помочь, что не так и как переделать?

initial(0).
final(1). final(2).
arc(0,c,1).
arc(1,d,1). arc(0,a,3).
arc(3,b,2).

test(number, Words) :-
  initial(Node),
  recognize(Node,number,Words).

recognize(Node, 0, []) :-
  final(Node).

recognize(FromNode,number,String) :-
  arc(FromNode,Label,ToNode),
  traverse(Label,String,NewString),
  recognize(ToNode,number-1,NewString).

traverse(First,[First|Rest],Rest).

Answer 1

Переменные в Прологе надо писать с прописных букв: number -> Number.

Надпись number-1 в Прологе не приводит к вычислению разницы. Нужно использовать is в отдельном предложении.

Рекурсию по number нужно ограничить нулём снизу.

В итоге получился такой код:

initial(0).

final(1).
final(2).

arc(0, a, 3).
arc(3, b, 2).
arc(0, c, 1).
arc(1, d, 1).

test(Number, Arcs) :-
  initial(Node),
  recognize(Node, Number, Arcs).

recognize(Node, 0, []) :-
  final(Node).

recognize(FromNode, Number, [Head|Tail]) :-
  Number > 0,
  arc(FromNode, Head, ToNode),
  M is Number - 1,
  recognize(ToNode, M, Tail).

$ swipl -s automata_2.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(0, X).
false.

@?- test(1, X).
X = [c] ;
false.

@?- test(2, X).
X = [a, b] ;
X = [c, d] ;
false.

@?- test(3, X).
X = [c, d, d] ;
false.

@?- test(4, X).
X = [c, d, d, d] ;
false.

@?-

Насколько эффективно, правильно и корректно такое решение не скажу. Сам первый раз писал на Прологе. :)

БЛОГ НА HUSL

Задача на автоматы Prolog

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