Найти все K-длину слово, принятое конечными автоматами (Пролог)

Question

Представлять Mfinite 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 ж слово распознано (принято) по M автоматов < =>accepted(W) (W представляет интересы список слов в)

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

Где accepted1 < =>ш принадлежит язык, который распознает состояние автоматов Q.

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

Вопрос состоит в следующем: как найти все положительные K -длина слова, принятые данным M конечных автоматов?

Answer 1

Другой подход заключается в установке фиктивный список длины вы хотите. Вы должны добавить вспомогательный список в качестве аргумента для своего 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). 

Answer 2

Из декларативного 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).