Детерминизм c Конечный автомат с Прологом

Question

Я пытаюсь создать Deterministi c Finite Automaton (DFA) с помощью Prolog, но я застрял. У меня не было этой проблемы с Haskell, поэтому я буду очень признателен за любую помощь. Пока что я сделал вот что:

start(q1).
final(q4).
transition(q1, '.', q3).
transition(q1, '0', q2).
transition(q1, '1', q2).
transition(q2, '.', q4).
transition(q2, '0', q2).
transition(q2, '1', q2).
transition(q3, '.', q5).
transition(q3, '0', q4).
transition(q3, '1', q4).
transition(q4, '.', q5).
transition(q4, '0', q4).
transition(q4, '1', q4).
transition(q5, '0', q5).
transition(q5, '1', q5).

accept(symbols, startState).

dfaAccept(symbols) :-
   start(startstate).
dfaAccept([], State) :-
   final(State).
dfaAccept([Symbol|Symbols], State) :-
   transition(State, Symbol, NextState),
   accept(Symbols, NextState).

Когда я запускаю

dfaAccept(df1, "1.01").

, я должен получить истину, но получаю ложь ....

Answer 1

Я думаю, что DCG - даже лучший способ представления конечных автоматов, но давайте поговорим о синтаксисе:

Вы вызываете

dfaAccept(df1, "1.01").

, но предикат dfaAccept/2 ожидает аргументов в обратном порядке:

dfaAccept([Symbol|Symbols], State)

df1 также не упоминается снова.

Тогда «1.01» может быть или не быть «списком символов (атомы длины 1)» в зависимости от на вашем Прологе. Если это SWI Prolog, вы должны сначала его трансмогрифицировать, используя atom_chars/2.

А для чего accept(symbols, startState).? Он болтается все в одиночестве.