Шпаргалка по "Программированию и компьютерам"

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

Пример 1.2. ОКА A = ({a, b}, {q₀, q₁, q₂, q₃}, {q₂}, q₀, #, I), допускающего слова {aⁿ b^m | n=1,2, ...; m=1,2, ...}, задается графом (рисунок 1.5). Программа I содержит команды:

q₀a®q₁; q₀b®q₃; q₁a®q₁; q₁b®q₂; q₂a®q₃; q₂b®q₂; q₃a®q₃; q₃b®q₃.

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

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

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

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

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

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

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

 

6. Моделирование схем программ, многоленточные автоматы

Многоленточный (детерминированный, односторонний) конечный автомат (МКА) задается так же, как ОКА. Отличие состоит в том, что множество состояний Q разбивается на n ³ 2 подмножеств (непересекающихся) Q₁, ..., Q_n. «Физическая» интерпретация n - ленточного автомата отличается тем, что он имеет n лент и n головок, по головке на ленту. Если автомат находится в состоянии qÎQ_i, то i-я головка читает i-ю ленту так же, как это делает ОКА. При переходе МКА в состояние q'ÎQ_j (i¹j) i-я головка останавливается, а j-я начинает читать свою ленту. МКА останавливается, когда головка на одной из лент прочитает символ #.

Рассмотрим функционирование МКА  с n=2 (рисунок 1.6) на примере сравнения  пар слов в алфавите {1, 0} и допуске  только совпадающих слов.

Здесь Q=Q₁UQ₂, где Q₁={q₀¹}; Q₂={q₁², q₂², q₃²}; R={q₀¹}; V={0, 1}, начальное состояние - q₀¹. МКА обрабатывает наборы слов (U₁, U₂), где слово U₁ записано на первой ленте, а U₂ - на второй. Допустимое множество наборов M_A -это все возможные пары одинаковых слов, т.е. наборы, где U₁ = U₂. Например, набор может быть (1101, 1101) и т.п.

В том случае, когда слова совпадают, МКА остановится в заключительном состоянии q₀¹ (именно в этом состоянии поступит символ #) и набор будет допущен. Если слова не совпадут хотя бы в одном символе, МКА перейдет в состояние q₃², из которого не выйдет до появления символа #, который и зафиксирует отсутствие совпадения слов, т.е. не допустит искаженный набор.

Доказывается разрешимость проблемы эквивалентности двухленточных автоматов.

 

7. Моделирование схем программ, двухголовочные автоматы

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

Двухголовочный конечный автомат (ДКА) имеет одну ленту и две головки, которые могут независимо перемещаться вдоль ленты в одном направлении. Множество состояний Q разбито на два непересекающихся множества. В состояниях Q₁ активна первая головка, а в состояниях Q₂ - вторая.

Двухголовочный автомат можно рассматривать как такой двухленточный автомат, который работает с идентичными словами на обеих лентах.

Приведем пример ДКА, который проверяет равенство двух последовательно записанных слов в алфавите V = {0, 1}. Признаком окончания каждого из слов сделаем вспомогательный символ *, не входящий в V. Автомат должен допускать только слова вида а * а *, где а Î V^*. Мы возьмем A = (V È {*}, Q₁ È Q₂, R, q₀¹, #, I), где               Q₁ = {q₀¹, q₁¹, q₂¹, q₇¹} - множество состояний, в которых активна первая головка; Q₁ = {q₃², q₄², q₅², q₆²} - множество состояний, в которых активна вторая головка; R = { q₇¹} - множество, содержащее единственное заключительное состояние. Граф автомата показан на рисунке 1.7, на котором вместо многих «параллельных» дуг с разными

Рисунок 1.7.          пометками нарисована одна дуга со всеми этими пометками.

Находясь в состоянии g₀¹, автомат передвигает первую головку к началу второго слова и, обнаружив его, переходит в состояние q₁¹. Если конец ленты # встречается раньше символа *, автомат переходит в незаключительное состояние q₆². Если же автомат приходит к состоянию q₁¹, он считывает поочередно символы второго слова первой головкой (состояние q₁¹), а символы первого слова — второй головкой (состояния q₃² и q₅²), сравнивая эти символы. Автомат возвращается каждый раз в состояние q₁¹, если символы одинаковы. Если же обнаружится несовпадение символов или первая головка встречает конец слова раньше символа *, автомат уходит в состояние q₆². Попав в это состояние, автомат не может выйти из него; перемещая вторую головку к концу слова на ленте, он достигает #, находясь в незаключительном состоянии, так что слово на ленте отвергается. Если первая головка достигнет конца второго слова, а вторая головка обнаружит, что первое слово тоже просмотрено до конца, то автомат перейдет в заключительное состояние q₇¹. В противном случае автомат перейдет в состояние q₆², отвергая слово.

Этот пример легко обобщить на случай произвольного алфавита V, увеличивая количество состояний множества Q.

Проблемы пустоты и эквивалентности.

Будем говорить, что ДКА моделирует работу машины Тьюринга над некоторым начальным словом, если автомат допускает единственное слово — конечный протокол paботы машины над ним.

Лемма (Розенберг). Существует алгоритм, который для любой машины Тьюринга и для любого начального слова строит двухголовочный автомат, моделирующий ее работу над этим словом.

Теорема. Проблема пустоты ДКА не является частично разрешимой.

Теорема. Проблема эквивалентности ДКА не является частично разрешимой.

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

 

8. Моделирование схем программ, двоичный двухголовочный автомат

Cтандартные схемы могут моделировать (в уточненном ниже смысле) двухголовочные автоматы, что позволяет свести проблему пустоты этих автоматов к проблеме пустоты схем. Такое моделирование можно осуществить более простым способом, если использовать специальный класс двухголовочных автоматов, а именно класс двоичных автоматов, работающих со словами над алфавитом {0, 1}. Следующая лемма устанавливает связь между классом всех двухголовочных автоматов и подклассом двоичных автоматов специального вида.

 

 

 

Лемма. Существует алгоритм преобразования двухголовочных автоматов в двоичные двухголовочные автоматы (ДДКА), сохраняющий пустоту автоматов (построенный двоичный автомат А_b пуст тогда и только тогда, когда пуст исходный автомат А).

Доказательство. Пусть ДКА А над алфавитом V = {a₁, a₂, ...a_n} имеет множество состояний  Q_А={q₁^k, q₂^k, …, q_k^k}, где верхний индекс (k = 1, 2) определяет номер активной головки. Преобразование этого автомата в двоичный начнем с кодировки символов и слов из V* словами в алфавите {0, 1} по следующему правилу:

код (#) = 0;

код (a_i) = 11....10 (i = 1, …, n);

код (aa_i) = код (a) код (a_i).

Так как символ # кодируется нулем, то любому непустому слову на ленте автомата А соответствует двоичное слово на ленте автомата А_b, оканчивающееся двумя нулями. Автомат останавливается, прочитав два нуля подряд (или 0, означающий пустое слово).

Автомат A преобразуется в двоичный автомат A_b так, как показано на графах рисунка 1.8. Каждый фрагмент графа А (рисунок 1.8, а) заменяется фрагментом (рисунок 1.8, б) для А_b.

После замены добавляются фрагменты (рисунок 1.8 в, г).

Множество состояний автомата А_b включает:

а) все старые состояния из Q_А;

б) для каждого старого состояния  q_j^k  n новых состояний, n - число символов алфавита V;

в) два новых состояния r₁¹ и r₂¹.

Заключительными состояниями автомата А являются заключительные состояния автомата А_b.

Вершины S_a (останов допускающий) и S_r (останов отвергающий) носят на графе вспомогательный характер в графе А_b. Они отмечают тот факт, что автомат прочитал два нуля подряд и остановился в заключительном состоянии (случай S_a) или в незаключительном состоянии (случай S_r).

Легко убедиться, что автомат А_ь допускает двоичное слово р тогда и только тогда, когда оно является двоичным кодом слова из V*, допускаемого автоматом А. Таким образом, из пустоты автомата А следует пустота автомата А_ь, и наоборот.

На рисунке 1.9, а приведен граф ДКА  A допускающий только те слова в  алфавите V = {a, b, c}, в которых символ a встречается не меньшее число раз, чем символы b и c, вместе взятые. Заключительное состояние R={q₀¹}. На рисунке 1.9, б приведен граф ДДКА, построенный по автомату А (10 – код символа a, 110 – код b, 1110 – код c).

По заданному ДДКА возможно построить ССП и наоборот, что позволяет решить задачу разрешимости (не разрешимости) свойств ССП, так как эта задача для ДДКА решена.

 

9. Рекурсивные схемы

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

Множества переменных и предикатных символов ничем не отличаются от ССП. Множество специальных символов - другое, а именно: {if, то, else, (, ), ,}. Отличие множества функциональных символов состоит в том, что оно разбито на два непересекающиеся подмножества: множество базовых функциональных символов и множество определяемых функциональных символов (обозначаются для отличия прописными буквами, например, F⁽¹⁾,G⁽²⁾, и т.д.).

В базисе РС нет множества операторов, вместо него – множество логических выражений и множество термов.

Рекурсивной схемой называется пара (t, М), где t - терм, называемый главным термом схемы (или ее входом). М - такое множество рекурсивных уравнений, что все определяемые функциональные символы в левых частях уравнений различны и всякий определяемый символ, встречающийся в правой части некоторого уравнения или в главном терме схемы, входит в левую часть некоторого уравнения. Другими словами, в РС имеется определение всякой вызываемой в ней функции, причем ровно одно.

Примеры РС:

R_S1: F(x); F(x) = if  p(x) then  a  else  g(x, F(h(x))).

R_S2: A(b, c); A(x, y) = if  p(x) then  f(x)  else  B(x, y);

B(x, y) = if  p(y) then  A(g(x), a) else  C(x, y);

C(x, y) = A(g(x), A(x, g(y))).

R_S3: F(x); F(x) = if  p(x) then x  else  f(F(g(x)), F(h(x))).

Пара (R_S, I), где R_S - PC в базисе В, а I - интерпретация этого базиса, называется рекурсивной программой. При этом заметим, что определяемые функциональные символы не интерпретируются.

Протоколы выполнения программы (R_S1, I₁) и (R_S1, I₂), где I₁ и I₂ - интерпретации из п. 1.2.3 (рисунок 1.2, б, в), выглядят следующим образом:

№ п/п	Значение терма для (RS1, I1)	Значение термадля (RS1, I2)
1 2 3 4 5 6	F(4) 4*F(3) 4*(3*F(2)) 4*(3*(2*F(1))) 4*(3*(2*(1*F(0)))) 4*(3*(2*(1*1)))=24	F(a,b,c) CONSCAR(abc, F(b,c)) CONSCAR(abc, CONSCAR(bc, F(c))) CONSCAR(abc, CONSCAR(bc, CONSCAR(c, F(ε)))) CONSCAR(abc, CONSCAR(bc, CONSCAR(c, ε)))=abc