Булевы функции¹⁾ названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения. С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через двухэлементное множество . Тогда - это множество всех двоичных последовательностей (наборов, векторов) длины . Булевой функцией от переменных (аргументов) называется любая функция . Каждый из ее аргументов может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из также может быть 0 или 1. Обозначим через множество всех булевых функций от переменных. Нетрудно подсчитать их число: .

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

Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции имеет столбец. В первых столбцах указываются значения аргументов , а в -ом столбце значение функции на этих аргументах - .

Таблица 1.1. Табличное представление функции

.  .  .
.  .  .        .  .  .        .  .  .      .  .  .  .  .  .   .  .  .

Наборы аргументов в строках обычно располагаются в лексикографическом порядке: существует такое , что при , а . Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, ... , а последняя - .

При больших табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых оно достаточно наглядно.

Перечислим вначале все булевы функции от 1-ой переменной . Как мы знаем, их всего четыре.

1. - константа 0;
2. - константа 1;
3. - тождественная функция;
4. . Эта функция называется отрицанием и обозначается (используется также обозначение , а в языках программирования эта функция часто обозначается как ).

В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х переменных.

Таблица 1.2. Булевы функции от 2-х переменных

0  0 0  1 1  0 1  1	0 0 0 0	1 1 1 1	0 0 1 1	1 1 0 0	0 1 0 1	1 0 1 0	0 0 0 1	0 1 1 1	1 1 0 1	0 1 1 0	1 0 0 1	1 1 1 0

Многие из этих функций часто считаются "элементарными" и имеют собственные обозначения.

• - константа 0;
• - константа 1;
• - функция, равная 1-му аргументу;
• - отрицание ;
• - функция, равная 2-му аргументу;
• - отрицание ;
• - конъюнкция, читается " и " (используются также обозначения , , и AND ));
• - дизъюнкция, читается " или " (используются также обозначения , и OR ));
• - импликация, читается " влечет " или "из следует " (используются также обозначения , и ( IF THEN ));
• - сложение по модулю 2, читается " плюс " (используется также обозначение );
• - эквивалентность, читается " эквивалентно (равносильно) " (используется также обозначение );
• - штрих Шеффера (антиконъюнкция), иногда читается как "не и ".

В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

Отметим, что функции и фактически не зависят от значений обоих аргументов, функции и не зависят от значений аргумента , а функции и не зависят от значений аргумента .

Определение 1.1. Функция не зависит от аргумента , если для любого набора значений остальных аргументов имеет место равенство

Такой аргумент называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

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

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

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

Мы будем рассматривать формулы, построенные над множеством элементарных функций . Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.

Зафиксируем некоторое счетное множество переменных . Определим по индукции множество формул над с переменными из . Одновременно будем определять числовую характеристику формулы , называемую ее глубиной, и множество ее подформул.

Определение 1.2. а) Базис индукции. 0, 1 и каждая переменная является формулой глубины 0, т.е. . Множество ее подформул состоит из нее самой.

б) Шаг индукции. Пусть и - формулы, . Тогда выражения и являются формулами. При этом , а . Множество подформул включает саму формулу и для все подформулы формулы , а для все подформулы формул и .

Каждой формуле сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

Базис индукции. Пусть . Тогда или В первом случае задает функцию , во втором - функцию, тождественно равную константе .

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

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

Пример 1.1. Например, для формулы

Таблица 1.3. Функция

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0  0  0 1  0  0  0  0 1  0  0  1  1 0  1  0  1  1 0  1  1  1  0 1  0  1  1  0 1  0  1  1  1 0  1  1  1  1 0  1	1 1 0 1 1 0 0 1	0  0  0  0  1  0 1  1  0  0  1  0 0  0  0  0  0  1 1  1  0  0  0  1 0  1  1  1  1  0 1  0  1  1  1  0 0  0  1  0  0  1 1  1  1  0  0  1

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

Определение 1.3. Булевы формулы и называются эквивалентными, если соответствующие им функции и равны.

Обозначение: . Эквивалентные формулы называют также тождественно равными, а выражения вида логическими тождествами.

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

Пусть - это одна из функций . Для этих трех функций выполнены следующие две эквивалентности (законы ассоциативности и коммутативности).

(1) Ассоциативность:

Следующие две эквивалентности позволяют выразить импликацию и сложение по модулю 2 через дизъюнкцию, конъюкцию и отрицание.

(7)

(8)

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

Соглашения об упрощенной записи формул. Законы ассоциативности показывают, что значения формул, составленных из переменных и одних операций конъюнкции, не зависят от расстановки скобок. Поэтому вместо формул и мы будем для упрощения писать . Аналогично, будем использовать выражения и для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно. Будем также опускать внешние скобки в записи формулы, если ее внешней функцией является одна из функций .

Таким образом, с использованием этих соглашений формула может быть записана как .

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

Пусть - это множество пропозициональных переменных. Введем для каждого обозначения: и . Формула ( ), в которой и все переменные разные, т.е. при , называется элементарной конъюнкцией (элементарной дизъюнкцией).

Определение 1.4.Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид , где каждая формула - это элементарная конъюнкция. называется совершенной ДНФ, если в каждую из ее конъюнкций входят все переменных из . Аналогично, формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е. , где каждая формула - это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую входят все переменных из .

Рассмотрим произвольную булеву функцию , зависящую от переменных из . Oбозначим через множество наборов значений переменных, на которых принимает значение 1, а через множество наборов, на которых принимает значение 0, т.е. и . Определим по этим множествам две формулы:

Теорема 1.1.

(1) Если функция не равна тождественно 0, то формула - это совершенная ДНФ, задающая функцию .

(2) Если функция не равна тождественно 1, то формула - это совершенная КНФ, задающая функцию .

Пример 1.2. Например, для функции , представленной в таблице 1.1 совершенная ДНФ равна , а ее совершенная КНФ: .

Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере может быть задана более простой ДНФ: .

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

Граф (ориентированный) - это пара , где - конечное множество вершин (узлов, точек) графа, а - некоторое множество пар вершин, т.е. подмножество множества или бинарное отношение на . Элементы называют ребрами (дугами, стрелками, связями). Для ребра вершина называется началом , а вершина - концом , говорят, что ребро ведет из в .

В графе полустепень исхода вершины - это число исходящих из нее ребер, а полустепень захода - это число входящих в данную вершину ребер.

Заметим, что в графе может быть ребро вида , называемое петлей.

Пример 1.3. На рис. 1.1 приведен пример графа . Здесь , В графе ребро является петлей, полустепень исхода вершины равна 2, а полустепень захода для нее равна 1.

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

Определение 1.6.

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

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

Упорядоченный граф с полустепенью исхода вершин называется бинарным.

В качестве множества меток ребер часто выступают числа, задающие "веса", "длины", "стоимости" ребер. Графы с такой разметкой часто называют взвешенными.

Часто на одном множестве объектов определено несколько различных бинарных отношений. Для представления такой ситуации служат мультиграфы.

Определение 1.7. Мультиграф состоит из конечного множества вершин и мультимножества ребер , состоящего из пар вершин , в которое эти пары могут входить по нескольку раз.

Обычно несколько ребер, соединяющих одну и ту же пару вершин, различаются метками - именами соответствующих бинарных отношений. В лекциях 4-6 мультиграфы будут использоваться для представления диаграмм конечных автоматов.

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

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

Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин: и/или ребер: .

Многие приложения графов связаны с изучением путей между их вершинами.

Определение 1.9.

Путь в ( мульти ) графе - это последовательность ребер вида . Этот путь ведет из начальной вершины в конечную вершину и имеет длину . В этом случае будем говорить, что достижима из . Будем считать, что каждая вершина достижима сама из себя путем длины 0. Путь в графе (не мультиграфе!) можно также определять как соответствующую последовательность вершин: , где при .

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

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

Если в графе нет циклов, то он называется ациклическим.

Следующее утверждение непосредственно следует из определений.

Лемма 1.1.Если в графе имеется путь из вершины в вершину , то в нем имеется и простой путь из в .

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

Определение 1.10. Граф называется деревом, если

1. в нем есть одна вершина , в которую не входят ребра ; она называется корнем дерева ;
2. в каждую из остальных вершин входит ровно по одному ребру ;
3. все вершины достижимы из корня.

На рисунке 2 показан пример дерева

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

Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины , подграф дерева , включающий все достижимые из вершины и соединяющие их ребра из , образует поддерево дерева с корнем .. Высота вершины - это высота дерева . Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

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

Пример 1.4. В дереве на рис. 1.2 вершина является корнем, вершины - листья. Путь - одна из ветвей дерева . Вершина является отцом (родителем) вершин и , а каждая из этих вершин - ее сыном (ребенком). Между собой вершины и являются братьями (сестрами). Глубина равна 1, а высота - 2. Высота всего дерева равна 3.

Для деревьев часто удобно использовать следующее индуктивное определение.

Определение 1.11. Определим по индукции класс графов , называемых деревьями. Одновременно для каждого из них определим выделенную вершину - корень.

1. Граф , с единственной вершиной и пустым множеством ребер является деревом (входит в ). Вершина называется корнем этого дерева.
2. Пусть графы с корнями принадлежат , а - новая вершина, т.е. . Тогда классу принадлежит также следующий граф , где , . Корнем этого дерева является вершина .
3. Других графов в классе нет.

Рисунок 1.3 иллюстрирует это определение.

Определения ориентированных деревьев 1.10 и 1.11 эквивалентны.

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

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

Бинарное дерево называется полным, если у каждой его внутренней вершины имеется два сына и все его ветви имеют одинаковую длину.

В этой и следующей лекциях мы свяжем два основных предыдущих раздела нашего курса: булевы функции и графы. В курсе "Основы дискретной математики" мы рассматривали два основных представления булевых функций: табличное и с помощью формул общего вида или формул специального вида, в частности, дизъюнктивных или конъюнктивных нормальных форм и многочленов Жегалкина. К сожалению, эти способы не позволяют эффективно представлять функции от большого числа переменных: таблица для функции от n переменных всегда содержит 2ⁿ строк, многочлен Жегалкина может включать до 2ⁿ слагаемых (и для большинства функций по порядку столько и включает). Такие представления нельзя реализовать на практике уже для n порядка нескольких десятков. Могло показаться, что сокращенные ДНФ, которые мы научились эффективно строить с помощью метода Блейка, и минимальные ДНФ, которые можно получить, удаляя из сокращенных "лишние" конъюнкции (впрочем, хороший алгоритм для такого удаления неизвестен), дают существенно более экономные представления. булевых функций. Но в общем случае это не так. Для большинства булевых функций от n переменных минимальные ДНФ имеют экспоненциальный от n размер. В качестве примера конкретной простой функции с длинной ДНФ можно рассмотреть линейную функцию, определяющую нечетность суммы аргументов: odd(X₁,X₂,..., X_n)= X₁ +X₂ +... + X_n (см. задачу 3.1).

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

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

Чтобы не усложнять определение, зафиксируем конкретный базис и определим схемы в этом базисе.

Определение 2.1. Логической схемой ( схемой из функциональных элементов ) в базисе B₀ называется размеченный ориентированный граф без циклов S=(V,E), в котором

1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
2. в каждую из остальных вершин входит одно или два ребра; вершины, в которые входит одно ребро помечены функцией а вершины, в которые входят по два ребра, - одной из функций или Такие вершины называются функциональными элементами.

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

Определение 2.2. Глубина вершины в схеме S=(V,E) - это максимальная длина пути из входов S в v .

Глубиной D(S) схемы S назовем максимальную из глубин ее вершин.

Пусть входы схемы S помечены переменными x₁, ... , x_n. С каждой вершиной схемы S свяжем булеву функцию f_v(x₁,... , x_n), реализуемую в этой вершине. Определим f_v индукцией по глубине v.

Определение 2.3.

Базис: v имеет глубину 0. Тогда это входная вершина, которая помечена некоторой переменной x_i. Положим f_v(x₁,... , x_n) = x_i.

Шаг индукции. Пусть всем вершинам w глубины <= k уже сопоставлены функции f_w и пусть v - произвольная вершина глубины k+1. Тогда

• если v помечена и в нее входит ребро (w,v) , то положим

  

• если v помечена и в нее входят два ребра (w₁,v) и (w₂,v), то положим

  

• если v помечена и в нее входят два ребра (w₁,v) и (w₂,v), то положим

  

Нетрудно понять, что шаг индукции в этом определении корректен, так как, если в схеме S имеется ребро (w,v) и глубина вершины v равна k+1, то глубина вершины w не превосходит k и для нее f_w уже определена по индукционному предположению.

Определение 2.4. Схема S реализует набор булевых функций g₁, g₂, ... , g_m, если для каждого в схеме существует такая вершина v_i, что .

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

Определение 2.5. Сложность L(S) схемы S - это число функциональных элементов в S. Сложность L(f) булевой функции f(x₁, ..., x_n) - это наименьшая из сложностей схем, реализующих эту функцию.

Отношения между булевыми функциями и схемами естественно приводят к двум следующим основным проблемам.

Проблема анализа: по заданной схеме из функциональных элементов и выделенному подмножеству ее выходных вершин определить булевы функции, реализуемые в этих вершинах.

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

Пример 2.1. Рассмотрим схему S₁ с тремя входными переменными x, y и z, изображенную на рис. 2.1 и решим для нее проблему анализа.

В соответствии с данным выше определением вершины схемы S₁ реализуют следующие функции:

, , , , и, наконец, .

Глубина этой схемы D(S₁)= 4, а ее сложность L(S₁)=6. В то же время формула для результирующей функции f_f содержит 7 функциональных знаков. За счет чего достигнута экономия? За счет того, что функция в схеме S₁ вычисляется один раз в вершине a, а в формуле приходится вычислять ее дважды.

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

Указанное выше свойство характерно и для программ, в которых один раз вычисленное значение выражения можно использовать неоднократно. Рассмотрим один из простейших классов программ - линейные или неветвящиеся программы. Такие программы представляют последовательности присваиваний вида:

где X, X₁, ... , X_k - переменные, F - имя k -местной базисной функции.

В случае нашего базиса линейная программа состоит из присваиваний вида: , и .

Линейная программа P с выделенными входными переменными X₁, ... , X_n порождает для каждого набора значений входных переменных естественный процесс вычисления: вначале переменным X₁, ... , X_n присваиваются значения , соответственно, а каждой из остальных переменных присваивается значение 0. Затем последовательно выполняются присваивания программы P, в результате чего каждая из переменных Z программы получит заключительное значение .

Определение 2.6. Скажем, что программа P со входными переменными X₁, ... , X_n вычисляет в выходной переменной Z функцию F(X₁, ..., X_n), если для любого набора значений входов после завершения работы .

Между схемами и линейными программами имеется тесная связь.

Теорема 2.1.

