Прологовые места в таблице

Вы можете использовать грамматику определенных предложений (DCG) для реализации преобразователя с конечным состоянием. Хотя DCG не выполняют много композиционных операций на стороне производства, они достаточно хороши для реализации стороны распознавания.

Итак, вы хотите распознать два разных типа прогонов единиц. Итак, в основном я предполагаю, что строка ввода выглядит следующим образом в расширенной форме Бэкуса-Наура (EBNF):

line :== exs run1 exs run2 exs | exs.
exs  :== { "x" } "x".
run1 :== { "1" } "1".
run2 :== { "1" } "1".

Для решения проблемы распознавания вы можете написать DCG без атрибутов (далее следует текст Пролога, который вы можете поместить в файл или напрямую обратиться к нему через ?- [пользователь]):

line --> exs, run1, exs, run2, exs | exs.

run1 --> "1", run1.
run1 --> "1".

run2 --> "1", run2.
run2 --> "1".

exs --> "x", exs.
exs --> "x".

Вот несколько примеров запусков:

?- phrase(line,"xxx").
Yes 
?- phrase(line,"xxx111xxx111xxx").
Yes 
?- phrase(line,"xxx111xxx"). 
No

Для производственной задачи вы можете просто добавить атрибуты в DCG. Использование списка различий работает проще всего:

line(I,O) --> exs(I,H), run1(H,J), exs(J,K), run2(K,L), exs(L,O) | exs(I,O).

run1([0'1|I],O) --> "1", run1(I,O).
run1([0'1|H],H) --> "1".

run2([0'2|I],O) --> "1", run2(I,O).
run2([0'2|H],H) --> "1".

exs([0'x|I],O) --> "x", exs(I,O).
exs([0'x|H],H) --> "x".

Вот несколько примеров запусков:

?- phrase(line(R,[]),"xxx").
R = [120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx111xxx").
R = [120, 120, 120, 49, 49, 49, 120, 120, 120, 50, 50, 50, 120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx").
No

Примечание. 0' — это нотация Пролога для кода символа. В ascii мы имеем 0'x = 120, 0'1 = 49, 0'2 = 50, что объясняет результат. Вышеописанное должно работать на большинстве систем Prolog, поскольку они поддерживают DCG.

Пока

Грамматика определенного предложения
http://en.wikipedia.org/wiki/Definite_clause_grammar

Преобразователь конечного состояния
http://en.wikipedia.org/wiki/Finite_state_transducer

Мы можем применить специальную транслитерацию (только для «горизонтальных» списков):

transliteration(Matrix, Translit) :-
  maplist(transliteration(not_seen), Matrix, Translit).

transliteration(_State, [], []).
transliteration(State, [X|Xs], [Y|Ys]) :-
  transliteration(State, X, NewState, Y),
  transliteration(NewState, Xs, Ys).

% handle only required state change
transliteration(not_seen, 0'1, seen_first, 0'1).
transliteration(seen_first, C, seen_last, C) :- C =\= 0'1.
transliteration(seen_last, 0'1, seen_last, 0'2).
% catch all, when no change required
transliteration(State, C, State, C).

Похоже на решение, предложенное @chac, но более прямое.

walk(L, R) :- walk(s0, L, R).
walk(_, [], []). % finish
walk(s0, [0'1|T], [0'1|R]) :- walk(s1, T, R).
walk(s1, [0'x|T], [0'x|R]) :- walk(s2, T, R).
walk(s2, [0'1|T], [0'2|R]) :- walk(s2, T, R).
walk(S, [H|T], [H|R]) :- walk(S, T, R). % keep state and do nothing