Моделирование недетерминированных вычислений.

В этом разделе представлены простые программы, имитирующие некоторые фундаментальные модели вычислений.На Прологе очень легко писать интерпретаторыдля автоматов различных классов.

Имитационные программы являются естественной областью применения недетерминированного программирования. Действие недетерминированного автомата хорошо иллюстрирует недетерминизм с неизвестным выбором альтернативы. Интересно, что вследствие присущего Прологу недетерминизма недетерминированный автомат имитируется так же легко, как и детерминированный.

Рассмотрим недетерминированный конечный автомат (НКА), определяемый пятеркой <Q,S,D,I,F>, где Q – множество состояний, S – множество символов, D – отображение из Q x S в Q, I – начальное состояние и F – множество конечных состояний автомата. Если отображение является функцией, то рассматриваемый автомат оказывается детерминированным.

В Прологе конечный автомат может быть описан тремя наборами фактов: initial (Q), истинным, если Q – начальное состояние автомата; final (Q), истинным, если Q – конечное состояние автомата; delta (Q, A, Q1), истинным, если НКА переходит из состояния Q в состояние Q1 при получении символа А. Множество состояний и множество входных символов определяются неявно как константы, входящие в предикаты.

Программа 14.13 является абстрактным интерпретатором НКА, Основной предикат программы – accept (S) истинен, если строка символов S, представляемая списком символов, допускаетсяНКА.

Чтобы воспользоваться интерпретатором для имитации поведения определенного конечного автомата, этот автомат следует специфицировать. Это влечет за собой определение его начального состояния, конечного состояния и отношения переходов delta. Программа 14.14 определяет НКА, распознающий язык (аb)*. Этот автомат изображен на рис. 14.5. Он имеет два состояния: q0 и q1. Если автомат находится в состоянии q0 и считывается символ а. то автомат переходит в состояние q1; переход из состояния q1 в состояние q0 происходит при считывании символа b.

Другая базовая модель вычислений представляется магазинным автоматом, который распознает языки из класса контекстно-свободных языков. Недетерминированный магазинный автомат (НМА) получается посредством расширения модели НКА добавлением магазинной памяти для внутреннего состояния автомата. Формально НМА представляется семеркой <Q,S,G,D,I,Z,F>, где Q,S,I и F определяются так же, как и для НКА, G – список символов, которые можно поместить в стек, Z – начальный символ, содержащийся в стеке, D (дельта-функция) – функция переходов, учитывающая состояние стека, текущий символ и внутреннее состояние автомата.

Рис.14.5. Простой автомат.

accept(S) ¬

Строка символов, представленная списком S, принимается НКА, определенным предикатами initial/1, delta/3 и final/1.

accept(S) ¬initial(Q), accept(Q,S)

accept (Q.[X | Xs]) ¬ deita(Q,X,Ql),accept (Ql,Xs).

accept (Q,[ ]) ¬ finа1(Q).

Программа 14.13 Интерпретатор для недетерминированного конечного автомата.

initial(q0).

final (q0).

delta(q0,a,q1)

delta(ql,b,q0).

Программа 14.14. НКА, распознающий язык (ab)*.

Функционирование НМА с заданной функцией D определяется его состоянием, первым символом во входной строке и элементом в вершине стека. За одну операцию НМА может поместить в стек или вытолкнуть из стека один символ.

Абстрактный интерпретатор НМА (программа 14.15) сходен с интерпретатором НКА, представленным программой 14.13. Как и в случае НКА, для имитации действия НМА необходимы предикаты, определяющие начальное и конечное состояния автомата. Множества символов определяются неявно. В программе 14.15 предполагается, что первоначально стек пуст. Отношение delta(Q,,A,S,Q1,S1) имеет незначительные отличия от аналогичного отношения для НКА. Оно истинно, если, находясь в состоянии Q при входном символе А и состоянии стека S, НМА переходит в состояние Q1 и переводит стек в состояние S1.

