查找有限自动机 (Prolog) 接受的所有 K 长度单词

Question

为了在序言中表示 M finite automata 我使用了以下谓词：

states      /*states(Q) <=> Q is the list of automata's states*/
symbols     /*symbols(Sigma) <=> Sigma is the list of automata's input symbols*/
transition  /*transition(X, A, Y) <=> δ(X, A)=Y*/
startState  /*startState(S) <=> S is the start state of automata*/
finalStates /*finalStates(F) <=> F is the list of automata's final states */

对于这个示例自动机：

表示为：

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]).

假设 fiven w 词被 M 自动机识别（接受）<=> accepted(W) (W是一个词的代表列表)

accepted(W):-startState(Q0), accepted1(Q0, W)

其中accepted1 <=> w属于自动机Q状态识别的语言

accepted1(Q, []):- finalStates(F), !, member(Q, F).
accepted1(Q, [A|W]):- transition(Q, A, Q1), accepted1(Q1, W),!.

这里的问题是：如何找到给定M有限自动机接受的所有正K长度的词？

Answer 1

从声明性 pov，你可以只写一个谓词 l_power_n(W,K) 来统一 W 和 Σ^K 中的任何字符串。然后生成并测试目标 l_power_k(W,K), accepted(W).

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, q2). % Edited to reflect image
transition(q2, b, q1). % Edited to reflect image
startState(q0).
finalStates([q2]).

accepted(W):-startState(Q0), accepted1(Q0, W).

accepted1(Q, []):- finalStates(F), !, member(Q, F).
accepted1(Q, [A|W]):- transition(Q, A, Q1), accepted1(Q1, W),!.


% in_language(Word, Length): True if Word is of length Length and is part of the language.
l_power_k([], 0):- !.
l_power_k([WHead|WTail],K):-
    symbols(Symbols), member( WHead,Symbols ),
    K1 is K-1,
    l_power_k( WTail, K1).

Answer 2

另一种方法是设置一个你想要的长度的虚拟列表。您可以将辅助列表作为参数添加到 accepted1:

accepted1(Q, [], []) :- finalStates(F), !, member(Q, F).
accepted1(Q, [_|K], [A|W]) :- transition(Q, A, Q1), accepted1(Q1, K, W),!.

accept_length(Q, R, Length) :-
    length(K, Length),
    accepted1(Q, K, R).

查找有限自动机 (Prolog) 接受的所有 K 长度单词

Find all K-length words accepted by finite automata (Prolog)

finite-automata

prolog