Недетермінізм із довільним вибором альтернативи та недетермінізм із невідомим вибором альтернативи
У літературі з логічного програмування розрізняють два види недетермінізму. Відрізняються вони принципом вибору наступної альтернативи, яка має бути виконана.Недетермінізм з довільним вибором альтернативив рамках моделі обчислень логічного програмування означає, що до рішення веде редукція будь-якої мети, і не має значення яке приватне рішення знайдено. У випадкунедетермінізму з невідомим вибором альтернатививибір має значення, але на момент вибору невідомо, який коректний вибір.
Більшість прикладів появи недетермінізму з довільним вибором альтернативи не становлять інтересу для програмуючих на Пролозі. Ілюстративний приклад недетермінізму із довільним вибором альтернативи дає програмаminimum(див. програму 3.7). ЯкщоХі У збігаються, програма
поводиться як недетермінована, з довільним вибором альтернативи.
З іншого боку, програми, які демонструють недетермінізм із невідомим вибором альтернативи, є цілком звичайними. Розглянемо програму для перевірки ізоморфності двох бінарних дерев. Така перевірка забезпечується програмою 3.25, яка виглядає так:
isotree (void, void).
isotree (tree (X, L1, R1), tree (X.L2, R2)) isotree (L1, R1), isotree (L2, R2).
isotree (tree , деQ– безліч станів, S – безліч символів,D–відображення зQxSв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,IіFвизначаються так само, як і для НКА,G–список символів , які можна помістити в стек, Z – початковий символ, що міститься у стеку,D(дельта-функція) – функція переходів, що враховує стан стека, поточний символ та внутрішній станавтомата.
Мал.14.5.Простий автомат.
Рядок символів, представлений списком 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Інтерпретатор для недетермінованого кінцевого автомата.
Функціонування НМА із заданою функцієюDвизначається його станом, першим символом у вхідному рядку та елементом у вершині стека. За одну операцію НМА може помістити в стек або виштовхнути один символ з стека.
Абстрактний інтерпретатор НМА (програма 14.15) подібний до інтерпретатора НКА, представленого програмою 14.13. Як і у випадку НКА, для імітації дії НМА необхідні предикати, що визначають початковий та кінцевий стан автомата. Безліч символів визначаються неявно. У програмі 14.15 передбачається, що спочатку стек порожній. Відношенняdelta(Q,,A,S,Q1,S1)має незначні відмінності від аналогічного відношення для НКА. Воно істинно, якщо, перебуваючи в станіQпри вхідному символіАта стані стекаS,НМА переходить у станQ1і переводить стек у станS1.
Окремий випадок НМА представлений програмою. Цей автомат розпізнає паліндром над кінцевим алфавітом. Паліндромом називається непустий рядок, який зліва направо і праворуч наліво читається однаково. Наприклад, рядкиabbaіabaahaaba–паліндроми. Розглянутий автомат має два стани: станq0,у якому символи поміщаються в стек, і станq1,у якому символи виштовхуються зі стека і порівнюються із символами вхідного потоку. Рішення про завершення запису в стек та проНа початку зчитування зі стека приймаються недетерміновано. У програмі визначено два фактиdelta,які відповідають переходам зі стануq0у станq1і враховують, що паліндроми можуть мати непарну або парну довжину.
Рядок, представлений списком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паліндромом.
delta(q0,X,S,q0,[XS]). delta (q0, X, S, ql, [X S]). dclta(q0,X,S,ql,S).
Програма14.16.Визначення НМА для паліндромів над кінцевим алфавітом.
Рядок, представлений списком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).
Програма14.17.Програма, що розпізнає паліндроми.
У процесі перетворення програм 14.15 та 14.16 у програму 14.17 використано методрозкриття цілейРозкриття – корисний прийом перетворення програм, що використовується і в інших місцях книги. Зробимо невеликий відступ, щоб визначити цей метод.
Розглянемо деяку метуA
Це визначення аналогічне визначення розкриття в мовах функціонального програмування.
Наприклад, розкриття мети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.
Так само можна побудувати інтерпретатор для машини Тьюринга. Цей факт, між іншим, говорить про те, що Пролог має потужність машини Т'юрінга, а отже, і всіх інших відомих моделей обчислень.