Теория вычислительных процессов

Методические указания к выполнению лабораторных работ

Оглавление

Лабораторная работа 1

Вычислимость и разрешимость

1. Изучить основные понятия:

D = { Пн, Вт, Ср, Чт, Пт, Сб, Вс }, D1 = { Вт, Ср, Чт, Пн, Сб, Пт, Вс }.

D и D1 эквивалентны, т.е. порядок элементов не важен.

Будем использовать обозначения:

Лабораторная работа 2

Конечные детерминированные полностью определённые одноленточные автоматы

Цель работы: изучить модель одноленточного автомата.

Задания

1. Изучить назначение одноленточного автомата, способы задания, алгоритм функционирования.

2. Изучить основные понятия:

Одноленточный конечный автомат (ОКА) над алфавитом V задается набором

A = { V, Q, R, q0, #, I } и правилом функционирования, общим для всех таких автоматов. В наборе А

V - алфавит;

# - «пустой» символ.

Говорят, что автомат допускает слово в алфавите V, если, начав работать с лентой, содержащей это слово, он останавливается в заключительном состоянии. Автомат A задает характеристическую функцию множества MA допускаемых им слов в алфавите V, т. е. он распознает, принадлежит ли заданное слово множеству MA если связать с остановкой в заключительном состоянии символ 1, а с остановкой в незаключительном состоянии - 0.

Наглядным способом задания ОКА служат графы автоматов. Автомат А представляется графом, множество вершин которого - множество состояний Q, и из вершины q в вершину q' ведет дуга, помеченная символом а, тогда и только тогда, когда программа автомата содержит команду qаq'. Работе автомата над заданным словом соответствует путь из начальной вершины q. Последовательность проходимых вершин этого пути - это последовательность принимаемых автоматом состояний, образ пути по дугам - читаемое слово. Любой путь в графе автомата, начинающийся в вершине q0 и заканчивающийся в вершине q,R, порождает слово, допустимое автоматом.

Пример 1. ОКА A = ({a, b}, {q0, q1, q2, q3}, {q2}, q0, , I), допускающего слова {an bm | n=1,2, ...; m=1,2, ...}, задается графом (рисунок 1). Программа I содержит команды:

q0aq1; q0bq3; q1aq1; q1bq2; q2aq3; q2bq2; q3aq3; q3bq3.

Другим способом задания ОКА является таблица, в которой строки соответствуют символам алфавита, столбцы - состояниям. В клетке, расположенной в строке a и столбце q записывается состояние q' , если в программе автомата есть команда qаq' . Столбцы, соответствующие заключительным состояниям, отмечаются единицами. Таблица автомата А (см. пример 1) представлена ниже.

Таблица 1. Таблица автомата.

Автомат называется пустым, если МА = , Автоматы А1 и А2 эквивалентны, если МА1 = МА2. Для машины Тьюринга проблемы пустоты и эквивалентности неразрешимы, более того, они не являются частично разрешимыми. Ситуация меняется для конечных автоматов.

Для ОКА доказано:

1) Проблема пустоты ОКА разрешима.

Доказательство основано на проверке допустимости конечного множества всех слов, длина которых не превышает числа состояний ОКА - n. Если ни одно слово из этого множества не допускается, то ОКА «пуст».

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

3) Проблема эквивалентности ОКА разрешима.

Доказательство основано на использовании отношения эквивалентности двух состояний q и q': если состояния q и q' эквивалентны, то для всех aA состояния (q, a) и '(q', a) также эквивалентны. Формируемые пары не должны входить одновременно заключительное и незаключительное состояния.

Полностью определенным называется ОКА, у которого в программе существует команда для любой пары (q, a). При табличном способе задания полностью определённого автомата заполнена каждая клетка.

Частичным называется называется ОКА, у которого в программе не для любой пары (q, a) существует команда. При табличном способе задания частичного автомата заполнены не все клетки.

К детерминированным относятся ОКА, у которых для любой пары (q, a) существует единственная команда, начинающаяся этими символами. При табличном способе задания детерминированного автомата в клетке записано только одно состояние.

ОКА называется минимальным, если он имеет наименьшее число состояний по отношению ко всем ОКА, ему эквивалентным.