Частный случай НМА представлен программой. Этот автомат распознает палиндромы над конечным алфавитом. Палиндромом называется непустая строка, которая слева направо и справа налево читается одинаково. Например, строки abba и abaahaaba – палиндромы. Рассматриваемый автомат имеет два состояния: состояние q0, в котором символы помещаются в стек, и состояние q1, в котором символы выталкиваются из стека и сравниваются с символами входного потока. Решения о завершении записи в стек и о начале считывания из стека принимаются недетерминированно. В программе определены два факта delta, которые соответствуют переходам из состояния q0 в состояние q1 и учитывают, что палиндромы могут иметь нечетную или четную длину.

accept(S)¬

Строка, представленная списком S. принимается НМД, определенным предикатами initial/1, delta/5 и final/1.

accepl(Xs) ¬ inilial(Q). accept(Q,Xs.[ ]).

accept(Q,[X | Xs],S)¬delta(Q,X.S,Ql,Sl), accept(QI,Xs,Sl).

accept (Q,[ ],[ ]) ¬ final (Q).

Программа 14.15 Интерпретатор недетерминированного магазинного автомата.

Интерпретатор и программу, определяющую автомат, можно представить в виде одной программы. В частности, программа 14.17 получена в результате объединения программ 14.15 и 14.16. В ней определено отношение palindrome (Xs), используемоедля проверки того, является ли строка Xs палиндромом.

initial(q0). final(ql).

delta(q0,X,S,q0,[X | S]). delta (q0,X,S,ql,[X | S]). dclta(q0,X,S,ql,S).

deita(ql,X,[X | S],ql,S).

Программа 14.16. Определение НМА для палиндромов над конечным алфавитом.

palindrome ( Xs) ¬

Строка, представленная списком Xs, –- палиндром.

palindrome(Xs) ¬ palindrome(q0,Xs,[ ]).

palindrome(q0, [X | Xs],S) ¬ palindrome(qO,Xs,[X | S]). palindrome(qO,[X | Xs],S)¬palindrome(ql,[X | Xs],S).

palindrome (qO,[X | Xs],S) ¬ palindrome (ql,Xs,S).

palindrome(ql,[X | Xs],[X | S]) ¬ paIindrome(ql,Xs,S).

pa!indrome(ql,[ ].[ ]).

Программа 14.17. Программа, распознающая палиндромы.

В процессе преобразования программ 14.15 и 14.16 в программу 14.17 использован метод раскрытие целей Раскрытие – полезный прием преобразования программ, используемый и в других местах книги. Сделаем небольшое отступление, чтобы дать определение этому методу.

Рассмотрим некоторую цель Aв предложении Н¬А...,Аи предложение С = (А¬ B,...,B), такие, что Аи А унифицируемы с наиболее общим унификатором Q. Раскрытие цели Аотносительно ее определения С дает предложение (H¬А...,A,B,...,B,А,...A)Q.

Это определение аналогично определению раскрытия в языках функционального программирования.

Например, раскрытие цели initial (Q) в предложении

accept (X) ¬ initial (Q),accept(Q,X,[ ]).

с использованием ее определения initial (q0) дает предложение

accept (X) ¬ accept(q0,X,[ ]).

Если цель определяется несколькими предложениями, то раскрытие даст столько предожений, сколько их было в определении цели. Например, раскрытие цели delta в предложении

accept(Q,[X | Xs],S)¬delta(Q,X.S,Ql,Sl), accept(Q1,Xs,Sl).

с использованием определения цели delta в программе 14.16 приведет к четырем предложениям.

Теперь должно быть понятно, каким образом была получена программа 14.17:

раскрытием целей initial и delta в первых двух предложениях программы 14.15 и раскрытием цели final в оставшемся предложении. Кроме того, предикат accept был заменен в новой программе предикатом palindrome.

Подобным образом можно построить интерпретатор для машины Тьюринга. Этот факт, между прочим, говорит о том, что Пролог имеет мощность машины Тьюринга, а следовательно, и всех других известных моделей вычислений.