DFA удалить недопустимые символы

Question

Итак, я представляю этот DFA:

Как это

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

И у меня есть предикат, который анализирует строку и возвращает true, если это приемлемо:

transition(X,[A|B]) :- arc(X,A,T),transition(T,B).  
transition(X,[]) :- final(X).
parse(X) :- initial(S),transition(S,X).

Теперь я хочу создать предикат check(X,Y), который возьмет список и удалит все индексы, которые не a или b. Y будет новым списком, который содержит неправильные индексы.

например:

?-check([a,1,b,c,b],Y).
Y=[a,b,b];
false

Я не в Прологе, и я много чего пробовал, но ничего не получилось, что мне нужно. Можете ли вы дать мне руководство, как сделать предикат проверки?

Answer 1

Я собираюсь предположить, что у вас есть список char-атомов, например [a,b,c,d,e,f,a,b,c], и вы хотите, чтобы он был [a,b,a,b]. Пустой список - это ваш базовый случай:

check([], []).

Затем, беспокойтесь о том, находится ли текущий символ в вашем приемлемом списке:

check([C|Cs], Result) :- 
    check(Cs, Rs),
    (arc(_, C, _) 
        -> Result = [C|Rs]
        ;  Result = Rs).

В действии:

?- check([a,b,c,d,a,b,e], X).
X = [a, b, a, b].

Вы можете использовать string_chars/2 для преобразования между строками SWI и этим представлением, если необходимо:

?- string_chars("abcdabe", S), check(S, SFiltered), string_chars(FilteredString, SFiltered).
S = [a, b, c, d, a, b, e],
SFiltered = [a, b, a, b],
FilteredString = "abab".