Рассмотрим метод минимизации полностью определенных ОКА, предложенный Ауфенкампом и Хоном.

Основная идея этого метода заключается в разбиении всех состояний исходного ОКА на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Т.о. получающийся в результате минимальный автомат имеет столько состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.

Для пользования методом введем несколько определений.

Два состояния абстрактного автомата называются 0-эквивалентными в том случае, если они оба заключительные или оба незаключительные.

Объединение всех 0-эквивалентных состояний абстрактного автомата образует 0-класс эквивалентности.

0-эквивалентные состояния автомата называются 1-эквивалентными, если они переводятся любым символом алфавита также в 0-эквивалентные состояния.

Объединение всех 1-эквивалентных состояний образует 1-класс эквивалентности.

По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения состояний автомата на ( i +1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на - классы эквивалентности.

Разбиение множества состояний автомата на - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

- схемы программ;

- базис, интерпретация, программа, протокол выполнения программы;

- свойства схем программ: пустота, тотальность, функциональная эквивалентность, свобода;

- свободные интерпретации, согласованные свободные интерпретации;

- стандартные и рекурсивные схемы программ;

- изоморфизм и логико-термальная эквивалентность стандартных схем.

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

3. Разработать нерекурсивный алгоритм решения задачи и программно реализовать его.

Построить стандартную схему программы.

Транслировать стандартную схему программы в рекурсивную.

Реализовать рекурсивную программу.

Провести тестирование программ.

begin integer x, y; begin integer x, y; begin

ввод(x); ввод(x); ввод(x);

y:=1; y:=е; y:=a;

L:if x=0 then goto L1;L: if x=0 then goto L1;L: if p(x) then goto L1;

y:=x*y; y:=CONSCAR(x, y); y:=g(x, y);

x:=x-1; x:=CDR(x); x:=h(x);

goto L; goto L; goto L;

L1:вывод(y);L1: вывод(y);L1: вывод(y);

end end end

Функция CONSCAR (суперпозиция функций CONS и CAR из языка Лисп) приписывает первую букву первого слова ко второму слову (т. е. CONSCAR(аб, в) = ав), а функция CAR стирает первую букву слова (т. е. CAR(аб) = б).

Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.

Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.

Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.

Множества символов полного базиса:

Х = x, х1, х2..., у, у1 у2..., z, z1, z2... - множество символов, называемых переменными;

F = f(0), f(1), f(2)..., g(0), g(1), g(2)..., h(0), h(1), h(2)... - множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;

Р = р(0), р(1), р(2)...; q(0), q(1), q(2)...; - множество предикатных символов; р(0), q(0) - ; нульместные символы называют логическими константами;

start, stop, ...,:= и т. д. - множество специальных символов.

Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:

односимвольные слова, состоящие из переменных или констант, являются термами;

слово ф вида f(n)(ф1, ф2...фn), где ф1, ф2...фn - термы, является термом;

те и только те слова, о которых говорится в п.п. 1,2, являются термами.

Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р(n)(ф1, ф2,...,фn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2) (f(2(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Множество операторов включает пять типов:

начальный оператор - слово вида start(х1, х2...хк), где k ?0, а х1, х2...хк - переменные, называемые результатом этого оператора;

заключительный оператор - слово вида stop(ф1, ф2...фn), где n ?0, а ф1, ф2...фn - термы; вхождения переменных в термы ф называются аргументами этого оператора;

оператор присваивания - слово вида х := ф, где х - переменная (результат оператора), а ф - терм; вхождения переменных в термы называются аргументами этого оператора;

условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;

оператор петли - односимвольное слово loop.

Среди операторов присваивания выделим случаи: когда ф - переменная, то оператор называется пересылкой (х:=у) и когда ф -константа, то оператор называется засылкой (х:=а).

Подклассы используют ограниченные базисы. Так, например, подкласс У1 имеет базис:

х1, х2, а, f(1), p(1), start, stop, (,),:=, ,и множество операторов start(х1, х2); х1:= f(x1), x2=f(x2), x1:=а, х2:= а, р(х1), р(х2), stop(х1,х2), т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.

ССП не является записью алгоритма, поэтому позволяет исследовать только структурные свойства программ, но не семантику вычислений. При построении «семантической» теории схем программ вводится понятие интерпретация ССП. Определим это понятие.

Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:

каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;

каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;

каждому функциональному символу f(n) - всюду определенную функцию F(n)=I(f(n));

каждой логической константе р(0) - один символ множества 0,1 ;

каждому предикатному символу р(n) - всюду определенный предикат P(n) = I(p(n)).

Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП).

Определим понятие выполнения программы.

Состоянием памяти программы (S,I) называют функцию W: XS D, которая каждой переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.

Значение терма ф при интерпретации I и состоянии памяти W (обозначим фI(W)) определяется следующим образом:

1) если ф=х, x - переменная, то фI(W) = W(x);

2) если ф=a, a - константа, то фI(W) = I(a);

3) если ф=f(n)(ф1, ф2..., фn), то фI(W)= I(f(n))(ф1I(W), ф2I(W),..., фnI(W)).