1. По каждой логической схеме S со входами x₁, ... , x_n и функциональными элементами v₁, ..., v_m можно эффективно построить линейную программу P_S со входными переменными x₁, ... , x_n и рабочими переменными v₁, ..., v_m, которая в любой переменной v_i, i=1,...,m, вычисляет функцию .
2. По каждой линейной программе P со входными переменными X₁, ... , X_n, вычисляющей в выходной переменной Z некоторую функцию F(X₁, ..., X_n) можно эффективно построить логическую схему S_P со входами X₁, ... , X_n, в которой имеется вершина v такая, что f_v((X₁, ..., X_n) = F(X₁, ..., X_n).

Доказательство. (1) Пусть S - схема со входами x₁, ... , x_n и функциональными элементами v₁, ..., v_m. Построим по ней линейную программу P_S со входными переменными x₁, ... , x_n следующим образом. Упорядочим все входные и функциональные вершины S по глубине (вершины одной глубины в любом порядке): u₁, ..., u_n+m. Программа P_S будет последовательностью m присваиваний.

• Пусть вершина u_n+i помечена и в нее входит
• ребро из u_j. Тогда в качестве i -ой команды поместим в P_S присваивание .
• Пусть вершина u_n+i помечена и в нее входят ребра из u_j и u_k. Тогда в качестве i -ой команды поместим в P_S присваивание .

Упорядочение вершин по глубине гарантирует, что j <n+ i и k <n+ i. Поэтому при вычислении u_{n+i} значения аргументов уже получены и индукцией по глубине легко показать, что для каждого i=1,...,m программа P_S вычисляет в переменной v_i функцию .

Доказательство пункта (2) проведите самостоятельно (см. задачу 2.1).

Пример 2.1. Применим конструкцию теоремы к схеме S₁, представленной на рис.2.1. Ее вершины можно упорядочить по глубине так: x, y, z, a, b, c, d, e, f. Порождая команды по описанным выше правилам, получим следующую линейную программу P_{S₁}:

Замечание. Число команд в линейной программе P_S, т.е. время ее выполнения, совпадает со сложностью L(S) схемы S. Глубина схемы D(S) также имеет смысл с точки зрения времени вычисления. Именно, D(S) - это время выполнения P_S на многопроцессорной системе. Действительно, все команды, соответствующие вершинам одинаковой глубины, можно выполнять параллельно на разных процессорах, так как результаты любой из них не используются в качестве аргументов другой.

Рассмотрим схему S₊ на рис. 2.2.

В соответствии с определением вершины этой схемы реализуют следующие функции:

, , , .

Таким образом, схема S₊ реализует (в вершине d ) функцию + сложения по модулю 2.

Из приведенного выше примера следует, что L(S₊)=4 и L(+) <= 4.

Используя схему S₊, нетрудно построить схему S_odd для реализации линейной функции-суммы n аргументов по модулю 2 odd(X₁,X₂,..., X_n)= X₁ +X₂ +... + X_n (см. рис. 2.3).

На этой схеме прямоугольники S₊⁽¹⁾, S₊⁽²⁾, ... ,S₊⁽ⁿ⁾ содержат копии схемы S₊. При этом входами S₊⁽¹⁾ являются переменные x₁ и x₂, а входами S₊⁽ⁱ⁺¹⁾ являются выход схемы S₊⁽ⁱ⁾ и переменная x_i+1. По индукции легко показать, что вершина d в S₊⁽ⁱ⁾ реализует функцию (x₁ + x₂ + ... + x_i+1). Таким образом, нами установлена

Теорема 2.2. Существует схема S_odd, реализующая функцию odd(X₁,X₂,..., X_n)= X₁ +X₂ +... + X_n со сложностью L(S_odd)= 4 (n-1).

Сумматором порядка n называют схему, вычисляющую результат сложения двух n -разрядных двоичных чисел и . Пусть ( здесь - соответствующие двоичные разряды этих чисел).

Сумматор должен вычислять набор из (n+1) -ой результирующей функции:

задающих соответствующие разряды суммы c.

Обозначим через p_i бит переноса из (i-1) -го разряда в i -ый. Тогда нетрудно видеть, что при i =0

c₀ = a₀ + b₀ и ,

а при 1 <= i <= n-1

c_i= p_i + a_i + b_i и .

Старший разряд c совпадает с последним переносом: c_n=p_n.

Рассмотрим теперь построенную выше схему S₊ как схему, вычисляющую набор из двух функций: (в вершине a ) и x+y (в вершине d ). Используя два экземпляра этой схемы S₊⁽¹⁾ и S₊⁽²⁾, можно легко реализовать схему одноразрядного сумматора SUM₁ (см. рис. 2.4) , которая имеет три входа a_i, b_ i и p_i ( 1 <= i <= n-1 ) и вычисляет c_i и p_i+1.

Действительно, из построения следует, что в вершине p этой схемы вычисляется функция . Из представленной схемы видно, что сложность одноразрядного сумматора L(SUM₁)= 9.

Теперь из S₊ и одноразрядных сумматоров SUM₁ соберем схему SUM_n для n -разрядного сумматора.

Таким образом мы установили следующее утверждение.

Теорема 2.3.

Для каждого n >= 1 cуществует схема SUM, реализующая операцию суммирования двух n -разрядных двоичных чисел и имеющая сложность L(SUM_n)= 9n -5.

Замечание Логические схемы интенсивно исследовались 50-х-70-х годах прошлого столетия. В частности, К. Шеннон и О.Б. Лупанов установили оценки сложности схем для булевых функций от n аргументов. Оказалось, что любую такую функцию можно реализовать со сложностью не большей (по порядку) 2ⁿ/n и что "почти все" они имеют не меньшую сложность. При этом до сих пор не известна ни одна последовательность "конкретных" функций f_n, сложность которых по порядку превосходила бы линейную функцию.

Задача 2.1. Докажите пункт (2) теоремы 2.1.

Задача 2.2. Докажите, что минимальная схема для сложения имеет сложность L(+) = 4.

Задача 2.3. Используя схему SUM_n, постройте схему, реализующую операцию вычитания двух n -разрядных двоичных чисел: d =a - b (при условии, что a >= b ). Оцените сложность полученной схемы.

Задача 2.4. Определите глубину схем S₊, S_odd, SUM₁ и SUM_n.

Задача 2.5. Два игрока независимо выбирают одно из четырех чисел от 0 до 3. Первый игрок выигрывает, если выбранные числа совпадают. Постройте схему, определяющую выигрыш 1-го игрока. Ее входы x₁,x₂ представляют число, выбранное 1-ым игроком, а y₁,y₂ - число, выбранное 2-ым игроком. Реализуемая функция F(x₁,x₂,y₁,y₂) равна 1 тогда и только тогда, когда x₁=y₁ и x₂ =y₂.

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

Задача 2.7. Пусть наборы аргументов булевой функции от трех аргументов упорядочены лексикографически, а ее значения задаются последовательностью 8 нулей и единиц. Постройте схемы, реализующие следующие функции.

• f₁=(1111 1011),
• f₂=(1001 1001),
• f₃ =(0011 1001).

Рассматриваемый в этой лекции способ представления булевых функций с помощью специального подкласса ориентированных графов без циклов был предложен Р. Бриантом (R. Bryant) в 1986г. Его английское название - "Ordered binary decision diagram", сокращенно - OBDD. Сейчас УБДР являются одним из основных средств реализации булевых функций от большого числа переменных в задачах искусственного интеллекта, проверки правильности электронных схем, программ, протоколов и т.п.

Одним из предшественников УБДР являются бинарные деревья решений.

Определение 3.1. Бинарное дерево решений (БДР) - это бинарное дерево T=(V,E), все внутренние вершины которого помечены переменными, а листья - значениями 0 или 1. Из каждой внутренней вершины v выходят 2 ребра, одно помечено 0, другое - 1; вершина w₀, в которую ведет ребро, помеченное 0, называется 0-сыном v, а вершина w₁, в которую ведет ребро, помеченное 1, называется 1-сыном v.

Такое дерево, вершины которого помечены переменными x₁, ..., x_n реализует булеву функцию f(x₁, ..., x_n), если для каждого набора значений переменных ветвь в дереве, соответствующая этому набору (из вершины x_i идем по ребру, помеченному ), завершается листом с меткой .

Пример 3.1. Например, рассмотрим изображенное ниже БДР T₁ (на всех рисунках предполагается, что ребра направлены сверху вниз).

По определению T₁ реализует функцию f₁(x,y,z), представленную в таблице 3.1.

Нетрудно построить ДНФ этой функции: .

УБДР являются модификацией БДР, в которой все листья с одной меткой представлены одной вершиной, в каждую вершину может входить несколько ребер, возможен выбор порядка появления переменных на ветвях.

Определение 3.2. Пусть зафиксирован некоторый порядок n переменных .

Упорядоченная бинарная диаграмма решений относительно порядка переменных - это ориентированный граф без циклов с одним корнем, в котором

1. существует лишь две вершины, из которых не выходят ребра; они помечены константами 0 и 1 и называются стоками ;
2. остальные ( внутренние ) вершины помечены переменными и из каждой из них выходят два ребра, одно помечено 0, другое - 1;
3. порядок, в котором переменные встречаются на любом пути из корня в сток, совместим с т.е. если из вершины, помеченной , есть путь в вершину, помеченную , то i < j.

Как и в случае БДР, УБДР реализует булеву функцию f(x₁, ..., x_n), если для каждого набора значений переменных путь в диаграмме, начинающийся в корне и соответствующий этому набору (из вершины x_i идем по ребру, помеченному ), завершается стоком с меткой .

Из этого определения непосредственно следует, что каждая внутренняя вершина диаграммы v, помеченная переменной , является корнем поддиаграммы, которая включает все вершины диаграммы, достижимые из v, и реализует некоторую функцию от (n -k +1) переменных . При этом ее 0-сын w₀ является корнем поддиаграммы, реализующей функцию , а 1-сын w₁ - корень поддиаграммы, реализующей функцию . Пусть диаграмма реализует функцию и - это набор значений переменных , который соответствует пути из корня в вершину v (таких наборов может быть несколько). Тогда .

Пример 3.2. Реализуем с помощью УБДР функцию f₁(x,y,z), представленную выше в примере 3.1, с помощью БДР T₁ и таблицы 3.1.

Вначале зафиксируем порядок переменных: x < y < z. Объединив листья с одинаковыми метками и две z - вершины с одинаковыми потомками, получим УБДР D₁, приведенную на рис.3.2.

Ясно, что реализация функции f₁(x,y,z) с помощью УБДР D₁ намного компактнее, чем с помощью БДР T₁.

Под сложностью L(D) УБДР D будем понимать число внутренних вершин в D. Например, L(D₁)=4. Может ли сложность диаграммы для некоторой функции зависеть от порядка переменных? Да! Рассмотрим порядок переменных y < x < z. Как показывает следующий рисунок, относительно этого порядка функцию f(x,y,z) можно реализовать УБДР D₂ со сложностью L(D₂)=3.

Когда порядок переменных зафиксирован, то достаточно просто можно по произвольной УБДР для функции построить минимальную УБДР, реализующую данную функцию.

Определение 3.3. УБДР называется сокращенной, если

1. из любой внутренней вершины v ее 0-сын и 1-сын не совпадают;
2. нет такой пары внутренних вершин u и v, для которых поддиаграммы с корнями u и v являются изоморфными (т.е. взаимно однозначно отображаются друг на друга с сохранением всех меток).

Смысл этого определения понятен: если из некоторой вершины v оба ребра ведут в одну вершину, то такая вершина v не нужна, а если имеются две вершины с одинаковыми поддиаграммами, то их можно слить. Определим два типа эквивалентных преобразований УБДР.

Правило сокращения: если 0-сын и 1-сын вершины v совпадают и равны w, то удалить v, перенаправив все входящие в нее ребра в вершину w .

Правило слияния: если вершины v и w помечены одной переменной и имеют одинаковых 0-сыновей и 1-сыновей, то удалить вершину v, перенаправив все входящие в нее ребра в вершину w .

На следующем рисунке показаны преобразования по этим правилам.

Следующая простая теорема показывает, что применимость этих двух правил является критерием несокращаемости УБДР.

Теорема 3.1. УБДР D является сокращенной тогда и только тогда, когда к ней не применимо ни правило слияния, ни правило сокращения.

Доказательство. Если к D применимо правило сокращения, то не выполнено условие (1) из определения сокращенной УБДР, а если к D применимо правило слияния, то поддиаграммы с корнями v и w являются изоморфными и не выполнено условие (2).

Пусть к УБДР D нельзя применить правило сокращения. Тогда в ней нет вершин с совпадающими 0- и 1-сыновьями и выполнено условие (1). Пусть к УБДР D нельзя применить правило слияния. Тогда из следующей леммы можно заключить, что в D нет пары вершин, поддиаграммы которых являются изоморфными, и следовательно, выполнено условие (2).

Лемма 3.2. Если в D есть такая пара вершин u и v, для которых поддиаграммы с корнями v и w являются изоморфными, то в D имеется и пара вершин v', w' с попарно одинаковыми 0- и 1-сыновьями и, следовательно, к D применимо правило слияния.

Доказательство леммы проведем индукцией по высоте h поддиаграмм D_v и D_w с корнями v и w, соответственно (так как D_v и D_w изоморфны, то их высоты, т.е. длины максимальных путей из корней до стоков, одинаковы).

Базис: h=1. В этом случае 0- и 1-сыновьями вершин v и w являются одинаковые стоки.

Шаг индукции. Предположим, что утверждение верно для h=k. Пусть D_v и D_w - поддиаграммы высоты h=k+1. Пусть v₀ и w₀ - это 0-сыновья вершин v и w, соответственно, а v₁ и w₁ - их 1-сыновья. Если v₀=w₀ и v₁=w₁, то в качестве v', w' подходят сами v и w. Если же для некоторого , то поддиаграммы и с корнями v_i и w_i являются изоморфными и имеют высоту k. Тогда по предположению индукции утверждение леммы выполнено.

Из теоремы 3.1 непосредственно следует, что, применяя к произвольной УБДР правила сокращения и слияния, мы, в конце концов, получим сокращенную УБДР. Чтобы эта процедура работала эффективо, нужно применять правила в порядке "снизу-вверх". Мы опишем этот алгоритм для "естественного" порядка переменных: x₁, ... , x_n.

Алгоритм СОКРАЩЕНИЕ-УБДР

Вход: УБДР D для функции f(x₁, ... , x_n).

Выход: сокращенная УБДР для .

1.    Занумеруем  множество вершин D: V = {v1, v2, ..., vm}; 
2.    ДЛЯ i = n, n-1, ..., 1   ВЫПОЛНЯТЬ 
3.      {
4.          V(i) = { v | v помечена переменной xi };
/* Применение правила сокращения:
5.         ДЛЯ КАЖДОЙ v из V(i) ВЫПОЛНЯТЬ
6.            ЕСЛИ (0-сын v) = (1-сын v) = w ТО}
7.             {   удалить v из V(i);
8.                перенаправить все ребра, входящие в v, в вершину  w;
9.                 удалить v из D }
10.         ИНАЧЕ key(v) = (j, k), где vj - это 0-сын v, а vk - 1-сын  v;
/* Применение правила слияния:
11.          Отсортировать V(i) по ключу key(v): 
               пусть в этом порядке V(i)={ u1, ..., uki};
12.          тек_ключ=(0, 0);
13.           ДЛЯ j = 1, ..., ki   ВЫПОЛНЯТЬ 
14.            ЕСЛИ тек_ключ=key(uj) ТО
15.            {   удалить uj из V(i);
16.               перенаправить все ребра, входящие в uj, в тек_вершина;
17.             удалить uj из D }
18.           ИНАЧЕ} {тек_вершина= uj; тек_ключ=key(uj)}
19.      }

Пример 3.1. Рассмотрим пример применения алгоритма СОКРАЩЕНИЕ-УБДР, показанный на следующем рисунке.

На исходной УБДР слева все вершины уже занумерованы. Стрелки разделяют УБДР, получаемые после очередных итераций основного цикла в строках 2 - 19. При первом исполнении цикла i=3, V(3) = {v₃}. Для вершины v₃ условие в строке 6 выполнено ( w= v₆ ), поэтому применяется правило сокращения и эта вершина удаляется, а ее входы направляются в v₆. При следующем исполнении цикла i=2, V(2) = {v₂, v₄}. После цикла в строках 5 - 10 key(v₂)= {5, 6} и key(v₄)= {5, 6}. После сортировки u₁=v₂, u₂ = v₄. В цикле в строках 13-18 для u₂ выполнено условие в строке 14. Поэтому применяется правило слияния и вершина v₄ удаляется, а ее вход передаeтся вершине v₂. При третьем исполнении цикла i=1, V(1) = {v₁}. Для вершины v₁ условие в строке 6 выполнено ( w= v₂ ), поэтому применяется правило сокращения и эта вершина удаляется.

Оказывается, что построенная алгоритмом УБДР является единственной и минимальной для заданного порядка.

Теорема 3.2.

1. Алгоритм СОКРАЩЕНИЕ-УБДР строит сокращенную УБДР, эквивалентную исходной УБДР D.
2. Эта сокращенная УБДР является при данном порядке переменных единственной (с точностью до изоморфизма) и минимальной.

Доказательство первого пункта непосредственно следует из выполнения критерия теоремы 3.1, так как к результирующей диаграмме никакое правило сокращения или слияния неприменимо.

Доказательство второго пункта основано на следующем индуктивном утверждении:

Лемма 3.1. После выполнения i -ой итерации алгоритма в полученной диаграмме для каждой подфункции при k=1,2,..., i-1 ), существенно зависящей от x_i, имеется ровно одна вершина - корень поддиаграммы, реализующей эту подфункцию.

Напомним, что функция f(x₁, x₂, ..., x_i, ..., x_n) существенно зависит от переменной x_i, если существуют такие два набора значений аргументов и , различающиеся только значением x_i, на которых f принимает разные значения: , ,

Доказательство этой леммы и вывод из нее утверждения 2 теоремы 3.2 оставляем в качестве задач 3.2 и 3.3.

Алгоритм СОКРАЩЕНИЕ-УБДР позволяет построить сокращенную УБДР для функции f, по любой другой ее УБДР. Но как построить УБДР, если f задана, например, с помощью формулы? Можно, конечно, попытаться построить полное бинарное дерево решений, объединить в нем все листья с меткой 0 в один сток, а листья с меткой 1 - в другой. Затем применить к получившейся УБДР алгоритм СОКРАЩЕНИЕ-УБДР. Но этот подход годится только для функций от небольшого числа переменных, так как полное БДР для f(x₁, ..., x_n) будет содержать 2ⁿ листьев.

Другой подход связан с построением УБДР "сверху-вниз". Объясним его для естественного порядка переменных: x₁< x₂ < ... < x_n.

Начнем построение с корня, помеченного x₁. Рассмотрим две остаточные функции: f₀(x₁, ..., x_n)=f(0, x₂, ..., x_n) и f₁(x₂, ..., x_n)=f(1, x₂, ..., x_n). Если они одинаковы, то f не зависит от x₁ и тогда изменим метку у корня на x₂. Если обе функции f₀ и f₁ существенно зависят от x₂, то для каждой из них добавляем вершину, помеченную x₂, и далее реализуем по индукции. Если не зависит от переменных x₂,... , x_j, но зависит существенно от x_j+1, то добавляем вершину, помеченную x_j+1, и проводим в нее ребро с меткой k из вершины, соответствующей f . Пусть для некоторого i уже построены вершины для всех различных остаточных функций вида , существенно зависящих от x_i. Для каждой из них получим две остаточные функции и . Затем выберем из множества этих функций разные, для каждой из них добавим в диаграмму вершину, помеченную x_i+1, и проведем в них соответствующие ребра из вершин, помеченных x_{i}. Продолжая построение, дойдем до функций от 1-ой переменной x_n и до констант, для которых минимальные реализации очевидны.

Пример 3.2. Рассмотрим, например, функцию f(x₁, x₂, x₃, x₄), заданную формулой , и построим для нее УБДР относительно порядка x₁ < x₂ < x₃ <x₄, используя описанную выше процедуру.

Вначале создадим корень, помеченный x₁, и рассмотрим остаточные функции, получающиеся при x₁=0 и x₁ =1. Имеем

Они разные и обе существенно зависят от x₂. Поэтому добавим для каждой из них вершину, помеченную x₂. Затем для каждой из них определим остаточные функции, получающиеся при x₂=0 и x₂ =1. Получим

Так как f₀₀=f₁₀, а f₀₁ и f₁₁ от x₃ не зависят, то нам потребуется только одна вершина, помеченая x₃. Она будет представлять функцию . При x₃=0 она превращается в x₄, а при x₃=1 равна константе 1. В результате получается УБДР D_f, показанная на рис.3.6.

Задача 3.1. Докажите, что совершенная, сокращенная и минимальная ДНФ функции odd(X₁,X₂,..., X_n) совпадают и состоят из 2_n-1 элементарных конъюнкций длины n.

Задача 3.2. Докажите лемму 3.2 возвратной индукцией по i.

Задача 3.3. Используя лемму 3.2, докажите утверждение 2 теоремы 3.2.

Задача 3.4. Постройте минимальные УБДР для двуместных функций: .

Задача 3.5. Постройте минимальные УБДР для функции

относительно двух упорядочений переменных:

• x₁ < x₂ < x₃ < x₄ < x₅ < x₆ и
• x₁ < x₃ < x₅ < x₂ < x₄ < x₆.

Задача 3.6. Пороговая функция T_n^k от n переменных с порогом k выдает 1, если во входном наборе имеется не менее k единиц: .

• Постройте минимальные УБДР для пороговых функций T₃², T₄², T₅³.
• Зависит ли сложность минимальной УБДР для пороговых функций от порядка переменных?
• Оцените сложность минимальной УБДР для пороговой функции T_n^k.

Задача 3.7. Выберите подходящий порядок переменных и постройте для него минимальные УБДР, реализующие функции из задач 12.5 и 12.6.

Задача 3.8. Как мы видели, логические схемы естественным образом реализуются в виде неветвящихся программ. Наоборот, для деревьев решений и УБДР естественным программным представлением являются ветвящиеся программы, включающие лишь условные операторы вида if ... then ... else ... с тестами вида "x = 0?" и "x = 1?" (они соответствуют внутренним вершинам диаграмм) и операторы присвоения значения 0 или 1 результату (они соответствуют вершинам- стокам ).

Напишите ветвящиеся программы, вычисляющие функции, представляемые УБДР D₂ на рис. 3.3 и D_f на рис.3.6.

Конечные автоматы являются математической моделью устройств, перерабатывающих дискретную входную информацию в режиме "реального времени", т.е. в темпе ее поступления.

На такие устройства в последовательные дискретные моменты времени 1,2, ..., t, t+1,... поступают входные сигналы x(1),x(2), ..., x(t),x(t+1),... и в ответ на них автомат A вырабатывает выходные сигналы y(1) y(2), ..., y(t), y(t+1),.... Конечные автоматы характеризуются двумя особенностями.

1. Отсутствие предвосхищения: выходной сигнал y(t), выдаваемый автоматом в момент t, зависит лишь от полученных к этому времени входов x(1),x(2), ..., x(t), т.е. автомат не может предвосхитить будущие входы и заранее на них отреагировать. Таким образом, имеется некоторая функция выходов , определяющая очередной выход по предшествующему входу.
2. Конечная память: в каждый момент t информация в автомате о полученном к этому моменту входе x(1),x(2), ..., x(t) конечна. Это свойство удобно интерпретировать следующим образом: автомат имеет конечное множество состояний Q и в каждый момент находится в одном из этих состояний. При получении очередного входа состояние может измениться. Таким образом, состояние , в котором находится автомат после получения входной последовательности x(1),x(2), ..., x(t), и представляет информацию об этой последовательности, используемую в дальнейшей работе автомата при определении следующего состояния и выхода.

Наше обсуждение приводит к следующему определению конечного автомата с выходом.

Определение 4.1. Конечный автомат - преобразователь - это система вида

включающая следующие компоненты:

• - конечное множество - входной алфавит ;
• - конечное множество - выходной алфавит ;
• Q={q₀, ... , q_n-1} (n >= 1) - конечное множество - алфавит внутренних состояний;
• - начальное состояние автомата;
• - функция переходов, - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a ;
• - функция выходов, - это символ из , который выдает на выход автомат в состоянии q, когда получает на вход символ a.

Иногда пару функций называют программой автомата A и задают как список из m n команд вида .

Другой удобный способ задания функций и - табличный. Каждая из них определяется таблицей (матрицей) размера n x m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита . В первой из них на пересечении строки q_i и столбца a_j стоит состояние , а во второй - выходной символ .

Еще один способ представления конечного автомата основан на использовании ориентированных размеченных графов.

Определение 4.2. Диаграмма автомата - это ориентированный (мульти) граф D_A=(Q, E) с помеченными ребрами, в котором выделена вершина- начальное состояние q₀ и из каждой вершины выходит ребер, помеченных парами символов . Таким образом, для каждой и каждого символа имеется единственное ребро с меткой из q в вершину .

Как автомат A перерабатывает входное слово x₁x₂ ... x_t? Он начинает работу в состоянии q(0)=q₀. Затем, получив (прочитав) входной символ x₁, переходит в состояние и выдает символ . Далее, получив x₂ A переходит в состояние и выдает символ и т.д. Таким образом, работа автомата, характеризуется последовательностью проходимых им состояний q(0), q(1), ... , q(t), ... и последовательностью выходных символов y(1), ... , y(t), .... Они определяются следующими реккурентными соотношениями:

Рассмотрим несколько примеров автоматов-преобразователей.

Пример 4.1. Сумматор последовательного действия

Мы уже строили схему из функциональных элементов SUM_n, реализующую для фиксированного n суммирование двух n -разрядных двоичных чисел. Построим теперь конечный автомат SUM, который сможет складывать два двоичных числа произвольной разрядности. На вход этого автомата будут последовательно подаваться пары x(i)= (x₁(i),x₂(i)) соответствующих i -ых (1<= i <= r) разрядов двух двоичных чисел x₁=x₁(r) ... x₁(2) x₁(1) и x₂=x₂(r) ... x₂(2) x₂(1), а признаком завершения чисел будет служить символ x(r+1)= * (если одно из слагаемых короче другого, то будем считать, что недостающие разряды - нули). Выходом автомата должна быть последовательность (r+1) двоичных разрядов суммы y = x₁ + x₂:

Таким образом, входной алфавит автомата: , а выходной алфавит: . Что нужно знать автомату SUM о первых i разрядах x₁ и x₂, чтобы получив их (i+1) -ые разряды (x₁(i+1),x₂(i+1)), верно определить выход y(i+1)? Ясно, что для этого достаточно знать, был ли перенос в i -ый разряд. Поэтому можно зафиксировать множество состояний Q = {q₀, q₁}, в котором q₀ означает, что переноса не было, а q₁ - что перенос был. Теперь легко построить таблицы, представляющие функции переходов и выходов автомата SUM.

:		(00)	(01)	(10)	(11)	*
	q0	q0	q0	q0	q1	q0
	q1	q0	q1	q1	q1	q0
:		(00)	(01)	(10)	(11)	*
	q0	0	1	1	0	0
	q1	1	0	0	1	1

Заметим, что после получения символа * автомат SUM переходит в начальное состояние q₀ и готов выполнять сложение следующей пары чисел.

На диаграмме автомата у вершины q₀ четыре петли, а у вершины q₁ - три, объединены в одну с четырьмя и тремя метками, соответственно. Точно так же слиты два ребра из q₁ в q₀. Стрелкой указано начальное состояние.

Пусть - это алфавит, который состоит из конечного множества элементов, называемых символами (буквами).

Слово в алфавите - это конечная последовательность символов этого алфавита: при i=1, ..., n . Число букв в этой последовательности называется длиной слова и обозначается |w|. Имеется одно специальное "пустое" слово длины 0. Будем обозначать его через На словах определена операция приписывания одного слова после другого, называемая конкатенацией: если слово w =w₁... w_n, а слово v =v₁... v_m, то их конкатенация - это слово w₁... w_nv₁... v_m длины n+m. Обычно знак конкатенации будем опускать и писать просто w v (по аналогии со знаком умножения в алгебре). Пустое слово - это единственное слово такое, что для любого слова w справедливо равенство . Операция конкатенации ассоциативна: для любых трех слов w, v и u, очевидно, имеет место равенство: (w v)u = w(v u). Поэтому скобки при записи конкатенации нескольких слов будем опускать. Для представления нескольких конкатенаций одного и того же слова используют сокращенную "степенную форму" записи: . Например, a³b⁴c² - это сокращенная запись слова aaabbbbcc.

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

Конечные автоматы часто используются для определения тех или иных свойств слов, т.е. для распознавания языков: автомат, распознающий некоторый язык L должен по произвольному слову w ответить на вопрос " ? ". Для решения такой задачи функция выходов может быть заменена на проверку того, в какое состояние переходит автомат после получения входного слова w - "принимающее" или "отвергающее".

Определение 4.3. Детерминированный конечный автомат (ДКА) - распознаватель - это система вида

включающая следующие компоненты:

• - конечное множество - входной алфавит ;
• Q={q₀, ... , q_n-1} (n >= 1) - конечное множество - алфавит внутренних состояний;
• - начальное состояние автомата;
• - множество принимающих (допускающих, заключительных) состояний ;
• - функция переходов,
• - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a.

Функцию называют программой автомата A и задают как список из m n команд вида .

Удобно также задавать функцию с помощью описанной выше таблицы размера n x m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита и в которой на пересечении строки q_i и столбца a_j стоит состояние .

Как и автоматы-преобразователи, автоматы-распознаватели можно представлять с помощью размеченных ориентированных графов, называемых диаграммами.

Определение 4.4. Диаграмма ДКА - это ориентированный (мульти)граф D_A=(Q, E) с помеченными ребрами, в котором выделена вершина- начальное состояние q₀ из каждой вершины выходит ребер, помеченных символами так, что для каждой и каждого символа имеется единственное ребро из q в вершину с меткой a .

Скажем, что представленный последовательностью ребер путь p=e₁e₂ ... e_t в диаграмме несет слово w=w₁w₂ ... w_t, если w_i - это метка ребра e_i (1 >= i >= t). Если q - начальная вершина (состояние) этого пути, а q' - его заключительная вершина, то будем говорить, что слово w переводит q в q'.

Работа конечного автомата-распознавателя состоит в чтении входного слова и изменению состояний в зависимости от его символов.

Определение 4.5. Назовем конфигурацией ДКА произвольную пару вида (q, w), в которой и .

На множестве конфигураций введем отношение перехода за один шаг :

Если , то положим для каждого : .

Через обозначим рефлексивное и транзитивное замыкание .

Содержательно, означает, что автомат A, начав работу в состоянии q на слове w=w₁ ... w_l, через некоторое конечное число шагов 0 <= k <= l прочтет первые k символов слова w и перейдет в состояние q', а w' =w_k+1 ... w_l - это непрочтенный остаток слова w.

Определение 4.6. ДКА A распознает (допускает, принимает) слово w, если для некоторого

т.е. после обработки слова w автомат переходит в принимающее состояние.

Язык L_A, распознаваемый (допускаемый, принимаемый) автоматом A, состоит из всех слов, распознаваемых этим автоматом:

Язык называется конечно автоматным, если он распознается некоторым ДКА.

Из этого определения, в частности, следует, что . Один и тот же язык может распознаваться разными автоматами.

Определение 4.7. Автоматы A и B называются эквивалентными, если совпадают распознаваемые ими языки, т.е. L_A = L_B .

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

Лемма 4.3. Автомат A распознает (допускает, принимает) слово w, если для некоторого в диаграмме D_A имеется путь из q₀ в q, который несет слово w, т.е. w переводит q₀ в заключительное состояние q.

Доказательство можно провести индукцией по длине слова w (см. задачу 4.3).

Tаким образом, язык L_A, распознаваемый автоматом A, состоит из всех слов, которые переводят в его диаграмме D_A начальное состояние q₀ в заключительные состояния из F.

Наша цель теперь состоит в изучении класса конечно автоматных языков.

Во многих случаях удается доказать, что язык L конечно автоматный, непосредственно построив распознающий его автомат. Для этого нужно постараться разбить множество всех входных слов на конечное число классов "однородных", "эквивалентных" слов, т.е. слов, получение которых на входе одинаково влияет на возможность их продолжения до слов распознавемого языка. Затем для каждого такого класса создать состояние автомата и определить переходы между этими состояниями. Часто полезно бывает выделить одно состояние для представления "ошибочных" слов, для которых ни они сами, ни любые их продолжения не входят в язык.

Пример 4.4. Рассмотрим язык L, состоящий из всех слов в алфавите , которые начинаются на aa и содержат нечетное число символов b.

Для выделения слов, начинающихся на aa, создадим начальное состояние q₀, которое первый символ a будет переводить в состояние q₁, а второй символ a будет переводить q₁ в состояние q₂. Ясно, что все слова, которые начинаются на ab, ba, bb, сами не входят в язык L и все их продолжения также ошибочны. Заведем для них "ошибочное" состояние q_!. Остальные слова естественно разбиваются на два класса: те, в которых четное число символов b, и те, в которых число таких символов нечетно (они и принадлежат L ).

Так как после получения aa число b четно, то для представления слов первого класса будем использовать состояние q₂, а для представления слов второго - создадим состояние q₃, которое и будет заключительным. В результате получаем автомат, диаграмма которого представлена на рис. 4.2. (Мы отмечаем на рисунках диаграмм начальное состояние стрелкой а заключительные состояния - двумя окружностями).

Проверим работу этого автомата, например, на входном слове w=aaababa. При его чтении порождается следующая последовательность конфигураций:

Заключительное состояние этого вычисления q₂ не является заключительным. Следовательно, . Если же мы рассмотрим в качестве входа слово w₁= w b= aaababab, то, продолжив на один шаг приведенное выше вычисление, получим, что . Следовательно, .

Мы проверили, что на двух входах автомат A работает верно. Как установить, что он построен корректно, т.е. верно работает на всех входных словах и распознает L? Типичная схема доказательства правильности конечного автомата такова:

1. определить (описать) для каждого состояния язык L(q), который состоит из слов, переводящих начальное состояние q₀ в q ;
2. доказать, что это определение правильное, используя индукцию по длине входного слова ;
3. показать, что .

Применим эту схему к доказательству правильности, построенного выше автомата A. Языки, связанные с состояниями этого автомата, фактически, уже были определены при его построении. Уточним их:

Правильность определения языков L(q₀), L(q₁) и L(q_!) следует непосредственно из определения A. Самое короткое слово, переводящее q₀ в q₂ - aa, и оно принадлежит L(q₂). Аналогично, самое короткое слово, переводящее q₀ в q₃ - aab, и оно принадлежит L(q₃). Предположим теперь, что для каждого слова w длины <= n выполнено условие (*):

w переводит начальное состояние q₀ в .

Покажем, что оно будет выполнено и для всех слов длины n +1.

Пусть |w|=n+1. Тогда , где . Так как |w'|=n, то для w' выполнено условие (*). Поэтому, если w' переводит q₀ в q₂, то это слово начинается с aa и содержит четное число b. При слово w переводит q₀ в q₂ и также начинается с aa и содержит четное число b, а при слово w переводит q₀ в q₃, начинается с aa и содержит нечетное число b, т.е. принадлежит L.

Аналогично, если w' переводит q₀ в q₃, то это слово начинается с aa и содержит нечетное число b. При слово w также переводит q₀ в q₃ и также начинается с aa и содержит нечетное число b, а при w переводит q₀ в q₂, оно начинается с aa и содержит четное число b. Обратно, если , то слово w переводит q₀ в w' переводит q₀ в q_i\ (i=2,3) и условие (*) выполнено, так как четность числа букв b в w и в w' одинакова. Если же , то из определения автомата A следует, что слово w переводит q₀ в w' переводит q₀ в q₃ и w переводит q₀ в w' переводит q₀ в q₂. Так как четность числа букв b в w и в w' разная, то и в этом случае условие (*) выполнено. Для завершения доказательства осталось заметить, что единственным заключительным состоянием автомата A является q₃ и поэтому L_A = L(q₃) = L.

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

Пусть и - два конечных автомата с общим входным алфавитом распознающих языки L₁ и L₂, соответственно. Определим по ним автомат M= , называемый произведением M₁ и M₂ (M= M₁ x M₂), следующим образом. , т.е. состояния нового автомата - это пары, первый элемент которых - состояние первого автомата, а второй - состояние второго автомата. Для каждой такой пары (q,p) и входного символа определим функцию переходов: . Начальным состоянием M является пара q₀= (q₀¹, q₀²), состоящая из начальных состояний автоматов-множителей. Что касается множества заключительных состояний, то оно определяется в зависимости от операции над языками L₁ и L₂, которую должен реализовать M.

Теорема 4.1.

• При или автомат распознает язык .
• При и автомат распознает язык .
• При и автомат M= распознает язык L = L₁ \ L₂.

Доказательство этой теоремы непосредственно выводится из следующего утверждения.

Лемма 4.2. Для любых двух состояний (q,p) и (q', p') автомата M и любого входного слова w слово w переводит (q,p) в (q', p') в автомате M тогда и только тогда, когда оно переводит q в q' в автомате M₁ и p в p' в автомате M₂.

Лемма устанавливается индукцией по длине слова w.

Следствие4.1.1. Класс конечно автоматных языков замкнут относительно теоретико множественных операций объединения, пересечения и разности.

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

Определение 4.8. Недетерминированный конечный автомат (НКА) - распознаватель - это система вида

включающая следующие компоненты:

• - конечное множество - входной алфавит ;
• Q={q₀, ... , q_n-1} (n >= 1) - конечное множество - алфавит внутренних состояний;
• - начальное состояние автомата;
• - множество принимающих (допускающих, заключительных) состояний ;
• - функция переходов.

Для значение - это множество состояний в каждое из которых может перейти автомат из состояния q, когда получает на вход символ a. - это множество состояний в каждое из которых может перейти автомат из состояния q без чтения символа на входе.

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

При табличном задании функции в таблице появляется (m+1) -ый столбец, соответствующий пустому символу и на пересечении строки q и столбца стоит множество состояний .

Для недетерминированного автомата в диаграмме D_M=(Q, E) с выделенной начальной вершиной q₀ и множеством заключительных вершин F ребра взаимно-однозначно соответствуют командам: команде вида q a -> q' соответствует ребро (q,q' ), с меткой a , а команде вида q -> q' соответствует ребро (q,q' ), с меткой .

Скажем, что заданный последовательностью ребер путь p=e₁e₂ ... e_T в диаграмме D_M несет слово w=w₁w₂ ... w_t (t <= T), если после удаления из него "пустых" ребер (т.е. ребер с метками ) остается последовательность из t ребер , метки которых образуют слово w , т.е. w_i - это метка ребра . Очевидно, это эквивалентно тому, что последовательность меток на ребрах пути p имеет вид , где k_j >= 0 (j=1,2, ... , t+1) и .

Слово w переводит q в q' в диаграмме D_M, если в ней имеется путь из q в q' который несет w .

На недетерминированные автоматы естественным образом переносится определение конфигураций и отношения перехода между ними.

Определение 4.9. Назовем конфигурацией НКА произвольную пару вида (q, w), в которой и . Определим отношение перехода из одной конфигурации в другую за один шаг:

или

Как и для ДКА, через обозначим рефлексивное и транзитивное замыкание отношения .

Внешне определение распознавания слов НКА совпадает с определением для ДКА.

Определение 4.10. НКА M распознает (допускает, принимает) слово w, если для некоторого \

Язык L_M, распознаваемый НКА M, состоит из всех слов, распознаваемых автоматом:

Отличие состоит в том, что у НКА может быть несколько различных способов работы (путей вычисления) на одном и том же входном слове w. Считаем, что НКА распознает (допускает, принимает) это слово, если хотя бы один из этих способов приводит в заключительное состояние из F.

Из определения диаграммы D_M непосредственно следует, что НКА M распознает слово w, тогда и только тогда, когда существует такое заключительное состояние , что в диаграмме D_M слово w переводит q₀ в q. Иными словами, в D_M имеется путь из q₀ в q, на ребрах которого написано слово w (с точностью до меток ).

Пример 4.1. Рассмотрим НКА , где

:		a	b
	0	{0,1}	{0}
	1			{4}
	2	{3}
	3			{1}
	4		{2}

Его диаграмма представлена ниже на рис. 4.3.

Рассмотрим работу этого автомата на слове ababa:

Так как 3 - заключительное состояние, то . Заметим, что у автомата N₁ имеются и другие способы работы на этом слове, не ведущие к заключительному состоянию. Например, он может после чтения каждого символа оставаться в состоянии 0. Но чтобы слово допускалось, достаточно существовать хотя бы одному "хорошему" способу.

Очевидно, что детерминированные конечные автоматы являются частными случаями недетерминированных. Естественно спросить, распознают ли недетерминированные конечные автоматы больший класс языков чем детерминированные? Следующая теорема показывает, что классы языков, распознаваемых НКА и ДКА совпадают.

Теорема 4.2. (Детерминизация НКА)

Для каждого НКА M можно эффективно построить такой ДКА A, что L_A = L_M.

Доказательство Пусть - НКА. Процедура построения по нему эквивалентного ДКА состоит из двух этапов: на первом по M строится эквивалентный ему НКА M₁, в программе которого отсутствуют переходы по а на втором этапе по M₁ строится эквивалентный ДКА A.

Этап 1. Устранение пустых переходов.

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

Пусть - это граф достижимости (транзитивного замыкания) для . Тогда или в имеется путь из q в q'}.

Определим НКА следующим образом: , т.е. кроме начального остаются лишь те состояния, в которые входят "непустые" ребра. , т.е. к заключительным состояниям M добавляются состояния, из которых можно было попасть в заключительные по путям из -ребер.

Для каждой пары полагаем , т.е. в D_M1} имеется a -ребро из q в r, если в D_M был (возможно пустой) путь из -ребер в некоторое состояние q', из которого a -ребро шло в r.

Из этого определения непосредственно следует, что в НКА M₁ нет пустых переходов по Установим эквивалентность M и M₁.

Лемма 4.1. .

Доказательство. Пусть w=w₁w₂... w_t - произвольное входное слово. Предположим, что . Это означает, что в диаграмме имеется путь p=e₁e₂ ... e_t (e₁= (q₀=r₀,r₁), e_i=(r_i-1,r_i), i=2,..., t) из q₀ в некоторое состояние , который несет слово w, т.е. ребро e_i помечено символом w_i. Из определения функции непосредственно следует, что для любого ребра e_i(r_i-1, r_i) этого пути в диаграмме D_M имеется путь из r_i-1 в r_i, начало (возможно пустое) которого состоит из -ребер, а последнее ребро помечено символом w_i. Объединив эти пути, получим в диаграмме D_M путь из q₀ в r_t , который несет слово w. Так как , то либо , либо в D_M имеется путь по -ребрам из r_t в некоторое состояние . В обоих случаях в D_M имеется путь из q₀ в заключительное состояние, который несет слово w, и следовательно, .

Обратно, пусть . Тогда в D_M имеется путь из q₀ в некоторое заключительное состояние r, который несет слово w. Пусть r₀=q₀, а r_i - это состояние этого пути, в которое приводит ребро с меткой w_i (i= 1,... , t). Рассмотрим отрезок этого пути между вершинами r_{i-1} и r_i. Последнее ребро этого отрезка имеет метку w_i, а все предыдущие (если они имеются) помечены Тогда по определению в диаграмме между r_{i-1} и r_i имеется ребро с меткой w_i. Объединив эти ребра, получим в путь из q₀ в r_t. Так как либо , либо в D_M из r_t имеется путь из -ребер в , то из определения F₁ следует, что . Таким образом, .

Этап 2. Детерминизация.

Идея детерминизации состоит в том, что состояниями ДКА объявляются подмножества состояний НКА. Тогда для каждого такого подмножества T и входного символа a однозначно определено множество состояний T', в которые НКА может попасть из состояний T при чтении a.

Определим по НКА ДКА следующим образом.

Ясно, что A - детерминированный конечный автомат. Следующая лемма устанавливает связь между его вычислениями и вычислениями исходного НКА.

Лемма 4.4. Для любой пары состояний Q', Q'' из Q^A и любого слова имеем

Доказательство. Применим индукцию по длине слова w.

Базис. Пусть |w|=0, тогда , Q' = Q'' и утверждение выполнено. Пусть теперь |w|=1 и . Тогда утверждение леммы следует непосредственно из определения .

Шаг индукции. Предположим, что лемма справедлива для всех слов длины <= k, и пусть |w| = k+1. Выделим в w первый символ: w=aw'. Пусть - это такое состояние, что . Тогда . Так как |w'|=k, то по индукционному предположению это эквивалентно следующему: . Но из определения следует, что . Объединив, эти два равенства, получаем: .

Для завершения доказательства теоремы покажем с помощью леммы 4.4, что .

Действительно, если слово w переводит состояние q₀ в некоторое в автомате M₁, то, положив в лемме Q' ={ q₀}, получим, что для состояния Q'', такого, что . Но тогда и .

Обратно, если , то для некоторого имеем . Тогда в Q'' имеется некоторое состояние и по лемме 4.4 в автомате , т.е. .

Пример 4.2. Применим процедуру из теоремы о детерминизации к НКА N₁ из примера 4.3.

На первом этапе получаем и НКА M₁ без пустых переходов, представленный на следующей диаграмме.

Заметим, что состояние 4 исчезло, так как в автомате N₁ в него можно было попасть только по -переходу.

На втором этапе детерминизируем M₁. ДКА A будет иметь 16 состояний: .

Во множество заключительных состояний войдут состояния, содержащие заключительное состояние 3 автомата M₁:

F^A={{3},{0,3}, {1,3}, {0,1,3}, {0,2,3},{1,2,3}, {0,1,2, 3}}.

Функция переходов определена в следующей таблице

	a	b
hline
{0}	{0,1}	{0}
{1}		{2}
{2}	{0,1,3}	{0}
{3}		{2}
{0,1}	{0,1}	{0,2}
{0,2}	{0,1,3}	{0}
{0,3}	{0,1}	{0,3}

	a	b
{1,2}	{0,1,3}	{0,2}
{1,3}		{2}
{2,3}	{0,1,3}	{0,2}
{0,1,2}	{0,1,3}	{0,2}
{0,1,3}	{0,1}	{0,2}
{0,2,3}	{0,1,3}	{0,2}
{1,2,3}	{0,1,3}	{0,2}
{0,1,2,3}	{0,1,3}	{0,2}

На самом деле нас интересуют лишь те состояния, в которые можно попасть из начального состояния {0}. Несложный анализ показывает, что их только три: {0,1}, {0,2 } и {0, 1, 3 }. Остальные состояния не достижимы из {0} и, следовательно, не влияют на работу автомата A. Их можно отбросить. Таким образом, в диаграмме автомата остаются 4 состояния, показанные на рис. 4.5.

Замечание. В рассмотренном примере у построенного ДКА A оказалось не больше состояний, чем у исходного НКА N₁. К сожалению, это не всегда так. Существуют примеры НКА с n состояниями, для которых эквивалентные ДКА содержат не менее 2ⁿ состояний.

Задача 4.1. Автомат по продаже кофе имеет щель для получения монет, кнопку, нажатие которой после уплаты достаточной суммы приводит к получению кофе, и накопитель, через который он выдает сдачу покупателю. Автомат принимает монеты достоинством в 1, 2 и 5 рублей. Чашка кофе стоит 8 руб. Пока полученная сумма недостаточна, горит красная лампочка. Если сумма, полученная автоматом, >= 8, то зажигается зеленая лампочка и после нажатия кнопки автомат наливает кофе и, если требуется, дает сдачу. Если автомат получает монету, когда горит зеленая лампочка, то он немедленно ее возвращает. Определите входной и выходной алфавиты конечного автомата, управляющего продажей кофе, и постройте его функции переходов и выходов.

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

Задача 4.3. Докажите лемму 4.1 индукцией по длине входного слова.

Задача 4.4. Постройте детерминированные конечные автоматы, которые распознают следующие языки в алфавите :

• L = {w | длина w делится на 5} ;
• L = {w | w не содержит подслов 'aab' и 'bba'} ;
• L = {w | w содержит четное число букв а и нечетное число букв b} ;
• L = {w | число букв а делится на 3, а число букв b на 2 }.

Задача 4.5. Выше в примере 4.1 был построен автомат с выходом, выполняющий сложение двух двоичных чисел. Постройте автомат-распознаватель, который проверяет правильность сложения. На вход поступают последовательности троек нулей и единиц:

Автомат должен допустить такую последовательность, если y = y(n) ... y(2)y(1) - это первые n битов суммы двоичных чисел x₁= x₁(n)... x₁(2)x₁(1) и x₂ = x₂(n)... x₂(2)x₂(1).

Задача 4.7. Докажите лемму 4.2.

Задача 4.8. Докажите, что приведенный на рис. 4.5 автомат A распознает язык, состоящий из всех слов, заканчивающихся на 'aba'.

Задача 4.9. Используя процедуру детерминизации недетерминированных автоматов из теоремы 4.2, постройте ДКА, эквивалентный заданному НКА M.

• с программой .
• с программой .

Регулярные выражения являются достаточно удобным средством для построения "алгебраических" описаний языков. Они строятся из элементарных выражений с помощью операций объединения ( + ), конкатенации ( ) и итерации ( ^* ). Каждому такому выражению r соответствует представляемый им язык L_r. Смысл операции объединения языков мы знаем. Определим операции конкатенации и итерации (иногда ее называют замыканием Клини).

Пусть L₁ и L₂ - языки в алфавите

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

Введем обозначения для "степеней" языка L:

Таким образом в Lⁱ входят все слова, которые можно разбить на i подряд идущих слов из L.

Итерацию (L)^* языка L образуют все слова которые можно разбить на несколько подряд идущих слов из L:

Ее можно представить с помощью степеней:

Часто удобно рассматривать "усеченную" итерацию языка, которая не содержит пустое слово, если его нет в языке: . Это не новая операция, а просто удобное сокращение для выражения .

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

В следующей таблице приведено формальное индуктивное определение регулярных выражений над алфавитом и представляемых ими языков.

Выражение r	Язык Lr
	La={a}
Пусть r1 и r2 -это	Lr1 и Lr2 -представляемые
регулярные выражения.	ими языки.
Тогда следующие выражения
являются регулярными	и представляют языки:
r=(r1+r2)
r=(r1circr2)
r=(r1)*	Lr=Lr1*

При записи регулярных выражений будем опускать знак конкатенации и будем считать, что операция ^* имеет больший приоритет, чем конкатенация и +, а конкатенация - больший приоритет, чем +. Это позволит опустить многие скобки. Например, можно записать как 10(1^* + 0).

Определение 5.1. Два регулярных выражения r и p называются эквивалентными, если совпадают представляемые ими языки, т.е. L_r=L_p. В этом случае пишем r = p.

Нетрудно проверить, например, такие свойства регулярных операций:

• r + p= p+ r (коммутативность объединения),
• (r+p) +q = r + (p+q) (ассоциативность объединения),
• (r p) q = r (p q) (ассоциативность конкатенации),
• (r^*)^* = r^* (идемпотентность итерации ),
• (r +p) q = rq + pq (дистрибутивность).

Пример 5.1. Докажем в качестве примера не столь очевидное равенство: (r + p)^* = (r^*p^*)^*.

Пусть L₁ - язык, представляемый его левой частью, а L₂ - правой. Пустое слово принадлежит обоим языкам. Если непустое слово , то по определению итерации оно представимо как конкатенация подслов, принадлежащих языку . Но этот язык является подмножеством языка L'=L_r^*L_p^* (почему?). Поэтому . Обратно, если слово , то оно представимо как конкатенация подслов, принадлежащих языку L'. Каждое из таких подслов v представимо в виде v= v₁¹... v_k¹ v₁²... v_l², где для всех i=1, ... , k подслово и для всех j=1, ... , l подслово (возможно, что k или l равно 0). Но это значит, что w является конкатенацией подслов, каждое из которых принадлежит и, следовательно, .

Рассмотрим несколько примеров регулярных выражений и представляемых ими языков.

Пример 5.2. Регулярное выражение (0 +1)^* представляет множество всех слов в алфавите {0, 1}.

Пример 5.3. Регулярное выражение 11(0 +1)^*001 представляет язык, состоящий из всех слов в алфавите {0, 1}, которые начинаются на '11', а заканчиваются на '001'.

Пример 5.4. Регулярное выражение представляет язык, состоящий из всех слов в алфавите {0, 1}, которые не содержат подслово '000' ( см. задачу 5.3).

Пример 5.5. Регулярное выражение 1^*(01^*01^*)^* представляет язык L_0ч, состоящий из всех слов в алфавите {0, 1}, в которых четное число нулей.

Действительно, каждое слово из L_0ч либо вообще не содержит нулей, т.е. входит в язык, представляющий 1^*, либо может быть разбито на блоки вида 01ⁱ01^j, i,j >= 0, которым, быть может, предшествует блок единиц. Выражение (01^*01^*), очевидно задает один такой блок, а его итерация - произвольную последовательность таких блоков.

Пример 5.6. Построим теперь регулярное выражение, представляющее язык L_0ч1ч, который состоит из всех слов в алфавите {0, 1}, содержащих четное число нулей и четное число единиц.

Пусть w=w₁w₂ ... w_n - произвольное слово из L_0ч1ч. Тогда, разумеется, n - четно, пусть n=2k. Разобьем w на пары соседних букв p_i =w_2i-1w_2i, i= 1,2,... ,k. Возможны 4 вида таких пар: 00, 11, 01 и 10. Пар вида 00 и 11 может быть сколько угодно, а пар вида 01 и 10 обязательно четное число. Поэтому w разбивается на блоки, каждый из которых начинается одной из пар 01 или 10 и содержит еще одну такую пару. Каждый такой блок описывается выражением (01 +10)(00 + 11)^*(01+10)(00 + 11)^*. При этом перед первым блоком может быть префикс, состоящий из пар 00 и 11. Множество слов состоящих из пар 00 и 11 задается выражением (00 +11)^*. Отсюда получаем выражение R_0ч1ч, задающее язык L_0ч1ч:

Покажем, что каждый регулярный язык можно распознать конечным автоматом.

Теорема 5.1. Для каждого регулярного выражения r можно эффективно построить такой недетерминированный конечный автомат M, который распознает язык, задаваемый r, т.е. L_M= L_r.

Доказательство Построение автомата M по выражению r проведем индукцией по длине r, т.е. по общему количеству символов алфавита символов и знаков операций и скобок в записи r.

Базис. Автоматы для выражений длины 1: и показаны на следующем рисунке.

Заметим, что у каждого из этих трех автоматов множество заключительных состояний состоит из одного состояния.

Индукционный шаг. Предположим теперь, что для каждого регулярного выражения длины <= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное регулярное выражение r длины k+1. В зависимости от последней операции оно может иметь один из трех видов: (r₁ + r₂), (r₁ r₂) или (r₁)^*. Пусть и - это НКА, распознающие языки L_r1 и L_r2, соответственно. Не ограничивая общности, мы будем предполагать, что у них разные состояния: .

Тогда НКА , диаграмма которого представлена на рис. 5.2, распознает язык .

У этого автомата множество состояний , где q₀ - это новое начальное состояние, q_f - новое (единственное !) заключительное состояние, а программа включает программы автоматов M₁ и M₂ и четыре новых команды -переходов: . Очевидно, что язык, распознаваемый НКА M, включает все слова из L_{M₁} и из L_{M₂}. С другой стороны, каждое слово переводит q₀ в q_f, и после первого шага несущий его путь проходит через q₀¹ или q₀². Так как состояния M₁ и M₂ не пересекаются, то в первом случае этот путь может попасть в q_f только по -переходу из q_f¹ и тогда . Аналогично, во втором случае .

Для выражения диаграмма НКА , распознающего язык L_r, представлена на следующем рисунке.

У этого автомата множество состояний , начальное состояние q₀= q₀¹, заключительное состояние q_f =q_f², а программа включает программы автоматов M₁ и M₂ и одну новую команду - -переход из заключительного состояния M₁ в начальное состояние M₂, т.е. . Здесь также очевидно, что всякий путь из q₀= q₀¹ в q_f =q_f² проходит через -переход из q_f¹ в q₀². Поэтому всякое слово, допускаемое M, представляет конкатенацию некоторого слова из L_M1} с некоторым словом из L_M2}, и любая конкатенация таких слов допускается. Следовательно, НКА M распознает язык .

Пусть r = r₁^*. Диаграмма НКА , распознающего язык L_r=L_r1* = L_M1^* представлена на рис. 5.3.

У этого автомата множество состояний , где q₀ - это новое начальное состояние, q_f - новое (единственное !) заключительное состояние, а программа включает программу автомата M₁ и четыре новых команды -переходов: . Очевидно, . Для непустого слова w по определению итерации для некоторого k >= 1 слово w можно разбить на k подслов: w=w₁w₂... w_k и все . Для каждого i= 1,... ,k слово w_i переводит q₀¹ в q_f¹. Тогда для слова w в диаграмме M имеется путь

Следовательно, . Обратно, если некоторое слово переводит q₀ в q_f, то либо оно есть либо его несет путь, который, перейдя из q₀ в q₀¹ и затем пройдя несколько раз по пути из q₀¹ в q_f¹ и вернувшись из q_f¹ в q₀¹ по -переходу, в конце концов из q_f¹ по -переходу завершается в q_f. Поэтому такое слово .

Из теорем 4.2 и 5.1 непосредственно получаем

Следствие 5.1. Для каждого регулярного выражения можно эффективно построить детерминированный конечный автомат, который распознает язык, представляемый этим выражением.

Это утверждение - один из примеров теорем синтеза: по описанию задания (языка как регулярного выражения ) эффективно строится программа (ДКА), его выполняющая. Справедливо и обратное утверждение - теорема анализа.

Теорема 5.2. По каждому детерминированному (или недетерминированному) конечному автомату можно построить регулярное выражение, которое представляет язык, распознаваемый этим автоматом.

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

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

Автомат M_r, который строится в доказательстве теоремы 5.1 по регулярному выражению r, не всегда является самым простым.

Например, для реализации выражения-слова a₁a₂ ... a_n, где , можно просто использовать автомат с (n+1) состоянием q_i (i=0,1,2, ... , n) и командами q_{i-1} a_i -> q_i, в котором нет пустых -переходов, участвующих в общей конструкции для конкатенации. Также при построении автомата для объединения M₁ и M₂ можно сливать их начальные состояния в одно, если в них нет переходов из других состояний (тогда не потребуется новое начальное состояние). Можно также объединить их заключительные состояния, если из них нет переходов в другие состояния и алфавиты M₁ и M₂ совпадают. Если из заключительного состояния M₁ нет переходов в другие состояния, то при конкатенации его можно объединить с начальным состоянием M₂. Вместе с тем, утверждения задачи 5.9 показывают, что наша общая конструкция достаточно экономна.

Пример 5.7. Применим теорему 5.1 к регулярному выражению , которое, как мы заметили в примере 5.4, представляет язык, состоящий из всех слов, которые не содержат подслово '000'.

На рис. 5.5 представлены диаграммы автоматов M₁ и M₂, построенных по выражениям r₁ = (1 +01 +001) и , соответственно, с помощью конструкций для конкатенации и объединения. Как мы отмечали выше, автомат M₁ можно было бы еще упростить, склеив начальные состояния q₂, p₁ и s₁, а также заключительные состояния q₃, p₃ и s₄.

Автомат M₃ для выражения r₁^* = (1 +01 +001)^* получается из M₁ добавлением нового начального состояния q₀ и заключительного состояния q₅ и -переходов из q₀ в q₁ и q₅, из q₄ в q₅ и из q₅ в q₁. Затем результирующий автомат для исходного выражения r получается последовательным соединением M₃ и M₂. Он представлен ниже на рис. 5.6.

Задача 5.1. Определите конкатенацию для следующих пар языков L₁ и L₂:

• L₁= {a, ab, abb} и ;
• и L₂= { a, b, abb, a} ;
• и ;

Задача 5.2. Пусть L={baa, bab, bba, bbb}. Какой из следующих языков является итерацией L^* этого языка?

• ;
• ;
• ;
• { w | w=bw' и | w| >= 12 }.

Задача 5.3. Докажите правильность регулярного выражения в примере 5.4.

Задача 5.4. Докажите следующие эквивалентности для регулярных выражений.

• p^*(p+q)^* = (p + qp^*)^* = (p+q)^* ;
• p(qp)^* = (pq)^*p ;
• (p^*q^*)^* =(q^*p^*)^* ;
• (pq)⁺(q^*p^* + q^*) = (pq)^*p q⁺p^*.

Задача 5.5. Постройте регулярное выражение, задающее язык язык L в алфавите .

• L= {w | w содержит нечетное число букв 0 и четное число букв 1}} ;
• L= {w | w содержит подслово 001 или подслово 110 } ;
• L= {w | w содержит по крайней мере мере два подряд идущих 0 } ;
• L= {w | w не содержит подслов 011 и 010}.

Задача 5.6. Определите, какой язык представляется следующими регулярными выражениями.

• (0^*1^*)0 ;
• (01^*)0 ;
• (00 +11 +(01 + 10)(00 +11)⁺(01+10))^*.

Задача 5.7. Упростить следующие регулярные выражения.

• (00^*)0 + (00)^* ;
• ;
• .

Задача 5.8. Выше в задаче 14.5 предлагалось построить автомат-распознаватель, который проверяет правильность сложения. Постройте регулярное выражение, задающее распознаваемый этим автоматом язык S, т.е. следующее множество слов в алфавите {0, 1}³

S= {(x₁(1),x₂(1),y(1)) (x₁(2),x₂(2),y(2)) ... (x₁(n),x₂(n),y(n)) | y = y(n) ... y(2)y(1) - это первые n битов суммы двоичных чисел x₁= x₁(n)... x₁(2)x₁(1) и x₂ = x₂(n)... x₂(2)x₂(1)}.

Задача 5.9. Пусть M_r - это автомат, который строится в доказательстве теоремы 5.1 по регулярному выражению r. Докажите, что

• у M_r нет переходов из единственного заключительного состояния q_f ;
• в диаграмме M_r из каждой вершины выходит не более двух ребер;
• число состояний M_r не более чем вдвое превосходит длину выражения r, т.е. |Q| <= 2 |r|.

Задача 5.10. Примените процедуру детерминизации из теоремы 4.2 и постройте ДКА, эквивалентный НКА из примера 5.7.

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

Предложение 6.1. Пусть L - автоматный язык в алфавите Тогда его дополнение - язык также является автоматным.

Действительно, достаточно заметить, что язык , включающий все слова в алфавите является автоматным и что .

Определенная ниже операция гомоморфизма формализует идею посимвольного перевода слов одного алфавита в слова другого.

Определение 6.1. Пусть и Delta - два алфавита. Отображение слов первого из них в слова второго называется гомоморфизмом, если

1. 
2. для любых двух слов w₁ и w₂ в алфавите имеет место равенство .

Из этого определения непосредственно следует, что гомоморфизм однозначно определяется своими значениями на символах алфавита Если w=w₁w₂ ... w_n, , то .

Пример 6.1.Пусть , Delta ={ 0, 1}, а гомоморфизм определен на символах следующим образом: .

Тогда .

Определение 6.2. Пусть - произвольный гомоморфизм и L - язык в алфавите Образом языка L при гомоморфизме называется язык , состоящий из образов всех слов языка L.

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

Оказывается, что класс автоматных языков замкнут относительно операций гомоморфизма и обращения гомоморфизма (взятия прообраза)

Теорема 6.1. Пусть - произвольный гомоморфизм и L - автоматный язык в алфавите Тогда и язык вляется автоматным.

Доказательство Пусть - ДКА, распознающий язык L. Построим по нему НКА , распознающий язык . Идея этого построения проста: нужно каждый переход из состояния q в q' по букве в автомате A превратить в переход из q в q' по слову в автомате M.

Пусть , Q= {q₀, q₁, ..., q_n} и (если ). Для каждого a_i зафиксируем простой НКА M_i, распознающий язык {d₁ⁱd₂ⁱ ... d_{k_i}ⁱ}, имеющий (k_i +1) состояние p₀ⁱ, p₁ⁱ, ..., p_{k_i}ⁱ и команды p_{l-1}d_lⁱ -> p_l (1<= l <= k_i). ( Если , то у M_i будут два состояния, соединенные -переходом). Теперь для каждой команды q_j a_i -> q_r поместим в M между q_j и q_r автомат M_i (цепочку состояний p₀ⁱ, p₁ⁱ, ..., p_{k_i}ⁱ ). Чтобы состояния различных цепочек не склеивались, придадим им верхний индекс j, т.е. у каждого q_j будет своя копия каждого из автоматов M_i. Для этого положим . Таким образом, p_l^{ji} - это l -ое состояние на пути из q_j по "старой" букве a_i. Программа автомата M строится по программе A следующим образом. Для каждой команды вида q_j a_i -> q_r из поместим в следующие команды:

Таким образом, из q_j автомат M по пустому переходу попадает в начальное состояние p₀^ji j -ой копии автомата M_i, затем проходит по слову и снова по пустому переходу попадает в q_r.

Для завершения определения M положим q₀^M = q₀ и F^M = F.

Докажем теперь, что наше построение корректно, т.е., что .

1. . Заметим вначале, что если , то и по определению , следовательно .

   Пусть . Тогда в диаграмме A имеется путь из q₀ в некоторое заключительное состояние , который несет слово w. Пусть это путь . Тогда для каждого 1 <= x <= k в имеется команда . Но из определения следует, что тогда в автомате M имеется путь из в , несущий слово . Объединив все такие пути, получим путь из из q₀ в , несущий слово . Следовательно, .

2. . Пусть слово принадлежит L_M. Покажем, что тогда для некоторого . Рассмотрим для этого путь в диаграмме M из q₀ в , несущий слово u . Выделим на этом пути все состояния из Q. Пусть это будут по порядку состояния q₀=q_{j₀}, q_{j₁}, ... q_{j_k}= q'. Тогда слово u разбивается на k подслов: u=u₁u₂ ... u_k таких, что u_x переводит в M состояние в ( 1 <= x <= k ). Покажем, что для каждого такого u_x существует символ такой, что и в имеется команда . Действительно, любой путь из в M начинается -переходом в некоторое состояние вида . Пусть это будет состояние на пути, который несет u_x в . Далее этот путь обязательно будет проходить по состояниям вида и завершится -переходом из в состояние . Тогда из определения M следует, что и в имеется команда . Положив w_x=a_i, получим, что и , для слова . При этом каждый символ w_x этого слова переводит в автомате A состояние в . Поэтому в A существует путь из q₀ в , несущий слово w и, следовательно

Пример 6.2. Пусть алфавиты и гомоморфизм определены как выше в примере 6.1. Рассмотрим язык L={ w | число букв а в слове w нечетно }.

На следующем рисунке показана диаграмма ДКА A, распознающего язык L, и диаграммы автоматов M_a для , M_b для и M_c для .

Подставив в A вместо a -переходов автомат M_a, вместо b -переходов автомат M_b и вместо c -переходов автомат M_c, получим представленный на рис. 6.2 недетерминированный автомат M, распознающий язык . На этом рисунке каждая из -петель в состояниях q₀ и q₁ заменяет по три -перехода, связанных с M_b.

Отметим, что конструкция автомата M в теореме 6.1 удобна для доказательства, но несколько избыточна. Без труда можно сократить в ней все -переходы, склеив начальные и заключительные состояния автоматов M_i с соответствующими состояниями автомата A. Например, в автомате на рис. 6.2 можно объединить начальные состояния p₀⁰ и p₀⁰¹ с q₀, заключительные состояния p₂⁰¹ и p₃¹³ с q₁ и т.п.

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

Определение 6.3. Пусть . Проекцией языка L в алфавите на подалфавит называется язык получено из некоторого слова вычеркиванием всех символов, не принадлежащих алфавиту .

Определим гомоморфизм следующим образом: , если и , если . Тогда для всякого языка L в алфавите имеет место равенство . Отсюда и из предыдущей теоремы 6.1 получаем замкнутость класса автоматных языков относительно проекции.

Предложение 6.2. Для любых алфавитов и таких, что , и любого автоматного языка L в алфавите проекция также является автоматным языком.

Отметим, что для проекции конструкция автомата M для по ДКА A для L существенно упрощается: достаточно в A все переходы по символам из заменить на -переходы.

Следующая теорема устанавливает замкнутость класса автоматных языков относительного обращения гомоморфизмов.

Теорема 6.2. Пусть - произвольный гомоморфизм и L - автоматный язык в алфавите Тогда и язык является автоматным.

Доказательство Пусть - ДКА, распознающий язык L. Пусть , Q= {q₀, q₁, ..., q_n} и (если ).

Перестроим его в ДКА с тем же множеством состояний, начальным и заключительными состояниями, который распознает язык .

Идея этого построения состоит в том, чтобы переходить из состояния q в q' по букве в автомате M, если в автомате A слово переводит q в q'. Если же для образ пуст, т.е. , то в автомате M слово a переводит каждое состояние в себя, так как символы a могут встречаться в каждом слове из в любом месте и в любом количестве.

Таким образом, положим для каждой пары и , если и в автомате A . Если же , то полагаем .

Так как A - детерминированный автомат, то функция переходов определена однозначно и для всех пар и . Следовательно, M детерминированный.

Нетрудно показать, что .

Действительно, если слово , то в M путь , несущий это слово ведет в заключительное состояние . Из определения следует, что тогда в A существует соответствующий путь из q₀ в , который несет слово . Следовательно, .

Обратно, пусть . Тогда слово и в автомате A имеется путь, несущий u, который переводит q₀ в некоторое заключительное состояние . Зафиксируем на этом пути состояния , в которые он попадает после прочтения префиксов слова u (j = 1, 2, ... , k). Тогда и для всех j = 1, 2, ... , k имеет место . Отсюда и из определения получаем, что в M для всех j = 1, 2, ... , k имеет место переход ха один шаг . Следовательно, в M путь q₀, q_{i₁}q_{i₂}... q_{i_k} несет слово w и завершается в заключительном состоянии . А это означает, что .

Пример 6.3. Пусть алфавиты и гомоморфизм определены как выше в примере: . Рассмотрим язык L={ w | число букв 0 в слове w нечетно, а число букв 1 - четно}.

На следующем рисунке показана диаграмма ДКА A, распознающего язык L.

Применив к этому автомату конструкцию из теоремы 6.2, обнаружим, что a и b оставляют все состояния на месте, а c переводит каждое состояние в соседнее состояние "по горизонтали". В результате получаем автомат M, показанный ниже на рис. 6.4.

Легко заметить, что в нем состояния q₂ и q₃ недостижимы из начального состояния q₀ и что этот автомат M распознает язык

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

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

Теорема 6.3. (о разрастании для автоматных языков)

Пусть L - бесконечный автоматный язык. Тогда существует такая константа n, что любое слово длины |w| > n можно разбить на три части x, y и z так, что w = xyz и

1. |xy| <= n ;
2. |y| > 0 ;
3. для любого m >= 0 слово w_m = x y^m z принадлежит языку L.

(Здесь ).

Доказательство Так как язык L автоматный, то существует ДКА , распознающий L. Пусть |Q|= n и слово имеет длину k > n. Рассмотрим путь в диаграмме A, который несет слово w. Очевидно, что среди первых (n+1) состояний этого пути хотя бы одно встречается дважды. Выберем первое из таких состояний . Тогда для некоторой пары чисел l < j <= n имеем . Пусть x=w₁w₂ ... w_l - это префикс w, который переводит q₀ в , - это подслово w, которое переводит в , и - это суффикс w, который переводит в . x и z могут быть пусты, но |y| = j-l >= 1. Длина |xy| = j <= n. Таким образом, условия (1) и (2) теоремы выполнены. Нетрудно убедиться и в выполнении условия (3). Действительно, выбросив из пути p цикл , получим путь p₀ из q₀ в , который несет слово xz, а повторив этот цикл m раз, получим путь p₀ из q₀ в , который несет слово xy^m z. Следовательно, для любого m >= 0 .

Содержательно, эта теорема утверждает, что у всякого достаточно длинного слова из автоматного языка имеется непустое подслово, которое можно вырезать или повторить сколько угодно раз, оставаясь внутри языка. Как, используя теорему ref{th-razr}, доказать, что некоторый язык L не является автоматным? Это можно сделать, используя схему доказательства "от противного":

1. Предположим, что L автоматный язык. Тогда для него имеется константа n из утверждения теоремы ref{th-razr}.
2. Определим по n некотрое "специальное" слово w из L длины > n и докажем, что для любого разбиения w = xyz, удовлетворяющего условиям (1) и (2) теоремы, найдется такое k >= 0, что слово w_k=xy^k z не принадлежит L.
3. На основании полученного противоречия делаем вывод, что L - не автоматный язык.

Разумеется, в этой схеме самым сложным является выбор "специального" слова w в пункте (2). Что касается, подбора такого k >= 0, для которого , то, как правило, достаточно рассмотреть k = 0 или k = 2.

Рассмотрим несколько примеров применения теоремы о разрастании.

Пример 6.4. Покажем, что язык L₁ ={ w =0ⁱ 1ⁱ | i >= 1 } не является автоматным.

Предположим, что он автоматный. Тогда для него имеется n из утверждения теоремы 6.3. Рассмотрим следующее ("специальное" !) слово w = 0ⁿ 1ⁿ. Очевидно, что . Предположим, что существует разбиение w = xyz, удовлетворяющего условиям (1) и (2) теоремы. Так как по условию (2) |xy| <= n, то y = 0ⁱ для некоторого i>0. Но тогда слово , что противоречит условию (3) теоремы. Следовательно язык L₁ не автоматный.

Пример 6.5. Покажем, что язык СКОБ правильных скобочных последовательностей в алфавите { (, ) } не является автоматным.

Схема доказательства та же. В качестве специального слова выберем слово w = (ⁿ )ⁿ, оно, очевидно, принадлежит СКОБ. Тогда для всякого разбиения w = xyz такого, что |xy| <= n слово y = (ⁱ для некоторого i>0. И, как и в предыдущем примере, слово , что противоречит условию (3) теоремы. Следовательно, язык СКОБ не автоматный.

Пример 6.6. Покажем, что язык L₂ ={ w =0ⁱ 1^j | i <= 2j+1 } не является автоматным.

Здесь, предположив, что L₂ автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово . Для всякого разбиения w = xyz такого, что |xy| <= n слово y = 0ⁱ для некоторого i>0. Рассмотрим слово w₂ = x y² z = 0^{2n+1+i}1ⁿ. Но . Следовательно, и язык L₂ не является автоматным.

Пример 6.7. Рассмотрим язык "квадратов" в унарном алфавите { | }:

Здесь, предположив, что L₃ автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = |^{n²}. Для всякого разбиения w = xyz такого, что |xy| <= n слово y = |ⁱ для некоторого 0 < i <= n. Тогда . Но n² - i >= n² -n > n² -2n +1 =(n-1)². Следовательно, n² - i не является полным квадратом и , т.е. язык "квадратов" L₃ не является автоматным.

Пример 6.8. Рассмотрим язык "простых чисел" в унарном алфавите { | }:

Предположим, что L_pr - автоматный язык и зафиксируем для него константу n из теоремы 6.3. Выберем простое число p > n и рассмотрим слово w = |^p. Пусть w = xyz - произвольное разбиение w такое, что |xy| <= n. Тогда для некоторого 0 < i <= n слово y = |ⁱ и xz = |^{p -i}. Положим k = p - i и рассмотрим слово w_k = x y^k z. Его длина p' равна |x| +k|y| + |z|= (p-i)(i+1). Так как 1 <= i < n+1 <= p, то p' - составное число и . Следовательно, L_pr - не автоматный язык. Заметим, что в этом примере k выбирается для каждого n по-своему.

Еще один прием доказательства неавтоматности языка L состоит в том, чтобы вместо L рассмотреть некоторый язык L' = op(L,L₁,... , L_k), полученный из L и автоматных языков L₁,... , L_k с помощью операций op, сохраняющих автоматность. Если доказать, что L' не является автоматным, то и исходный язык L не автоматен.

Пример 6.9. Рассмотрим язык .

Пусть L₅= {0ⁱ1^j | i >= 1, j >= 1}. Очевидно, что язык L₅ автоматный. Нетрудно заметить, что его пересечение с дополнением L₄ совпадает с языком L₁ из примера 6.4, т.е. . Так как мы установили, что L₁ не автоматный, то и L₄ не является автоматным.

Являются ли условия теоремы 6.3 достаточными для того, чтобы язык оказался автоматным? Следующий пример показывает, что ответ на этот вопрос отрицателен.

Пример 6.10.Пусть L₆ ={c^r aⁱ bⁱ | r >= 1 , i>= 0 }, L₇= { aⁱb^j | i >= 0, j >= 0}. Рассмотрим язык .

Для этого языка можно в качестве n выбрать 1. Каждое слово w из L₈ принадлежит L₆ или L₇. Если слово , то оно представимо в виде xyz, где . Тогда w₀ = z= c^r-1 aⁱ bⁱ ( r >= 1, i >= 1 ) и при r=1 слово , а при r > 1, очевидно, . При k >= 1 имеем . Если слово и i >= 1, то его можно представить как в виде xyz, где и для каждого k>= 0 . Если же i =0, то w= b^j ( j >= 1 ) и его можно разбить на части . И в этом случае для каждого k >= 0 . Во всех случаях и, следовательно язык L₈ удовлетворяет условиям теоремы 6.3. Но этот язык не автоматный. Действительно, пусть - это гомоморфизм, заданный как . Тогда из примера 6.4. Так как язык L₇ является автоматным, а L₁ - нет, то и язык L₈ не является автоматным.

Задача 6.1. Примените процедуру детерминизации из теоремы 4.2 и постройте ДКА, эквивалентный построенному выше в примере 6.2 НКА M.

Задача 6.2. Цилиндрификация - это операция, которая обратна проекции. Для любых алфавитов и таких, что , и любого языка L в алфавите определим его цилиндрификацию как язык .

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

Задача 6.3. Обращением слова называется слово w^{-1}= w_k ... w₂ w₁. Показать, что для автоматного языка L его обращение - язык также является автоматным языком.

Задача 6.4. Пусть L - автоматный язык в алфавите Доказать, что автоматными являются и следующие языки:

1. .
2. .
3. .
4. .

Задача 6.5. Пусть L - автоматный язык в алфавите , а L₁,..., L_m - это автоматные языки в алфавите Доказать, что автоматным является и язык ЗАМ(L), полученный из слов L заменой каждой буквы a_i на некоторое слово из L_i, т.е. и такие слова , что для всех j=1,2,... n }.

Задача 6.6. Пусть L - автоматный язык в алфавите k - целое положительное число и - отображение в Доказать, что автоматным является язык .

Задача 6.7. Докажите, что теорема 6.3 о разрастании остается справедливой и при замене условия 1) |xy| <= n на условие 1') |yz| <= n, т.е. повторяющееся подслово y имеется и в суффиксе w длины <= n.

Задача 6.8. Доказать, что следующие языки в алфавите не являются автоматными.

• Множество всех слов, в которых букв a на 3 больше, чем букв b.
• L={ aⁿcb^m | m > 3n }.
• L={ wcw^-1 | w =a²bⁿa для некоторого n > 0}.
• L={ w | |w| = 2ⁿ для некоторого целого числа n }.
• .

Задача 6.9. -выражение - это либо переменная x, или символ за которым следует переменная, а далее либо -выражение, либо левая скобка, -выражение, еще одно -выражение и правая скобка. Например, - это правильные -выражения, а и - неправильные. Докажите, что язык -выражений в алфавите не является автоматным.

Задача 6.10. Выше в задаче строился автомат-распознаватель, который проверял правильность сложения двоичных чисел. Докажите, что для операции умножения двоичных чисел такого автомата не существует, т.е. что язык в алфавите троек битов U = {(x₁(1),x₂(1),y(1)) (x₁(2),x₂(2),y(2)) ... (x₁(n),x₂(n),y(n)) | y = y(n) ... y(2)y(1) - это первые n битов произведения двоичных чисел x₁= x₁(n)... x₁(2)x₁(1) и x₂ = x₂(n)... x₂(2)x₂(1)} не является автоматным.

Задача 6.11. Доказать, что язык в алфавите не является автоматным.

Первоначальной целью теории алгоритмов является классификация всех задач на алгоритмически разрешимые и неразрешимые, т.е. на те, для которых существуют решающие их алгоритмы, и те, для которых таких алгоритмов нет. Неформально под алгоритмом можно понимать выраженный в некотором языке набор правил (предписание, рецепт, способ), позволяющий применить к исходным (входным) данным x из некоторого множества допустимых данных X последовательность дискретных действий (операций, команд), приводящую к определенному результату - выходным данным из некоторого множества Y. В этом случае говорят, что алгоритм вычисляет функцию типа X -> Y. Это нестрогое определение вполне подходит в тех случаях, когда для некоторой функции нам предъявляется "объект", называемый алгоритмом ее вычисления (например, алгоритм Эвклида для вычисления наибольшего общего делителя двух целых чисел), и можно легко проверить, позволяет ли он действительно вычислить требуемую функцию. Однако оно совершенно не годится для доказательства того, что для заданной функции никакого алгоритма нет.

Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для формализации понятия алгоритма. Перечислим некоторые из предложенных разными авторами в разное время формальных моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), -исчисление (Черч, Клини), итеративные автоматы Неймана, нормальные алгорифмы Маркова, счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др. Заложенные в них идеи в значительной степени повлияли затем на архитектуру и языки программирования реальных компьютеров (например, на базе -исчисления построен широко применяемый в задачах искусственного интеллекта язык ЛИСП, а из нормальных алгорифмов Маркова произошел хорошо подходящий для текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков программирования также задает некоторую формальную модель алгоритмов. Мы вначале рассмотрим один из простейших таких языков - простые структурированные программы. А затем сравним их с двумя другими моделями алгоритмов: описаниями частично рекурсивных функций и машинами Тьюринга.

Хотя алгоритмы в разных прикладных областях имеют дело с дискретными объектами различных видов: целыми и рациональными числами, строками, формулами, разного рода выражениями, графами, матрицами, таблицами, точечными изображениями и др., мы в этой части курса будем рассматривать только задачи вычисления функций от натуральных аргументов, принимающих натуральные значения. Такие функции часто называют арифметическими. Дело в том, что для любого естественного множества дискретных объектов (в частности, для всех перечисленных выше) имеется простое кодирование его элементов целыми числами. Поэтому задачи вычисления функций на этих множествах превращаются в задачи вычисления арифметических функций.

Напомним, что через N обозначается множество натуральных чисел, т.е. N={0,1,2,...}. Для частичной n - местной арифметической функции f: Nⁿ -> N через обозначим область ее определения. Чтобы указать, что f не определена на некотором наборе чисел a₁,..., a_n будем писать , а если f на этом наборе определена, то будем писать . Таким образом, .

В этом разделе рассмотрим в качестве средства описания алгоритмов структурированные программы. Они вычисляют функции, используя минимальные средства: элементарные присваивания, условные операторы и циклы.

Определим вначале синтаксис структурированных программ. Зафиксируем для этого некоторое счетное множество имен переменных Var, которые будут использоваться в программах. Как обычно, будем считать, что оно включает имена x, x₁,x₂,..., y, y₁,..., z,z₁,... и т.п. В последующих определениях x, y, z - это произвольные переменные из Var.

Определение 7.1. Оператор присваивания. Присваивание - это выражение одного из следующих трех видов:

• x := x+1
• x := 0
• x := y.

Определение 7.2. Условия. Условие - это выражение одного из двух видов:

а) x = y или б) x < y.

Структурированные программы определяются индуктивно.

Определение 7.3. Структурированные программы.

• Каждое присваивание - это структурированная программа.
• Если и - структурированные программы, то и - это структурированная программа.

• Если и - структурированные программы, а - это условие, то

  

  является структурированной программой.

• Если - структурированная программа, а - это условие, то

  

  все является структурированной программой.

• Других структурированных программ нет.

Конструкция в п. (б) называется последовательным применением или композицией программ и , конструкция в п. (в) называется условным оператором ; конструкция в п. (г) - это оператор цикла, - условие цикла, а - тело цикла.

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

Определение 7.4. Состояние - это отображение из множества переменных Var во множество N. Для через обозначим значение переменной x в состоянии Через S обозначим множество всех состояний.

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

Определение 7.5. Операционная семантика программы - это отбражение (вообще говоря, частичное) типа S -> S, которое программа индуцирует на множестве всех состояний. Через обозначим состояние - результат применения программы к состоянию . Оно определяется индукцией по построению программы.

• , где при , и .
• , где при , и .
• , где при , и
• Пусть . Тогда , при этом, если или и , то и .

• Пусть если x = y то иначе конец. Тогда

  

• Пусть если x < y то иначе конец. Тогда

  
• Пусть пока x = y делай все. Тогда при , а при - это первое такое состояние в последовательности состояний ., что при i <= m все состояния определены, при i <m имеет место , и .
• Семантику для цикла с условием x < y определите самостоятельно (см. задачу 7.1).

Пусть - программа, - множество ее переменных. Выделим среди эти переменных некоторое подмножество входных переменных x₁,..., x_n и одну результирующую (выходную) переменную y (она может быть одной из входных). Переменные из , не являющиеся входными, будем называть вспомогательными.

Определение 7.6. Программа с входными переменными x₁,..., x_n и результирующей переменной y вычисляет частичную функцию F: ⁿ -> , если для любого набора значений аргументов , она переводит начальное состояние в котором при 1<= i<= n и при , в состояние тогда и только тогда, когда и .

Функцию, вычисляемую программой с входными переменными x₁,..., x_n в (результирующей) переменной y, обозначим .

Арифметическая функция F(x₁, ..., x_n) программно вычислима, если она вычислима некоторой программой в некоторой переменной y при некотором разбиении переменных на входные: x₁,..., x_n и вспомогательные.

Заметим, что в нашем языке нет понятия процедуры (подпрограммы). Для сокращения записи мы будем иногда использовать имя одной ранее написанной программы внутри текста другой: . Такая запись будет означать текстовую (in-line) подстановку текста (кода) программы в соответствующее место программы Подчеркнем, что при этом переменные не переименовываются и программист сам должен заботиться о правильной инициализации переменных из . Например, если использует отдельно написанную программу из приведенного ниже примера 7.3 для сложения переменных a и b и получения результата в t, то "безопасный" и корректный способ сделать это может выглядеть так:

т.е. вначале сохраняются текущие значения переменных x,y,z, используемых в , затем входным переменным x и y присваиваются нужные значения a и b и вызывается , ее результат передается в t, затем восстанавливаются значения x,y,z.

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

Пример 7.1.

Ясно, что тождественно равна 0.

Пример 7.2.

А здесь для любого x.

Пример 7.3.

Зафиксируем входные переменные x, y и выходную переменную x ( z - рабочая переменная ). Легко показать, что .

Действительно, при y=0 тело цикла не выполняется и выход равен x=x+0. При y >= 1 тело цикла выполняется y раз и при каждом его выполнении x увеличивается на 1.

Пример 7.4.

вычисляет в x₁ функцию выбора i-го аргумента: .

Пример 7.5.

Нетрудно понять, что вычисляет нигде не определенную функцию от n переменных: .

Задача 7.1. Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида

пока x < y делай все.

Задача 7.2.Построить структурированные программы, вычисляющие в z следующие функции, и доказать их корректность:

• f_{x}(x,y)= x*y;
• f_fact(x)= x!;
• f_-1(x)= x 1, где 0 1 = 0 и (x+1) 1 = x ;
• f_-(x,y)= x y, где x y = x-y, если x >= y и x y=0, если x < y ;
• f_sqr(x)= [sqrt x];
• f_exp(x)= 2^x;
• f_log(x)= [log₂x];
• f_/(x,y)= [x/y].

Задача 7.3. Пусть - структурированная программа и . Из определений следует, что при различной фиксации входных переменных и выходной переменной программа может вычислять различные функции.

• Каково максимальное число функций от n <= m переменных, которое может вычислять Сколько всего разных функций может вычислить
• Постройте программу , которая вычисляет максимальное число различных функций от n <= m переменных.
• Постройте программу с , которая для каждого n <= m вычисляет максимальное число различных функций от n переменных.

Задача 7.4.Построить структурированные программы, вычисляющие в z следующие функции:

Задача 7.5. Пусть структурированная программа вычисляет в переменной y некоторую всюду определенную взаимно однозначную функцию f(x), область значений которой совпадает с множеством всех натуральных чисел N. Пусть . Постройте структурированную программу, которая вычисляет обратную функцию f^-1(x) = { z | f(z)=x}.

Задача 7.6. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) (элементы последовательности F(x) называются числами Фибоначчи). Постройте структурированную программу, которая вычисляет функцию F(x).

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

Мы будем рассматривать частичные арифметические функции fⁿ(x₁, ..., x_n): Nⁿ -> N. Здесь верхний индекс n у имени функции f обозначает число ее аргументов ("арность"). Если арность ясна из контекста или несущественна, то этот индекс будем опускать. Определим вначале три оператора, позволяющих по одним функциям получать другие.

Определение 8.1. Суперпозиция. Пусть F^m и f₁ⁿ,..., f_mⁿ - арифметические функции. Скажем, что функция Gⁿ получена из F^m , f₁ⁿ, ..., f_mⁿ с помощью оператора суперпозиции (обозначение: Gⁿ=[F^m;f₁ⁿ, ..., f_mⁿ] ), если для всех наборов аргументов (x₁,...,x_n)

При этом для каждого набора аргументов (a₁, ..., a_n) функция (т.е. определена), если определены все значения f₁ⁿ (a₁, ..., a_n)=b₁,..., f_mⁿ (a₁, ..., a_n)=b_m и .

Определение 8.2. Примитивная рекурсия. Скажем, что функция Fⁿ⁺¹(x₁,... ,x_n,y) получена с помощью оператора рекурсии из функций gⁿ(x₁,..., x_n) и hⁿ⁺²(x₁, ..., x_n, y, z), если она может быть задана схемой примитивной рекурсии

В этом случае будем писать Fⁿ⁺¹ = R(gⁿ,hⁿ⁺²).

При этом и для каждого b

и .

В случае, когда n=0, т.е. F зависит от одного аргумента y, а аргументов x₁,...,x_n нет, схема примитивной рекурсии принимает вид

где .

Заметим, что если исходные функции в операторах суперпозиции и примитивной рекурсии всюду определены, то и результирующие функции также всюду определены. Следующий оператор позволяет задавать не всюду определенные, т.е. частичные, функции.

Определение 8.3. Минимизация. Скажем, что функция Fⁿ(x₁,... ,x_n) получена с помощью оператора минимизации( -оператора) из функции gⁿ⁺¹(x₁,..., x_n,y), если Fⁿ(x₁,...,x_n) определена и равна y тогда и только тогда, когда все значения gⁿ⁺¹(x₁,..., x_n,0),...,gⁿ⁺¹(x₁,..., x_n,y-1) определены и не равны 0, а gⁿ⁺¹(x₁,..., x_n,y)=0. В этом случае будем писать

Определение 8.4. Простейшие функции. Функция называется простейшей, если она является одной из следующих функций:

• o¹(x)=0 - тождественный нуль;
• s¹(x)= x+1 - следующее число (плюс один);
• функции выбора аргумента I_mⁿ (x₁, ... ,x_n)=x_m (1 <= m <= n).

Заметим, что все простейшие функции вычислимы в интуитивном смысле. Кроме того, операторы суперпозиции, примитивной рекурсии и минимизации таже вычислимы: понятны алгоритмы, по которым из программ для исходных функций можно получить программы для результирующих. Следующее определение вводит интересующий нас класс частично рекурсивных функций и его важные подклассы.

Определение 8.5. Частично рекурсивные функции. Функция f называется частично рекурсивной функцией (ч.р.ф.), если она является одной из простейших функций или может получиться из них с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации, т.е. существует последовательность функций f₁,f₂,..., f_n=f, каждая из которых является либо простейшей, либо получена из предыдуших с помощью одного из указанных операторов. Указанная последовательность функций называется частично рекурсивным описанием функции f.

Функция f называется общерекурсивной функцией (о.р.ф.), если она частично рекурсивна и всюду определена.

Функция f называется примитивно рекурсивной функцией (п.р.ф.), если она частично рекурсивна и для нее существует частично рекурсивное описание, использующее лишь операторы суперпозиции и примитивной рекурсии. В таком случае оно называется примитивно рекурсивным описанием функции f.

Нетрудно проверить, что каждая примитивно рекурсивная функция всюду определена, т.е. является общерекурсивной (обратное, вообще говоря, неверно).

Приведем некоторые примеры частично рекурсивных функций.

Пример 8.1. Постоянные функции.

Пусть fⁿ(x₁,...,x_n)=k для всех наборов аргументов (x₁,...,x_n) и числа . Тогда

Пример 8.2. Сложение: +²(x,y)=x+y.

Функция сложения определяется следующей примитивной рекурсией.

Следовательно, +² =R(I₁¹,[s¹;I₃³]).

Пример 8.3. Умножение: x²(x,y)=x x y.

Используя сложение, умножение можно задать следующей примитивной рекурсией:

Следовательно, x² =R(o¹,[+;I₃³,I₁³]).

Пример 8.4. Минус 1: .

Нетрудно проверить, что .

Пример 8.5. Вычитание : , если x >= y и , если x < y.

Вычитание определяется следующей примитивно рекурсивной схемой:

Следовательно, .

Пример 8.6. Предикаты равенства и неравенства нулю:

Примитивная рекурсивность этих функций следует из равенств и .

Пример 8.7. Модуль разности: .

Пример 8.8. rm(x,y)= остаток от деления y на x (при x=0 положим rm(0,y)=y ).

Заметим, что

Тогда функцию rm(x,y) можно задать примитивно рекурсивной схемой

Правую часть второго равенства легко представить как функцию g(x,y,rm(x,y)), полученную с помощью суперпозиции уже построенных примитивно рекурсивных функций.

Пример 8.9. Нигде не определенная функция .

Эта функция может быть задана, например, соотношением .

Отметим, что все функции в примерах 8.1 - 8.8 являются примитивно рекурсивными.

В этом параграфе рассмотрим соотношение между программно вычислимыми и частично рекурсивными функциями. Справедлива следующая

Теорема 8.1. Каждая частично рекурсивная функция программно вычислима.

Доказательство индукцией по определению ч.р.ф.

Базис: программная вычислимость простейших функций была установлена в примерах 1.1, 1.2 и 1.4.

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

Суперпозиция. Пусть F^m и f₁ⁿ,..., f_mⁿ - арифметические функции, вычислимые программами так, что , и при i=1,...,n. Пусть переменные y₁, ..., y_m, z₁,..., z_n не используются в программах . Кроме того, пусть все вспомогательные переменные этих программ - это w₁, ... , w_r. Рассмотрим следующую программу P:

В качестве входных переменных зафиксируем x₁, ..., x_n, а выходной - x₁. Пусть в исходном состоянии x₁=a₁, ..., x_n = a_n. Тогда в первой строке эти значения сохраняются в переменных z₁, ..., z_n, которые своих значений далее не меняют. Поэтому для каждого i=1,...,m-1 после выполнения фрагмента

значением переменной y_i является f_iⁿ(a₁,..., a_n), x₁=a₁, ..., x_n = a_n, а значения всех вспомогательных переменных равны 0. Тогда после выполнения

значением каждого x_i также является f_iⁿ(a₁,..., a_n), а после выполнения значение x₁ равно . Таким образом, .

Примитивная рекурсия. Рассмотрим для простоты случай n=1. Пусть функция F²(x₁,y) получена с помощью оператора примитивной рекурсии из функций g¹(x₁) и h³(x₁, y, z), т.е. F² =R(g¹,h³). Предположим, что существуют программы и , вычисляющие функции g¹ и h³ так, что и . Пусть вспомогательные переменные - это z₁,..., z_m и они не встречаются в , а переменные u₁, y₁ и v не используются в программах и . Рассмотрим программу P: пока v < y₁ делай z:=x₁; x₁:=u₁; y:=v; все В качестве входных переменных P возьмем x₁ и y, а выходной - x₁.

Рассмотрим работу P на исходном состоянии в котором . При b=0 цикл не выполняется и в результирующем состоянии имеем . При b > 0 цикл будет выполняться b раз, так как в его теле v всякий раз увеличивается на 1, а значение y₁=b и не меняется. Перед первым выполнением все ее рабочие переменные z_i равны 0, x₁=a, y=0, z=F²(a, 0), а после ее выполнения x₁=h³(a,0,F(a,0))=F(a,1). Предположим теперь по индукции, что перед (i+1) -ым выполнением все ее рабочие переменные z_i равны 0, x₁=a, y=i и z=F²(a, i). После этого выполнения x₁=h³(a,i,z)=h³(a,i,F(a,i))=F(a,i+1). Тогда присваивания z₁:=0; ... ; z_m:=0; v:= v+1 после и z:=x₁; x₁:=u₁; y:=v; перед ее следующим выполнением установят значения переменных так, что все ее рабочие переменные z_i равны 0, x₁=a, y=i+1 и z=F²(a, i+1). Следовательно, после b -го выполнения тела цикла x₁=h³(a,b-1,F(a,b-1))=F(a,b).

Минимизация. Предположим, что функция Fⁿ(x₁,... ,x_n) получена с помощью оператора минимизации ( mu -оператора) из функции gⁿ⁺¹(x₁,..., x_n,y), т.е.

Пусть программа вычисляет gⁿ⁺¹, так что , и пусть рабочие переменные - это z₁,..., z_m. Зафиксируем переменные x₁',... , x_n', y';, u, z, не входяшие в . Рассмотрим следующую программу

Рассмотрим работу на входных значених x_i = a_i (i=1,...,n). В первой строке они сохраняются в переменных x'_i, которые нигде в не изменяются, z получает значение 0, которое тоже не меняется по ходу вычисления, а u вначале получает значение 1. Поэтому условие цикла после первой строки истинно и он хотя бы один раз выполняется. Докажем, что для каждого i >= 1, (i+1) -ая итерация цикла выполняется тогда и только тогда, когда g(a₁, ..., a_n,0)=b₁ >0, ..., g(a₁, ..., a_n, i-1)=b_i-1 > 0, останавливается после (i+1) -ой итерации цикла с результатом x₁=i тогда и только тогда, когда g(a₁, ..., a_n,i)=0. При этом перед выполнением входные переменные x₁,...,x_n,y имеют значения a₁,...,a_n, i, соответственно, y'= i, а все рабочие переменные z_j (j=1,..., m) равны 0.

Действительно, предположив это условие, получим, что после очередного выполнения фрагмента

значение u = x₁ = g(a₁,...,a_n,i), а рабочие переменные восстанавливают нулевые значения. Если g(a₁,...,a_n,i)=0, то u=z и в условном операторе x₁ получает значение y'=i. После этого условие цикла нарушено и завершает работу с выходным значением x₁=i =F(a₁,..., a_n). Если же g(a₁,...,a_n,i)> 0, то u>z и в условном операторе y' увеличивает значение до (i+1). Тогда условие цикла выполнено и перед (i+2) -ым выполнением ее входные переменные x₁,...,x_n,y имеют значения a₁,...,a_n, i+1, соответственно, y'= i+1, а все рабочие переменные равны 0.

Из доказанного утверждения непосредственно следует, что

Имеет место и утверждение, обратное теореме 8.1, которое мы приводим здесь без доказательства.

Теорема 8.2. Каждая программно вычислимая функция является частично рекурсивной.

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

Лемма 8.1. Рекурсивность табличных функций. Пусть всюду определенная функция f(x) на всех аргументах, кроме конечного числа, равна некоторой константе c (такую функцию назовем табличной). Тогда она является примитивно рекурсивной.

Доказательство Пусть для функции f из условия леммы . Доказательство проведем индукцией по n_f.

При n_f=0 функция f является постоянной и поэтому примитивно рекурсивной (пример 8.1).

Предположим что все табличные функции g со значением n_g <= k примитивно рекурсивны и пусть n_f = k +1 и f(0)=a. Определим табличную функцию f^'(x) = f(x+1). Ясно, что n_f' = k, и по предположению индукции f^' примитивно рекурсивна. Легко проверить, что тогда f задается следующей схемой:

и, следовательно, также примитивно рекурсивна.

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

Лемма 8.2. Суммирование и произведение. Пусть функция f(x₁,..., x_n, y) является частично (примитивно) рекурсивной. Тогда и функции Fⁿ⁺¹ и Gⁿ⁺¹, заданные следующими равенствами

является частично (примитивно) рекурсивными.

Доказательство Действительно, эти функции задаются следующими примитивно рекурсивными схемами:

Приведем примеры использования леммы 8.2.

Пример 8.10. max_deg_div(x,y) = максимальная степень x, на которую нацело делится y.

Пусть exp(x,y) - экспоненциальная функция: exp(x,y) = x^y. Ее примитивную рекурсивность легко установить, используя функцию умножения (см. задачу 8.1 (а) ). Тогда нетрудно проверить, что искомая функция задается соотношением

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

Пример 8.11. Ограниченная минимизация. Пусть примитивно рекурсивная функция g(x,y) такова, что для каждого x найдется y <= x, для которого g(x,y) =0. Положим F(x) = mu y [g(x,y) = 0].

Тогда, по определению, F(x) является частично рекурсивной функцией. Покажем, что, на самом деле, она примитивно рекурсивна. Действительно, определим . По лемме 8.2 эта функция примитивно рекурсивна. Пусть для данного x . Тогда при i < y₀ имеем h(x,i) = 1, а при i >= y₀ h(x,i) =0. Поэтому искомая функция F задается равенством и также является примитивно рекурсивной.

Лемма 8.3. Кусочное задание или разбор случаев. Пусть h₁(x₁,...,x_n), ..., h_k(x₁,...,x_n) - произвольные ч.р.ф., а всюду определенные ч.р.ф. f₁(x₁,...,x_n), ..., f_k(x₁,...,x_n) таковы, что на любом наборе аргументов (a₁, ..., a_n) одна и только одна из этих функций равна 0. Тогда функция g(x₁,..., x_n), определенная соотношениями:

является частично рекурсивной.

Доказательство Действительно, gⁿ можно представить как сумму k произведений:

Следующий класс функций, который нас будет интересовать, - это функции для однозначной нумерации пар и n-ок целых чисел и обратные им. Определим для любой пары чисел (x,y) ее номер c₂(x,y)=2^x(2y+1) - 1. Например, c₂(0,0)=0, c₂(1,0)=1, c₂(0,1)=2, c₂(1,1)=5, c₂(2,1)= 19. Из единственности разложения чисел на простые множители следует, что функция c₂: N² -> N взаимно однозначно нумерует пары целых чисел. Нетрудно понять, что если c₂(x,y) = z, то двоичная запись числа (z+1) имеет следующий вид: (двоичная запись y ) 10^x. Из такого представления можно однозначно извлечь значение x и значение y. Эти значения определяются следующими обратными функциями:

Из этих определений непосредственно следует, что для любого z выполнено равенство c₂(c₂₁(z), c₂₂(z))=z.

Определим теперь по индукции функции c_n нумерации n-ок чисел при n > 2 и обратные им координатные функции c_ni (1 <= i <= n):

Из этих определений также непосредственно следует, что для любого z имеет место равенство c_n(c_n1(z), c_n2 (z),..., c_nn (z))=z. (Проверьте это свойство индукцией по n.)

Лемма 8.4. Рекурсивность нумерационных функций. Для любых n >= 2 и 1 <= i <= n все определенные выше функции c_n и c_ni являются примитивно рекурсивными.

Доказательство Примитивная рекурсивность c₂(x,y) устанавливается непосредственно (см. задачу 8.1(а)). Функция c₂₁(z) задается равенством c₂₁(z)= max_deg_div(2,z+1) и является примитивно рекурсивной (это показано в примере 8.10). Для функции c₂₂(z) справедливо определение c₂₂(z) = div(2, div(2 ^c21(z)}, z+1) - 1) (здесь мы используем примитивную рекурсивность функции целочисленного деления div(x,y) из задачи 8.1(e)). Примитивная рекурсивность остальных нумерационных функций следует по индукции из их определений (см. задачу 8.10).

В следующей лемме обобщается оператор примитивной рекурсии.

Лемма 8.5. (совместная рекурсия) Пpедположим, что фyнкции и фyнкции пpимитивно pекypсивны. Тогда фyнкции f₁ⁿ⁺¹(x₁, ..., x_n, y), ..., f_kⁿ⁺¹(x₁, ..., x_n, y), опpеделяемые следyющей совместной pекypсией

(1 <= i <= k) также являются пpимитивно pекypсивными.

Доказательство Обозначим чеpез набоp пеpеменных x₁,...,x_n. Опpеделим следyющие пpимитивно pекypсивные фyнкции: , , и положим

Фyнкция Fⁿ⁺¹ полyчена пpимитивной pекypсией из пpимитивно pекypсивных фyнкций и, следовательно, сама пpимитивно pекypсивна. Спpаведливость леммы тепеpь следyет из того, что для всякого .

Задача 8.1. Показать, что следующие функции являются частично (примитивно) рекурсивными.

• exp(x,y) = x^y ;
• fact(x) = x ,!;
• min(x,y)= наименьшее из x и y ;
• max(x,y)= наибольшее из x и y ;
• div(x,y)= частное от деления y на x (пусть div(0,y)=y ).

• предикаты равенства и неравенства:

  
• .

Задача 8.2. Докажите, что если f(x₁,...,x_n) является ч.р.ф. (п.р.ф.), то и функция g(x₁,...,x_n)=f(x_{i₁},...,x_in) является ч.р.ф. (п.р.ф.) для любой перестановки (i₁, ..., i_n) чисел 1,2,...,n.

Задача 8.3. Оператор сдвига. Пусть g(x₁,..., x_n) - частично (примитивно) рекурсивная функция, a и b >0 - числа из N. Тогда и функция

является частично (примитивно) рекурсивной.

Задача 8.4. Показать, что следующие функции являются частично ( примитивно) рекурсивными.

• - корень n -ой степени из x (целая часть).
• (пусть при или x= 0 log(i,x) =0 ).
• p(x)=1, если x - простое число, и p(x)=0, если x составное.
• pn(k) - k -ое простое число в порядке возрастания (pn(0)=0, pn(1)=2, pn(2)=3, pn(3)=5...).
• t(x) = число pазличных делителей числа x (t(0)=0).
• d(n,m,i) - i -ый знак в m -ичном разложении числа n, т.е. если , где 0 <= a_i <= m-1, то d(n,m,i)=a_i.
• nod(x, y)= наибольший общий делитель чисел x и y (пусть nod(0,y)=nod(x,0) =0 ).

Задача 8.5. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) ( элементы последовательности F(x) называются числами Фибоначчи). Покажите, что функция F(x) примитивно рекурсивна.

(Указание: покажите сначала, что функция g(x)= 2^F(x) 3^F(x+1) примитивно рекурсивна.)

Задача 8.6. Докажите, что если значения общерекурсивной функции f(x) изменить на конечном множестве, то получившаяся функция f^'(x) также будет общерекурсивной.

Задача 8.7. Доказать, что из функции o(x)=0 и из функций выбора I_mⁿ(x₁,...,x_n)=x_m с помощью суперпозиции и примитивной рекурсии нельзя получить функцию s(x)=x+1 и функцию d(x) =2*x.

Задача 8.8. Пусть g(x₁,...,x_n,y) - примитивно рекурсивна. Доказать, что функция

примитивно рекурсивна.

Задача 8.9. Доказать, что если функции f(x₁,...,x_n,y), g(x₁,...,x_n,y) и h(x₁,..., x_n,y) частично рекурсивны, то и функция

является частично рекурсивной.

Задача 8.10. Докажите, что определенные выше функция нумерации n -ок c_n(x₁, ... , x_n) и обратные ей функции выбора i -го элемента набора c_ni(z) (1 <= i <= n) являются примитивно рекурсивными.

Задача 8.11. Предположим, что все пары (x,y) натуральных чисел упорядочены по возрастанию суммы (x+y), а внутри группы пар с одинаковой суммой - по возрастанию x -координаты. Этот порядок выглядит так: (0,0), (0,1), (1,0),(0,2),(1,1), (2,0),... , (0,x+y), (1, x+y-1), ... , (x,y), ... , (x+y, 0), ... . Пусть d(x,y) - это номер пары (x,y) в этом порядке (будем считать, что пара (0,0) имеет номер 0). Тогда функция d² однозначно нумерует все пары.

• Докажите, что .
• Найдите обратные функции d₁(z) и d₂(z) такие, что d₁(d(x,y))=x, d₂(d(x,y))= y и, следовательно, d(d₁(z), d₂(z))=z.

Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеров¹⁾ Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.

Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигается головка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемся вычислении используется только конечная часть этой памяти - конечное число ячеек. В каждой ячейке ленты записан один символ из конечного внешнего алфавита машины . Головка машины представляет конечный автомат, который в каждый момент времени находится в одном из внутренних состояний Q ={q₀,q₁,... , q_n }. На каждом шаге головка в зависимости от своего внутреннего состояния и символа в ячейке, которую она наблюдает, изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки и может сдвинуться на одну ячейку вправо или влево либо остаться на месте.

Дадим более формальное определение.

Определение 9.1. Машина Тьюринга - это система вида

включающая следующие компоненты:

• Q ={q₀,q₁,... ,q_n } - внутренний алфавит (алфавит состояний);
• - внешний алфавит (алфавит ленты );

• P - программа машины, в которой для каждой пары имеется (одна!) команда вида

  

  задает сдвиг головки вправо, влево или на месте;

• - начальное состояние;
• - заключительное состояние.

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

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

Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n x m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита в которой на пересечении строки q_i и столбца a_j стоит тройка q_k a_l C - правая часть команды q_i a_j -> q_k a_l C.

Определение 9.2. Назовем конфигурацией м.Т. в некоторый момент времени слово K= w_л q_i a_j w_п, где - слово на ленте левее текушего положения головки, q_i - внутреннее состояние в данный момент, a_j - символ, обозреваемый головкой, - слово на ленте правее текушего положения головки.

Будем считать, что слово w_л a_j w_п содержит все значащие символы на ленте. Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если , т.е. пусто, то левее положения головки все ячейки пусты, а если , то правее положения головки все ячейки пусты.

Начальная конфигурация - это конфигурация вида q₀w, т.е. в начальный момент времени головка в состоянии q₀ обозревает первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w₁ q_f w₂, в которой машина находится в заключительном состоянии q_f.