[ «Н. Т. Когабаев ЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВ Учебное пособие Новосибирск 2009 УДК 510.5(075) ББК В12я73-1 К 570 Когабаев Н. Т. Лекции по теории алгоритмов: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2009. 107 с. ...»
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Механико-математический факультет
Н. Т. Когабаев
ЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВ
Учебное пособие
Новосибирск
2009
УДК 510.5(075)
ББК В12я73-1
К 570
Когабаев Н. Т. Лекции по теории алгоритмов: Учеб. пособие / Новосиб. гос.
ун-т. Новосибирск, 2009. 107 с.
ISBN 978-5-94356-799-5 В настоящем учебном пособии изложены математические основы теории алгоритмов. Пособие отражает содержание лекций основного курса Теория алгоритмов, прочитанных автором для студентов 1-го курса механико-математического факультета НГУ и охватывает материал из нескольких областей математики, так или иначе связанных с понятием алгоритма: теория автоматов и регулярных языков, машины Тьюринга и Шёнфилда, нормальные алгорифмы Маркова, классическая теория вычислимости, теория нумераций, теория сложности вычислений.
Предназначено для студентов 1-го курса механико-математического факультета НГУ, изучающих курс Теория алгоритмов, а также для всех желающих познакомиться с основами упомянутых в пособии математических теорий.
Рецензент канд. физ.-мат. наук В. Н. Власов Издание подготовлено в рамках выполнения инновационно-образовательной программы Инновационные образовательные программы и технологии, реализуемые на принципах партнерства классического университета, науки, бизнеса и государства национального проекта Образование.
c Новосибирский государственный университет, c ISBN 978-5-94356-799-5 Когабаев Н. Т., Оглавление Глава I. Предварительные сведения § 1. Некоторые аксиомы теории множеств.................... § 2. Алфавиты и формальные языки....................... § 3. Интуитивные свойства алгоритмов..................... Глава II. Конечные автоматы и формальные грамматики § 4. Детерминированные конечные автоматы.................. § 5. Недетерминированные конечные автоматы................. § 6. Свойства автоматных языков........................ § 7. Регулярные языки............................... § 8. Определение формальных грамматик.................... § 9. Свойства формальных грамматик...................... Глава III. Формализации понятия вычислимой функции § 10. Машины Шёнфилда.............................. § 11. Частично рекурсивные функции....................... § 12. Рекурсивность некоторых функций и отношений............. § 13. Кодирование машин Шёнфилда....................... § 14. Машины Шёнфилда vs Частично рекурсивные функции......... § 15. Машины Тьюринга.............................. § 16. Нормальные алгорифмы Маркова...................... § 17. Тезис Чёрча.................................. Глава IV. Теория вычислимости § 18. Теорема о неподвижной точке........................ § 19. Нумерации и алгоритмические проблемы.................. § 20. Вычислимо перечислимые множества.................... § 21. Универсальные функции........................... § 22. Единственность сильно универсальной функции............. Глава V. Теория сложности алгоритмов § 23. О вычислительной сложности........................ § 24. Недетерминированные машины Тьюринга................. § 25. Классы P и NP................................. § 26. NP-полные проблемы............................. § 27. Теорема Кука.................................. Список литературы Глава I Предварительные сведения § 1. Некоторые аксиомы теории множеств Все объекты, изучаемые в данном курсе, являются множествами. Множествами являются символы, алфавиты и языки. Множествами являются числа, кортежи и последовательности. Множествами являются предикаты, функции и операторы. Даже автоматы, машины и алгоритмы, изучению которых посвящен настоящий курс, являются множествами.
Для работы с множествами и формализации определенных понятий нам потребуются некоторые аксиомы теории множеств Цермело-Френкеля ZF. Теория ZF является формальной (синтаксической) теорией в языке с одним символом двухместного предиката и символом равенства. Однако мы будем формулировать понятия и аксиомы данной теории на естественном (общематематическом) языке. Подобная нестрогость не должна пугать читателя, поскольку при желании все формулировки можно перевести на формальный язык ZF, но в рамках данного курса в этом нет необходимости. Для более глубокого и подробного ознакомления с системой ZF можно порекомендовать книги [2], [3].
Понятия множества и отношения принадлежности являются неопределяемыми через другие математические объекты. Неформально множество это некоторая совокупность объектов A, отношение x A означает, что объект x является элементом совокупности A. Мы также будем использовать термины семейство и совокупность для описания некоторых множеств.
Определение. Говорят, что множество A является подмножеством множества B, и пишут A B, если x(x A x B). Другими словами, A B, если каждый элемент множества A является элементом множества B.
Равенство двух множеств A и B определяется следующей аксиомой.
Аксиома экстенсиональности: A = B тогда и только тогда, когда x(x A x B). Таким образом, множества A и B равны, если A B и B A.
Следующая естественная аксиома постулирует существование наименьшего по включению множества.
Аксиома пустого множества: существует пустое множество, т. е. множество, не содержащее ни одного элемента.
Следующие четыре аксиомы позволяют из одних множеств строить другие, более сложные по своей структуре.
Аксиома пары: если A и B множества, то существует неупорядоченная пара {A, B}, составленная из этих множеств.
Аксиома суммы: если A множество, то существует множество A = {x | x y для некоторого y A}, которое называется объединением множества A.
Аксиома степени: если A множество, то существует множество P (A) = {B | B A} всех подмножеств множества A.
Аксиома подстановки: если A множество, а (x, y) некоторое условие на множества x, y такое, что для любого x существует не более одного y, удовлетворяющего условию (x, y), то существует множество {y | (x, y) для некоторого x A}.
Например, из аксиомы пустого множества, аксиомы пары и аксиомы суммы следует, что существуют множества, {}, {, {}}, {, {}, {, {}}} и т. д. (каждое следующее состоит из всех предыдущих), эти множества мы будем называть натуральными числами и обозначать их соответственно через 0, 1, 2, 3 и т. д.
Заметим, что используя только те пять аксиом существования, которые сформулированы выше, можно получить лишь конечные множества. В частности, из этих пяти аксиом невозможно вывести, что совокупность всех натуральных чисел образует множество. Для разрешения этого вопроса вводится следующая Аксиома бесконечности: существует множество = {0, 1, 2, 3,...} всех натуральных чисел.
Теперь, располагая каноническим бесконечным множеством, можно строить другие бесконечные множества. В следующем определении вводятся стандартные теоретико-множественные операции объединения, пересечения, разности и дополнения (до некоторого множества).
Определение. Если A и B множества, то их объединением называется множество B}, разностью множество A \ B = {x | x A и x B}.
Если рассматриваемые множества являются подмножествами некоторого фиксированного множества U, то можно говорить о дополнении A = U \ A множества A (до множества U ).
Объединением семейства множеств A называется множество A = {x | B A(x B)}. Пересечением непустого семейства множеств A называется множество Из перечисленных выше аксиом следует, что применяя эти операции к множествам, мы снова получаем множества. Например, если A, B множества, то в силу аксиомы пары существует неупорядоченная пара {A, B}, а в силу аксиомы суммы существует объединение A B = {A, B}. Затем, используя аксиому подстановки, заключаем, что существует пересечение A B = {y | (y A и y B и y = x) для некоторого x A B}.
Аксиома пары постулирует существование множества {a, b}. Однако порядок расположения элементов в паре формально никак не задается, поскольку {a, b} = {b, a}.
Более того, если a = b, то пара {a, b} превращается в одноэлементное множество {a}.
Чтобы все-таки упорядочить элементы пары, вводится следующее Определение. Упорядоченной парой элементов a и b называется множество a, b = {{a}, {a, b}}. В упорядоченной паре мы задаем строгий порядок расположения элементов: a первый, b второй. Следует различать a, b = {a, b}!
Предложение 1. Для любых элементов a, b, c, d имеет место: a, b = c, d тогда и только тогда, когда a = c и b = d.
Доказательство. Предлагается читателю в качестве упражнения.
Определение. Пусть n, n 1. Упорядоченная n-ка (кортеж длины n) определяется по индукции: a1 = a1, a1,..., an1, an = a1,..., an1, an.
Пустое множество по определению называем кортежем длины 0.
Следствие 2. a1,..., an = b1,..., bn тогда и только тогда, когда имеет место Доказательство. Следует из предыдущего предложения по индукции.
Определение. Декартовым произведением множеств A1,..., An называется множество n-ой декартовой степенью множества A называется множество An = A... A.
При n = 0 по определению полагаем A0 = {}.
Определение. Любое подмножество R A1... An называется отношением (предикатом) на множествах A1,..., An. Если x1,..., xn R, то говорят, что предикат R истиннен на элементах x1,..., xn, и пишут R(x1,..., xn ), иначе говорят, что предикат R ложен на элементах x1,..., xn, и пишут ¬R(x1,..., xn ).
Любое подмножество R An называется n-местным отношением (предикатом) на множестве A.
Определение. Композицией отношений R1 A B и R2 B C называется отношение R1 R2 = { a, c | b( a, b R1 и b, c R2 )}.
Определение. Обратным отношением к отношению R A B называется отношение R1 = { b, a | a, b R}.
Определение. Отношение f A B называется функцией (отображением), если для любого a A существует не более одного b B такого, что a, b f.
Для данного a A, если существует b B со свойством a, b f, то говорят, что значение f (a) определено и равно b, и пишут f (a), в противном случае говорят, что значение f (a) не определено, и пишут f (a).
Областью определения f называется множество dom(f ) = {a A | f (a) }.
Областью значений f называется множество range(f ) = {f (a) | a A, f (a) }.
Определение. Запись f : A B означает, что для некоторых множеств X, Y отношение f X Y является функцией такой, что dom(f ) = A и range(f ) B. При этом говорят, что f является функцией из A в B.
Определение. Говорят, что функция f : A B является инъективной (разнозначной), и пишут f : A B, если для любого b B существует не более одного a A такого, что f (a) = b.
Определение. Говорят, что функция f : A B является сюръективной (отобрана жением на), и пишут f : A B, если range(f ) = B.
Определение. Говорят, что функция f : A B является биективной (взаимнооднозначной), и пишут f : A B, если f одновременно инъективна и сюръективна.
Определение. Если f AB, g BC функции, то их композиция f g AC определяется как композиция отношений. Легко видеть, что f g тоже является функцией.
Определение. Если f : A B f определяется как обратное отношение. Легко видеть, что f 1 является биекцией Определение. Функция вида f : X A, где X An называется n-местной частичной функцией на A.
Замечание. Заметим, что существуют только два вида 0-местных частичных функций это либо нигде не определенная функция f =, либо функция вида f = {, a } для некоторого a A. Во втором случае мы будем называть функцию константой и отождествлять ее с элементом a, т. е. f = a.
§ 2. Алфавиты и формальные языки В большинстве случаев данные, с которыми работают алгоритмы, представляются в виде слов некоторого языка. Алгоритмы подобного вида можно назвать словарными.
Например, все алгоритмы из следующей главы безусловно являются словарными.
Более того, описание самих алгоритмов, как правило, осуществляется с помощью специального текста, который обычно называют программой.
Понятия слова, языка и текста имеют очень широкий спектр значений, выходящий за рамки математической науки. Мы будем работать только с формальными языками, т. е. с языками, которые поддаются формальному описанию в рамках теории множеств и которые можно изучать, используя строгие математические методы.
Определение. Алфавитом будем называть любое непустое конечное множество A = {a0,..., an }. Элементы алфавита принято называть буквами, или символами.
Определение. Словом длины n в алфавите A мы будем называть любой кортеж a1, a2,..., an длины n, где a1,..., an буквы алфавита A. Слова обычно записывают в виде a1 a2... an. Пустое слово не содержит ни одной буквы, имеет длину и обозначается через.
Замечание. В дальнейшем запись слова в виде a1 a2... an подразумевает, в частности, что при n = 0 это слово пусто. Это же соглашение распространяется на конечные кортежи и конечные множества, т. е. a1,..., an = {a1,..., an } = при n = 0.
Определение. Множество всех слов в алфавите A, включая пустое слово, обозначается через A. Множество всех непустых слов в алфавите A обозначается через A+, т. е. A+ = A \ {}.
Определение. Длина слова w A обозначается через |w|.
Определение. Слово u называется подсловом слова v, если существуют слова w и w2 такие, что v = w1 uw2, при этом вхождением подслова u в слово v назовем упорядоченную тройку w1, u, w2. Отметим, что одно и то же слово u может иметь несколько различных вхождений в слово v.
Определение. Слово u называется префиксом слова v, если v = uw для некоторого слова w. Слово u называется суффиксом слова v, если v = wu для некоторого w.
Определение. Введем следующие операции над словами в алфавите A:
(а) Конкатенацией слов u и v называется слово uv, полученное приписыванием к слову u слова v справа.
(б) Степень слова u определяется индукцией по n следующим образом: u0 =, un+1 = un u.
(в) Обращением слова u = a1 a2... an, где a1, a2,..., an буквы алфавита A, называется слово uR = an... a2 a1.
Пример. Конкатенацией слов kein и mehrheit является слово keinmehrheit. Если теперь взять конкатенацию тех же слов, но в другом порядке, то получится слово mehrheitkein. Слово ei является подсловом слова keinmehrheit, причем оно имеет два вхождения: первое вхождение начинается со 2-го символа слова, а второе с 10-го символа. Обращением слова mehrheit будет слово tiehrhem. Степенями слова kein являются слова, kein, keinkein, keinkeinkein и т. д. При этом каждое слово из данной последовательности является префиксом всех последующих слов.
Определение. Любое подмножество L A называется формальным языком над алфавитом A.
Определение. Введем следующие операции над языками в алфавите A:
(а) Объединение L1 L2 и пересечение L1 L2 языков L1 и L2 определяются как обычные теоретико-множественные объединение и пересечение.
(б) Дополнением языка L называется язык L = A \ L.
(в) Конкатенацией языков L1 и L2 называется язык L1 L2 = {uv | u L1, v L2 }.
(г) Степень языка L определяется индукцией по n следующим образом: L0 = {}, Ln+1 = Ln L.
(д) Звездочкой Клини от языка L называется язык L = Ln. Другими словами, В частности, всегда имеет место L (при n = 0).
Замечание. Заметим, что определение звездочки Клини согласуется с введеным выше обозначением A. Звездочка Клини от алфавита это и есть множество всех слов в данном алфавите.
Пример. С помощью введенных операций можно определять формально те языки, которые изначально имеют неформальное описание.
Например, язык всех слов в алфавите A = {a, b}, имеющих хотя бы одно вхождение буквы a, совпадает с языком {b} {a}{a, b}. Действительно, в любом таком слове можно выделить первое вхождение буквы a, т. е. представить в виде bn aw, где n, w некоторое слово в алфавите A. С другой стороны, любое слово вида bn aw лежит в языке {b} {a}{a, b}.
Другой пример это язык всех слов четной длины в том же алфавите, который можно представить как {aa, ab, ba, bb}. Действительно, слово w имеет четную длину тогда и только тогда, когда его можно представить в виде w = w1... wn для некоторого n и некоторых слов wi, каждое из которых имеет длину 2, т. е. каждое wi {aa, ab, ba, bb}.
Отсюда следует, что язык всех слов нечетной длины можно получить как дополнение предыдущего языка, т. е. {a, b} \ {aa, ab, ba, bb}, а язык всех слов четной длины, содержащих букву a, можно получить, используя операцию пересечения ({b} {a}{a, b} ) {aa, ab, ba, bb}.
Язык всех слов четной длины, содержащих букву a, можно получить и другим способом, а именно как язык {bb} {aa, ab, ba}{aa, ab, ba, bb}.
§ 3. Интуитивные свойства алгоритмов древних времен. Однако до определенного времени алгоритмы возникали лишь при описании алгоритмических решений вполне конкретных математичеких задач. При этом автор решения в 10 18 17 16 явном виде предъявлял описание своего алгоритма и доказывал, что его алгоритм приводит к T верному результату. Этого было достаточно, чтобы по достоинству оценить новый математичеc ский результат. Но позднее, ближе к эпохе современности, в различных областях математики относительно которых предполагалось, что они не имеют алгоритмического решения.
Чтобы формально доказывать такие гипотезы, естественно, потребовалось более общее, формальное описание понятия алгоритма.
Прежде чем вводить формальные определения различных алгоритмических систем, мы попытаемся выявить с интуитивной точки зрения те характерные черты, которыми обладают алгоритмы. В дальнейшем мы убедимся в том, что все существующие подходы к формализации понятия алгоритма удовлетворяют этим свойствам.
Это наблюдение будет служить подтверждением того, что данные подходы являются естественными и адекватными.
Чтобы наши интуитивные рассуждения были более наглядными, рассмотрим следующую несложную задачу, имеющую алгоритмическое решение.
Пример. На плоскости задан прямоугольник, разбитый на одинаковые клетки со стороной единичной длины. Некоторые клетки заштрихованы это стены, остальные клетки это коридоры. Таким образом, у нас задан лабиринт, вход которого находится в правой нижней клетке, а выход в левой верхней (выход помечен символом, см. рисунок). В начальный момент времени на входной клетке находится робот Бендер, который умеет отличать стены от коридоров, умеет делать ходы на одну соседнюю незаштрихованную клетку сверху, справа, снизу или слева, умеет принимать простейшие логические решения, и способен распознать символ. Заранее известно, что в таком лабиринте существует как минимум один путь, ведущий по коридорам из входа в выход. Необходимо запрограммировать Бендера так, чтобы он, руководствуясь данной программой несложных операций, смог найти выход из лабиринта.
Для этого мы зарезервируем достаточно большое количество меток, занумерованных натуральными числами. Этими метками Бендер будет помечать свои ходы.
Искомая программа состоит из следующих шести пунктов:
0) Помечаем правую нижнюю клетку меткой 0. Переходим к пункту (1).
1) Проверяем, верно ли, что клетка, на которой стоит Бендер, является выходом.
Если это верно, то переходим к пункту (5). Если нет, переходим к пункту (2).
2) Проверяем, существует ли хотя бы одна непомеченная соседняя (сверху, справа, снизу или слева) клетка. Если существует, то переходим к пункту (3). Если нет, то переходим к пункту (4).
3) Выбираем каким-нибудь эффективным способом одну соседнюю непомеченную клетку. Например, можно выбирать первую непомеченную клетку при обходе всех четырех соседних клеток по часовой стрелке, начиная с верхней. Помечаем выбранную клетку наименьшей неиспользованной меткой. Затем передвигаем Бендера на эту клетку и переходим к пункту (1).
4) Возвращаемся на один ход назад, т. е. передвигаем Бендера обратно на ту клетку, с которой он в последний раз перешел на текущую клетку. Переходим к 5) Работа алгоритма останавливается. Выход из лабиринта найден. Таким образом, задача решена.
Данный алгоритм всегда приводит к нахождению выхода из лабиринта. Действительно, если бы алгоритм не приводил к успеху, то это означало бы, что Бендер, проделав определенное число ходов и расставив метки от 0 до некоторого n, вернулся бы на исходную позицию, т. е. в правый нижний угол. Но тогда искомый путь, который тоже начинается в правом нижнем углу, полностью содержался бы в множестве помеченных клеток. В частности, левая верхняя клетка тоже была бы помечена Бендером, а значит, он побывал бы на ней в процессе своего блуждания по лабиринту, но вернулся назад. Последнее невозможно в силу пункта (5) из описания алгоритма.
Анализируя свойства алгоритма из данного примера, выделим теперь следующие Основные черты алгоритмичеких процессов:
а) Конечность описания любой алгоритм задается как набор инструкций конечных размеров, т. е. программа имеет конечную длину. В нашем примере описание алгоритма состоит из 6 пунктов, каждый из которых записан с помощью конечного числа слов.
б) Дискретность алгоритм исполняется по шагам, происходящим в дискретном времени. Шаги четко отделены друг от друга. В алгоритмах нельзя использовать аналоговые устройства и непрерывные методы. В нашем примере один шаг работы алгоритма это выполнение одного из пунктов (0)–(5), эти шаги можно занумеровать натуральными числами. В итоге Бендер проделывает всегда лишь конечное число шагов для того, чтобы найти выход (хотя в общем случае допускается бесконечное количество шагов, т. е. алгоритмы могут не останавливаться).
в) Направленность у алгоритма есть входные и выходные данные. В алгоритме четко указывается, когда он останавливается, и что выдается на выходе после остановки. В нашем примере входные данные это схема лабиринта, выходные данные путь по коридорам, ведущий к выходу.
г) Массовость алгоритм применим к некоторому достаточно большому классу однотипных задач, т. е. входные данные выбираются из некоторого, как правило, бесконечного множества. В нашем примере один и тот же алгоритм годится для поиска выхода из любого лабиринта прямоугольной формы, а не только для того лабиринта 8 8, который изображен на рисунке.
д) Детерминированность (или конечная недетерминированность) вычисления продвигаются вперед детерминированно, т. е. вычислитель однозначно представляет, какие инструкции необходимо выполнить в текущий момент. Нельзя использовать случайные числа или методы. Конечная недетерминированность означает, что иногда в процессе работы алгоритма возникает несколько вариантов для дальнейшего хода вычислений, но таких вариантов лишь конечное число. В нашем примере действия Бендера детерминированны, но этот алгоритм можно переделать и в недетерминированный, если предоставить Бендеру свободу самостоятельного выбора клетки в пункте (3). При этом, поскольку этот выбор конечен (соседних клеток всего четыре), можно представить дальнейшие действия Бендера в виде распределенных (параллельных) вычислений:
в момент выбора Бендер создает несколько своих клонов, и каждый клон идет по своему пути, руководствуясь теми же пунктами (0)–(5). Если хотя бы один из клонов находит выход, то задача считается решенной.
Глава II Конечные автоматы и формальные грамматики § 4. Детерминированные конечные автоматы Конечные автоматы относятся к классу словарных алгоритмов. С помощью конечных автоматов можно решать задачи из достаточно широкого семейства алгоритмических проблем. Например, технология проектирования микросхем основана на результатах теории автоматов. Другой пример это компиляторы, перерабатывающие текст программы, написанной на языке программирования высокого уровня, в программу на машинном языке. Работа любого такого компилятора состоит из двух стадий. Первая стадия лексический анализ текста, который реализуется с помощью определенного конечного автомата. Вторая стадия синтаксический анализ, который осуществляется с помощью автомата с магазинной памятью. Однако, как будет видно позднее, не любая алгоритмическая задача поддается решению с помощью конечного автомата.
Дадим сначала неформальное определение конечных автоматов и описание их работы.
Входными данными любого конечного автомата являются слова в некотором заранее фиксированном алфавите, выходными данными являются две логические константы true и false. В каждый момент времени автомат находится в определенном внутреннем состоянии. Число состояний автомата конечно. В начальный момент времени автомат находится в начальном состоянии. Кроме этого, некоторые состояния автомата считаются выделенными. Входное слово записывается на входной ленте, разбитой на ячейки: в каждой ячейке содержится одна буква слова. Автомат связан с лентой посредством специальной управляющей головки, которая последовательно считывает символы из ячеек, двигаясь слева направо. Очередной считанный символ отправляется в процессор, который по текущему состоянию и по данному считанному символу определяет новое состояние, в которое переводится автомат.
Функция, вычисляющая это новое состояние называется функцией перехода. Функция перехода расположена внутри процессора и не изменяется в ходе вычислений.
Считав все символы слова, автомат останавливается в определенном состоянии: если это состояние оказывается выделенным, то на выход подается константа true автомат распознал слово, в противном случае подается константа false автомат не распознал слово.
Уже из неформального определения видно, что конечные автоматы обладают такими интуитивными свойствами, как конечность описания, дискретность, направленность и массовость. Детерминированность также присутствует в данном описании: по текущему состоянию и считанному символу функция перехода однозначно определяет новое состояние. Отличительной чертой конечных автоматов является отсутствие памяти вне процессора, т. е. вся память автомата занята программой. Эта особенность позволяет пролить свет на причины неспособности конечных автоматов решить любую алгоритмически разрешимую задачу (для алгоритмов определенного вида необходима дополнительная память).
Теперь перейдем к формальным определениям в терминах теории множеств.
Определение. Детерминированным конечным автоматом (сокращенно д.к.а.) называется упорядоченная пятерка A = Q, A,, q0, F, состоящая из следующих объектов:
а) Q = {q0,..., qm } конечный алфавит внутренних состояний автомата;
б) A = {a0,..., an } конечный входной алфавит автомата;
г) q0 Q начальное состояние;
д) F Q множество выделенных (конечных) состояний.
Графическое изображение детерминированных автоматов Автоматы удобно изображать графически, используя следующие геометрические фигуры:
r i начальное состояние; i выделенное состояние;
i промежуточное состояние; r i i aE i такая дуга присутствует в автомате, если значение функции a такая петля присутствует в автомате, если значение функции Пример. Например, автомат A = Q, A,, q0, F, где A = {0, 1}, Q = {q0, q1, q2 }, F = {q2 }, а функция перехода задается соотношениями 14 Глава II. Конечные автоматы и формальные грамматики имеет следующее графическое изображение:
Определение. Путем в детерминированном конечном автомате A = Q, A,, q0, F назовем любую конечную последовательность r0, s1, r1,..., sk, rk, где r0,..., rk Q, автомате, то будем обозначать его через и говорить, что слово w = s1 s2... sk читается вдоль дуг данного пути. В частности, пустое слово читается вдоль пути r0, состоящего из одного состояния и не содержащего ни одной дуги.
Определение. Пусть A = Q, A,, q0, F д.к.а. Расширим функцию до функции : Q A Q следующим образом индукцией по длине слова:
Определение. Говорят, что д.к.а. A = Q, A,, q0, F распознает слово w A, если Другими словами, слово w = s1 s2... sk распознается автоматом, если в нем существует путь такой, что он начинается в начальном состоянии q0, вдоль его дуг читается слово s1 s2... sk (в детерминированном автомате такой путь определяется однозначно по слову w) и заканчивается в некотором выделенном состоянии.
Определение. Через T (A) = {w A | (q0, w) F } будем обозначать язык всех слов, распознаваемых конечным автоматом A.
Определение. Язык L A называется автоматным, если существует конечный автомат A такой, что L = T (A).
Пример (продолжение). Автомат из предыдущего примера распознает в точности все слова в алфавите {0, 1}, которые содержат подслово 11, т. е. T (A) = {w {0, 1} | w содержит подслово 11}. Действительно, начав чтение произвольного слова w в начальном состоянии данного автомата, попасть в выделенное состояние можно, только пройдя по дуге, ведущей из q0 в q1 (помеченной 1), а затем сразу же по дуге, ведущей из q1 в q2 (тоже помеченной 1), такое возможно лишь в случае, когда w содержит две единицы подряд.
§ 5. Недетерминированные конечные автоматы чтения символов, перейдя в любое из возможных состояний.
Можно считать, что в таких ситуациях работа автомата разветвляется на несколько параллельных ветвей вычислений, каждая из которых начинается с определенного состояния qi (q, a). Если (q, a) пусто, то работа автомата вдоль данной ветви вычислений заканчивается в состоянии q, даже если на входной ленте остались несчитанные символы. Таким образом, вдоль одних ветвей вычислений автомат может прочитать все входные символы и остановится в выделенном состоянии, вдоль других может прочитать все символы, но остановится в невыделенном состоянии, вдоль третьих ветвей работа автомата обрывается на полуслове.
Перейдем к формальным определениям, связанным с недетерминированными автоматами.
Определение. Недетерминированным конечным автоматом (сокращенно н.к.а.) называется упорядоченная пятерка A = Q, A,, q0, F, в которой Q, A, q0, F определяются и называются так же, как в детерминированном случае, а функция переходов является функцией вида : Q A P (Q), где P (Q) множество всех подмножеств Q (см. аксиому степени из § 1).
Графическое изображение недетерминированных автоматов При графическом изображении недетерминированных автоматов используются те же обозначения, что и в детерминированном случае. При этом из одного состояния автомата могут выходить сразу несколько (или нисколько) стрелок, помеченных одной и той же буквой алфавита. Дуга, выходящая из состояния q, входящая в состояние q, помеченная символом a, присутствует в схеме автомата тогда и только тогда, когда q (q, a).
Пример. Например, автомат A = Q, A,, q0, F, где A = {0, 1}, Q = {q0, q1, q2 }, F = {q2 }, а функция переходов задается соотношениями имеет следующее графическое изображение:
Определение. Путь в недетерминированном конечном автомате A= Q, A,, q0, F определяется и обозначается так же, как в детерминированном случае, нужно лишь условие (ri, si+1 ) = ri+1 заменить на условие ri+1 (ri, si+1 ).
16 Глава II. Конечные автоматы и формальные грамматики Определение. Говорят, что н.к.а. A= Q, A,, q0, F распознает слово s1 s2... sk A, если существует последовательность состояний q0 = r0, r1,..., rk такая, что и при этом rk F.
Другими словами, слово w = s1 s2... sk распознается автоматом, если в нем существует хотя бы один путь такой, что он начинается в начальном состоянии q0, вдоль его дуг читается слово s1 s2... sk (в недетерминированном автомате такой путь определяется неоднозначно по слову w) и заканчивается в некотором выделенном состоянии.
Определение. Как и раньше, через T (A) обозначается язык всех слов, распознаваемых автоматом A.
Пример (продолжение). Автомат из предыдущего примера распознает в точности все слова в алфавите {0, 1}, которые имеют суффикс 11, т. е. T (A) = {w {0, 1} | v {0, 1} (w = v11)}. Действительно, любой путь, заканчивающийся в выделенном состоянии данного автомата, обязан содержать участок q0 q1 q2. Отсюда следует, что слова, распознаваемые A, должны содержать хотя бы одно вхождение подслова 11. Поскольку из выделенного состояния нет выходящих стрелок, то любой путь, содержащий описанный выше участок, обрывается как раз после прохождения данного участка. Отсюда следует, что в словах, распознаваемых автоматом, после крайнего справа вхождения подслова 11 нет букв.
Теорема 3 (о детерминизации). Для любого недетерминированного конечного автомата A существует детерминированный конечный автомат A такой, что T (A) = T (A).
Доказательство. Пусть A = Q, A,, q0, F исходный н.к.а. Определим следующий д.к.а. A = Q, A,, q 0, F (см. пример на рисунке):
Докажем, что T (A) = T (A), показав два включения: T (A) T (A) и T (A) T (A).
Пусть слово w = s1... sk T (A). Следовательно, существуют такие состояния Иначе говоря, слово w читается вдоль дуг следующего пути в автомате A.
Подадим слово w на вход автомата A. Тогда он будет находиться в следующих состояниях:
10. Базис индукции очевиден: r0 = q0 {q0 } = q 0 = r0.
Что и требовалось доказать.
Итак, для любого i k выполняется ri ri. В частности, rk rk. Поскольку rk F, то rk F =. Следовательно, rk F. Отсюда заключаем, что w T (A), и значит включение T (A) T (A) доказано.
Пусть теперь слово w = s1... sk T (A), и пусть при чтении данного слова автомат A находился в состояниях причем последнее состояние rk F.
Так как rk rk = (rk1, sk ) = (r, sk ), то найдется rk1 rk1 такое, что rk (rk1, sk ).
Так как rk1 rk1, то аналогично находим rk2 rk2 такое, что выполняется rk1 (rk2, sk1 ).
И так далее.
В итоге получаем последовательность r0, r1,..., rk Q такую, что для каждого i {1,..., k} выполняется ri1 ri1 и ri (ri1, si ). Поскольку r0 r0 = q 0 = {q0 }, заключаем r0 = q0. Кроме этого, по построению rk F. Отсюда по определению следует, что w T (A). Таким образом, включение T (A) T (A) тоже доказано.
18 Глава II. Конечные автоматы и формальные грамматики Замечание. В заключение параграфа заметим, что в некоторых источниках (см., например, [4],[12]) используется другое определение недетерминированного конечного автомата, которое отличается от введенного выше тем, что функция переходов имеет вид : Q(A{}) P (Q). Автоматы данного типа называют автоматами с -переходами, поскольку в них допускаются дуги, помеченные пустым словом.
Наличие дуги, помеченной, выходящей из состояние q и входящей в состояние q, означает, что автомат, находясь в состоянии q, может перейти в состояние q, не считывая символа с ленты. Пользуясь терминами из программирования, можно сказать, что в такой ситуации автомат осуществляет безусловный переход из q в q.
Соответствующим образом изменяется и определение распознаваемости слова.
Слово w = s1 s2... sk, где si буквы алфавита, распознается автоматом с -переходами, если в нем существует хотя бы один путь такой, что он начинается в начальном состоянии r0, заканчивается в некотором выделенном состоянии rm, и вдоль его дуг читается слово t1 t2... tm = s1 s2... sk, причем m k, т. е. некоторые из символов t1,..., tm могут быть пустыми.
Такое определение удобно использовать при доказательстве некоторых свойств.
Однако добавление -переходов в определение недетерминированного автомата не расширяет класс автоматных языков, т. е. язык распознается некоторым недетерминированным конечным автоматом (согласно нашему определению) тогда и только тогда, когда он распознается некоторым недетерминированным конечным автоматом с -переходами. Таким образом, можно окончательно утверждать, что три различных подхода детерминированные автоматы, недетерминированные автоматы и недетерминированные автоматы с -переходами, эквивалентны.
§ 6. Свойства автоматных языков В данном параграфе мы докажем важные теоретико-множественные свойства автоматных языков, а также покажем, что существуют неавтоматные языки. Для этих целей нам понадобятся следующие определение и лемма.
Определение. Говорят, что д.к.а. A = Q, A,, q0, F обладает свойством вахтера, если для любых q Q, a A имеет место (q, a) = q0, т. е. автомат находится в начальном состоянии только в самом начале своей работы.
Лемма 4 (о вахтере). Для любого д.к.а. A = Q, A,, q0, F существует д.к.а. A = Q, A,, q0, F такой, что T (A) = T (A ) и A обладает свойством вахтера.
Доказательство. Мы дадим неформальное доказательство, описав процесс преобразования графической диаграммы автомата A в графическую диаграмму искомого автомата A (см. схему преобразования на рисунке):
а) Добавим в автомат A новое состояние q0. Если q0 было выделенным, то q0 тоже сделаем выделенным.
б) Для каждой стрелки из q0 в q1 = q0 добавим в автомат новую стрелку из q0 в q1 и пометим ее той же буквой.
в) Для каждой стрелки из q0 в q0 добавим в автомат новую стрелку из q0 в q0 и пометим ее той же буквой.
г) Перенаправим все стрелки, приходящие в q0 из q2 (включая стрелки из q0 в q0 ) так, чтобы они приходили из q2 в q0.
Построенный таким образом автомат обозначим как A = Q, A,, q0, F. Нетрудно видеть, что A детерминированный. В силу пункта (г) автомат A обладает свойством вахтера. Равенство T (A) = T (A ) следует из того, что если слово w A читается вдоль пути в автомате A, начинающегося в q0 и заканчивающегося в некотором r F, то, преобразовав этот путь в соответствии с пунктами (а)–(г), мы получим путь в автомате A, начинающийся в q0, заканчивающийся в некотором r F, вдоль которого читается то же самое слово w, и наоборот, если w читается вдоль пути в автомате A, начинающегося в q0 и заканчивающегося в некотором r F, то, сделав обратное преобразование, мы получим путь в автомате A, который начинается в q0, заканчивается в r F, и вдоль которого читается w.
Определение. Говорят, что подмножество X множества A замкнуто относительно операции f : An A, если для любых x1,..., xn X имеет место f (x1,..., xn ) X.
Теорема 5. Автоматные языки замкнуты относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини.
Доказательство. Для каждой из пяти операций мы неформально опишем, как по заданым автоматам, распознающим исходные языки, построить автомат, распознающий результат применения данной операции к исходным языкам. Заметим, что в силу теоремы 3 для каждого из случаев достаточно строить недетерминированный автомат.
Объединение. Пусть A1, A2 детерминированные конечные автоматы над алфавитом A. Нам необходимо определить автомат A такой, что T (A) = T (A1 ) T (A2 ).
В силу Леммы о вахтере можно считать, что A1 и A2 обладают свойством вахтера.
Кроме этого, можно считать, что множества состояний A1 и A2 не пересекаются, в противном случае следует переименовать состояния.
Автомат A строится следующим образом (см. схему построения на рисунке):
а) Соединим графические диаграммы автоматов A1 и A2 в одну диаграмму, отождествив их начальные состояния. Объявим полученное таким отождествлением состояние начальным в A. Поскольку множества состояний автоматов не пересекались, никакие другие состояния (кроме начальных) не склеиваются.
б) Множеством выделенных состояний A будет объединение множеств выделенных состояний автоматов A1 и A2.
в) Начальное состояние A будет выделенным тогда и только тогда, когда оно является выделенным хотя бы в одном из исходных автоматов.
20 Глава II. Конечные автоматы и формальные грамматики Такое описание полностью задает автомат A. Поскольку A1 и A2 обладают свойством вахтера, то любой путь по дугам автомата A, который начинается в начальном состоянии и заканчивается в выделенном состоянии, будет полностью расположен внутри A1 или внутри A2. Следовательно, любое слово, распознаваемое A, это слово, распознаваемое A1 или A2. С другой стороны, любое слово, распознаваемое A1 или A2, очевидно, распознается автоматом A. Таким образом, автомат A искомый.
Дополнение. Пусть д.к.а. A = Q, A,, q0, F распознает язык L, т. е. для любого слова w A имеет место эквивалентность w L (q0, w) F. Отсюда вытекает эквивалентность w L (q0, w) F. Другими словами, имеет место условие w A \ L (q0, w) Q \ F. Отсюда следует, что д.к.а A = Q, A,, q0, Q \ F распознает дополнение L = A \ L.
Пересечение. Замкнутость автоматных языков относительно пересечения следует из замкнутости относительно объединения и дополнения, а также из теоретикомножественного тождества A B = A B.
Конкатенация. Пусть A1, A2 детерминированные конечные автоматы над алфавитом A. Можно считать, что A2 обладает свойством вахтера. Построим автомат A, распознающий язык T (A1 )T (A2 ), следующим образом (см. схему построения на рисунке):
а) К каждому выделенному состоянию автомата A1 подвесим копию автомата A2, отождествив данное выделенное состояние с начальным состоянием копии. При этом считаем, что остальные состояния автоматов не склеиваются (этого можно добиться путем переименования состояний).
б) Начальным состоянием полученного автомата объявляется начальное состояние A1.
в) Выделенными состояниями полученного автомата объявляются все выделенные состояния всех копий автомата A2. Других выделенных состояний нет.
В силу Леммы о вахтере любой путь вдоль дуг нового автомата, начинающийся в начальном состоянии и заканчивающийся в выделенном состоянии, разбивается на два участка. Первый участок состоит только из дуг автомата A1 и заканчивается в одном из (бывших) выделенных состояний A1. Второй участок состоит только из дуг соответствующей копии автомата A2 и заканчивается в одном из выделенных состояний нового автомата. Отсюда следует, что T (A) = T (A1 )T (A2 ).
Звездочка Клини. Пусть A д.к.а., обладающий свойством вахтера. Построим автомат A, распознающий язык (T (A)), следующим образом (см. схему построения на рисунке):
а) Для каждой дуги автомата A, выходящей из начального состояния, входящей в состояние q и помеченной символом a, проделаем следующее: для каждого выделенного состояния добавим дугу, выходящую из этого выделенного состояния, входящую в q и помеченную буквой a (если такая дуга уже есть в автомате A, то не добавляем ее).
б) Начальным состоянием автомата A объявляется начальное состояние A.
в) Выделенными состояниями автомата A объявляются все выделенные состояния A. Кроме этого, сделаем начальное состояние выделенным (если оно уже не было таковым).
Докажем, что (T (A)) = T (A ). Для этого сначала установим справедливость включения (T (A)) T (A ). Пусть слово w (T (A)). Если w =, то w T (A ) в силу пункта (в). Если же w =, то слово w представимо в виде w = w1... wn, где wi T (A) для каждого 1 i n. Следовательно, для каждого 1 i n слово wi читается вдоль следующего пути в автомате A:
в котором последнее состояние rki является выделенным. Поэтому в силу пункта (а) для каждого 2 i n в новом автомате A существует дуга, выходящая из rki1, входящая в r1 и помеченная буквой si. Таким образом, для каждого 2 i n слово wi будет читаться вдоль следующего пути в автомате A :
Соединив последовательно все такие пути в одну цепочку, мы получим путь в автомате A, который начинается в начальном состоянии, заканчивается в выделенном состоянии, и вдоль дуг которого читается w. Следовательно, w T (A ).
Теперь установим обратное включение T (A ) (T (A)). Пусть w T (A ). Можно считать, что w = (случай пустого слова тривиален). Следовательно, w читается вдоль пути в автомате A, который начинается в начальном состоянии q0 и заканчивается в некотором выделенном состоянии q. Заметим, что в силу свойства вахтера q0 = q, поэтому состояние q является выделенным и в исходном автомате A. Пусть в данном пути встречается ровно k новых дуг, т. е. дуг, добавленных по пункту (а).
Для 1 i k введем следующие обозначения. Пусть i-ая новая дуга, встретившаяся в данном пути, имеет вид pi i ri, т. е. выходит из состояния pi, входит в состояние ri и помечена символом si. В частности, pi является выделенным. Обозначим через w0 слово, которое читается вдоль участка нашего пути, начинающегося в состоянии q0 и заканчивающегося в p1. Для 1 i k 1 обозначим через wi слово, которое читается вдоль участка пути, начинающегося в pi и заканчивающегося в pi+1. Наконец через wk обозначим слово, которое читается вдоль участка пути, начинающегося в pk и заканчивающегося в q. Очевидно слово w0 T (A), поскольку оно читается вдоль участка, не содержащего новых дуг. Для каждого 1 i k заменим в i-ом участке дугу pi i ri на дугу q0 i ri из исходного автомата A (такая дуга существует по 22 Глава II. Конечные автоматы и формальные грамматики построению), в результате получим путь по дугам исходного автомата, который начинается в q0, заканчивается в выделенном состоянии, и вдоль которого по-прежнему читается слово wi. Следовательно, wi T (A). Таким образом, w = w0 w1... wk, где все wi T (A), т. е. w (T (A)).
Замечание. В предыдущей теореме можно предложить прямое доказательство замкнутости автоматных языков относительно пересечения, а именно, если заданы два д.к.а. A1 = Q1, A, 1, q0, F1 и A2 = Q2, A, 2, q0, F2, то определим д.к.а. A1 A2, который называется прямым произведением исходных автоматов, следующим образом: A1 A2 = Q1 Q2, A,, q0, q0, F1 F2, где функция перехода ( q1, q2, a) = 1 (q1, a), 2 (q2, a) для любых q1 Q1, q2 Q2, a A. Несложно убедиться в том, Теорема 6. Любой конечный язык является автоматным.
Доказательство. а) Нетрудно построить в явном виде автоматы, распознающие языки, {}, {a}, где a буква.
б) Из (а) и теоремы 5 (конкатенация) следует, что любой язык вида {w}, где w слово, является автоматным.
в) Из (б) и теоремы 5 (объединение) следует, что любой непустой конечный язык является автоматным.
Лемма 7 (о накачивании). Пусть L автоматный язык. Тогда существует n такое, что для любого слова w L, где |w| n, существует представление в виде w = xyz, где y =, |xy| n и xy i z L для всех i 0.
Доказательство. Пусть A д.к.а. такой, что T (A) = L, и пусть n число состояний автомата A. Рассмотрим произвольное слово w L со свойством |w| n.
Следовательно, можно представить w = s1... sn sn+1... sm, где si буквы. Так как w распознается автоматом A, то существует путь по дугам A, начинающийся в начальном состоянии, заканчивающийся в выделенном состоянии, и вдоль которого читается слово w.
Рассмотрим первые n переходов в этом пути, вдоль которых читаются первые n букв слова w. Так как число состояний, пройденных на этом участке пути, равно n + 1, то существует хотя бы одно состояние q, которое встречается не менее двух раз.
Пусть x часть слова s1... sn, которая читается от начального состояния до первого попадания в состояние q; y часть слова s1... sn, которая читается от первого попадания в состояние q до последнего попадания в состояние q; z остальная часть w (см. рисунок). Тогда y = и |xy| n. Кроме этого, чтение подслова y начинается и заканчивается в состоянии q. Следовательно, этот участок можно удалить из нашего пути или пройти по нему произвольное количество раз. Отсюда заключаем, что слово xy i z T (A) для всех i 0.
Следствие 8. Существуют неавтоматные языки.
Доказательство. Рассмотрим язык L = {am bm | m } над алфавитом {a, b}. Допустим, L автоматный. Следовательно, существует n 1 как в лемме о накачивании.
Рассмотрим слово an bn L. Длина |an bn | > n. Следовательно, по лемме можно представить an bn = xyz, где y =, |xy| n и xy i z L для любого i 0. Отсюда следует, что существует k 1 такое, что y = ak, и слово x не содержит букв b. Следовательно, слово xz = ank bn L, что невозможно, поскольку n k < n. Таким образом, L не является автоматным.
Замечание. Лемма о накачивании является необходимым условием автоматности языка. Это условие является достаточно сильным и демонстрирует определенную ограниченность вычислительных возможностей конечных автоматов. Например, как мы заметили, никакой конечный автомат не способен распознать язык {am bm | m }. Однако несложно построить формальную грамматику, которая порождает этот язык. Другими словами, не любую алгоритмически разрешимую задачу можно решить с помощью конечных автоматов. Тем не менее, язык конечных автоматов оказывается достаточным для алгоритмического описания многих важнейших классов задач в различных разделах математики и приложениях.
§ 7. Регулярные языки В этом параграфе будет предложен другой подход для описания класса автоматных языков. Будет доказано, что автоматные языки это в точности те языки, которые имеют синтаксическое описание в терминах регулярных выражений.
Определение. Пусть A конечный алфавит, не содержащий символов (, ),,.
Определим по индукции множество регулярных выражений над алфавитом A:
10. Множества,, a, где a A, являются регулярными выражениями.
20. Если и регулярные выражения, то (), ( ) и ( ) тоже являются регулярными выражениями.
Таким образом, слово в алфавите A{(, ),, } называется регулярным выражением, если оно может быть получено конечным числом применений пунктов 10 и 20.
Определение. Схожим образом определим множество обобщенно регулярных выражений над алфавитом A:
10. Множества,, a, где a A, являются обобщенно регулярными выражениями.
20. Если и обобщенно регулярные выражения, то (), ( ), ( ) и () тоже являются обобщенно регулярными выражениями.
Замечание. В дальнейшем мы будем опускать некоторые (в том числе внешние) скобки при записи обобщенно регулярных выражений, как это делается в обычной алгебре, считая, что операции имеют следующий приоритет: самая сильная операция, далее идет, затем следует, а операция самая слабая. Например, запись на самом деле означает ((( )) (())).
24 Глава II. Конечные автоматы и формальные грамматики Определение. Определим отображение L из множества всех обобщенно регулярных выражений над алфавитом A в множество всех языков над A следующим образом:
Определение. Язык L над алфавитом A называется (обобщенно) регулярным, если существует (обобщенно) регулярное выражение над алфавитом A такое, что L() = L. При этом будем говорить, что выражение задает язык L.
Пример. Язык L = {w {0, 1} | w содержит подслово 11} является регулярным, поскольку его можно задать регулярным выражением (0 10) 11(0 1). Заметим, что для любого (обобщенно) регулярного языка существует бесконечно много (обобщенно) регулярных выражений, задающих его. Например, тот же язык L можно задать регулярным выражением (0 1) 11(0 1) или обобщенно регулярным выражением 11.
Теорема 9. Класс автоматных языков совпадает с классом регулярных языков.
Доказательство. Сначала докажем, что любой регулярный язык автоматен. Пусть L регулярный язык над алфавитом A. Следовательно, найдется хотя бы одно регулярное выражение, которое задает L. Индукцией по длине выражения докажем, что L автоматный.
10. Если является выражением вида, или a, где a A, т. е. L =, L = {} или L = {a}, то в силу теоремы 6 язык L является автоматным.
20. Если является выражением вида (), ( ) или ( ), где, регулярные, то по индукционному предположению заключаем, что языки L1 = L() соответственно. В любом случае по теореме 5 получаем, что L автоматен.
Теперь докажем, что любой автоматный язык регулярен. Пусть L произвольный автоматный язык. Следовательно, существует д.к.а. A = Q, A,, q1, F с состояними Q = {q1,..., qn } такой, что T (A) = L. Докажем, что L регулярный. Для этого определим для всех 1 i n, 1 j n и 0 k n множество слов:
R(i, j, k) = {w A | w читается вдоль пути автомата A, который начинается в qi, заканчивается в qj и который в промежутке между ними не заходит в состояния qk+1, qk+2,..., qn }.
(Здесь термином промежуток между qi и qj мы называем множество всех состояний пути, исключая его начало qi и его конец qj. Напомним также, что пустое слово по определению читается вдоль пути, который содержит только одно состояние и не содержит ни одной дуги.) Заметим, что при k = n множество R(i, j, n) состоит в точности из всех слов, читаемых вдоль путей нашего автомата, идущих из qi в qj. Кроме этого, ясно, что Так как регулярные языки замкнуты относительно объединения, то достаточно доказать, что все R(i, j, k) регулярны. Докажем это утверждение индукцией по k.
10. При k = 0 множество R(i, j, 0) это все слова, читаемые вдоль одной дуги, ведущей из qi в qj. Возможны три случая. Если такая дуга существует и она помечена символом a, то R(i, j, 0) = {a}. Если такой дуги нет и qi = qj, то R(i, j, 0) = {}. Если такой дуги нет и qi = qj, то R(i, j, 0) =. По определению все такие языки регулярны.
20. Допустим, что утверждение доказано для k 1, т. е. все языки R(i, j, k 1) регулярны. Рассмотрим произвольное слово w R(i, j, k), оно читается вдоль пути, который начинается в qi, несколько раз (может и 0 раз) заходит в qk и заканчивается в qj. Если этот путь не заходит в qk, то вдоль него читается слово из R(i, j, k 1), т. е. w R(i, j, k 1). Если же этот путь заходит в qk, то пусть u подслово w, которое читается вдоль участка пути, начинающегося в qi и заканчивающегося в первом попадании в состояние qk ; w1 подслово w, которое читается вдоль участка, начинающегося в первом попадании в qk и заканчивающегося во втором попадании в qk ;... ; ws подслово w, которое читается вдоль участка, начинающегося в предпоследнем попадании в qk и заканчивающегося в последнем попадании в qk ; и, наконец, пусть v подслово w, которое читается вдоль участка, начинающегося в последнем попадании в qk и заканчивающегося в qj.
следует, что слово w = uw1... ws v R(i, k, k 1)R(k, k, k 1) R(k, j, k 1).
Объединяя оба случая, заключаем, что имеет место включение R(i, j, k) R(i, j, k 1) R(i, k, k 1)R(k, k, k 1) R(k, j, k 1). Нетрудно проверить, что обратное включение тоже верно. Таким образом, мы доказали равенство Следовательно, в силу индукционного предположения и замкнутости регулярных языков относительно объединения, конкатенации и звездочки Клини окончательно получаем, что R(i, j, k) регулярный язык. Что и требовалось доказать.
Следствие 10. Язык является регулярным тогда и только тогда, когда он является обобщенно регулярным.
26 Глава II. Конечные автоматы и формальные грамматики Доказательство. Если язык L регулярный, то, очевидно, L обобщенно регулярный, поскольку любое регулярное выражение является обобщенно регулярным.
С другой стороны, если L обобщенно регулярный, то, используя теорему 5 (дополнение), можно так же, как и в первой части доказательства предыдущей теоремы, показать, что L автоматный. Следовательно, L регулярный.
Таким образом, регулярные и обобщенно регулярные выражения задают одни и те же языки. Однако этот факт не стал поводом для прекращения изучения свойств обобщенно регулярных выражений. Более того, с обобщенно регулярными выражениями связана одна достаточно известная математическая проблема, которая имеет простую формулировку, но до сих пор является открытой.
Определение. Определим отображение sh из множества всех обобщенно регулярных выражений над алфавитом A в множество следующим образом:
Число sh() называется звездной высотой выражения.
Определение. Для каждого регулярного языка L над алфавитом A определим:
sh(L) = min{sh() | регулярное выражение такое, что L() = L}, gsh(L) = min{sh() | обобщенно регулярное выражение такое, что L() = L}.
Число sh(L) называется звездной высотой языка L, а gsh(L) обобщенно звездной высотой языка L. Нетрудно видеть, что gsh(L) sh(L).
Пример. Найдем звездную и обобщенно звездную высоту языка L = {w {0, 1} | w содержит подслово 11}. Сначала заметим, что конкатенация и объединение конечных языков являются конечными языками. Поэтому, в силу бесконечности языка L, заключаем, что любое регулярное выражение, задающее L, должно содержать звездочку Клини. Отсюда следует, что sh(L) 1. С другой стороны, язык L можно задать регулярным выражением (0 1) 11(0 1), звездная высота которого равна 1. Таким образом, sh(L) = 1.
Обобщенно звездная высота gsh(L) = 0, поскольку L можно задать обобщенно регулярным выражением 11, не содержащим звездочек Клини.
Замечание. Известно, что для любого n существует регулярный язык L такой, что его звездная высота sh(L) = n. Однако вопрос о существовании примеров языков L таких, что gsh(L) > 1, до сих пор является нерешенным.
§ 8. Определение формальных грамматик Часто формальные языки описываются как совокупности слов, полученных с помощью правил замены одних цепочек символов на другие. Такой подход лежит в основе понятия формальной грамматики. В отличие от конечных автоматов, формальные грамматики не распознают слова, а порождают их. Любую формальную грамматику можно представлять как некоторый генератор языка. Запуск такого генератора производится с помощью стартового сигнала, после чего начинается порождение слов языка. Действия генератора на каждом этапе порождения слов недетерминированны, но ограничены конечным списком правил. Время от времени этот процесс прерывается для того, чтобы выдать очередное выходное слово. Множество всех слов, появившихся на выходе в процессе работы, образует язык, порожденный данной грамматикой. Процесс порождения слов по правилам формальной грамматики безусловно является алгоритмическим.
Пример. Термин формальная грамматика неслучайно имеет такое лингвистическое происхождение. Процесс порождения слов в латинском языке может служить примером использования некоторой формальной грамматики.
Рассмотрим определенный фрагмент латинского языка, который неформально описывается следующими правилами словообразования:
1) Любое слово имеет приставку, корень, суффикс и окончание, причем они расположены в слове именно в указанном здесь порядке.
2) Приставка либо отсутствует, либо присутствует в единственном числе и является элементом множества {ad, de, dis, in, prae, suc,...}.
3) В слове может быть либо один, либо два корня из множества {albi, capill, cub, fect, it, laborat,...}.
4) Суффикс либо отсутствует, либо присутствует в единственном числе и является элементом множества {bu, re, r,...}.
5) В слове может быть только одно окончание из множества {, o, rum, nt, s, us,...}.
Теперь перепишем правила (1)–(5) формально, используя так называемые продукции:
1) (слово)(приставка)(корень)(суффикс)(окончание) 2) (приставка) (приставка)in (приставка)ad (приставка)prae (приставка)de (приставка)suc (приставка)dis · · · 3) (корень)(корень1)(корень2) (корень2) 4) (суффикс) (суффикс)re (суффикс)bu (суффикс)r 28 Глава II. Конечные автоматы и формальные грамматики 5) (окончание) a (окончание)o (окончание)rum (окончание)nt (окончание)s (окончание)us Например, процесс порождения слова albicapillus (седовласый) по данным правилам выглядит следующим образом:
(слово) (приставка)(корень)(суффикс)(окончание) (корень)(суффикс)(окончание) (корень1)(корень2)(суффикс)(окончание) albi(корень2)(суффикс)(окончание) albicapill(суффикс)(окончание) Слово aditrus (намеревающийся подойти) порождается так:
(слово) (приставка)(корень)(суффикс)(окончание) ad(корень)(суффикс)(окончание) ad(корень1)(корень2)(суффикс)(окончание) adit(корень2)(суффикс)(окончание) adit(суффикс)(окончание) Слово incubus (инкуб ) порождается следующим образом:
(слово) (приставка)(корень)(суффикс)(окончание) in(корень)(суффикс)(окончание) in(корень1)(корень2)(суффикс)(окончание) incub(корень2)(суффикс)(окончание) incub(суффикс)(окончание) Слово succubus (суккуб ) имеет схожую цепочку порождения:
(слово) (приставка)(корень)(суффикс)(окончание) suc(корень1)(корень2)(суффикс)(окончание) succub(корень2)(суффикс)(окончание) succub(суффикс)(окончание) Определение. Формальной грамматикой называется упорядоченная четверка = V, T, P, S, состоящая из следующих объектов:
а) V конечное множество нетерминальных (вспомогательных) символов;
б) T конечное множество терминальных символов такое, что V T = ;
в) P конечное множество продукций, т. е. цепочек вида, где, Определение. Пусть = V, T, P, S Говорят, что слово непосредственно получается из слова в грамматике, и пишут, если существуют слова 0, 1,, такие, что = 0 1, = 0 1, и продукция принадлежит множеству P.
Определение. Говорят, что слово выводимо из слова в грамматике, и пишут, если существует конечная последовательность слов 0,..., k такая, что k = и имеет место Цепочка () называется выводом слова из слова в грамматике.
Определение. Пусть = V, T, P, S формальная грамматика. Язык L() = {w T | S w} называется языком, порожденным грамматикой.
Пример. Вернемся к предыдущему примеру. С формальной точки зрения в данной грамматике множество нетерминальных символов имеет вид V = { (слово), (приставка), (корень), (корень1), (корень2), (суффикс), (окончание) }, множеством терминальных символов является множество T = { ad, de, dis, in, prae, suc, albi, capill, cub, bu, r,, nt, o,...}. Продукциями являются цепочки из пунктов (1)–(5). Начальный символ это символ (слово).
Пример. Рассмотрим теперь пример формальной грамматики, которая порождает язык всех десятичных записей натуральных чисел в алфавите из десяти терминальных цифр T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Каждая запись натурального числа есть либо 0, либо получается приписыванием ненулевой цифры слева к некоторой последовательности цифр. В свою очередь каждая последовательность цифр есть либо пустое слово, либо получается приписыванием любой цифры (включая 0) слева к некоторому слову, про которое уже известно, что оно является последовательностью цифр.
Эти рассуждения позволяют формально выписать множество продукций P :
Таким образом, алфавит нетерминальных символов V = {S, A} состоит из двух букв.
Символ S начальный, он соответствует термину запись натурального числа.
Символ A соответствует термину последовательность цифр.
Определение (типы грамматик). Формальная грамматика = V, T, P, S называется:
а) неукорачивающей, если для любой ее продукции выполняется || ||;
б) контекстно-свободной, если все ее продукции имеют вид A, где A V, в) регулярной, если все ее продукции имеют вид A aB или A a, где Замечание. Любая регулярная грамматика является контекстно-свободной. Любая контекстно-свободная грамматика является неукорачивающей. Регулярные грамматики также иногда называют праволинейными, поскольку при порождении слов в таких грамматиках каждый новый терминальный символ появляется справа от предыдущего, т. е. слово порождается слева направо.
30 Глава II. Конечные автоматы и формальные грамматики § 9. Свойства формальных грамматик Как было замечено выше, в регулярных грамматиках слова порождаются слева направо без возможности возврата в начальные символы слова. Иначе говоря, если на промежуточном шаге было выведено слово a1 a2... ak A, где a1,..., ak терминальные символы, A нетерминальный символ, то на всех последующих шагах префикс a1 a2... ak останется неизменным. Похожим свойством обладают конечные автоматы, которые не имеют памяти вне процессора и в которых символы слов также прочитываются слева направо. Это наблюдение лежит в основе следующей теоремы.
Теорема 11. Имеют место следующие два утверждения:
1) Если язык L порождается регулярной грамматикой, то L автоматный.
2) Если L автоматный язык, то L \ {} порождается регулярной грамматикой.
Доказательство. Сначала докажем первое утверждение теоремы. Пусть язык L порождается регулярной грамматикой = V, T, P, S. Определим недетерминированный конечный автомат A следующим образом:
а) Множеством состояний автомата является множество V {q}, где q новый б) Внешним алфавитом автомата будет множество T.
в) Начальным состоянием является S.
г) Единственным выделенным состоянием будет q.
д) Переходы в автомате A определяются по следующему принципу. Для каждой продукции вида A aB добавляем дугу. Для каждой продукции Покажем, что L = T (A). Пусть w = a0 a1... ak T произвольное слово. Тогда имеет место следующая цепочка эквивалентных утверждений:
a0... ak1 ak слова w в грамматике. В множестве P имеются продукции вида В построенном автомате A имеется путь вида w = a0 a1... ak T (A). Что и требовалось доказать.
Теперь докажем второе утверждение теоремы. Пусть L распознается конечным автоматом A. В силу леммы о вахтере можно считать, что A обладает свойством вахтера. Преобразуем автомат A в автомат A, сделав начальное состояние невыделенным, если оно было выделенным в A. Ясно, что L \ {} = T (A ). Пусть A = Q, A,, q0, F. Определим регулярную грамматику следующим образом:
а) Множеством нетерминальных символов грамматики является множество Q.
б) Множеством терминальных символов будет множество A.
в) Начальным символом является q0.
г) Множество продукций определяется по следующему принципу. Для каждой дуa ги автомата вида добавляем продукцию q1 aq2. Кроме этого, если состояние q2 является выделенным, то добавляем дополнительно продукцию q1 a.
Покажем, что L \ {} = L(). Ясно, что пустое слово не принадлежит обеим частям этого тождества. Пусть w = a1... ak A произвольное непустое слово.
Тогда имеет место следующая цепочка эквивалентных утверждений:
w L В автомате A существует путь вдоль которого распознается слово w. В построенной грамматике имеются продукции Существует вывод q0 a1 q1 a1 a2 q2... a1... ak1 qk1 a1... ak1 ak слова w в грамматике. w L(). Что и требовалось показать.
Замечание. Предыдущая теорема позволяет утверждать, что класс автоматных языков почти совпадает с классом языков, порождаемых регулярными грамматиками. Иногда в литературе дается несколько другое определение регулярной грамматики, в котором допускается возможность вывода пустого слова. Это делается для того, чтобы избавиться от слова почти в предыдущем утверждении. При таком расширенном определении класс автоматных языков в точности равен классу языков, порождаемых регулярными грамматиками.
Теперь мы докажем важное свойство разрешимости любого языка, порождаемого неукорачивающей грамматикой. Под разрешимостью языка L над алфавитом A мы понимаем существование алгоритма, который по любому слову w A за конечное число шагов позволяет определить, принадлежит ли w языку L или нет. Ниже мы 32 Глава II. Конечные автоматы и формальные грамматики приведем лишь неформальное описание разрешающей процедуры для языка, порожденного неукорачивающей грамматикой. В наших рассуждениях мы будем опираться на интуитивную эффективность таких процедур, как непосредственное получение одного слова из другого по правилам заданной формальной грамматики; проверка принадлежности заданного слова конечному множеству, имеющему эффективное описание; и др.
В формулировке следующего утверждения через |V T | мы обозначаем количество элементов в конечном множестве V T.
Предложение 12. Пусть = V, T, P, S неукорачивающая грамматика. Если, то в существует вывод..., содержащий не более ||·|V T ||| слов.
Доказательство. Пусть имеется вывод = 0 1... n =. Так как неукорачивающая, то 1 |0 | |1 |... |n |. Разобъем данный вывод на несколько участков, каждый из которых состоит из слов одинаковой длины:
Рассмотрим произвольный участок, состоящий из всех слов длины m. Заметим, что количество слов длины m над алфавитом V T равно |V T |m. Поэтому, если рассматриваемый участок содержит более, чем |V T |m элементов, то среди них найдутся одинаковые слова i = j, i < j. Следовательно, вывод можно укоротить, удалив участок i... j. Повторив, если потребуется, аналогичные рассуждения несколько раз, мы добьемся того, что слов длины m в нашем выводе окажется не более, чем |V T |m штук.
Применив описанную процедуру ко всем m, мы получим новый вывод слова из, в котором суммарное количество слов не превосходит Что и требовалось доказать.
Теорема 13. Пусть = V, T, P, S неукорачивающая грамматика. Тогда язык L() разрешим, т. е. существует алгоритм, который по любому слову w T за конечное число шагов позволяет определить, порождается ли w в грамматике или не порождается.
Доказательство. Пусть w произвольное слово в алфавите T. Алгоритм имеет следующее описание. Сначала вычисляем натуральное число k = |w| · |V T ||w|.
Затем строим конечную последовательность A1, A2,..., Ak конечных множеств слов по индукции:
A1 = {S}, Заметим, что для любого 1 n k множество An состоит из всех слов, имеющих вывод в грамматике, длина которого не превосходит n. В силу предыдущего предложения имеет место эквивалентность w L() w Ak. Следовательно, если условие w Ak выполнено, то w порождается заданной грамматикой, в противном случае не порождается.
Следствие 14. Если язык L принадлежит одному из следующих классов, то L разрешим:
a) класс языков, порождаемых контекстно-свободными грамматиками;
б) класс языков, порождаемых регулярными грамматиками;
в) класс автоматных языков.
Доказательство. Разрешимость языков из пунктов (а) и (б) следует из теоремы 13.
Если L автоматный язык, не содержащий пустого слова, то его разрешимость следует из пункта (б) и теоремы 11. Если же L автоматный и L, то в силу пункта (б) и теоремы 11 язык L1 = L \ {} разрешим. Следовательно, язык L = L1 {} также разрешим, поскольку он получен из L1 добавлением пустого слова.
Глава III Формализации понятия вычислимой функции Основной целью данной главы является формализация понятия вычислимой функции, действующей на натуральных числах. Напомним, что n-местной частичной функцией на мы называем любую функцию вида f : X, где X n, n.
Существует несколько различных подходов, приводящих к тому или иному определению частичной вычислимой функции. Мы рассмотрим четыре подобных подхода и покажем, что все они эквивалентны. Первая из формализаций, с которой мы познакомимся в следующем параграфе, связана с машинами Шёнфилда [8], [13].
§ 10. Машины Шёнфилда Содержимое регистров может меняться по ходу вычислений. Отметим, что каждая конкретная машина Шёнфилда использует в своих вычислениях только конечное число регистров. Основное назначение регистровой памяти это хранение входных, промежуточных и выходных данных.
2) Счетчиком команд, являющимся особой ячейкой памяти, которая в каждый данный момент содержит некоторое натуральное число. Счетчик команд указывает на номер команды в программе, которая исполняется в данный момент.
В начальный момент в счетчик команд заносится 0.
3) Программой, содержащейся в отдельной выделенной памяти машины. Программа это конечный список команд, последовательно пронумерованных натуральными числами от 0 до некоторого n. В ходе вычислений программа не меняется, она фиксирована.
Шаг машины состоит в исполнении той команды из программы, номер которой указан в данный момент в счетчике команд. Если команды с таким номером в программе нет, то машина останавливается.
Существует только два типа команд:
При исполнении данной команды машина увеличивает содержимое i-го регистра и счетчик команд на 1, после чего переходит к следующему шагу в своей 2) DEC i, n Если к началу исполнения данной команды содержимое i-го регистра больше 0, то машина уменьшает его на 1 и заносит n в счетчик команд. Если же в данный момент содержимое i-го регистра равно 0, то машина увеличивает счетчик Еще раз подчеркнем, что машина останавливается тогда и только тогда, когда в счетчик команд заносится номер несуществующей в программе команды. Однако не исключены ситуации, в которых машина работает бесконечно, т. е. не останавливается.
Для наших дальнейших рассуждений будет удобно расширить язык машин Шёнфилда и ввести дополнительные команды, отличные от команд типа INC i и DEC i, n.
Чтобы вычислительные возможности исходных машин не изменились, мы будем добавлять только те команды, которые допускают реализацию в виде программы, использующей только команды типа INC i и DEC i, n. Любую дополнительную команду, обладающую таким свойством, будем называть макросом.
Таким образом, любой макрос получается по следующему принципу: если P обычная программа, то ей сопоставляется оператор P, который называется макросом и который может исполняться как отдельная команда. Программы, содержащие макросы, будем называть макропрограммами.
Исполнение макроса P, находящегося в макропрограмме в строке под номером m, происходит следующим образом:
1) Если в счетчике команд находится m, то в машину (в качестве подпрограммы) вызывается программа P.
2) P исполняется с теми данными в регистрах, которые там содержались в данный 3) Если работа программы P закончилась, то в счетчик команд заносится m + и исполнение макроса на этом заканчивается. Если же P работает бесконечно, то макропрограмма также не останавливается.
Любой макрос может использовать конечный набор параметров, каждый из которых является номером некоторого регистра (эти номера обычно присутствуют в имени макроса). Макросы не могут использовать в качестве своих параметров номера строк программы.
36 Глава III. Формализации понятия вычислимой функции Пример. Исполнение последовательной пары команд 0 : INC 0 и 1 : DEC 0, n просто заносит n в счетчик команд, при этом содержимые регистров не меняются. Однако мы не можем сопоставить этой короткой программе макрос, использующий параметр n, поскольку n здесь является номером строки.
Пример. Программа с простейшим циклом 0 : DEC i, 0 обнуляет содержимое i-го регистра. Обозначим макрос, соответствующий этой программе, через ZERO i.
Пример. Пусть i, j, k фиксированные натуральные числа такие, что i = k и j = k.
Обозначим через [i] [j], (k) макрос, который копирует содержимое i-го регистра в j-й регистр, используя k-й регистр как вспомогательный. Содержимое i-го регистра не изменяется. Программа, реализующая данный макрос при i = j, имеет следующий вид:
При i = j можно взять любую программу, которая ничего не меняет, например Определение. Макропрограммы P и Q называются эквивалентными, если запуски машин Шёнфилда с этими макропрограммами на одних и тех же начальных содержимых регистров либо приведут к остановке обеих машин с одинаковыми содержимыми всех регистров, либо обе машины никогда не остановятся.
Следующая теорема показывает, что введение макросов не расширяет класс алгоритмических задач, которые допускают решение на машинах Шёнфилда. Таким образом, макросы это лишь удобный инструмент для сокращения текстов программ.
Теорема 15 (об элиминации макросов). Любая макропрограмма эквивалентна программе, не содержащей макросы.
Доказательство. Опишем, как следует преобразовать произвольную макропрограмму Q в эквивалентную ей макропрограмму Q, содержащую на один макрос меньше, чем в Q. Повторяя эту процедуру необходимое число раз, мы в конце концов получим программу без макросов, эквивалентную исходной.
Пусть P некоторый макрос в Q. Чтобы получить искомую макропрограмму Q, заменим вхождение P на список команд P, которые реализуют данный макрос, при этом необходимо проделать следующее:
а) заново перенумеровать все команды полученной макропрограммы, начиная с б) если DEC i, n старая команда из Q или P, n номер существующей команды C из Q или P соответственно, то заменить ее на DEC i, m, где m новый номер в) если DEC i, n старая команда из Q, n номер несуществующей в Q команды, то заменить ее на DEC i, m, где m больше, чем число команд новой макропрограммы;
г) если DEC i, n старая команда из P, n номер несуществующей в P команды, то заменить ее на DEC i, m, где m номер команды, следующей после списка команд P в новой макропрограмме.
Пример. Обозначим через ADD [1] TO [0], (3) макрос, при исполнении которого содержимое 1-го регистра прибавляется к содержимому 0-го регистра. При этом содержимое 1-го регистра сохраняется, а 3-й регистр используется как вспомогательный.
Программа, реализующая данный макрос, имеет следующий вид:
Запишем теперь с помощью введенного макроса макропрограмму, перемножающую содержимые 1-го и 2-го регистров и записывающую полученное произведение в 0-й регистр:
Если применить к данной макропрограмме процедуру преобразования, описанную в доказательстве теоремы об элиминации макросов, то получим эквивалентную ей программу без макросов:
38 Глава III. Формализации понятия вычислимой функции Определение. k-местная частичная функция f : M k называется вычислимой на машине Шёнфилда, если существует машина Шёнфилда с программой P такая, что для любых x1,..., xk выполняется:
а) если f (x1,..., xk ) определено, то после запуска машины с начальными значениями x1,..., xk в регистрах 1,..., k соответственно и с нулями в остальных регистрах машина после конечного числа шагов останавливается, и после остановки в 0-ом регистре находится f (x1,..., xk );
б) если f (x1,..., xk ) не определено, то после запуска машины с начальными значениями x1,..., xk в регистрах 1,..., k соответственно и с нулями в остальных регистрах машина никогда не останавливается и работает бесконечно.
Замечание. Если в определении выше f нульместная функция, то входные данные x1,..., xk отсутствуют, а результат вычислений по программе P не зависит от начальных содержимых регистров.
Определение. Пусть f k-местная частичная функция, вычислимая на машине Шёнфилда с программой P. Обозначим через макрос, который вычисляет значение функции f от содержимых регистров с номерами i1,..., ik, записывает его в j-й регистр и при этом не изменяет содержимое всех регистров до s-го включительно, кроме j-го регистра. Если упомянутое значение функции не определено, то исполнение данного макроса приводит к бесконечной работе программы.
Нам необходимо построить макропрограмму, реализующую введенный выше макрос f ([i1 ],..., [ik ]) [j], s. Обозначим, как обычно, через P макрос, соответствующий программе P. Пусть m произвольное число, превосходящее числа i1,..., ik, j, s и номера всех регистров, входящих в программу P. Отсюда, в частности, следует, что результат исполнения макроса P не зависит от содержимых регистров, номера которых больше, чем m1. Тогда искомая макропрограмма имеет вид (номера строк опущены):
В дальнейшем мы будем опускать параметр s, поскольку его всегда можно заранее выбрать достаточно большим, чтобы не влиять на работу внешней макропрограммы.
§ 11. Частично рекурсивные функции В этом параграфе мы рассмотрим другой подход к формализации понятия вычислимой функции. Его можно назвать алгебраическим, поскольку определяемый здесь класс функций будет порождаться из некоторых простейших функций с помощью определенных операций. Совокупность функций, возникающих в результате подобного алгебраического порождения, называется классом частично рекурсивных функций.
В рамках данного параграфа рассматриваются только частичные функции на, т. е. всевозможные функции вида f : X, где множество X n является всюду определенную функцию f = a мы отождествляем с константой a. Нигде не определенная функция единственна и имеет вид f =, причем любое натуральное число является местностью нигде не определенной функции.
Если f n-местная, а g m-местная частичная функция, то для любых значений когда либо эти значения одновременно не определены, либо они оба определены и совпадают.
Определение. Простейшими функциями называются нульместная функция 0, всюду определенные одноместные функции o(x) = 0, s(x) = x + 1 и n-местные функn ции Im (x1,..., xn ) = xm для всех m, n таких, что 1 m n.
Определение. Говорят, что функция f (x1,..., xn ) получается с помощью оператора суперпозиции S из функций h(y1,..., ym ), g1 (x1,..., xn ),..., gm (x1,..., xn ), если для любых x1,..., xn выполняется:
40 Глава III. Формализации понятия вычислимой функции Замечание. С неформальной точки зрения оператор суперпозиции соответствует принципу последовательного запуска вычислительных устройств, когда результаты вычислений одних устройств служат входными данными для других. Если f получена с помощью суперпозиции из h, g1,..., gm, то вычисление значения f (x1,..., xn ) происходит следующим образом. Сначала на входных данных x = x1,..., xn вычисляются значения y1 = g1 (x),..., ym = gm (x). Если хотя бы одно из этих значений не определено, то значение f (x) тоже не определено. Если же все y1,..., ym определены, то затем они подаются на вход функции h. Если выходное значение h(y1,..., ym ) не определено, то f (x) считается неопределенным, иначе f (x) = h(y1,..., ym ) определено и является окончательным выходным значением.
Определение. Говорят, что функция f (x1,..., xn, y) получается с помощью оператора примитивной рекурсии R из функций g(x1,..., xn ) и h(x1,..., xn, y, z), если для любых x1,..., xn, y выполняется схема примитивной рекурсии:
Замечание. Оператор примитивной рекурсии формализует циклическую структуру, вычисляющую функции, заданные рекуррентными соотношениями (или по индукции). Если f получена с помощью примитивной рекурсии из g и h, то вычисление значения f (x, y) происходит следующим образом. Сначала на входных данных x вычисляется значение g(x), которое совпадает с f (x, 0). Если это значение не определено, то f (x, y) тоже не определено, иначе, подав x, 0 и f (x, 0) на вход функции h, мы вычисляем h(x, 0, f (x, 0)), которое совпадает с f (x, 1). Если последнее значение не определено, то f (x, y) не определено, иначе мы подаем x, 1 и f (x, 1) на вход функции h, и так далее. Данные вычисления продолжаются до тех пор, пока мы не достигнем значения f (x, y). Если при этом на промежуточных шагах хоты бы одно вычисляемое значение функции h не определено, то f (x, y) считается неопределенным.
Определение. Говорят, что функция f (x1,..., xn ) получается с помощью оператора минимизации M из функции g(x1,..., xn, y) и обозначается f (x1,..., xn ) = µy[g(x1,..., xn, y) = 0], если для любых x1,..., xn выполняется:
Замечание. Оператор минимизации формально описывает такой вычислительный прием, как эффективный перебор: последовательно перебирая числа из натурального ряда, мы проверяем, удовлетворяет ли текущее число фиксированному эффективному условию. Эффективное условие записывается в виде уравнения g(x, y) = 0.
Вычисление значения f (x) происходит следующим образом. Сначала на входных данных x, 0 вычисляется значение g(x, 0). Если это значение не определено, то f (x) тоже не определено. Иначе если g(x, 0) = 0, то вычисления заканчиваются – число будет подано на выход. Если же g(x, 0) = 0, то на входных данных x, 1 вычисляется значение g(x, 1). Если это значение не определено, то f (x) тоже не определено. Иначе если g(x, 1) = 0, то вычисления заканчиваются – число 1 будет подано на выход. Если же g(x, 1) = 0, то данный процесс продолжается. В результате мы либо вычислим наименьшее решение уравнения g(x, y) = 0, либо ничего не вычислим. Последнее возможно по двум причинам: либо некоторое вычисляемое значение функции g окажется неопределенным, либо g(x, y) определено для всех y, но не равно нулю.
Определение. Частичная функция f (x1,..., xn ) называется частично рекурсивной (примитивно рекурсивной), если существует конечная последовательность функций f0,..., fm = f такая, что для любого i m функция fi либо простейшая, либо получается из некоторых предыдущих с помощью одного из операторов S, R или M (операторов S или R).
Определение. Всюду определенные частично рекурсивные функции называтся рекурсивными.
Замечание. Будем использовать сокращения: ч.р.ф. для частично рекурсивных функций, п.р.ф. для примитивно рекурсивных функций, р.ф. для рекурсивных функций.
Из определения следует, что если функция f получается из некоторых ч.р.ф.
(п.р.ф.) с помощью оператора S, R или M (S или R), то f тоже является ч.р.ф.
(п.р.ф.).
Кроме этого, очевидно, между введенными классами функций имеют место следующие теоретико-множественные включения:
Замечание. Заметим, что одноместную функцию o(x) можно исключить из числа простейших функций класс частично рекурсивных функций при этом не изменится. Это следует из того, что o(x) можно получить из 0-местной функции 0 и 2-местной функции I2 (x, y) с помощью оператора примитивной рекурсии.
Теорема 16 (о вычислимости ч.р.ф. на машинах Шёнфилда). Любая частично рекурсивная функция является вычислимой на машине Шёнфилда.
Доказательство. Пусть f ч.р.ф. Следовательно, по определению существует конечная последовательность функций f0,..., fk = f такая, что для любого i k функция fi либо простейшая, либо получается из некоторых предыдущих с помощью оператора S, R или M. Индукцией по числу k докажем, что f вычислима на некоторой машине Шёнфилда.
Если k = 0, то f является простейшей, т. е. либо константой 0, либо функцией o(x), либо функцией s(x), либо функцией вида Im (x1,..., xn ). Следующие три макропрограммы вычисляют эти функции на машинах Шёнфилда (0 и o(x) вычисляются одной программой):
Пусть k > 0. Тогда f получена из некоторых ч.р.ф. с помощью одного из трех операторов. Рассмотрим соответствующие три случая.
Если f (x1,..., xn ) получена с помощью оператора суперпозиции из h(y1,..., ym ), g1 (x1,..., xn ),..., gm (x1,..., xn ), то в силу индукционного предположения функции h, g1,..., gm вычислимы по Шёнфилду. Тогда следующая макропрограмма вычисляет функцию f :
42 Глава III. Формализации понятия вычислимой функции Если f (x1,..., xn, y) получена с помощью оператора примитивной рекурсии из частичных функций g(x1,..., xn ) и h(x1,..., xn, y, z), которые мы считаем вычислимыми по Шёнфилду, то следующая макропрограмма будет вычислять f :
Если функция f (x1,..., xn ) получена с помощью оператора минимизации из вычислимой по Шёнфилду функции g(x1,..., xn, y), то следующая макропрограмма будет вычислять f :
Теорема доказана.
§ 12. Рекурсивность некоторых функций и отношений Нашей дальнейшей целью является доказательство утверждения, обратного теореме 16. Для этого нам потребуется целая серия предварительных фактов и новых понятий. Всюду далее через x мы обозначаем кортеж x1,..., xn, при n = 0 этот кортеж считается пустым.
Лемма 17. Все нульместные всюду определенные функции являются примитивно рекурсивными.
Доказательство. Пусть a произвольная константа. Возможны два случая.
Если a = 0, то это по определению простейшая функция, и значит она является п.р.ф. Если же a > 0, то a = s(s... s(0)...), т. е. a получена из простейших функций 0 и s(x) с помощью a-кратного применения оператора S.
Лемма 18. Следующие функции являются примитивно рекурсивными:
в) f (x, y) = xy (здесь 00 = 1);
г) sg(x) = д) sg(x) = Доказательство. а) Для функции f (x, y) = x + y имеет место следующая схема примитивной рекурсии:
т. е. f (x, y) получена с помощью оператора R из п.р.ф. g(x) = x = I1 (x) и п.р.ф.
h(x, y, z) = s(I3 (x, y, z)), которая, в свою очередь, получена из простейших функций s и I3 с помощью оператора S.
б) Для функции f (x, y) = x · y имеет место следующая схема примитивной рекурсии:
где (u, v) = u + v п.р.ф. из предыдущего пункта, т. е. f (x, y) получена с помощью оператора R из п.р.ф. g(x) = 0 = o(x) и п.р.ф. h(x, y, z)=(I3 (x, y, z), I1 (x, y, z)), которая, в свою очередь, получена из п.р.ф., I3, I1 с помощью оператора S.
в) Доказывается аналогично путем выписывания соответствующей схемы примитивной рекурсии.
г) Выписываем схему примитивной рекурсии:
Другими словами, sg(x) получена с помощью оператора R из 0-местной функции 0, которая является простейшей, и 2-местной функции s(o(I1 (x, y))), которая является п.р.ф., поскольку получена суперпозициями из простейших.
д) Выписываем схему примитивной рекурсии:
Таким образом, sg(x) получена с помощью оператора R из 0-местной функции 1, которая является п.р.ф. в силу предыдущей леммы, и 2-местной функции o(I1 (x, y)), которая является п.р.ф., так как получена суперпозициями из простейших функций.
44 Глава III. Формализации понятия вычислимой функции е) Доказывается аналогично.
ж) Обозначим f (x, y) = xy. Тогда имеет место схема примитивной рекурсии:
где (u) = u1 п.р.ф. из предыдущего пункта. Выше мы воспользовались тождеством x(y + 1) = (xy)1, которое верно для любых x, y.
з) Заметим, что |x y| = (xy) + (yx) суперпозиция примитивно рекурсивных функций.
Лемма 19. Если функция g(x, y) является ч.р.ф. (п.р.ф.), то функции f (x, y) = g(x, i) и h(x, y) = g(x, i) тоже являются ч.р.ф. (п.р.ф.).
Доказательство. Частичная (примитивная) рекурсивность функции f вытекает из пункта (а) леммы 18 и следующей схемы примитивной рекурсии:
Утверждение для функции h доказывается аналогично с использованием пункта (б) леммы 18.
Определение. Говорят, что функция f (x) получается с помощью ограниченной минимизации из всюду определенных функций g(x, y) и h(x), и обозначается f (x) = µy h(x)[g(x, y) = 0], если для любых значений x выполняется:
Предложение 20 (об ограниченной минимизации). Если функции g и h примитивно рекурсивны и функция f получена из g и h с помощью ограниченной минимизации, то f тоже примитивно рекурсивна.
Распространим понятие рекурсивности на класс всех отношений, заданных на.
Для этого достаточно связать с каждым отношением некоторую частичную функцию, которая однозначно его задает, и назвать отношение рекурсивным, если таковой является данная функция.
Определение. Отношение (предикат) R n называется рекурсивным (примитивно рекурсивным), если его характеристическая функция является рекурсивной (примитивно рекурсивной).
Напомним, что вместо x1,..., xn R иногда пишут R(x1,..., xn ) и говорят, что предикат R истиннен на элементах x1,..., xn. Если же x1,..., xn R, то пишут ¬R(x1,..., xn ) и говорят, что предикат R ложен на элементах x1,..., xn.
Определение. Для P, Q n введем следующие обозначения для n-местных отношений:
Кроме этого, для R n+1 введем следующие обозначения для (n + 1)-местных отношений:
Замечание. С теоретико-множественной точки зрения отношение P &Q совпадает с пересечением P Q, отношение P Q совпадает с объединением P Q, а отношение ¬P совпадает с дополнением n \ P. Кроме этого, имеет место тождество P Q = ¬P Q.
Предложение 21. Если отношения P (x) и Q(x) рекурсивны (примитивно рекурсивны), то отношения P (x)&Q(x), P (x) Q(x), ¬P (x), P (x) Q(x) тоже рекурсивны (примитивно рекурсивны).
Доказательство. Следует из леммы 18 и следующих тождеств:
XP &Q (x) = XP (x) · XQ (x), XP Q (x) = sg(XP (x) + XQ (x)), X¬P (x) = sg(XP (x)), рекурсивными.
Доказательство. Примитивная рекурсивность данных отношений следует из леммы 18 и тождеств Предложение 23. Если отношение R(x, i) рекурсивно (примитивно рекурсивно), то отношения i y R(x, i), i y R(x, i), i < y R(x, i), i < y R(x, i) тоже рекурсивны (примитивно рекурсивны).
46 Глава III. Формализации понятия вычислимой функции Доказательство. Утверждение для отношения P (x, y) = i y R(x, i) следует из леммы 19 и тождества Утверждение для остальных отношений вытекает из предложений 21, 22 и эквивалентностей Предложение 24 (о кусочном задании функции). Пусть R0,..., Rk n рекурсивные (примитивно рекурсивные) отношения, такие, что R0... Rk = n и Ri Rj = при i = j. Пусть далее f0 (x1,..., xn ),..., fk (x1,..., xn ) рекурсивные (примитивно рекурсивные) функции. Тогда функция тоже рекурсивна (примитивно рекурсивна).
Доказательство. Достаточно заметить, что F (x) = f0 (x)·XR0 (x)+...+fk (x)·XRk (x).
Определение. Пусть R(x, y) отношение, h(x) всюду определенная функция.
Обозначим через µy[R(x, y)] функцию µy[|XR (x, y)1| = 0], а через µy h(x)[R(x, y)] обозначим функцию µy h(x)[|XR (x, y) 1| = 0]. Ясно, что если R(x, y) рекурсивно, то µy[R(x, y)] ч.р.ф. Кроме этого, из предложения 20 следует, что если R(x, y) и h(x) примитивно рекурсивны, то µy h(x)[R(x, y)] п.р.ф.
курсивна (по определению считаем, что [ x ] = x).
б) Отношение Div(x, y), истинное тогда и только тогда, когда x делит y, примитивно рекурсивно.
число, примитивно рекурсивно.
Доказательство. Докажем утверждение пункта (а). Имеет место цепочка эквивалентностей [x/y] = z (y = 0 & x = z) (y = 0 & z x/y < z + 1) 0 & z – наименьшее, такое, что x < (z + 1)y). Кроме этого, ясно, что [x/y] x. Отсюда получаем:
Таким образом, функция [x/y] получена ограниченной минимизацией из примитивно рекурсивных функций, а значит, является п.р.ф.
Утверждения пунктов (б) и (в) следуют из эквивалентностей:
Лемма 26. а) Функция f (x) = px, где p0 = 2, p1 = 3, p2 = 5,... перечисление всех простых чисел в порядке возрастания, является примитивно рекурсивной.
«