Аналогично определяется значение теста при интерпретации I и состоянии памяти W или I(W):

если =р(n)(ф1, ф2..., фn), то I(W)= I(p(n))(ф1I(W), ф2I(W),... фnI(W)), n ?0.

Конфигурацией программы называют пару U=(L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностей конфигураций, которую называют протоколом выполнения программы (ПВП).

Протокол (U0, U1,..., Ui, Ui+1,...) выполнения программы (S,I) определяем следующим образом (ниже ki означает метку вершины, а Wi - состояние памяти в i-й конфигурации протокола, Ui=(ki,Wi)):

U0=(0, W0), W0 - начальное состояние памяти схемы S при интерпретации I.

Пусть Ui=(ki, Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если О - заключительный оператор stop(ф1, ф2... фn), то Ui - последняя конфигурация, так что протокол конечен. В этом случае считают, что, программа (S,I) останавливается, а последовательность значений ф1I(W), ф2I(W),..., фnI(W) объявляют результатом val(S,I) выполнения программы (S,I). В противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая, (i+1)-я конфигурация Ui+1 = (ki+1, Wi+1), причем

а) если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

б) если О - оператор присваивания х:=ф, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L, Wi+1 = Wi, Wi+1(х) = ф1(Wi);

в) если О - условный оператор и I(Wi) = Д, где Д 0,1, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

г) если О - оператор петли, то ki+1 = L и Wi+1 = Wi, так что протокол бесконечен.

Таким образом, программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном случае программа зацикливается и результат ее выполнения не определен.

ССП S в базисе В тотальна (пуста), если для любой интерпретации I базиса В программа (S, I) останавливается (зацикливается).

Стандартные схемы S1 и S2 в базисе В функционально эквивалентны (S1 S2), если либо обе зацикливаются, либо обе останавливаются с одинаковым результатом, т. е. val (S1, I) val (S2, I).

Цепочкой стандартной схемы (ЦСС) называют:

1. конечный путь по вершинам схемы, ведущий от начальной вершины к заключительной;

2. бесконечный путь по вершинам, начинающийся начальной вершиной схемы.

В случае, когда вершина-распознаватель (v), то дополнительно указывается верхний индекс (1 или 0), определяющий 1-дугу или 0-дугу, исходящую из вершины.

Цепочкой операторов (ЦО) называется последовательность операторов, метящих вершины некоторой цепочки схемы.

Пусть S - ССП в базисе В, I - некоторая его интерпретация, (0, 1, к2, к3,…) - последовательность меток инструкций S, выписанных в том порядке, в котором эти метки входят в конфигурации протокола выполнения программы (S, I). Ясно, что эта последовательность - цепочка схемы S. Считают, что интерпретация I подтверждает (порождает) эту цепочку.

ЦСС в базисе В называют допустимой, если она подтверждается хотя бы одной интерпретацией этого базиса.

ССП свободна, если все ее цепочки допустимы.

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

Все СИ базиса В имеют одну и ту же область интерпретации, которая совпадает со множеством Т всех термов базиса В. Все СИ одинаково интерпретируют переменные и функциональные символы, а именно:

а) для любой переменной х из базиса В и для любой СИ Ih этого базиса Ih(x)=x;

б) для любой константы a из базиса В Ih(a)=a;

в) для любого функционального символа f(n) из базиса В, где n1, Ih(f(n))=F(n): TnT, где F(n) - словарная функция такая, что

F(n)(1, 2, ..., n)= f(n) (1, 2, ... n),

т. е. функция F(n) по термам 1, 2, ...n из Т строит новый терм, используя функциональный смысл символа f(n).

Что касается интерпретации предикатных символов, то она полностью свободна, т.е. разные СИ различаются лишь интерпретаций предикатных символов.

Таким образом, после введения СИ термы используются в двух разных качествах, как функциональные выражения в схемах и как значения переменных и выражений. В дальнейшем термы-значения будем заключать в апострофы. Например, если где 1=`f(x,a)` - терм-значение переменной x, а где 2 = `g(y)` - терм-значение переменной y, то значение свободно интерпретированного терма 3=f(x, h(y)) равно терму-значению `f(f(x,a), h(g(y)))`.

Полагают, что интерпретация I и СИ Ih (того же базиса В) согласованы, если для любого логического выражения справедливо Ih()=I().

Если интерпретация I и свободная интерпретация Ih согласованы, то программы (S, I) и (S, Ih) либо зацикливаются, либо обе останавливаются и I(val(S,Ih))= val(S,I), т.е. каждой конкретной программе можно поставить во взаимно-однозначное соответствие свободно интерпретированную (стандартную) согласованную программу.

Если интерпретация и свободная интерпретация согласованы, они порождают одну и ту же цепочку операторов схемы.

Теорема Лакхэма - Парка - Паттерсона. Стандартные схемы S1 и S2 в базисе В функционально эквивалентны тогда и только тогда, когда они функционально эквивалентны на множестве всех свободных интерпретаций базиса В, т.е. когда для любой свободной интерпретации Ih программы (S1,Ih) и (S2,Ih) либо обе зацикливаются, либо обе останавливаются и val(S1,I) = {I(val(S1 Ih)) = I(val(S2 Ih))} = val(S2,I).

Стандартная схема S в базисе В пуста (тотальна, свободна) тогда и только тогда, когда она пуста (тотальна, свободна) на множестве всех свободных интерпретаций этого базиса, т.е. если для любой свободной интерпретации Ih программа (S, Ih) зацикливается (останавливается).

Стандартная схема S в базисе В свободна тогда и только тогда, когда она свободна на множестве всех свободных интерпретаций этого базиса, т. е. когда каждая цепочка схемы подтверждается хотя бы одной свободной интерпретацией.

Одним из отношений эквивалентности является логико-термальная эквивалентность (ЛТЭ).

Определим термальное значение переменной х для конечного пути щ схемы S как терм t(щ, x), который строится следующим образом.

Если путь щ содержит только один оператор А, то: t(щ, x) = , если А - оператор присваивания, t(щ, x) = х, в остальных случаях.

Если щ = щ'Ае, где А - оператор, е - выходящая из него дуга, щ' - непустой путь, ведущий к А, а x1, …, xn - все переменные терма t(Ае, x), то t(щ, x) = t(Ае, x)[ t(щ', x1)/x1, …, t(щ', xn)/xn].

Понятие термального значения распространим на произвольные термы :t(щ, x) = [ t(щ, x1)/x1, …, t(щ, xn)/xn].

Например, пути

start(х); y:=x; p1(x); x:=f(x); p0(y); y:=x; p1(x); x:=f(x) в схеме на рисунке 3.1, а соответствует термальное значение f(f(x)) переменной х.

Для пути щ в стандартной схеме S определим ее логико-термальную историю (ЛТИ) lt(S, щ) как слово, которое строится следующим образом.

Если путь щ не содержит распознавателей и заключительной вершины, то lt(S, щ) - пустое слово.

Если щ = щ'vе, где v - распознаватель с тестом p(1, ..., k), а е - выходящая из него Д-дуга, Д 0,1, то lt(S, щ) = lt(S, щ') pД(t(щ', 1), …, t(щ', k)).

Если щ = щ'v, где v - заключительная вершина с оператором stop(1, ..., k), то

lt(S, щ) = lt(S, щ') t(щ', 1) … t(щ', k).

Например, логико-термальной историей пути, упомянутого в приведенном выше примере, будет p1(x) p0(x) p1(f(x)).

Размещено на http://www.allbest.ru