/
Text
В. Н. КАСЬЯНОВ
автоматов и
сложности
вычислении
ягрг по теории
формальных языков
ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ
ФЕДЕРАЦИИ
ПО ВЫСШЕМУ ОБРАЗОВАНИЮ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
В.Н Касьянов
Лекции по теории формальных языков,
автоматов и сложности вычислений
Новосибирск
1995
УДК 519.6
ББК 22.18
Касьянов В.Н. Лекции по теории формальных языков, авто-
матов и сложности вычислений: Учеб, пособ. / Новосиб. гос.
ун-т. Новосибирск, 1995.
Излагаются основы теории формальных языков и грам-
матик. Рассматриваются классы регулярных и контекстно-
свободных языков и их связь с конечными и магазинными
автоматами. Обсуждаются фундаментальные вопросы слож-
ности решения задач дискретной математики.
Для студентов вузов, обучающихся по специальности "ма-
тематика”, "прикладная математика” и "информатика”.
Подписано в печать 30.10.95
Печать офсетная. Заказ № 468.
Уч.-изд. л. 7 Усл. печ. л. 6,5
Формат 68 х 84/16
Тираж 500 экз.
Цена 2000 р.
Редакционно-издательский отдел Новосибирского университе-
та; участок оперативной полиграфии НГУ; 630090, Новосибирск-
ие, ул. Пирогова, 2.
© Новосибирский государственный
университет, 1995
Предисловие
Учебное пособие содержит изложение элементов теории
формальных языков, автоматов и сложности вычислений. Не-
обходимость издания такого пособия возникла в связи с курсом
"Введение в дискретную математику”, который читается сту-
дентам первого курса механико-математического факультета
начиная с 1993 года. Наряду с рассмотренными в данном учеб-
ном пособии вопросами курс содержит материал таких "более
классических” разделов современной дискретной математики,
как общая алгебра, комбинаторика и теория графов [1].
Учебное пособие состоит из четырех глав.
В первой главе вводятся основные термины, связанные с
множествами цепочек, а также обсуждается один из самых рас-
пространенных способов задания языков — с помощью грам-
матик Хомского.
Во второй главе описывается ряд методов задания языков,
каждый из которых определяет в точности регулярные мно-
жества. Среди них — регулярные выражения, праволинейные
грамматики, детерминированные и недерминированные конеч-
ные автоматы.
В третьей главе рассматривается класс контекстно-свобод-
ных языков и связанный с ним класс магазинных автоматов, а
также обсуждаются преобразования, которым можно подверг-
нуть контекстно-свободные грамматики, чтобы привести их к
более удобному виду.
В четвертой главе излагаются основы теории ХР-полных
задач и доказывается фундаментальная теорема Кука. Здесь
формализуется ряд интуитивных понятий, возникающих в
практике решения задач дискретной математики, таких как,
например ’’задача”, ’’алгоритм”, ’’сложность”. Вводятся клас-
сы языков Р и NV, эффективно распознаваемых на детерми-
нированных и недерминированных вычислительных устрой-
ствах, и обсуждается их связь с переборными задачами. Изу-
3
чается понятие Л'Р-полноты, выделяющее класс наиболее
трудных переборных задач, рассматриваются основные Л^Р-
полные задачи и обсуждаются методы доказательства MV-
полноты конкретных дискретных задач.
Так как лекции по теории формальных языков, автоматов и
сложности вычислений читаются в курсе после лекций по те-
ории графов, то в них мы используем без определений ряд об-
щеупотребительных теоретико-графовых терминов, таких как
граф или дерево. Чи гатель, не знакомый с терминологией те-
ории графов, может обратиться к [1 - 3] или к любой другой
литературе по теории графов. Помимо указанных от читателя
не требуется никаких других предварительных знаний, выхо-
дящих за пределы программы средней школы.
Каждая глава снабжена упражнениями, большинство кото-
рых носят чисто тренировочный характер, но некоторые из
них содержат материал, являющийся дополнением к основно-
му тексту. Диапазон трудностей упражнений весьма широк:
от простых переформулировок определений до открытых про
блем, завершающих каждую главу; к некоторым упражнениям,
не являющимся тривиальными, даны краткие указания.
Читатель, желающий расширить свои знания по теории
формальных языков, автоматов и сложности вычислений мо-
жет обратиться к монографиям [4 - 10].
Учебное пособие является одним из серии пособий ко-
торые были подготовлены в рамках работ по теме ’ Пре-
подавание фундаментальных основ программирования, со-
гласование программ курсов и подготовка учебных посо-
бий”, выполненных в 1994-95 гг. при финансовой поддерж-
ке Государственного комитета РФ по высшему образованию
(грант по исследованиям в области автоматики и телемеха-
ники, вычислительной техники и информатики, кибернети-
ки, метрологии и связи). Работы по гранту велись под ру-
ководством автора коллективом преподавателей НГУ в со-
4
ставе профессора В.А.Евстигнеева, д.ф.м.н. В.К.Сабельфельда
и доцентов М.А.Бульонкова, И.Б.Вирбицкайте, Л.В.Городней,
Н.А.Калининой и Л.С.Мельникова; всем им автор благодарен
за плодотворное и приятное сотрудничество.
Особую признательность автор выражает Л.К.Грушецкой,
разделившей с ним трудности технической подготовки руко-
писи, а также Е.В.Касьяновой за помощь при ее оформлении.
9 октября 1995 г.
В.Н.Касьянов
5
Введение
Основоположником теории формальных языков по праву
считается Н .Хомский. Именно он в 50-е годы положил начало
математическому исследованию формальных грамматик, вве-
дя некоторые важные для этого понятия (в частности, понятия
порождающей грамматики и автомата с магазинной памятью)
и доказав ряд основополагающих результатов. Возникнув в ре-
зультате усилий, направленных на разработку точных методов
описания естественных языков, теория грамматик является
активно развиваемым направлением математической лингви-
стики и теории алгоритмов, занимающимся конструктивными
способами задания множеств ’’правильно построенных выра-
жений” (формальных языков) и получившим широкое приме-
нение для описания языков программирования и автоматиза-
ции программирования методами трансляции.
Найдется немного научных терминов, так быстро завоевав-
ших широкую известность как понятие "Л'Р-полная задача".
За короткий промежуток времени с момента введения этого
понятия С.Куком в начале 70-х годов оно стало символом тех
трудностей, которые встречаются на пути создания достаточ-
но общих и эффективных методов решения задач дискретной
математики.
Неудачи, постигшие многочисленных исследователей на
этом пути, привели к необходимости анализа сложности ал-
горитмов и задач. Первые результаты о труднорешаемости
задач — полученные А.Тьюрингом около 40 лет назад и став-
шие уже классическими результаты о неразрешимости ряда
задач, для которых вообще не существует алгоритмов их реше-
ния. Например он доказал, что невозможно указать алгоритм,
который по произвольной программе определял бы, остановит-
ся ли эта программа на произвольно заданном входе или нет.
В настоящее время известно большое число других (алгорит-
мически) неразрешимых задач из разных разделов дискретной
6
математики. К ним относится, например, задача выяснения
тривиальности конечно-порожденных групп, десятая задача
Гильберта (разрешимости в целых числах полиномиальных
уравнений), ряд задач о покрытии области равными областями
и многие другие.
На практике, однако, мы не можем довольствоваться кон-
статацией того, что данная задача является разрешимой. Нам,
как правило, нужны алгоритмы, предъявляющие при своем
выполнении разумные требования к ресурсам используемых
вычислительных устройств. Вместе с тем далеко не все разре-
шимые задачи являются реально разрешимыми, и существует
феномен труднорешаемых разрешимых задач.
Первые примеры труднорешаемых разрешимых задач бы-
ли получены в начале 60-х годов в работах Лж.Хартманниса
и Р.Стирнза по ’’иерархии” сложности. Однако их приме-
ры включали только "искусственные” (специально построен-
ные) задачи. Только в начале 70-х А.Мейеру, Л.Стокмейеру,
М.Фишеру, М.Рабину и ряду исследователей удалось показать,
что некоторые "естественные” разрешимые задачи трудноре-
шаемы. Было доказано существование для любого к таких
труднорешаемых задач, временная сложность решения кото-
а*
рых больше чем 2‘ , где к — высота башни степеней, ап —
размер входа задачи.
Оказалось, что к классу труднорешаемых задач относится
большое число изучавшихся ранее задач из теории автоматов,
теории формальных языков, математической логики и других
разделов дискретной математики. Причем эти задачи не могут
быть эффективно (за полиномиальное время) решены даже с
помощью недетерминированного вычислительного устройства,
обладающего способностью параллельно выполнять неограни-
ченное количество независимых вычислений.
Все известные в настоящее время задачи, труднорешае-
7
мость которых доказала, попадают в один из рассмотренных
выше классов: они либо вовсе неразрешимы, либо труднореша-
емы даже на недерминированном вычислительном устройстве.
Вместе с тем большинство представляющихся труднорешае-
мыми практических задач дискретной математики лежит вне
этих классов и может быть решено за полиномиальное время
с помощью недетерминированной машины.
Это так называемые переборные задачи. Переборная зада-
ча характеризуется экспоненциальным множеством вариантов,
среди которых нужно найти решение, и может быть разрешена
алгоритмом полного перебора. Так, в задаче о выполнимости
логических формул решение можно отыскать среди 2П булев-
ских векторов длины п, где п - число переменных формулы, и,
перебрав это экспоненциальное множество векторов при вычи-
слении значения формулы, мы обязательно решим задачу. Пе-
реборный алгоритм имеет экспоненциальную временную слож-
ность и может хорошо работать на практике для небольших
размеров задачи. Но с ростом размера задачи число вариантов
быстро растет, и задача становится практически неразреши-
мой рассмотренным методом перебора.
Поэтому в конечной области аналогом алгоритмической не-
разрешимости является необходимость перебора экспоненци
ального числа вариантов, а аналогом разрешимости — суще-
ствование алгоритма решения задачи за полиномиальное вре-
мя на детерминированном вычислительном устройстве. При
этом Л'^Р-полные задачи являются эталоном сложности клас-
са переборных задач. На центральный вопрос, можно ли ис-
ключить перебор при решении дискретных задач, можно отве-
тить либо построив полиномиальный алгоритм решения одной
из ЛгР-полных задач, либо доказав невозможность построения
эффективного алгоритма для этой задачи. До настоящего вре-
мени эта важная проблема дискретной математики остается
открытой.
8
1 Цепочки, языки и грамматики
Учебное пособие посвящено формальным языкам — множе-
ствам, элементами которых служат цепочки символов.
В данной главе мы определим основные термины, связанные
с такими множествами, а также обсудим один из самых рас-
пространенных способов задания языков — с помощью грам-
матик Хомского.
1.1 Множества цепочек
Определение. Алфавитом называется непустое конечное
множество, элементы которого называются символами (а так-
же буквами и знаками).
Если написать последовательность символов из некоторо-
го алфавита Е, располагая их один за другим, то получается
цепочка (слово или строка) символов в алфавите Е. Число
символов в цепочке w называется ее длиной и обозначается че-
рез |ы|. Цепочка нулевой длины (пустая цепочка) не содержит
ни одного символа и обозначается через е .
Если а и 0 — две цепочки, то цепочка ш = ар называется
ком катена цией (или сцеплением) а к р. Для любого симво-
ла а и целого k,k > 0, через а* обозначается fc-кратная его
конкатенация, т.е. а0 = е, а1 = а и а*+1 = а*а для всех k > 1.
Для любых цепочек а, Р, 7 цепочка Р называется префик-
сом цепочки Ра, суффиксом цепочки аР и подцепочкой цепочки
аР^. Следует заметить, что префикс и суффикс любой цепочки
являются ее подцепочками, а пустая цепочка является префик-
сом, суффиксом и подцепочкой любой цепочки. Если а / р и а
— префикс (суффикс) цепочки р, то о называется собственным
префиксом (суффиксом) цепочки р.
Обращением цепочки а (обозначается ан) называется це-
почка а, записанная в обратном порядке, т.е. если а =
9
aia2... an, где все a< — символы, то ан = апап_).. .аг. Кроме
того, ея = е. □
Пример 1.1. Два примера алфавитов: множество, состоя-
щее из 26 прописных и 26 строчных букв (латинский алфавит)
и множество {0,1}, часто называемое двоичным алфавитом.
Последовательность а = 000110 является цепочкой длины 6
в двоичном алфавите, которую можно рассматривать как кон-
катенацию цепочек 7 = 0001 и /3 = 10, т.е. а — у/З. Цепочки
ООН, 000110, 1 — примеры подцепочек цепочки a. aR = 011000.
I3 обозначает цепочку 111, а 1° — пустую цепочку. □
Определение. Пусть Е — некоторый алфавит.
Через Е* обозначается множество всех цепочек в алфавите
Е, включая е, а через Е+ — множество Е* \ {е}.
Формально множество Е* цепочек в алфавите Е, определя-
ется по следующим правилам:
(1)е€Е%
(2) если a G Е* и a G Е, то аа G Е*,
(3) a G Е* тогда и только тогда, когда а является цепочкой
в алфавите Е в силу (1) или (2). □
Определение. Произвольное множество L цепочек в Е,
т.е. L С Е*, называется языком в алфавите S. □
Пример 1.2. Языками в двоичном алфавите, папример,
являются:
• пустой язык — 0,
• язык, состоящий из одной пустой цепочки, — {е},
• язык всех двоичных цепочек — {0,1}’,
• язык симметричных непустых двоичных слов четной дли-
ны — {ааЛ : a G {0,1}+},
• язык двоичных представлений натуральных чисел — {la :
aG{0,l}*}. О
10
Так как язык — это множество, то операции объединения,
пересечения, нахождение разности и дополнения применимы
и к языкам. Кроме того, различные операции, определенные
для цепочек, применяются и к языкам (например, Xя — {ая :
а £ X}). Среди основных из них — операции конкатенации и
итерации.
Определение. Пусть Xj — язык в алфавите Е2, а Х2 •
язык в алфавите Ej. Язык XjXj, называемый конкатенацией
(а также сцеплением или произведением) языков Xj и Ха, —
это язык
{а/3 : а 6 Xj и 0 6 Ха}.
Итерация языка X, обозначаемая через X*, определяется по
следующим правилам:
(1) L9 = {с},
(2) Ln = LLn~l для п > 1 ,
(3) X* = U Ln .
п>О
Позитивная итерация языка X, обозначаемая через Х+ , —
это язык (J X". Заметим, что Х+ = XX* = Х*Х и X* = Х+и{е}.
П>1
□
Пример 1.3. Пусть Х2 = {О" 1 :п >0} иХ2 = {10" : п > 0}
Тогда L\L,2 = {0"110m : n > 0, т > 0} и X* = {е} U {0"1 : п >
0} U {0"10т1 : п > 0,т > 0} U {0"10m10*l : п > 0,m > 0,к >
0}... □
1.2 Грамматики составляющих
Рассмотрим задачу задания языка. Если определяемый язык
X состоит из небольшого числг цепочек, то самый очевидный
способ описания языка — составить список всех цепочек из
X. Однако многие языки (например, языки программирова-
ния) невозможно или нежелательно задавать исчерпывающим
11
перечислением входящих в них цепочек, и поэтому, как пра-
вило, используются другие способы определения языка. При-
чем, используются только такие способы, которые позволяют
описанию языка быть обозримым (заведомо конечным), хотя
описываемый язык может быть и бесконечным. Известно не-
сколько методов определения языка, удовлетворяющих этому
требованию.
Один из них связан со способом задания множества с по-
мощью характеристического свойства (предиката) и состоит
в использовании частичного алгоритма (предписания произво-
дить некоторые действия), который для произвольной входной
цепочки остановится и ответит ”да” после конечного числа ша-
гов, если эта цепочка принадлежит языку. Схематизированные
устройства, используемые для представления таких алгорит-
мов, получили название распознавателей. Примерами распо-
знавателей являются рассмотренные ниже конечные автома-
ты, автоматы с магазинной памятью и машины Тьюринга.
Второй метод описания языка имеет вид исчисления, назы-
ваемого грамматикой составляющих, — некоторой порождаю-
щей системы (разрешения производить некоторые действия),
используя которую можно получить (породить) все цепочки
языка L и только их. Одно из преимуществ определения языка
с помощью грамматики составляющих в том, что грамматика
придает цепочкам (’’предложениям”) языка полезную струк-
туру, которая может использоваться, например, для придания
смысла предложениям языка.
В грамматике, определяющей язык Z, используются два
непересекающихся алфавита: терминальных и нетерминаль-
ных символов. Из терминальных символов образуются цепочки
определяемого языка L, а терминальные символы используют-
ся при порождении языка L как вспомогательные.
Сердцевину грамматики составляет конечное множество
порождающих правил (или правил вывода), которые могут
12
использоваться в процессе получения цепочек языка. Каждое
такое правило — это просто пара, состоящая из заменяемой
и заменяющей цепочек в алфавите терминальных и нетерми-
нальных символов. Причем, заменяющей может быть любая
цепочка, а заменяемая должна содержать хотя бы один нетер-
минал.
Если установлено, что некоторая цепочка а порождается
грамматикой (или, как говорят, выводится в ней), то также
выводимой в данной грамматике является любая цепочка, ко-
торая получается из а заменой в ней подцепочки, являющей-
ся заменяемой цепочкой некоторого правила грамматики, на
заменяющую цепочку соответствующего правила. Например,
пусть некоторая цепочка а = FGABH АВ порождается грам-
матикой, в которой есть правило с заменяемой цепочкой АВ и
заменяющей CDE. Тогда также выводимы в данной грамма-
тике цепочки 0 = FGCDEHАВ и 7 = FGABHCDE, которые
можно получить подходящими заменами в цепочке а подцепоч-
ки АВ на CDE.
Язык, определяемый грамматикой, — это множество цепо-
чек, которые состоят только из терминальных символов и вы-
водятся, начиная с одной особой цепочки, состоящей из одного
выделенного символа, называемого начальным.
Перейдем к формальному определению грамматики.
Определение. Порождающей грамматикой (или просто
грамматикой) называется четверка G — (/V,E, Р, S), где
(1) N — алфавит нетерминальных символов, или нетер-
миналов (иногда называемых вспомогательными символами,
синтаксическими переменными или понятиями);
(2) Е — не пересекающийся с N алфавит терминальных
символов, или терминалов;
(3) Р — конечное множество так называемых правил (или
продукций) — слов вида
а —♦ 0
13
где a G (О E)*jV^ U £)*,/? G (N U E)* и ” —» ” — символ,
не принадлежащий ни N, ни Е;
(4) S — выделенный символ из N, называемый начальным
(или исходным) символом. □
Пример 1.4. Примером грамматики служит четверка G =
({A,S},{0,1},P,S), где Р состоит из правил
5 —♦ 0А1
ОА —♦ ООА1
А —♦ е .
Нетерминальными символами являются А и S, а терми-
нальными — 0 и 1. □
Определение. Пусть G = (./V, Е, Р, S) — грамматика.
Отношение непосредственной выводимости =>G на мно-
жестве (N U Е)‘ определяется следующим образом: если а/?7 -
цепочка из (/VUE)* и /3 —♦ 6 — правило из Р, то а(3-у =>G аб-у.
Транзитивное замыкание отношения =>с обозначается че-
рез =>g (<р Ф читается: V’ выводима из <р нетривиальным
образом), а его рефлексивное и транзитивное замыкание — че-
рез =>G (<р =^g Ф читается: ф выводима из <р).
Через =>g будем обозначать ^-степень отношения и будем
опускать нижний индекс G в тех случаях, когда из контекста
ясно, о какой грамматике идет речь.
Последовательность а0, , состоящая из к + 1 цепо-
чек (не обязательно различных), в которой а = а0 , a,_j
а, для всех i > 1 и а* = 3 , называется выводом длины к
цепочки в из цепочки а в грамматике G.
Цепочка а называется выводимой цепочкой грамматики G,
если S =>,g о.
Язык, порождаемый грамматикой G (обозначается L(G))
— это множество терминальных выводимых цепочек грамма-
тики G, т.е. L(G) = {w : ш Е Е’ и S =>G ш}. □
14
Пример 1.5. Рассмотрим грамматику G из примера 1.4 и
вывод S 0А1 ==> 00А11 => ООН.
На первом шаге этого вывода S заменяется на 0А1 в соот-
ветствии с правилом S —♦ 0А1. На втором шаге ОА заменя-
ется на 00А1, и на третьем шаге А заменяется на е. Можно
сказать, что S =>3 ООН, S =>+ ООН, S =^* ООП, и что ООН
принадлежит языку L(G). Можно показать, что грамматика
порождает язык L(G) = {0"1“ : п > 1}. □
Пример 1.6. Пусть G = ({E,T,F},{a,+,*,(,)},P,E), где
Р — состоит из правил
Е —♦ Е + Т\Т
T—*T*F\F
F—>{E)\a.
Вот пример вывода в этой грамматике
Е => Е + Т
=> Т + Т
=> F + T
=> а + Т
=> а 4- Т * F
=> а + F ♦ F
=> а + а * F
=> а + а ♦ а .
Язык 1(G) представляет собой множество арифметических
выражений, построенных из символов <»,+,♦, ( и ). □
Замечание. Для обозначения п правил
а —
а —♦ 02
15
a
0п
удобно пользоваться сокращенной записью
а—> Д|Д|...|Л .
Примем еще следующие соглашения относительно различ-
ных символов, связанных с грамматикой:
(1) a,b,c,d и цифры 0,1,...,9 обозначают терминалы;
(2) А, В, С, D,S обозначают нетерминалы; S — начальный
символ;
(3) обозначают либо нетерминалы, либо терми-
налы.
Эти соглашения распространяются также и на буквы с ниж-
ними и верхними индексами. Мы не будем напоминать об этих
соглашениях, когда рассматриваемые символы им удовлетво-
ряют. О
Указанные соглашения избавляют от необходимости при
описании грамматики говорить о множествах терминалов и не-
терминалов или о начальном символе. Например грамматику
G примера 1.4 можно задать списком правил
S —» 041
04 —♦ 0041
4 —♦ е.
Определение. Две грамматики называются эквивалент-
ными, если они порождают один и тот же язык. □
Пример 1.7. Эквивалентной грамматике примера 1.6 явля-
ется грамматика с правилами
Е -- Е+ Е | Е • Е | (Е) | а ,
16
а также грамматика с правилами
Е + Т\Е*Т\Т
Т_(Е)\а.
Приведем еще примеры грамматик.
Пример 1.8. Пусть грамматика G определяется правилами
S aS ВС | аЬС
СВ — ВС
ЬВ —*ЬЬ
ЬС —♦ Ьс
сС —» сс .
В грамматике G возможен вывод
aSBC
ааЬС ВС
ааЬВСС
ааЬЬСС
aabbcC
aabbcc .
Эта грамматика порождает язык {апЬпсп : п > 1} . □
Пример 1.9. Пусть G — грамматика с 11 правилами
S - » CD Ab — bA
с ► аСА Ba —♦ aB
с ► ЬСВ Bb bB
AD ► aD C e
BD ► bD D e
Аа > аА .
17
Пример вывода, в грамматике G:
S => CD
=> aCAD
=► abCBAD
=> abBAD
=> abBaD
=> abaBD
ababD
=> abab .
Можно показать, что L(G) = {uw : w 6 {a, 6}*}, т.е. L(G)
состоит из цепочек четной длины, составленных из букв а и Ь,
причем первая половина каждой цепочки совпадает со второй
половиной. □
1.3 Грамматики с ограничениями на правила
Грамматики можно классифицировать по виду их правил.
Определение. Пусть G = (N,^,P,S) — грамматика. G
называется:
(1) праволинейной, если каждое правило из Р имеет вид
А —♦ аВ или А —♦ а, где А, В € Лг и a € S’;
(2) контекстно-свободной (или бесконтекстной), если ка-
ждое правило из Р имеет вид А —♦ о, где A G и a 6 (iVUE)*;
(3) контекстно-зависимой (или неукорачивающейся), если
каждое правило из Р имеет вид а —♦ 0, где |а| < |/?|.
Грамматика, на которую не накладывается ни одно из ука-
занных ограничений, называется грамматикой составляющих
(или грамматикой с фразовой структурой). □
Пример 1.10. Грамматика примера 1.4 праволинейная.
Другой пример праволинейной грамматики — грамматика с
правилами
S —* OS | IS | е .
18
Эта грамматика порождает язык {0,1}*.
Важным примером контекстно-свободной грамматики слу-
жит грамматика примера 1.6.
Рассмотренная в примере 1.8 грамматика, очевидно, кон-
текстно-зависимая, а грамматика примера 1.9 — граммати-
ка составляющих, которая не является ни праволинейной, ни
контекстно-свободной, ни контекстно-зависимой. □
Заметим, что согласно определению каждая праволинейная
грамматика контекстно-свободная. Следует подчеркнуть, что
определение контекстно-завися мой грамматики не допускает
правил вида А —» е, обычно называемых е- правилами. Та-
ким образом, контекстно-свободная грамматика, содержащая
е-правила, не является контекстно-зависимой.
Запрещение е-правил в контекстно-зависимой грамматике
вызвано желанием гарантировать так называемую рекурсив-
ность порождаемого ею языка. Иначе говоря, желанием иметь
алгоритм, который для произвольной контекстно-зависимой
грамматики G и входной цепочки определял бы, принадле-
жит ли эта цепочка языку L(G).
Если допустить, что среди правил контекстно-зависимой
грамматики есть только одно е-правило (не снимая с грамма-
тики остальных ограничений), то расширенный класс грам-
матик уже способен порождать все языки с фразовой структу-
рой (см. упражнение 1.9). Этот более широкий класс обладает
более слабым свойством так называемой рекурсивной перечи-
слимости, означающим существование алгоритма порождения
всех цепочек данного языка и только их.
Определение. Язык L называется праволинейным, кон-
текстно-свободным, контекстно-зависимым или с фразовой
структурой, если существует грамматика G соответствую-
щего типа, которая порождает этот язык, т.е. для которой
£(G) = L. □
19
Указанные четыре типа грамматик и языков часто называ-
ют иерархией Хомского.
Пример 1.11. Язык L(G) примера 1.4 — праволинейный,
язык 1(G) примера 1.7 — контекстно-свободный, а язык L(G)
примера 1.8 — контекстно-зависимый. Язык {шш : w G {а,6}*},
порожденный грамматикой примера 1.9, — это язык с фразовой
структурой, а язык {ww : w Е {а,4)‘ и / е} - контекстно-
зависимый. □
Замечание. Далее мы будем иногда пользоваться стан-
дартными сокращениями КС и КЗ для терминов "контекстно-
свободный” и ’’контекстно-зависимый" соответственно. □
Теорема 1.1. Язык является контекстно-зависимым тогда
и только тогда. когда он может быть порожден грамматикой
G = (N,E,P, S), в которой каждое правило имеет вид
аА(3 —► auf},
где А € jV,u> Е (ЛШ£)+ и a,0 € (N U Е)*.
Доказательство. Достаточность очевидна, поскольку
|аЛД| = |а| + |Л| + |Д| = |а| + 1 + |Д| < |а| + |w| + |Д| = |аы0|.
Покажем необходимость. Если L контекстно-зависимый
язык, то существует грамматика G = (TV, Е,Р, S), которая по-
рождает язык L и содержит правила о —► Д, удовлетворяю-
щие соотношениям 1 < |а| < |Д|, т.е. правила, которые имеют
вид:
1) А —♦ ZxZ2...Zm или же
2) ЦV2 ... Vn —► ZXZ2... Zm, где 1 < n < m.
Во всех правилах заменим каждый встречающийся терми-
нал a G Е новым (т.е. не принадлежащим множеству нетерми-
налов грамматики) нетерминальным элементом Аа и добавим
в грамматику правила Аа —* а.
20
В результате получим эквивалентную грамматику, в кото-
рой все правила имеют правильную форму, за исключением
правил вида А3... Ап —♦ В} В2... Вт, где 1 < п < т, полу-
ченных из правил типа 2. Для каждого такого правила введем
новые нетерминальные символы Pt,...,Pm и заменим его на
п + т следующих правил:
п правил
А\А2Аз... Ап —♦ Di Л 2 A3 ... Ап
D] А2 А3... Ап —♦ Di D2A3... Ап
D\... Вп_!Ап —♦ Di... Dn_iDn ••• Dm
и т правил
D1D2D3... Dm —* B1D2D3... Dm
BlD2D3...Dm-^ BlB2D3...Dm
B\... Bm_iDm —♦ B\... Bm-\Bm.
Полученная в результате грамматика эквивалентна исход-
ной и имеет нужный вид, что завершает доказательство тео-
ремы. □
Определение. КС-грамматика <7=(Л\Е, P,S) называется
грамматикой без е-правил, если
либо Р не содержит е-правил, т.е. правил вида А —» е, где
А€ ЛГ,
либо в Р есть точно одно е-правило S —» е и S не встреча-
ется в правых частях остальных правил из Р. □
Алгоритм 1.1.
Вход. Контекстно-свободная грамматика G - (N,£, P,S).
Выход. Эквивалентная контекстно-свободная грамматика
G' — (N',L,P,,S>) без е-правил.
Метод.
1. Построить Ne = {А : А € N и A е} следующим
образом:
21
(а) Положить No = {A : A —» e € P} и » = 1.
(б) Положить N, = {A : A —» a € P и a G U
(в) Если Ni / Ni.i, положить t = t +1 и перейти (вер-
нуться) к шагу 1,а. В противной случае положить
N, = Ni.
2. Построить Р‘ так:
(а) Если А —» а0Вха}В7а2... Вкак принадлежит Р,
к > 0 и Bi G Nt для 1 < i < к, но ни один сим-
вол в цепочках а, (0 < t < к) не принадлежит Nt, то
включить в Р‘ все правила вида
А —* аоХ^ауХз ... ak^iX как,
где Xi — либо Bi, либо е, но не включать правило
А —♦ е (это могло бы произойти в случае, если все
а, равны е).
(б) Если S € N,, то включить в Р1 правила
S' —» е | S,
где S' — новый символ, и положить N' = N U {S1}.
В противном случае положить N' = N и S' = S.
3. Положить G' = (JV',E, P',S'). □
Пример 1.12. Рассмотрим грамматику с правилами
S aSbS|bSaS|е .
Применяя к этой грамматике описанный выше алгоритм,
получаем грамматику
S' — S | е
22
S —♦ aSbS | bSaS | aSb | abS | ab | bSa | baS | ba . □
Теорема 1.2. Алгоритм 1.1 строит грамматику без е-
правил, эквивалентную входной грамматике.
Доказательство. Очевидно, что алгоритм всегда остана-
вливается через конечное число шагов. Действительно, Nt С
jV, и каждое повторение шага 1.6, отличное от последнего, рас-
ширяет Ne по крайней мере на один элемент. Поэтому алго-
ритм должен остановиться самое большее после п + 1 повторе-
ний шага 1.6, если Л' содержит п нетерминалов.
Непосредственно видно, что алгоритм строит грамматику
G' без е-правил. Чтобы доказать, что L(G) = L(G'), доста-
точно показать индукцией по длине цепочки ш, что A =>G. ш
тогда и только тогда, когда ш / е и A =>*G ш.
Доказательство этого утверждения оставляем в качестве
упражнения. Подставив S вместо А в данное утверждение,
видим, что w G L(G) для ш / е тогда и только тогда, ко-
гда w G ЦС'). Очевидно, что е G L(G) тогда и только тогда,
когда е 6 Таким образом, L(G) = L(G'). □
Упражнения
1.1. Докажите, что L(G) = {0"1" : п > 1}, где G — грамма-
тика из примера 1.4.
1.2. Докажите, что Z(G) = {an6ncn : n > 1), где G — грам-
матика из примера 1.8.
1.3. Докажите, что L(G) = {ош : ы G {а,Ь}*}, где G —
грамматика из примера 1.9.
1.4. Постройте контекстно-свободные грамматики, поро-
ждающие
а) все цепочки из нулей и единиц с одинаковым числом тех
и других;
б) {их^я : ш G {0,1}+};
в) всевозможные последовательности правильно расста-
вленных скобок;
23
г) {Onln :п > 1}.
1.5. Постройте контекстно-зависимые грамматики, поро-
ждающие
а) {<*"’: n > 1};
б) {ыо> :w е {в,Ь}+);
в) {ambnambn sn,m > 1};
г) {w :w€ {а,Ь,с}+ и число букв а в цепочке ш равно числу
букв Ь, равному числу букв с}.
1.6. Опишите язык, порождаемый грамматикой
S —► bSS | а .
1.7. Какой класс языков может порождаться грамматиками,
использующими только левый контекст, т.е. грамматиками,
в которых каждое правило имеет вид
аА —* а/3 ,
где а е (2VuE)’,0 G (tfuE)+?
1.8. Докажите, что алгоритм 1.1 строит по исходной грам-
матике G такую грамматику G', что для любых нетерминала
А и цепочки и) справедливо А =>д. w тогда и только тогда,
когда и> / е и A =^G w.
1.9. Покажите, что если G = (ЛГ, Е,Р, S) — грамматика со-
ставляющих, то существует такая контекстно-зависимая грам-
матика G' = (JV', Е U {с}, Р1, S'), что w € 1(G) тогда и только
тогда, когда wc’ G L(G') для некоторого i > 0.
Проблема для исследования-.
1.10. Является ли дополнение любого контекстно-зависи-
мого языка контекстно-зависимым?
24
2 Регулярные множества,
их распознавание и порождение
Регулярные множества образуют класс языков, занимаю-
щих центральное положение по отношению к значительной
части теории формальных языков.
В данной главе мы опишем несколько методов задания язы-
ков, каждый из которых определяет в точности регулярные
множества. Среди них — регулярные выражения, праволиней-
ные грамматики, детерминированные и недерминированные
конечные автоматы.
2.1 Регулярные множества
и регулярные выражения
Определение. Пусть Е — некоторый алфавит. Регуляр-
ное множество в алфавите Е определяется рекурсивно следу-
ющим образом:
(1) 0 (пустое множество) — регулярное множество в алфа-
вите Е;
(2) {е} — регулярное множество в алфавите Е;
(3) {а} — регулярное множество в алфавите Е для каждого
элемента а Е Е;
(4) если Р, Q — регулярные множества в алфавите Е, то
регулярными являются множества
(a) PUQ,
(б) PQ,
(в) Р';
(5) других регулярных множеств в алфавите Е нет. □
Итак, некоторое множество цепочек в заданном алфавите
Е называется регулярным тогда и только тогда, когда либо
25
оно является одним из множеств: 0, {е} или {а} для некоторо-
го а G Е, либо его можно получить из этих множеств приме-
нением конечного числа операций объединения, конкатенации
и итерации. Удобным способом обозначения регулярных мно-
жеств являются регулярные выражения.
Определение. Регулярные выражения в алфавите S и ре-
гулярные множества, которые они обозначают, определяются
рекурсивно следующим образом:
(1) 0 — регулярное выражение, обозначающее регулярное
множество 0;
(2) е — регулярное выражение, обозначающее регулярней?
множество {е},
(3) если a G S, то а — регулярное выражение, обозначающее
регулярное множество {а},
(4) если р и q — регулярные выражения, обозначающие ре-
гулярные множества Р и Q соответственно, то
(а) (р+д) — регулярное выражение, обозначающее мно-
жество Р U Q-,
(б) (pg) — регулярное выражение, обозначающее мно-
жество PQ-,
(в) (р)* — регулярное выражение, обозначающее мно-
жество Р‘ ;
(5) других регулярных выражений нет. □
Замечание. Мы будем пользоваться записью р+ для со-
кращенного обозначения выражения рр* и, кроме того, будем
устранять из регулярных выражений лишние скобки там, где
это не может привести к недоразумениям. В этой связи пред-
полагается, что наивысшим приоритетом обладает операция
*, затем идет конкатенация и далее операция +. Так, 0 + 10‘
означает (0 + (1(0*))). □
Пример 2.1. Вот несколько примеров регулярных выраже-
ний и обозначаемых ими множеств:
26
(1) 01 обозначает {01}.
(2) 0* обозначает {0}*.
(3) (0 + 1)* обозначает {0,1}*.
(4) (0 + 1)*011 обозначает множество всех цепочек, соста-
вленных из нулей и единиц и оканчивающихся цепочкой 011.
(5) (а + 6)(а + 6 + 0 + 1)* обозначает множество всех цепочек
из {0,1, а, 6}*, начинающихся с а или 6.
(6) (00+11)*((01 + 10)(00 + 11)*(01 + 10)(00+11)*)* обозначает
множество всех цепочек нулей и единиц, содержащих четное
число нулей и четное число единиц. □
Очевидно, что для каждого регулярного множества суще-
ствует по крайней мере одно регулярное выражение, обозна-
чающее это множество. И обратно, для каждого регулярного
выражения можно построить регулярное множество, обознача-
емое этим выражением. К сожалению, для каждою регулярно-
го множества существует бесконечно много обозначающих его
регулярных выражений.
Говорят, что два регулярных выражения равны (=), если
они обозначают одно и то же множество.
Ниже приводятся некоторые основные алгебраические свой-
ства регулярных выражений.
Пример 2.2. Пусть а,0 и 7 — регулярные выражения. То-
гда
(1) а + /3 = /3 + а ;
(2) а + (/3 + 7) = (а +/3) + 7
(3) а(/3 + 7) = а/3 + а7 ;
(4) ае = еа — а ;
(5) а* = а + а* ;
(6) а + а = а ;
(7) 0* = е ;
(8) а(^7) = (а/3)7 ;
(9) (а + /3)7 = агу + /З7
(10) 0а — а0 = а ;
(11) (а*)* = а* ;
(12) а + 0 = а .
27
2.2 Конечные автоматы
Определение. Недетерминированный конечный авто-
мат (или просто конечный автомат) — это пятерка М =
(Q,L,6,q0, F), в которой
(1) Q — конечное множество состояний1,
(2) Е — конечное множество допустимых входных символов]
(3) 6 — отображение множества Q X Е в множество подмно-
жеств Q, называемое функцией переходов]
(4) € Q — выделенное начальное состояние]
(5) F С Q — множество заключительные состояний. □
Определение. Если М = {Q,Y,,b,q^,F) — конечный авто-
мат, то пара (g,u>) € Q х Е* называется конфигурацией авто-
мата М. Конфигурация (qo,<*>) называется начальной, а пара
(q,e), где q G F, называется заключительной (или допускаю-
щей).
Такт работы автомата М представляется бинарным отно-
шением определенным на конфигурациях. Если 6(q,a) со-
держит р, то (q,aw) FM (р,о>) для всех G Е*. Отношения F^
и F^ являются соответственно транзитивным замыканием и
рефлексивным и транзитивным замыканием отношения FM.
Автомат М допускает цепочку w € Е‘,если (g0,w) \-‘м (q,e)
для некоторого q Е F. Языком, определяемым (распознавае-
мым, допускаемым) автоматом М (обозначается L(M)), назы-
вается множество входных цепочек, допускаемых автоматом
Л/, т.е. L(M) = Е‘ и (g0,w) (9,е) для некоторого
q е Г}. О
Конечный автомат можно представить в виде устройства,
состоящего из входной ленты, входной головки и управляюще-
го устройства.
Входная лента — это линейная последовательность клеток,
или ячеек, каждая из которых может содержать любой символ
28
из Е. В каждый данный момент входная головка читает, или,
как иногда говорят, обозревает одну входную ячейку, а упра-
вляющее устройство находится в одном состоянии из конечного
множества Q, т.е. имеет конечную память.
Работа конечного автомата представляет собой некоторую
последовательность шагов (или тактов). Каждый такт опреде-
ляется текущим состоянием управляющего устройства и вход-
ным символом, обозреваемым в данный момент входной голов-
кой. Сам шаг состоит из изменения состояния управляющего
устройства и сдвига входной головки на одну ячейку вправо.
Следует заметить, что в нашем определении конечный ав-
томат — недетерминированное устройство, и для каждой теку-
щей конфигурации в общем случае существует конечное мно-
жество возможных следующих шагов, любой из которых ко-
нечный автомат может сделать, исходя из этой конфигурации.
Можно представлять себе, что конечный автомат переходит
из текущего состояния во все свои следующие состояния, как
бы дублируя себя таким образом, что в каждое из возможных
следующих состояний переходит свой экземпляр этого устрой-
ства. При такой трактовке конечный автомат допускает вход-
ную цепочку, если какой-либо из его параллельно работающих
экземпляров достигает допускающей конфигурации.
Определение. Пусть = (Q,L,6,q0,F) — конечный ав-
томат. М называется детерминированным, если множество
0(д,а) содержит не более одного состояния для любых q G Q и
а G Е. Если 6(q,a) всегда содержит точно одно состояние, то
автомат М называется полностью определенным. □
Приведем два примера конечных автоматов. Первый — при-
мер простого "детерминированного” автомата; второй пример
показывает использование недетерминизма.
Пример 2.3. Пусть М = ({р,q, г}, {0,1},6,р, {г}) — конеч-
ный автомат, где 6 задается табл. 2.1.
29
Табл. 2.1
Состояние Вход
0 1
Р {q} {р}
q {г} {р}
г {г} {г}
М допускает все цепочки нулей и единиц, содержащие два
стоящих рядом нуля. Начальное состояние р можно интерпре-
тировать так: ’’два стоящих рядом нуля еще не появились и
предыдущий символ не был нулем”. Состояние q означает, что
”два стоящих рядом нуля еще не появились, но предыдущий
символ был нулем”. Состояние г означает, что ’’два стоящих
рядом нуля уже появились”. Заметим, что попав в состояние
г, автомат М остается в этом состоянии.
Для входа 01001 единственной возможной последовательно-
стью конфигураций, начинающейся конфигурацией (р,01001),
будет
(р,01001) F (9,1001)
h (р,001)
ь (9,01)
Ь (г,1)
Ь (г,е).
Таким образом, 01001 Е £(Af). О
Пример 2.4. Построим недетерминированный конечный
автомат, допускающий цепочки в алфавите {1,2,3}, у кото-
рых последний символ цепочки уже появлялся в ней раньше.
Иными словами, цепочка 121 допускается, а 31312 — нет. Вве-
дем состояние 7о, смысл которого в том, что автомат в этом
30
Табл. 2.2
Состояние Вход
1 2 3
9о {9o,9i} {90,92} {9о,9з}
91 {fli,?/} {91} {91}
92 {92} {92,9/} {92}
9з {9з} {9з} {9з, 9/}
Ч) 0 0 0
состоянии не пытается ничего распознать, он (или какой-то
его экземпляр) находится в так называемом нейтральном со-
стоянии. Введем также состояния qx,qi и 93, смысл которых в
том, что они "делают предположение” о том, что последний
символ цепочки совпадает с индексом состояния. Кроме то-
го, пусть будет одно заключительное состояние qf. Находясь
в состоянии q0, автомат может остаться в нем или перейти
в состояние qa, если а — очередной символ. Находясь в со-
стоянии qa, экземпляр автомата может перейти в состояние
qf, если видит символ а. Из состояния qj автомат никуда не
переходит, так как вопрос о том, допускается ли входная цепоч-
ка, решается только один раз, когда автомат сочтет входной
символ "последним”. Формально автомат М определяется как
пятерка
М = ({g0,91,92,9з,9/}, {1,2,3},6,q0, {«?/}),
где <5 задается табл. 2.2.
Процесс порождения конфигурации для входа 12321 показан
на рис. 2.1.
Так как (д0,12321) Р (д/,е), то 12321 € 1(М). Заметим, что
некоторые конфигурации на рис. 2.1 повторяются. Поэтому для
31
(9o,12321)—(go,2321)_(9o,321)-(9o,21)—(<?о,1)—(9о,е)
'Ч---(92,321)^-(q2,21)— (^2,1)—(?2,е)
-----(9/ Л)
91,2321)—(91,321)—(gi, 21)—(91,1)—(9i,e)
(<?/,«)
Рис. 2.1
представления конфигураций, в которые попадает автомат М
больше подходит ориентированный ациклический граф. □
Часто бывает удобно использовать графическое представле-
ние конечного автомата.
Определение. Пусть М = (Q, S,6,90, F) — недетерми-
нированный конечный автомат. Диаграммой (или графом пе-
реходов) автомата М называют неупорядоченный помеченный
граф, вершины которого помечены символами состояний и в
котором есть дуга (р, 9), если существует такой символ a G Е,
что 9 G 6(р,а). Кроме того, дуга (р,9) помечается списком,
состоящим из таких а, что 9 G 6(р,а). □
Пример 2.5. На рис.2.2 изображены диаграммы автоматов
из примеров 2.3 и 2.4. Начальное состояние автомата указыва-
ется на диаграммах направленной на него стрелкой, помечен-
ной словом "начало”, а заключительные состояния обводятся
дополнительным кружком. □
32
Замечание. Так как нам придется рассматривать в основ-
ном детерминированные конечные автоматы, мы будем писать
6(q,a) = р вместо 6(q,a) = {р}, когда автомат с функцией пе-
реходов 6 детерминированный, и говорить, что 6(q,a) не опре-
делено, если 6(q,a) = 0. □
Теорема 2.1. (Теорема о детерминизации). Если L =
L(M) для некоторого недетерминированного конечного авто-
мата М, то L = L(M') для некоторого полностью определен-
ного конечного автомата М1.
Доказательство. Пусть М = (Q,E,6,qo,F). Построим
М' = (Q',E,6',q'o, F*) следующим образом:
(1) Q' = 2^, т.е. состояниями автомата М' являются мно-
жества состояний автомата М\
(2) 9о = {9о};
33
(3) F1 состоит из всех таких подмножеств S множества Q,
что S Л F / 0;
(4) 6(S,a) = S' для всех S С Q, где S' = {р : 6(q,a) содержит
р для некоторого q € S}.
Оставляем в качестве упражнения доказательство индукци-
ей по i того, что (5,w) (S',e) тогда и только тогда, когда
S' = {р : (g,w) (р,е) для некоторого q 6 S).
Из этого утверждения следует, что ({<?0},ш) (5',е) для
некоторого состояния S' € F' тогда и только тогда, когда
(9o>w) (р,е) для некоторого р G F. Итак, L(M') = ЦМ). □
Пример 2.в. Построим конечный автомат
М' = ((?,{!, 2,F),
допускающий язык L(M), определяемый автоматом М из при-
мера 2.4. Так как М имеет 5 состояний, то, казалось бы, М'
должен иметь 32 состояния. Однако не все они достижимы из
начального состояния. Состояние R называется достижимым
в М', если существует такая цепочка ш, что ({go},w) h* (Я,е),
где {д0} — начальное состояние автомата М'. Мы будем стро-
ить только достижимые состояния.
Совершенно ясно, что состояние {д0} достижимо. Далее
заметим, что £'({9о}»«) = {9о,9«} Для а = 1,2 и 3. За-
тем рассмотрим состояние {?o-9i} и для него получим, что
^({9о»91}» 1) = {<7o.9i>9/}• Продолжая указанные рассуждения,
убедимся в том, что множество состояний автомата М (оно
является состоянием автомата М') достижимо только тогда,
когда справедливы следующие два свойства: оно содержит q0
и либо не содержит д/, либо содержит Ц/ вместе с состоянием
«ь q? или q3.
Множество всех достижимых состояний автомата М' вме-
сте с функцией 6' приведено в табл. 2.3.
Начальным состоянием автомата М' является А, а множе-
ством заключительных состояний — □
34
Табл. 2.3
Состояние Вход
1 2 3
Л = {д0} В С D
В = {9о, 91} Е F G
С = {90,92} F Н I
D = {до,дз} G I J
Е = {9o,9i,9/} Е F G
F = {90,91,92} К К L
G = {до,91,9з} М L М
Я = {9о,92,9/} F Н I
I — {9о,92,9з} L N N
J = {9о,9з,9/} G I J
К = {90,91,92,9/} К К L
L = {до, 91,92,9з} Р Р Р
М = {до, 91,93,9/} М L М
N = {до, 92,9з, 9/} L N N
Р = {9о,91,92,9з,9/} Р Р Р
2.3 Свойства регулярных множеств
Определение. Праволинейная грамматика G = (N,"£,P,S)
называется регулярной (или автоматной), если
(1) все ее правила, за исключением S —♦ е, имеют вид
А —♦ аВ или А —* а, где В G N, а G Е,
35
(2) если S —» е принадлежит Р, то S не встречается в
правых частях правил. □
Теорема 2.2. Эквивалентны следующие утверждения:
(1) L — регулярное множество,
(2) L — праволинейный язык,
(3) L — язык, порождаемый регулярной грамматикой,
(4) L — язык, допускаемый недетерминированным конеч-
ным автоматом,
(5) L обозначается регулярным выражением.
Доказательство
(1) —♦ (2). Докажем индукцией по числу шагов в рекурсив-
ном определении регулярного множества L.
Очевидно, что 0, {е} и {а} для всех а € Е — праволинейные
языки.
Пусть L построено из регулярных множеств Li и £2, ко-
торые порождаются праволинейными грамматиками Gi =
hGj = (N2,L2,P2,S2) соответственно, и пусть
S — символ, не принадлежащий ни ни N2. Определим
праволинейную грамматику G = (JV,E,P, S), по следующим
правилам:
(а) Если В — Ij\ U L2, то Л — Ni U N2 U {S}.E = Ej U E2 и
P = Px U PaU {$ —» й | 52};
(б) Если L = LiL2, to N = Ni U N2 U {5},E = Ei U E2,
а множество P состоит из всех продукций из Р2, которые не
являются е-правилами, продукции S —» Si, всех тех продук-
ций из Рь которые имеют вид А —♦ аВ, где А, В 6 М и
a G Ej, и содержит по одной продукции А —♦ aS2 для каждой
такой продукции А —♦ а из Pi, в которой a G Е|, а также
продукцию S —» S2, если е G и все продукции А —» а из
Pi, в которых a Е Е|, если е Е £2,
(в) Если L = L*, то N = Ni U {S},E = Еь а множество
Р состоит из всех продукций из Рх отличных от Si —» е,
36
продукций S —♦ Si | e, а также продукций вида A —► aSj
для всех тех продукций А —♦ а из Рь в которых a G Sf.
Очевидно, что L(G) = L для каждого из способов построе-
ния L.
(2) —* (3). Пусть G = (N,L,P,S) — праволинейная грам-
матика. Рассмотрим следующую последовательность преобра-
зований, которая переводит G в эквивалентную регулярную
грамматику.
Сначала применим к G алгоритм 1.1; пусть G — полученная
в грамматика без е-правил. Очевидно, что G — праволинейная
грамматика.
Осуществим преобразование грамматики G по следующим
правилам.
Если продукция А —♦ а1а2...а* принадлежит Р, к > 1 и
а, € Е для всех », то заменяем ее на к продукций
А * Oj А?
Aj —* о2Аз
Ак —► ак ,
где Д2, А3,... Ак — новые нетерминалы.
Если продукция А —♦ ага2...акВ принадлежит Р, к > 1,
В G А и a, G S для всех », го заменяем ее на к продукций
А —♦ Qj А2
А2 —» а2А3
где A2,A3,...,Ak — новые нетерминалы.
Нетрудно убедиться, что полученная в результате преобра-
зований грамматика является эквивалентной исходной и регу-
лярной.
(3) —♦ (4). Пусть G = (JV,E,P, S) — регулярная грамма-
тика, и пусть В. — символ, не принадлежащий ЛГ. Построим
автомат М = (N U {Я},Е,£, S, F), где для любых a Е Е и
А, В 6 N функция 6 и множество F определены по следующим
правилам:
(а) В Е б(А,а) тогда и только тогда, когда А —► аВ содер-
жится в Р;
(б) Я Е 6(А,а) тогда и только тогда, когда А —♦ а содер-
жится в Р;
(в) F = {Я}, если G не содержит е-правил, и F = {Я,5},
если S —» е принадлежит Р.
Заметим, что е Е L(G) тогда и только тогда, когда е Е
ЦМ).
Индукцией по i можно показать, что для любого А Е JV и
любой а Е Е+ справедливо А =>' а тогда и только тогда,
когда (А,а) Н (Я,е).
Базис индукции очевиден, поскольку А —♦ а Е Р равно-
сильно Я Е £(А,а). Пусть утверждение истинно для i и рас
смотрим а = а0, где | 0 |= ». Тогда А =>'+1 а равносиль-
но тому, что А —> аВ =>' а0 для некоторого В Е N. Но
А —♦ аВ равносильно В Е 6(А,а). По индуктивному предпо-
ложению В =>’ 0 тогда и только тогда, когда (В,0) Р (Я,е).
Следовательно, А =><+* а равносильно (A,a) Р+1 (Я,е).
Получаем, что S ==>* а для а Е Е‘ тогда и только тогда,
когда (S,a) Р (£),е) для некоторого D Е F. Таким образом,
L(G) = ЦМ).
(4) —♦ (5). Докажем индукцией по числу дуг в графе пере-
ходов конечного автомата М.
38
Для языка ЦМ), допускаемого автоматом М, граф пере-
ходов которого не содержит ни одной дуги, это утверждение
очевидно.
Пусть оно доказано для автоматов, диаграммы которых со-
держат менее к дуг, и пусть М = (Q,E,q0>F) — автомат с
к дугами в диаграмме. Удалим из графа переходов некоторую
дугу, ведущую из начальной вершины q0 в некоторую вершину
А. Пусть эта дуга помечена символом а. Конечный автомат
с таким графом переходов обозначим через М'. Рассмотрим
также автоматы Afi,A/2,A/3, диаграмма каждого из которых
получается из диаграммы автомата М' применением соответ-
ствующего из следующих преобразований:
1) сделать начальной вершиной А;
2) объявить q0 единственной заключительной вершиной;
3) совместно выполнить предыдущие два преобразования.
Нетрудно видеть, что
ЦМ) = ЦМ') U ЦМ^аЦМ^аЦМ^ .
Пусть p,q,u,u — регулярные выражения, обозначающие
языки ЦМ'),ЦМ1), ЦМ2),ЦМ3) соответственно. Они суще-
ствуют в силу индуктивного предположения. Таким образом,
р + u(au)’aq — выражение, обозначающее язык язык ЦМ).
(5) —» (1). Доказательство непосредственно из определе-
ний. □
Теорема 2.3. (Лемма о разрастании для регулярных мно-
жеств). Пусть L —регулярное множество. Существует такая
константа к, что если ш G L и | ш |> к, то иепочку о, можно
представить в виде xyz, где 0 <| у |< к и xy'z G L для всех
i> 0.
Доказательство. Пусть М = (Q,T^,6,q0,F) — конечный
автомат, допускающий L, т.е. ЦМ) = L, который существует
в силу теоремы 2.2, и к =| Q |.
39
Пусть w Е L и | ш |> к. Рассмотрим последовательность
конфигураций, которые проходит автомат Л/, допуская цепоч-
ку и>. Так как в ней по крайней мере к + 1 конфигурация, то
среди первых к +1 конфигураций найдутся две с одинаковыми
состояниями. Таким образом, получаем существование такой
последовательности тактов, что
(ge,zyz) Р (gi,yz) К (qlyz) P (g2,e)
для некоторых qx E Q,q2 QFnO<r<k. Отсюда 0 <| у |< n.
Но тогда для любого i > 0 автомат может проделать последо-
вательность тактов
(у,,!!?*) Р
Р
(9ьУ*)
(91,*)
(92, е)
Таким образом, xy'z Е L для всех t > 1. Случай i = 0, т.е.
ху Е L, также очевиден. □
Пример 2.7. С помощью леммы о разрастании можно по-
казать, что язык L = {0"1п : п > 1} не является регулярным
множеством.
Допустим, что L регулярен. Тогда для достаточно большого
п цепочку 0" Iя можно представить в виде xyz, причем у / е
и xy'z Е L для всех » > 0. Если у Е 0+ или у Е 1+, то xz =
xy°z $ L. Если у Е 0+1+, то xyyz £ L. Получили противоречие.
Следовательно L не может быть регулярным множеством. □
Упражнения
2.1. Какие из следующих множеств в двоичном алфавите
Е = {0,1} являются регулярными ? Для тех регулярных напи-
шите регулярные выражения.
40
(а) Множество цепочек с равным числом нулей и единиц;
(б) Множество цепочек с четным числом нулей и нечетным
числом единиц;
(в) Множество цепочек, длины которых делятся на 3;
(г) Множество цепочек, не содержащих подцепочки 101;
(д) Множество цепочек, содержащих два стоящих рядом ну-
ля;
(е) Множество цепочек, содержащих четное число нулей и
четное число единиц;
(ж) Множество цепочек, каждая из которых начинается с
единицы и имеет только один нуль.
2.2. Покажите, что множество регулярных выражений в ал-
фавите Е является контекстно-свободным языком.
2.3. Покажите, что если L — произвольное регулярное мно-
жество, то существует бесконечно много регулярных выраже-
ний, обозначающих L.
2.4. Докажите тождества из примера 2.2.
2.5. Для автоматов М и М', рассмотренных в доказатель-
стве теоремы 2.1, покажите, что для любого i равносильны
следующие два свойства:
(а) (Я,и) Нм, ($',е);
(б) S' = {р : (р,е) для некоторого q G S}.
2.6. Покажите, что следующие множества не регулярны:
(а) {0"10" : п > 1};
(б) {wu> : w € {0,1}’};
(в) L(G), где G определяется правилами
S —♦ aSbS | е ;
(г) {а"’: n > 1};
(д) {ар : р — простое число };
(е) {а, : w € {0,1}* и имеет одинаковое число нулей и
единиц }.
41
2.7. Пусть Lj и Lj — регулярные множества в алфавите £.
Покажите, что следующие множества регулярны:
(a) L2 = {w : шх G Li для некоторого х G Z2};
(б) INIT(Li) = {w : шх G L\ для некоторого х € £*};
(в) FIN(Li) = {ш : хш € L} для некоторого х G £’};
(г) SUB(Li) = {о>: хшу G Lx для некоторых х,у G £’};
(д) = {w : ш 6 Lx и никакой собственный пре-
фикс цепочки ш не принадлежит Lt, т.е. не существует такой
цепочки а Е Li, что ш = а0, где 0 £ е};
(е) МAX(Li) = {ш : ш Е Li и не существует такого х / е,
что шх G Li};
(ж) {и : шх G Li для некоторого такого х, что | ш |=| х |);
(з) Z* = {ш : шн € Lt , т.е. цепочка, полученная выписыва-
нием в обратном порядке символов, составляющих ш, принад-
лежит Li};
(и) Li П L2 — {и/ : ш G Li и ш G Z?};
(к) Li = {w : ш $ Li и ш 6 Е’}.
2.8. Разработайте алгоритм ’’минимизации состояний ко-
нечного автомата" (здесь и ниже конечным автоматом называ-
ется полностью определенный детерминированный конечный
автомат), который по любому конечному автомату М строит
такой конечный автомат, допускающий язык L(M), который
имеет наименьшее число состояний среди всех таких конеч-
ных автоматов.
Указание. Рассмотрите процесс минимизации числа состо-
яний конечного автомата за счет исключения недостижимых
состояний и склеивания неразличимых состояний.
Состояние q G Q автомата М = (Q,L,6,q0, F) называется
недостижимым, если не существует такой входной цепочки х,
что (q0,x} Р (д,е).
Говорят, что цепочка х G Е* различает состояния q} и q2 из
Q, если (9i,х) Н (9з,е)>(92,х) Ь’ и одно из состояний q3
42
или 74 не принадлежит F. Состояния q} и q3 неразличимы, если
не существует такой цепочки х Е Е*, которая их различает.
2.9. Проблемы принадлежности, пустоты и эквивалентно-
сти формулируются следующим образом.
Проблема принадлежности: "Дано определенного типа опи-
сание языка и дана цепочка о>; принадлежит ли ш этому языку
или нет?”
Проблема пустоты: ’’Дано определенного типа описание
языка; пуст ли этот язык или нет?”
Проблема эквивалентности: "Даны два описания одинако-
вого типа; определяют ли они один и тот же язык или нет?”
Дайте эффективные алгоритмы, решающие проблемы при-
надлежности, пустоты и эквивалентности для следующих ти-
пов описаний языка:
(а) регулярных выражений;
(б) праволинейных грамматик;
(в) недетерминированных конечных автоматов.
Проблема для исследования:
2.10. Найдите эффективный алгоритм (скажем такой, кото-
рый для автомата с п состояниями требует времени не более
пк, где к константа), дающий недетерминированный конеч-
ный автомат с минимальным числом состояний, эквивалент-
ный данному.
43
3 Контекстно-свободные языки
и магазинные автоматы
Из основных подклассов грамматик Хомского класс кон-
текстно-свободных грамматик наиболее важен с точки зрения
приложений к языкам программирования и трансляции. В дан-
ной главе мы рассмотрим класс контекстно-свободных языков,
определяемый указанным классом грамматик, и связанный с
ним класс магазинных автоматов, а также определим дере-
вья выводов и преобразования, которым можно подвергнуть
контекстно-свободные грамматики, чтобы привести их к более
удобному виду.
3.1 Деревья выводов и однозначность грамматик
Определение. Помеченное упорядоченное дерево D назы-
вается деревом вывода (или деревом разбора) в контекстно-
свободной грамматике G(A) = (?V,E,P, А), если выполнены
следующие условия:
(1) Корень дерева D помечен символом А;
(2) Если — поддеревья, корнями которых явля-
ются сыновья корня D, помеченные символами Xi,...,Xt со-
ответственно, то А —> X,... Хц — правило из множества Р.
Каждое Р, должно либо быть деревом вывода в грамматике
G(Xi) = (TV, Е,Р, если Xi - нетерминал, либо состоять из
единственной вершины, помеченной символом Xi, если Xi —
терминал;
(3) Если корень дерева имеет единственного сына, помечен-
ного е, то этот сын образует дерево, состоящее из единственной
вершины, и А —► е — правило из множества Р. □
44
Рис. 3.1
Пример 3.1. Дерево вывода в грамматике из примера 1.4
изображено на рис. 3.1. На рис. 3.2 изображено четыре дерева
выводов в грамматике из примера 1.7. □
Определение. Сечением дерева D называется такое мно-
жество С вершин дерева D, что
(1) никакие две вершины из С не лежат на одном пути в D,
(2) ни одну вершину дерева D нельзя добавить к С, не на-
рушив свойства 1.
Крона сечения дерева D определяется как цепочка, которая
получается конкатенацией меток вершин, образующих данное
сечение, в их упорядочении слева направо, определяемым по
следующим правилам.
Рассматривается имеющееся упорядочение на множестве
сыновей рг, каждого отца р в дереве D, и считается,
45
что для любых t < j вершина р, и все ее потомки расположе-
ны левее вершины Pj и всех ее потомков.
Кроной дерева D называется крона сечения, образованного
из листьев дерева D. □
Пример 3.2. Дерево вывода, изображенное на рис. 3.1, име-
ет, в частности, следующие кроны сечений: Е, Е + Т, Т + Т, F +
Т, а + Г, Е + Т + F, Е F F + F, EFa*F, EfT ♦ в, Е F F + а, Е F
а* а,Т FT ♦ F,T F F * F,T + a ♦ F. Цепочка a + a ♦ a является
кроной этого дерева. □
Рис. 3.2
Свойство 3.1. Пусть «(ьоц,... ,an — вывод цепочки ап из
а0 = S в контекстно-свободной грамматике G = (N, Е,Р, S).
Тогда в G можно построить дерево вывода D, для которою оп
— крона, а ao,ai,... ,an-i — некоторые из крон сечений.
Свойство 3.2. Пусть D — дерево вывода в контекстно-
свободной грамматике G = (N,L,P,S) с кроной а. Тогда
S =►* а.
46
Определение. Вывод a0>air • • ,«п в контекстно-свободной
грамматике G = (JV, Е,Р, S) называется левым (соответствен-
но правым), если для любого i цепочка о, получается из a,_i
заменой самого левого (соответственно правого) нетерминала.
□
Определение. Контекстно-свободную грамматику G на-
зывают неоднозначной, если существует цепочка lj G L(G),
являющаяся кроной двух или более различных деревьев выво-
да; в противном случае грамматика G называется однознач-
ной. О
3.2 Преобразования КС-грамматик
Имеющуюся грамматику часто требуется модифицировать
так, чтобы порождаемый ею язык приобрел нужную структу-
ру. Рассмотрим, например, язык, порождаемый грамматикой
G с правилами
Е —> Е+ Е\ Е* Е\(Е)\а .
Но грамматика G имеет два недостатка. Она неоднозначна
из-за наличия в ней правил Е —» Е + Е | Е * Е. Эту неодно-
значность можно устранить, взяв вместо G грамматику С7) с
правилами
Е—* Е + Т\ Е*Т\Т
Т^(Е)\а.
Другой недостаток грамматики G, которым обладает также
и Gi, заключается в том, что операции + и ♦ имеют один и тот
же приоритет. Иначе говоря, структура выражений а + а ♦ а и
а ♦ а + а, которую придает им грамматика G\, подразумевает
тот же порядок выполнения операций, что и в выражениях (а+
а) ♦ а и (а * а) + а соответственно.
47
Чтобы получить обычный приоритет операций + и *, при
котором ♦ предшествует 4- и выражение а 4- а ♦ а понимается
как а 4- (а ♦ а), надо перейти к грамматике из примера 1.4.
Общего алгоритмического метода, который придавал бы
любому заданному языку произвольную структуру, не суще-
ствует. Но есть ряд преобразований, котрыми можно изменить
грамматику, не испортив порождаемого ею языка. К преобра-
зованиям такого типа относится, например, преобразование
контекстно-свободной грамматики в эквивалентную ей грам-
матику без е-правил, рассмотренное в разделе 1. Ниже мы
рассмотрим еще несколько преобразований такого рода.
Начнем с очевидных, но важных преобразований. В не-
которых случаях КС-грамматика может содержать беспо-
лезные символы и правила. Например в грамматике G —
({5, А}, {а,Ь}, Р, S), где Р - {S —♦ а, А —► Ь}, нетерминал А
и терминал b не могут появиться ни в какой выводимой цепоч-
ке. Таким образом, эти символы не имеют отношения к языку
L(G), и их можно устранить из определения грамматики G, не
затронув языка L(G).
Определение. Символ X Е JVUE называется бесполезным
в КС-грамматике G = (./V,S, Р, S), если в ней нет вывода вида
S =>* шХу =>* wxy, где w,ar,y принадлежат £*. □
Чтобы установить, бесполезен ли нетерминал А, построим
сначала алгоритм, выясняющий, может ли нетерминал поро-
ждать какие-нибудь терминальные цепочки, т.е. решающий
проблему пустоты множества {w :=^* Е £*}. Из суще-
ствования такого алгоритма следует разрешимость проблемы
пустоты для КС-грамматик.
Алгоритм 3.1.
Вход. КС-грамматика G = (JV, £,Р,5).
Выход. ”ДА”, если L(G) / 0, "НЕТ” в противном случае.
Метод. Строим множества N0,Ni,... рекурсивно:
48
1. Положить No — 0 и ii = 1.
2. Положить Ni = {А : А —♦ a Е Р и a 6 (JVi-iUE)*}uJVi_i.
3. Если Ni / Ni-i, положить » = i+ 1 и перейти к шагу (2).
В противном случае положить Nt = Ni.
4. Если S € N', выдать выход ”ДА”, в противном случае
’’НЕТ”. □
Теорема 3.1. Алгоритм 3.1 останавливается через конеч-
ное число шагов и выдает ”ДА” тогда и только тогда, когда
S =>* w для некоторой цепочки ш 6 S*.
Доказательство. Так как Nt С N, то алгоритм 3.1 должен
остановиться самое большее после п 4- 1 повторений шага (2),
если | N |= п.
Теперь докажем индукцией по возрастанию i, что для лю-
бого нетерминала А,если A Е Ni, то А =>* ш для некоторой
цепочки w Е Е’.
Базис, i = 0, не нуждается в доказательстве, так как No =
0. Предположим, что утверждение истинно для », и возьмем
А Е JVj+i. Если А принадлежит также и Л\, то шаг индук-
ции тривиален. Если А Е Ni+i \ N,, то существует правило
А —» где каждый символ Xi принадлежит либо
Е, либо Ni. Таким образом, для каждого Х} можно найти та-
кую цепочку <*/,, что Х} =>’ если 6 Е, то Wj = Xj, в
противном случае существование о/, следует по индуктивному
предположению. Легко видеть, что
А Xi... Xh u>iX?... Xh => ... => Wj.. .
Случай к = 0 (т.е. правило А —♦ е) не составляет исключения
Шаг индукции окончен.
Определение множеств N, гарантирует, что если N, - N,_i,
то N, = Лт,+1 = .... Осталось показать, что если А w для
49
некоторой цепочки w G S’, то A G Ne. В силу сделанного выше
замечания осталось показать, что А € Ni для некоторого ».
Индукцией по п докажем, что
если А =>” и, то А € N, для некоторого i.
Базис, п = 1, тривиален — в этом случае i = 1. Допу-
стим, что утверждение истинно для п, и пусть A =>n+1 ш.
Тогда можно написать А => =$►" и, где цепочка
ш = w1 .. . w* такова, что Xj =^п‘ для каждого j и п} < п
(т.е. в дереве вывода для А =>"+' и цепочка является кро-
ной поддерева с корнем Xj). Согласно индуктивному предпо-
ложению, если Xj G N, то X, G Ni} для некоторого i,. Если
Xj G Е, то ij = 0. Пусть i = l + max(ii,... ,it). Тогда по
определению A G N,. Индукция завершена.
Положив А = S в доказанных выше утверждениях, получим
утверждение теоремы. □
Следствие 1. Для контекстно-свободной грамматики G
проблема пустоты языка L(G) разрешима.
Определение. Символ X G N UE называется недостижи-
мым в контекстно-свободной грамматике G(N, Е, Р, S), если X
не появляется ни в одной выводимой цепочке. □
Алгоритм 3.2.
Вход. КС-грамматика G = (А,Е,Р, S).
Выход. КС-грамматика G' = (N1, £',/*,8), у которой
(i)L(G') = L(G),
(it) для всех X G N' U Е' существуют такие цепочки о и 3
из (A'U Е')‘, что S =>*а. аХ(3.
Метод. Правила построения G1 следующие:
1. Положить Уо = {$} и i = 1.
50
2. Положить V, = {X : в Р есть А —♦ аХ0 и А € K-i) U
3. Если V* / Vj-i, положить i = i + 1 и перейти к шагу (2).
В противном случае
• N' = V,DN,
• Е' = V, П Е,
• Р' состоит из правил множества Р, содержащих
только символы из Vit
• G' = (AT',E',P',S).D
Алгоритмы 3.1 и 3.2 очень похожи Заметим, что шаг (2)
алгоритма 3.2 можно повторить только конечное число раз, так
как V, С N U Е. Кроме того, прямое доказательство индукцией
по i показывает, что S =>‘а- аХ0 тогда и только тогда, когда
X € V, для некоторого i.
Теперь мы готовы устранить из грамматики все бесполез-
ные символы.
Алгоритм 3.3.
Вход. КС-грамматика G = (JV,E,P,5), определяющая непу-
стой язык, т.е. Z(G) / 0.
Выход. КС-грамматика G' = (А',Е', P'S), которая эквива-
лентна исходной (т.е. L(G') = L(G)) и у которой сре/и симво-
лов из N' U Е' нет бесполезных.
Метод.
1. Применив к G алгоритм 3.1, получить Nt. Положить
Gx = (N П N,,£, P\,S), где Рх состоит из правил мно-
жества Р, содержащих только символы из Nt U Е.
51
2. Применив к грамматике Gx, полученной на первом шаге,
алгоритм 3.2, получить G' = (Я',Е',Р'$).О
На шаге (1) алгоритма 3.3 из G устраняются все нетерми-
налы, которые не могут порождать терминальных цепочек.
Затем на шаге (2) устраняются все недостижимые символы.
Каждый символ X результирующей грамматики должен по-
явиться хотя бы в одном выводе вида 5 =>* шХу =>* и>ху.
Заметим, что если сначала применить алгоритм 3.2, а потом
алгоритм 3.1, то не всегда результатом будет грамматика, не
содержащая бесполезных символов (см. пример 3.2).
Теорема 3.2. Грамматика G', которую строит по исход-
ной грамматике G алгоритм 3.3, не содержит бесполезных
символов u L(G) = ЦСУ).
Доказательство. Доказательство того, что ЦСУ) = L(G)
оставляем в качестве упражнения. Предположим, что А € N'
— бесполезный символ. Тогда возможны два случая.
Случай Г. Вывод S =^*G> &АЦ ни для каких а и (3 невоз-
можен. В этом случае символ А устраняется на шаге (2) алго-
ритма 3.3.
Случай 2: S аА/З для некоторых о и Д, но вывода
A =>g* ш для w G Е" не существует. Тогда А не устраняется
на шаге (2) и, кроме того, если А =>д iBf), то и Я не устраня-
ется на шаге (2). Таким образом, если Л то A =*G' и-
Тогда можно заключить, что вывода A ==>g w для cu G Е* не
существует и А устраняется на шаге (1).
Доказательство того, что ни один терминал в G' не может
быть бесполезным, проводится аналогично; мы оставляем его
в качестве упражнения.□
Пример 3.3. Рассмотрим грамматику G = (N,^,P,S), в
которой N = {5, А, В} ,Е = {а,Ь} и Р состоит из правил:
52
S —♦ a | A
A В
В — b.
Применим к G алгоритм 3.3. На шаге (1) получим Ne =
{5,В} и = ({$,Б),{а,Ь},{5 —♦ а,В —* 6},$). При-
менив алгоритм 3.2, получим V2 = Vi = {S,а}. Итак, G' =
({Я,{а},{5^п},5).
Если применить к G сначала алгоритм 3.2, то окажется,
что все символы достижимы, так что грамматика не изме-
нится. Затем применение алгоритма 3.1 дает Ne = {S, В}, и
результирующей будет грамматика Gi отличная от G'. □
Определение. В грамматике G = (A, Е, Р, S) правило ви-
да А —» В, где А, В G N, называется цепкыж правилом. О
Алгоритм 3.4.
Вход. Контекстно-свободная грамматика G без е-правил.
Выход. Эквивалентная контекстно-свободная грамматика
G' без е-правил и без цепных правил.
Метод..
1. Для каждого А € N построить = {В | А =>’ В}
следующим образом:
(а) Положить No = {А} и t = 1.
(б) Положить Ni = {С : В —♦ С принадлежит Р и
В € Ni.,} U Ni.t.
(в) Если Ni / Ni.i, положить t = »+ 1 и повторить шаг
(б). В противном случае положить NA = N,.
53
2. Построить Р' так: если правило В —» а принадлежит Р
и не является цепным правилом, включить в Р1 правило
А —» а для всех таких Л, что В 6 NA.
3. Положить G'= (ЛГ,Е, Г'. S).D
Пример 3.4. Применим алгоритм 3.4 к грамматике ариф-
метических выражений (7 с правилами:
Е Е + Т\Т
Т —* T*F\F
F -* (Е)|а.
На шаге (1) NE = {E,T,F},NT = {T,F},Nf = {F}. После
шага (2) множество Р1 станет таким:
Е —» Е + Т | Г» F | (Е) | а
Т —» 7 ♦ F | (Е) | а
F -» (Е)|а.
□
Теорема 3.3. Грамматика G', которую строит по исходной
грамматике G алгоритм 3.4 не имеет цепных правил и L(G) =
I(G').
Доказательство. Непосредственно видно, что алгоритм
3.4 лает грамматику G' без цепных правил.
Покажем сначала, что L(G') С L(G). Пусть ш G E(G'). То-
гда в грамматике G' существует вывод $ => а0 => =>
- • а„ = ы. Если при переходе от ctj к а<+1 применяется
правило 4 —» /3, то существует такой символ В € N (воз-
можно, В = А), что А В и В =>G 0. Таким образом,
4 =>с 0 и a, =>G а1+!. Отсюда следует, что S =>£ w и
uj € L(G), так что L(G') С L(G)
54
Теперь покажем, что Z(G) С L(G'). Пусть w G и
5 = а0 =>( а, =>( ... =^( ап = ш — левый вывод це-
почки и в грамматике G. Можно найти последовательность
индексов ii,t2,... ,ц, состоящую в точности из тех j, для ко-
торых на шаге a,_i =>g aj применяется не цепное правило.
В частности, ц = п, так как вывод терминальной цепочки не
может оканчиваться цепным правилом.
Так как мы рассматриваем левый вывод, то последователь-
ные применения цепных правил заменяют символ, занимаю-
щий одну и ту же позицию в левовыводимых цепочках, из ко-
торых состоит соответствующая часть вывода. Отсюда видно,
что S =>g' «i, =*G' «и =><?- =>в' alk = w. Таким обра-
зом, w € L(G') и, значит, L(G') = b(G).O
Определение. Говорят, что контекстно-свободная грам-
матика G — IN.'S, P,S) находится в нормальной форме Хом-
ского (или в бинарной нормальной форме), если каждое прави-
ло из Р имеет один из следующих видов:
(1) А —* ВС. где А,В и С принадлежат 7V;
(2) А —* а, где a € S;
(3) S —• е, если е € L(G), причем S не встречается в пра-
вых частях правил. □
Теорема 3.4. Любую контекстно-свободную граммати-
ку можно преобразовать в эквивалентную ей контекстно-
свободную грамматику в нормальной форме Хомского.
Доказательство. К исходной контекстно-свободной грам-
матике применим сначала алгоритм 1.1, а затем алгоритм
3.4. Полученная в результате КС-грамматика G = (N.T. P.S)
эквивалентна исходной и является грамматикой без е-правил
и без цепных правил.
В дальнейшем подвергнем 1рамматику G следующим пре-
образованиям.
55
Рассмотрим все терминальные символы Е' С Е, входящие в
правые части таких правил А —» ZiZ2... Zm из Р, что т > 1,
и каждому терминалу a G Е' сопоставим новый нетерминал Da
и новое правило Da —* а.
Затем каждое правило вида А —♦ ZjZ2... Zm G Р, в кото-
ром т > 1, заменим на правило А —» ВХВ2 ... Вт, где
Bi =
Zi,
D.a,
если Zi G N,
если Zi = a G Е.
Рассмотрим все те правила А —► ВХВ2... Вт из Р, в кото-
рых т > 2, и заменим каждое такое правило на группу правил
вида
А —» BxCt
С\ • В2С2
С2 —♦ В3С\
в которых С\,С2,.. .Cm-i — это новые нетерминалы.
Ясно, что полученная в результате этих преобразований
грамматика эквивалентна исходной и находится в нормальной
форме Хомского. □
Свойство 3.3. Пусть КС-грамматика G находится в нор-
мальной форме Хомского. Тогда для любой цепочки а, если
a G L(G) и тп — высота дерева вывода с кроной а, то | а |<
Теорема 3.5. (Лемма о разрастании для контекстно-
свободных языков). Для любого контекстно-свободного язы-
ка L существуют такие целые I и k, что любая цепочка а из
L, | a |> I, представима в виде a = uvwxy, где
(1) | vwz |< к;
(2) vx * е;
56
(3) uv'wx'y € L для любого t > 0.
Доказательство. Пусть L = L(G), где G = (N, E,P, S) —
контекстно свободная грамматика в нормальной форме Хом-
ского, которая существует в силу теоремы 3.5.
Обозначим через п число нетерминалов, т.е. n =| N |, и
рассмотрим I = 2""1 и к = 2".
Для доказательства того, что I и к удовлетворяют условию
теоремы, рассмотрим произвольную цепочку a € L, для кото-
рой | о |> I = 2"-1. В силу свойства 3.3 получаем, что высота
дерева с кроной а больше п и самый длинный путь по дере-
ву (обозначим его через Р) проходит более чем через п + 1
вершин. Отсюда по определению дерева вывода имеем, что Р
содержит более п вершин, помеченных нетерминалами. Таким
образом, существует нетерминал А 6 N, который метит не ме-
нее двух вершин пути Р. Обозначим их через р и q, где р —
ближе к корню, чем q (см. рис. 3.3), и представим крону а в
виде uvwxy, где w — крона поддерева Dx с корнем q и vwx —
крона поддерева D2 с корнем р.
Ясно, что высота дерева Dj не превышает п + 1, и, таким
образом, | vwx |< 2” = к.
Также очевидно, что vx / е, поскольку в силу определения
нормальной формы Хомского р имеет двух сыновей, помечен-
ных нетерминалами, из которых не выводится пустая цепочка.
Кроме того, S =>* иАу =>* uvAxy =>* uvwxy, а также
А =>" vAx =>* vwx. Отсюда получаем А =>* v‘wz‘ для всех
1> 0, и S =>* uv'wx'y для всех » > 0. □
Пример 3.5. С помощью леммы о разрастании покажем,
что язык L = {а" | п > 1} не является контекстно-свободным
языком.
Если бы он был контекстно-свободным языком, то нашлось
бы такое число к, что если п2 > к, то an’ = uvwxy, где цепочки
v и х не могут быть обе пустыми и | vwx |< к.
57
Рис. 3.3
Пусть, в частности, n = к. Так как к2 > к, то по предпо-
ложению uv2wx2y € L. Но так как | vwx |< к, то 1 <| vx |< к
и Л2 <| uv2wx2y < к2 + к. Заметим, что следующий после к2
квадрат целого числа — число (к 4- I)3 = к2 + 2к 4- 1. Так как
к2 4- к < к2 4- 2к 4- 1, то | uv2wx2y | не равно квадрату цело-
го числа. Но по лемме о разрастании uv2wx2y € L\ получили
противоречие. □
Пример 3.6. Покажем, что язык L — {anbncn : п > 1} — не
контекстно-свободный язык.
Если бы он был контекстно-свободным языком, то мы взяли
бы константу к, которая определяется в лемме о разрастании.
Пусть z — акЬкск. Тогда z = uvwxy. Так как | vwx |< к, то
в цепочке vwx не могут быть вхождения каждого из символов
а,Ь и с. Таким образом, цепочка uwy, которая по лемме о раз-
растании принадлежит £, содержит либо к символов а, либо
к символов с. Но она не может иметь к вхождений каждого
58
ждений какого-то одного из этих символов в ишу больше, чем
другого, и, следовательно, uwy G L. Полученное противоречие
позволяет заключить, что L — не контекстно-свободный язык.
□
3.3 Автоматы с магазинной памятью
Определение. Автомат с магазинной памятью (сокра-
щенно МП-автомат — это семерка Р = (ф,Е,Г, 6,q0,Z0,F),
где
(1) Q — конечное множество символов состояний, предста-
вляющих возможные состояния управляющего устройства;
(2) Е — конечный входной алфавит;
(3) Г — конечный алфавит магазинных символов;
(4) 6 — отображение множества Qx(EU{e))x Г в множество
конечных подмножеств множества Q х Г*;
(5) <?о € Q — начальное состояние управляющего устрой-
ства;
(6) Zo € Г — символ, находящийся в магазине в начальный
момент (начальный символ);
(7) F С Q — множество заключительных состояний. □
Определение. Конфигурацией МП-автомата Р называет-
ся тройка (q,u>,a) G Q х Е’ х Г*, где
(1) q — текущее состояние управляющего устройства;
(2) ш — неиспользованная часть входной цепочки; первый
символ цепочки ы находится под входной головкой; если ш = е,
то считается, что вся входная лента прочитана;
(3) а — содержимое магазина; самый левый символ цепочки
считается верхним символом магазина; если а = е, то магазин
считается пустым.
59
Начальной конфигурацией МП-автомата Р называется кон-
фигурация вида (g0,w,Z0), где ш 6 Е*. Заключительная его
конфигурация — это конфигурация вида (д,е,е), где q € F. □
Определение. Такт работы МП-автомата Р представля-
ется в виде бинарного отношения Ьр, определенного на кон-
фигурациях следующим образом: (g,aw,Za) (р, 1^,70), если
множество £(g,a, Z) содержит (р,7), где q,p € Q,a € Eu{e},w €
E*,Z € Г и a,7 € Г*. Через и Ьр обозначаются соот-
ветственно рефлексивное и транзитивное замыкание и тран-
зитивное замыкание отношения hp.
Цепочка о; допускается МП-автоматом Р, если (g0,w,Z0) Нр
(?,е,е) для некоторого q 6 F.
Языком, определяемым (или допускаемым) автоматом Р
(обозначается £(Р)), называют множество цепочек, допускае-
мых автоматом Р. □
Сравнивая понятия конечного и магазинного автоматов,
можно сказать, что МП-автомат получается из конечного авто-
мата добавлением потенциально бесконечной рабочей (вспомо-
гательной) памяти, в которой элементы информации хранятся
и используются так же как патроны в магазине автоматиче-
ского оружия, т.е. в каждый момент доступен только верхний
элемент магазина (см. рис. 3.4).
Такт работы некоторого МП-автомата Р, связанный с пе-
реходом от конфигурации (g,au>, Za) к конфигурации (g',u;,7a)
при А / е говорит о том, что МП-автомат Р, находясь в со-
стоянии q и имея а в качестве текущего входного символа,
расположенного под входной головкой (т.е. обозревая а), а Z
— в качестве верхнего символа магазина, может перейти в но-
вое состояние q', сдвинуть входную головку на одну ячейку
вправо и заменить верхний символ магазина цепочкой 7 мага-
зинных символов. Если 7 = е, то верхний символ удаляется из
магазина, и тем самым магазинный список сокращается.
60
Такт, в котором а = е, называют e-тактом. В е-такте те-
кущий входной символ не принимается во внимание и вход-
ная головка не сдвигается. Однако состояние управляющего
устройства и содержимое памяти могут измениться. Заметим,
что е-такт может происходить и тогда, когда вся входная це-
почка прочитана.
Следующий такт невозможен, если магазин пуст. □
Пример 3.7. Рассмотрим язык L = {0п1п : п > 0} и опре-
деляющий его МП-автомат
Р = ({<7о, 91,9з}, {0,1}, {Z, 0},6, q0, Z, {ф>}),
где функция 6 определяется по следующим правилам:
61
6(qo,0,Z) = {(91,02)}
«(91,0,0) = {(«i,00)J
«(9i,l,0) = {(93,e)}
«(92,1,0) = {(92,e)}
6(92, e,Z) = {(?o,e)J .
Работа МП-автомата P состоит в том, что он копирует в
магазине начальную часть входной цепочки, состоящую из ну-
лей, а затем устраняет из магазина по одному нулю на каждую
единицу, которую он видит на входе. Кроме того, переходы со-
стояний гарантируют, что все нули предшествуют единицам.
Например, для входной цепочки ООН автомат Р проделает та-
кую последовательность тактов:
(9о,0011,Z) h (gi,011,0Z)
I- (91,11,002)
Ь (91,1,02)
Ь (92, е, Z)
Ь (9о,е,е) •
"Вообще можно показать, что
(9о,0,2)
(9г,О',02)
(91,1,0<+12)
(92,1',0'И)
(9з,е,2)
F (91, е, 020
Н (9i,e,0’+12)
h (92,6,0*2)
Н (92,е,2)
h (9о,е,е).
Объединяя все это, получаем для п > 1
(9о,0"1",2) Р3"*’ (9о,б,е),
62
(q0,e,Z) h° (q0,e,Z) .
Таким образом, L C L(P).
Покажем, что L □ L(P), т.е. что P допускает только це-
почки вида 0nln. Эта часть доказательства труднее. Обычно
легче доказать, что такие-то цепочки распознаватель допуска-
ет, и так же, как для грамматик, гораздо труднее доказать,
что он допускает цепочки только определенного вида.
В данном случае заметим, что если Р допускает непустую
цепочку, то он должен пройти через состояния g0, gi, 9г» ?о имен-
но в таком порядке.
Далее, если (g0,w,Z) Н (qi,e,a) для » > 1, то w = 0* и
а = 0‘Z. Аналогично, если (g2,w,a) Н (q2,e,/3), то = Г и
а = 0*/3. К тому же h (g2,e,/3) только тогда, когда
w = 1 и а = 0/3, a (q2,w, Z) h’ (q0,e, е) только тогда, когда
w = е. Таким образом, если (q0,w,Z) Н (q0,e,a) для некоторого
i > 0, то либо ш = е и i — 0, либо = 0” ln, t = 2n + 1 и а = е.
Следовательно, L Э L(P). О
Пример 3.8. Рассмотрим МП-автомат, допускающий язык
L = {о>а>я : ш G {a,b}+} .
Напомним, что сий обозначает обращение цепочки w, т.е. <дя =
ап .. .a2ai, если и = а^а2 •ап.
Пусть Р = ({q0,qi,q2},{a,b},{Z,a,b},6,q0,Z,{q2}), где функ-
ция 6 определяется по следующим правилам:
(1). 6(<?o,a,Z) = {(g0,aZ)} ;
(2). 6(go,b,Z) = {(go,6Z)};
(3). 6(q0,a,a) = {(g0»aa),(g1,e)} ;
(4). b(q0,a,b) = {(g0,a6)} ;
(5). 6(q0,b,a) = {(go, ba)} ;
(6) . 6(q0,6,b)= {(go,bb),(gbe)} ;
(7) . b(gi,a,a) = {(qbe)} ;
63
(8) . *(ft,6,6) = {(ft,e)};
(9) . 6(qi,e,Z) = {(ft,e)} .
МП-автомат P вначале копирует в магазине какую-то часть
входной цепочки по правилам (1), (2), (4) и (5) и первым аль-
тернативам правил (3) и (6).
Однако Р — недетерминированный распознаватель. В лю-
бой момент, когда текущий входной символ совпадает с верх-
ним символом магазина, он может перейти в состояние ft и
начать сравнивать цепочку в магазине с оставшейся частью
входной цепочки. Этот выбор осуществляют вторые альтер-
нативы правил (3) и (6), а по правилам (7) и (8) происходит
сравнение. Если Р обнаруживает несовпадение очередных сим-
волов, то этот экземпляр МП-автомата Р "умирает”, т.е. пере-
стает работать. Однако, так как автомат Р — недетерминиро-
ванный, то разные его экземпляры могут делать все возмож-
ные для него такты. Если какой-то выбор тактов приводит к
тому, что Z снова оказывается верхним (и единственным) сим-
волом магазина, то по правилу (9) Р стирает Z и попадает в
состояние ft. Итак, Р допускает цепочку тогда и только тогда,
когда все сравнения обнаружили совпадение символов.
Например, для входной цепочки abba автомат Р может среди
прочих сделать следующие две последовательности тактов:
(ft, abba, Z) F
F
F
F
(ft,abba,Z) F
F
F
F
F
(ft, bba,aZ)
(ft, ba.baZ)
(q0,a,bbaZ)
(q0,e,abbaZ) ;
(ft, bba,aZ)
(q0,ba,baZ)
(qt,a,aZ)
(qi,e,Z)
(ft,e,e) .
64
Так как вторая из рассмотренных выше последовательно-
стей оканчивается заключительным состоянием то МП-
авгомат Р допускает входную цепочку abba. □
Свойство 3.4. Пусть Р = (Q,E,r,i,go,2o,F) — некото-
рый МП-автомат, и (g,w, А) Ь" (f\e,e). Тогда (g,w,Aa) Ь"
/,е,а) для всех А € Г и a G Г*.
Другими словами, то, что происходит с верхним символом
магазина МП-автомата не зависит от того, что находится в
магазине под этим символом.
Определение. МП-автомат Р = (Q,L,T,6,q0,Z0,F) назы-
вается детерминированным (сокращенно ДМП-автоматом),
если для каждых q Е Q и Z Е Г либо
(1) 6(q, a, Z) содержит не более одного элемента для каждого
а € Е и 6(q,e, Z) = 0, либо
(2) 6(q, а, Z) = 0 для всех а G Ей 6(q,e,Z) содержит не
более одного элемента. □
Детерминированным является, например, МП-автомат при-
мера 3.3.
3.4 Свойства класса КС-языков
Теорема З.в. L является КС-языком тогда н только тогда,
когда L определяется некоторым МП-автоматом.
Доказательство. Необходимость. Пусть G = Е,Р, 5)
некоторая КС-грамматика. Рассмотрим МП-автомат R =
4?n,?,p),S,r,S U N U {Zo},6,<?o,Zo,{p}), в котором 6 опреде-
ляется следующим образом:
(l)«(9o,e,Zo) = {(g,SZ0)};
(2) если А —» о принадлежит Р, то 6(q,e,A) содержит
(3) 6(q,a,a) = {(g,e)} для всех a Е Е;
65
(4) ^,e,Z0) = {(p,e)}.
Покажем справедливость следующего утверждения:
А =>т ш для некоторого т > 1 тогда и только тогда, когда
(g,w, A) F” (q,e,e) для некоторого n > 1.
Необходимость утверждения докажем индукцией по т. До-
пустим, что А =>т о».
Если т = 1 и w = а!...ak(k > 0), то
(q,ai...aitA) I- (q^ ... ак,ах.. .ай)
Ь* (?,е,е) .
Теперь предположим, что А =Э-т ш для некоторого т,т >
1. Первый шаг этого вывода должен иметь вид А =>
XiX}... Хк, где X, =>т‘ х, для некоторого т, < m,l < > < к,
и ziza... ж* = w. Тогда
(9,o»,A)l-(9,W,X1X2...Xi).
Если X,, Е N, то по предположению индукции
(q,Xi,Xi) F* (?,е,е).
Если Xi = Xi Е Е, то
(9,х.,Х.) h (g,e,e).
Объединяя вместе эти последовательности тактов, видим, что
(g,w,A) h+ (g,e,e).
Для доказательства достаточности утверждения покажем
индукцией по п, что если (g,w, A) l-n (д,е,е), то А =>+ и.
Если n = 1, то w = е и А —♦ е принадлежит Р. Предпо-
ложим, что утверждение верно для всех п1 < п. Тогда первый
такт, сделанный МП-автоматом R, должен иметь вид
(g,w,A)l- (g,u>,Xi...X4) ,
66
причем (q,xiyXi) hn‘ (q,e,e) для 1 < i < fc И w = xxx2...xk
(Свойство 3.4). Тогда A —♦ Xx ...Xk — правило из P, и по
предположению индукции X, =>+ Xi для X, £ N. Если X, £ Е,
то Xi =$° Xi. Таким образом,
А => ХЛз.-Х^.Х*
=>• ххХ2...Хк.хХк
Xjlj .. . Х*_1Х*
Z]Ху ♦ • • |Х£ = Ц/
— вывод цепочки ш из А в грамматике G.
Из доказанного утверждения, в частности, вытекает, что
S =>+ w тогда и только тогда, когда (g,w,S) 1-+ (д,е,е). Сле-
довательно в силу свойства 3.3 имеем, что S =>+ ы тогда
и только тогда, когда (q,w,SZ0) И (q,e,Z0). Таким образом,
получаем L(R) = L(G),
Достаточность. Пусть R = (Q, Е, Г, 6, g0, Zo, F) некоторый
МП-автомат. Построим грамматику G = (N, Е,Р, S) так, что-
бы левый вывод цепочки и в грамматике G прямо соответство-
вал последовательности тактов, которую делает МП-автомат
R при обработке цепочки ш.
Пусть N = {[qZr] : q,r 6 Q,Z £ Г} U {S}, множество про-
дукций Р определяется по следующим правилам:
(1) если 6(q,a,Z) содержит (г,Хх.. .Хк), где к > 1 и а =
а £ Е или а = е, то в Р включаются все продукции вида
[<?Zst] ♦ afrX^Jf^XjSj]... [s*_i At3*]
для каждой последовательности состояний ax,s2,. ..,зк из Q;
(2) если 6(q,a,Z) содержит (г,е), где а = а £ Е или а = е,
то в Р добавляется продукция
[gZr] —» а ;
67
(3) в Р включаются все продукции вида S —♦ [q0Z0q] Для
любого q G F.
Нетрудно проверить, что [qZr] =>+ и> тогда и только то-
гда, когда (g,w, Z) Ь+ (г,е,е). (Доказательство оставляем в ка-
честве упражнения). Из этого утверждения следует, что S =>
[qoZ0q] ==>+ w тогда и только тогда, когда (q0,Zo) 1-+ (д, е, е)
для q G F. Таким образом, L(R) = £((7).D
Определение. Пусть С — класс языков и язык L С Е’
принадлежит £. Допустим Е = {щ ... а„) и языки .,£<>.
принадлежат £. Класс языков £ замкнут относительно под-
становки, если для любого набора языков L, La,,..., Ze, язык
{ij... z* : в;,,...,вд € L,X] Е £а^,,• ♦ •,Е }
принадлежит £. □
Пример 3.9. Пусть L = {0п1" : п > 1},£0 = {в},£1 =
{6mcm : т > 1}. Тогда результатом подстановки языков Lo в
Li в язык L будет язык
L' = {a"bm‘cm,6m’cmi ...bm-em- : n > 1,т, > 1}.
□
Теорема 3.7. Класс контекстно-свободных языков замкнут
относительно подстановки.
Доказательство. Пусть L С Е* — контекстно-свободный
язык и Е = {ai,...,an}. Пусть La С Е* — контекстно-
свободный язык для каждого а £ Е и L' — результат под-
становки языков La вместо а в цепочки языка L. Пусть G =
(ЛГ, Е,Р, S) — контекстно-свободная грамматика языка L и
Ga = (Na,Ea,Pa,a') — контекстно-свободная грамматика язы-
ка La. Предполагаем, что N и все Na попарно не пересекаются.
Возьмем G' = (N',E', P'S), где
(1) N'= \J Na UN-,
a€S
68
(2) £' = и
(3) пусть h — гомоморфизм, определенный на JVuE и такой,
что Л(А) = А для всех А € N и Л(а) = а' для Е; положим
F = {А —♦ Л(а): А —> a Е Р} U J Ра.
аСЕ
Итак, Р' состоит из правил всех грамматик Ga и правил
грамматики G, в которых все терминалы сделаны нетерми-
налами со штрихами. Пусть а,, ... а)к € L и х, 6 La) для
1 < t < fc. Тогда а',...а', =>£' =*в>
... =>*Gi Xj . ..х*. Следовательно, L' С L(G').
Допустим, что w € I\G'} и рассмотрим дерево вывода Т
цепочки <д. Так как N и Na не пересекаются, каждый лист с
меткой, отличной от е, имеет по крайней мере одного предка,
помеченного а', где а £ Е. Если удалить из Т каждую верши-
ну, у которой есть предок, отличный от нее и помеченный а'
для а Е Е, то получим дерево вывода Т“ с кроной а'}1 ...а*д,
где ...aih € L. Если i, — крона поддерева дерева Т, над
которыми доминирует i-й лист дерева Т', то и = ... xt и
Xi € La,t- Таким образом, L(G') = L'(G).O
Следствие 1. Класс контекстно-свободных языков за-
мкнут относительно (1) объединения, (2) конкатенации, (3)
итераций; (4) позитивной итерации и (5) гомоморфизма.
Доказательство. Пусть La и — КС-языки.
(1) Подставим La вместо а и £* вместо b в КС-язык {а,6}.
(2) Подставим La вместо а и £* вместо b в {ai>}.
(3) Подставим La вместо а в а*.
(4) Подставим La вместо а в а+.
(5) Для гомоморфизма h возьмем La = {Л(а)} и, подставив
La вместо а в L, получим /»(£).□
Теорема 3.8. Класс контекстно-свободных языков не за-
мкнут относительно пересечения и дополнения.
69
Доказательство. Lx = {anbnc* : n > l,i > 1} и L2 =
{a*6nc" : i > l,n > 1} — контекстно-свободные языки. Однако
Li П L2 = {anb"c" : n > 1} — не контекстно-свободный язык
(см. пример 3.5). Таким образом, класс контекстно-свободных
языков не замкнут относительно пересечения.
Отсюда можно также заключить, что класс контекстно-
свободных языков не замкнут относительно дополнения. В
самом деле, в силу закона де Моргана любой класс языков,
замкнутый относительно объединения и дополнения, должен
быть замкнут относительно пересечения. Но по следствию из
теоремы 3.7 класс контекстно-свободных языков замкнут от-
носительно объединения. □
Упражнения
3.1. Докажите непротиворечивость определения упорядо-
ченности множества вершин дерева, рассмотренного в опре-
делении кроны сечения.
3.2. Докажите свойства 3.1, 3.2 и 3.3.
3.3. Покажите эквивалентность следующих утверждений о
контекстно-свободной грамматике G и цепочке ш:
(а) и) — крона двух различных деревьев выводов в G,
(б) ш имеет два различных левых вывода в G,
(в) ш имеет два различных правых вывода в G.
3.4. Преобразуйте следующие грамматики к нормальной
форме Хомского:
(a) S — 0S1 101 ;
(б) S — аВ | ЬА
А —» aS | ЬАА | а
В — bS\aBB\b;
70
(в) S —» ABC
А —♦ В В | е
В —» СС \ а
С —» АА | Ь ;
(г) S — Л | Я
A —> C\D
В — D\E
С —» S|a|e
D — 5|6
Е —* 5|с|е;
(д) S —• Ва | АЬ
А —♦ Sa | ААЬ | а | В
В —+ Sb | ВВа | b | е .
3.5. Нетерминал А контекстно-свободной грамматики G =
(jV, Е,Р, 5) называется рекурсивным, если А =>+ аА/3 для не-
которых а и /3. Если а = е, то А называется леворекурсивным.
Аналогично, если (3 = е, то А называется праворекурсивным.
Грамматика G называется леворекурсивной (соответственно
праворекурсивной), если в G имеется хотя бы один леворе-
курсивный (соответственно праворекурсивный) нетерминал.
Грамматика, в которой рекурсивны все нетерминалы, кроме,
быть может, начального символа, называется рекурсивной. По-
стройте алгоритм, который по произвольной КС-грамматике
G-.
(а) проверяет леворекурсивна ли G\
(б) строит эквивалентную КС-грамматику без левой рекур-
сии;
(в) проверяет праворекурсивна ли G;
71
(г) строит эквивалентную КС-грамматику без правой ре-
курсии;
(д) проверяет рекурсивна ли G,
(ж) строит эквивалентную рекурсивную КС-грамматику.
3.6. Докажите, что МП-автомат из примера 3.7 определяет
язык : ш € {а,Ь}+}.
3.7. Докажите свойство 3.3.
3.8. Покажите, что для грамматики G, построенной при до-
казательстве достаточности теоремы 3.6 по исходному МП-
автомату R, справедливо утверждение [qZr] ш тогда и
только тогда, когда (g,w,Z) hj (r,e,e).
3.9. Покажите, что следующие языки в алфавите {а,Ь,с} не
контекстно-свободны:
(a) {aW : j < *};
(б) {a'b’c* :i < j < к};
(в) множество цепочек с одинаковым числом символов a,Ь и
(г) {a'b,aJb' : j < »};
(д) : i, j > 1);
(ж) {aWc* : числа i,j и к — попарно различны };
(з) {иш : ш € {а, 6}+}.
Проблема для исследования:
3.10. Разрешима ли проблема эквивалентности в классе
ДМП-автоматов, т.е. существует ли алгоритм, который по лю-
бым двум ДМП-автоматам Рг и Р2 определяет равны или не
равны языки L(Pi) и L(p?)?
72
4 Сложность алгоритмов и языков
В главе излагаются основы теории ЛГР-полных задач и до-
казывается фундаментальная теорема Кука. Здесь формали-
зуется ряд интуитивных понятий, возникающих при решении
задач дискретной математики, таких как, например "задача”,
"алгоритм”, ’’сложность”. Вводятся классы языков Р и МР,
эффективно распознаваемых на детерминированных и неде тер-
минированных вычислительных устройствах, и обсуждается
их связь с переборными задачами. Изучается понятие МР-
полноты, выделяющее класс наиболее трудных переборных
задач, рассматриваются основные .VP-полные задачи и об-
суждаются методы доказательства .VP-полноты конкретных
дискретных задач.
4.1 Машины Тьюринга
Понятие алгоритма принадлежит к числу основных понятий
математики. Неформально алгоритм — это однозначно трак-
туемое предписание о выполнении в определенном порядке дей-
ствий для решения всех задач данного типа, различающихся
конкретными значениями переменных параметров предписа-
ния, входными данными алгоритма.
Существует много точных математических определений по-
нятия алгоритма, связанных с различными уточнениями вы-
числительных возможностей исполнителя, реализующего ал-
горитм, среди которых одним из основных является машина
Тьюринга, описанная ниже. Все эти определения алгоритма
равносильны между собой и, следовательно, определяют од-
но и то же понятие; это и есть современное точное понятие
алгоритма, позволившее уточнить вопрос об алгоритмической
разрешимости того или иного класса однотипных задач, полу-
чивших название массовых задач.
73
Оказалось, что далеко не для всякой массовой задачи (вся-
кой серии однотипных, так называемых индивидуальных, или
единичных задач, называемых также частными случаями мае
совой задачи) существует единый алгоритм, позволяющий ре-
шить любую индивидуальную задачу данного класса. Приме-
ром такой {алгоритмически неразрешимой') массовой задачи
является так называемая модифицированная проблема соот-
ветствий Поста, в которой требуется по любому множеству
А = {(«ьД(ао А)} С Е+х Е+, где Е = {0,1}, опре-
делить, существует или нет последовательность (возможно с
повторениями) элементов (а*,, Д,),..(а,,,/?„) из А такая, что
равны слова Oia4l... и ДД,... Д,.
Такие массовые задачи, которые имеют только два возмож-
ных решения "да” или ’’нет”, получили названия задач рас-
познавания свойств. Задача распознавания свойств состоит
просто из двух множеств: всех ее индивидуальных задач и тех
из них, ответ для которых ”да”. Поэтому стандартная форма,
применяемая для описания задачи распознавания свойств, со-
стоит из двух частей: условия задачи в терминах подходящих
объектов (множеств, графов, функций, чисел и т.д.) и вопро-
са, предполагающего один из возможных ответов — ”да” или
"нет”.
Пример 4.1. Задачей распознавания свойств является за-
дача о неэквивалентности регулярных выражений, формули-
руемая следующим образом.
Условие. Задан конечный алфавит Е и два регулярных вы-
ражения Ei и Е3 над алфавитом Е.
Вопрос. Верно ли, что Ех и Е2 представляют различные
языки?
Примером индивидуальной задачи для нее является задача
с Е = {0,1}, Ei = (0 + 0(0 + 1)*) и Е2 = (0(0 + 1)’), ответ на
которую — "нет”. □
74
Пример 4.2. Рассмотрим задачу о клике для неориентиро-
ванных графов. Напомним, что fc-кликой в графе G называют
^-вершинный полный (т.е. такой, в котором каждая пара раз-
личных вершин соединена ребром) подграф графа G. Задача о
клике формулируется следующим образом.
Условие. Дан неориентированный граф G = (V, Е) и поло-
жительное число к <| V |.
Вопрос. Верно ли, что G содержит fc-клику?
Граф, изображенный на рис. 4.1, содержит три 3-клики, а
именно {vi,V2,v4}, {и2,1>з, v4} и {v3,v4,tJ5}. Поэтому примером
индивидуальной задачи для задачи о клике, ответ на которую
- "да”, является задача для графа с рис.4.1 и к равного 3. □
Рис. 4.1
Определение. Машиной Тьюринга (сокращенно Л/Т) М
называется семерка b,q0,qf), где
(1) Q — конечное множество состояний управляющего
устройства;
(2) Т — конечное множество символов на ленте;
(3) Е — множество входных символов, ЕСТ;
(4) b — пустой символ, Ь 6 Т \ Е;
(5) qo — начальное состояние, € Q;
(6) qf — заключительное (или допускающее) состояние,
€ Q ;
75
(7) 6 — так называемая функция перехода — отображение
множества Q х Т в множество подмножеств в Q х Т х {L, R, S},
где L — означает сдвиг головки по ленте влево, R — вправо,
S — головка остается на месте.
Машина Тьюринга работает на неограниченной с обеих сто-
рон ленте, разделяемой на ячейки, одну из которых обозревает
головка. В любой момент времени все ячейки, кроме конеч-
ного числа, заняты пустыми символами. Конфигурацией (или
мгновенным описанием) машины Тьюринга М называется сло-
во вида xqy, где ху — непустая часть ленты, a q — текущее
состояние управляющего устройства (головка на ленте обозре-
вает символ, стоящий справа от q).
Начальной конфигурацией М называется конфигурация ви-
да qow, где w G S*. Заключительная конфигурация — это кон-
фигурация вида xq}y.
Такт работы машины Тьюринга М представляется в ви-
де бинарного отношения hM, определенного на конфигурациях,
для которого a (i в одном из трех следующих случаев:
(1) а = = ypYu,(p,Y, S) G 6(q,X) для некоторых
7,w € T*;
(2) a = 'fqXu),^ = yYpcj,(p,Y,R) G 6(q,X) для некоторых
7,^ G T*;
(3) a = ^ZqXu,0 = 7р£Уо>,(р,У, I) G 6(g,X) для некото-
рых 7,w G T’ .
M допускает цепочку w G £*, если qow F-J, а, где a - неко-
торая заключительная конфигурация с пустой лентой, так на-
зываемая допускающая конфигурация. Языком, допускаемым
М (обозначается £(Л/)), называют множество всех цепочек,
допускаемых М. □
Таким образом, подобно конечному автомату машина Тью-
ринга состоит из ленты, головки и управляющего устройства
с конечным числом состояний.
76
Однако в машине Тьюринга лента неограниченно прости-
рается вправо и влево, а головка не только читает, но и пишет.
В силу этого лента в машине Тьюринга играет роль не толь-
ко входной ленты в конечном и магазинном автоматах, но и
бесконечной вспомогательной памяти последнего, причем без
присущих МП-автомату ограничений на’’магазинный” харак-
тер ее использования.
Поэтому не случайно, что машины Тьюринга облада-
ют большей вычислительной мощностью, чем МП-автоматы,
определяющие класс КС-языков. Известно, что язык порожда-
ется грамматикой составляющих тогда и только тогда, ко-
гда он допускается машиной Тьюринга. Промежуточное место
между МТ и МП-автоматами занимают так называемые ли-
нейно ограниченные автоматы — некоторое расширение класса
МП автоматов за счет разрешения входной головке двигаться
в обе стороны по входной ленте, снабженной концевыми мар-
керами. Класс линейно ограниченных автоматов определяет
класс контекстно-зависимых языков.
В дополнении к естественной интерпретации машины Тью-
ринга как распознавателя, допускающего тот или иной язык,
ее можно рассматривать как устройство, которое вычисляет
некоторую функцию f. Аргументы этой функции кодируются
на ленте в виде слова X со специальным символом (маркером),
отделяющим их друг от друга. Если машина Тьюринга оста-
навливается с заключительной конфигурацией vq}w, то слово
Y = vw рассматривается как код значения функции /, т.е.
/(Х) = У.
Пример 4.3. Машина Тьюринга М, функция переходов ко-
торой изображена в табл. 4.1, работает с алфавитами Q =
{<7о,Ро,Р1,Р2,Рз,Р4,Рв}»Г = {0,1,6} и Е = {0,1}. Нетрудно ви-
деть, что М допускает язык {w0*wfl : ш € Е’}. О
Определение. Машина Тьюринга Л/ называется детер-
минированной (сокращенно ДМТ), если для любых q Е Q и
77
Табл. 4.1
Текущее состояние Символ на ленте
0 1 Ь
?о {(роЛЯ), <(Р1ЛЯ)} <(9/Л5)}
(РзДЯ)}
Ро {(Ро,0,Я)} {(Ро,1,Я)}
Pi {(Pi.O, Я)} {(Ря,1,Я)} {(Рэ.М)}
Pi {(p<,b,L)} 0 0
Рз 0 {(Р4,М)} 0
Р< {(р.,0.1)) {(P4,1,Z)J {(9о,Ь,Я)}
Ръ {(р»ДЯ)} 0
X G Т множество b(q,X) содержит не более одного элемента.
□
4.2 Классы Р и Х'Р
Определение. Говорят, что машина Тьюринга М име-
ет временную сложность Т(п), если для всякой допускаемой
входной цепочки длины п найдется последовательность, состо-
ящая не более чем из Т(п) шагов, которая приводит в допус-
кающее состояние, и емкостную сложность S(n), если для
всякой допускаемой входной цепочки длины п найдется после-
довательность шагов, приводящая в допускающее состояние,
в которой число просмотренных головкой клеток на ленте не
превосходит 5(п).
Говорят, что М имеет полиномиальную временную (соот-
ветственно емкостную) сложность, если для некоторого поли-
78
нома р(п) справедливо T(n) = О(р(п)) (соответственно S(n) =
O(p(n))). °
Определение. Через V обозначается множество всех язы-
ков, допускаемых ДМТ с полиномиальной временной сложно-
стью, а через ЛГР — множество всех языков, допускаемых МТ
с полиномиальной временной сложностью. □
Имеется определенное соответствие между задачами распо-
знавания и языками, которое осуществляется с помощью ко-
дирования, обычно применяемого для представления задачи
при ее решении на ЭВМ. Выбрав способ кодирования всех
возможных индивидуальных задач в виде цепочек в некото-
ром фиксированном алфавите, можно переформулировать мас-
совую задачу как задачу распознавания языка, состоящего из
всех цепочек, представляющих индивидуальные задачи, ответ
для которых — "да”. При этом естественно требовать, чтобы
способ кодирования давал "сжатое” представление индивиду-
альных задач и допускал "декодирование”. Указанное соответ-
ствие позволяет отождествлять решение задачи распознавания
свойств с распознаванием соответствующего языка.
Чтобы связь задача — язык стала более явной, зафиксиру-
ем определенные "стандартные” представления задач, которые
удовлетворяют описанным выше требованиям и которые мы в
дальнейшем будем использовать по умолчанию. В частности,
примем следующие соглашения.
1. Целые числа будем представлять в десятичной системе
счисления.
2. Вершины графа будем представлять числами 1,2, ...,п,
закодированными как десятичные числа в соответствии с со-
глашением 1. Ребро будем представлять цепочкой (*i, »з), где ц
и ц — десятичные представления пары вершин, определяющей
это ребро, и t'i < ц.
3. Булевы выражения (формулы) с п пропозициональны-
ми переменными будем представлять цепочками, в которых
79
* представляет "и”, 4- представляет "или”, представляет
"не”, = представляет "тогда и только тогда”, а целые чи-
сла 1,2,...,п представляют пропозициональные переменные.
Знак *, когда можно, опускается. Если нужно, будем ставить
скобки.
Теперь мы можем сказать, что задача принадлежит V или
МР, если ее стандартный код принадлежит V или NV соот-
ветственно.
Пример 4.4. Рассмотрим задачу о клике для неориентиро-
ванных графов. Напомним, что задача о клике формулируется
так (см. пример 4.2): содержит ли данный граф G fc-клику, где
к — данное целое число?
Индивидуальную задачу задачи о клике для графа G, изо-
браженного на рис.4.1, и к = 3 можно закодировать цепочкой
3(1,2)(1,4)(2,3)(2,4)(3,4)(3,5)(4,5).
Здесь первое число представляет значение к. За ним идут па-
ры вершин, соединенных ребрами, причем вершина предста-
влена числом ». Таким образом, ребра в порядке перечисления
выглядят так: (vi,v2),(v1,v4),...,(v4,v5).
Язык L, представляющий задачу о клике, образуют все та-
кие цепочки вида
Jj) • • •
что граф с ребрами (tr,jr),l < г < т, содержит /г-клику.
Задачу о клике могут представлять и другие языки. Напри-
мер, можно было бы потребовать, чтобы константа к стояла
за, а не перед кодом графа. Или можно было бы использовать
двоичные числа вместо десятичных. Но для любых двух таких
языков должен существовать такой полином р, что цепочку w,
представляющую частный случай задачи о клике в одном язы-
ке, можно за время р(| и> |) преобразовать в цепочку, предста-
вляющую тот же частный случай этой задачи в другом языке.
80
Таким образом, когда речь идет о принадлежности классу V
или ЛГР, точный выбор языка для представления задачи о кли-
ке не важен, если применяется "стандартное” кодирование.
Нетрудно убедиться, что задача о клике принадлежит клас-
су МР. Недетерминированная машина Тьюринга, создавая
нужное количество своих экземпляров и отдавая на провер-
ку отдельному экземпляру каждое подмножество, состоящее
из к вершин, сначала может как бы "догадаться”, какие к вер-
шин составляют полный подграф, а затем проверить (соответ-
ствующим своим экземпляром), что любая пара этих вершин
соединена ребром, при этом для проверки достаточно 0(п3)
шагов, где п — длина кода задачи о клике. Это демонстриру-
ет "силу” недетерминизма, ибо все подмножества из к вершин
проверяются "параллельно” независимыми экземплярами рас-
познающего устройства. Граф на рис. 4.1 содержит ровно три
3 клики, а именно {vt,v3,v4},{v2,V3,v4) и {v3,v4,v5}- °
Пример 4.5. Булеву формулу (pi +р2) *рз можно предста-
вить цепочкой (1 + 2)3, где число i представляет переменную
р,. Рассмотрим язык L, образованный всеми цепочками, пред-
ставляющими выполнимые булевы формулы (т.е. формулы,
принимающие значение 1 на некотором наборе 0-1-значений
переменных). Нетрудно увидеть, что L принадлежит ЛГР. Не-
детерминированный алгоритм, распознающий L, начинает с
того, что "угадывает” выполняющий набор 0-1-значений про-
позициональных переменных во входной цепочке, если такой
набор существует. Затем угаданное значение (0 или 1) каждой
переменной подставляется вместо всех вхождений этой пере-
менной во входную цепочку. Чтобы закрыть дыры, образую-
щиеся в цепочке в результате подстановки одного символа О
или 1 вместо десятичного представления пропозициональной
переменной, потребуются некоторые сдвиги цепочки. Далее
вычисляется значение полученного выражения, чтобы прове-
рить его совпадение с 1.
81
Это вычисление легко осуществить за 0(п2) шагов. Сле-
довательно, некоторая недетерминированная машина Тьюрин-
га допускает выполнимые булевы формулы с полиномиаль-
ной временной сложностью, и потому задача распознавания
выполнимости булевых формул принадлежит Л/'Р. Снова от-
метим, что недетерминизм пригодился, чтобы "параллелизо-
вать” задачу, поскольку "угадывание" правильного решения в
действительности означает параллельную проверку всех воз-
можных решений. □
Различие между полиномиальными алгоритмами (или ал-
горитмами, представляемыми машинами Тьюринга с полино-
миальной временной сложностью) и алгоритмами, временная
сложность которых не поддается подобной оценке, становится
особенно заметным при решении задач большого размера, что
видно из табл. 4.2, описывающей зависимость времени реше-
ния в секундах от размера входных данных и вида функции
временной сложности, и табл. 4.3, показывающей зависимость
размера наибольшей задачи, решаемой за 1 час, от быстро-
действия ЭВМ и вида функции временной сложности. Первая
из них позволяет сравнить скорости роста полиномиальных
и экспоненциальных функций, а вторая показывает насколько
увеличатся размеры задач, решаемых за один час машинного
времени; если быстродействие ЭВМ возрастет в 100 или 1000
раз.
Большинство из алгоритмов, имеющих экспоненциальную
временную сложность, — это просто варианты полного пе-
ребора, в то время как полиномиальные алгоритмы для ре-
шения той или иной задачи удается построить лишь тогда,
когда глубоко понята суть решаемой задачи. Поэтому зада-
ча не считается "хорошо решаемой” до тех пор, пока для нее
не построен полиномиальный алгоритм, и обычно задачу на-
зывают труднорешаемой, если для ее решения не существует
такого алгоритма.
82
Таблица 4.2
Функция временной сложности Размер исходной задачи
10 30 50
п 0,00001 сек 0,00003 сек 0,00005сек
п2 0,0001 сек 0,0009 сек 0,0025сек
п3 0,001 сек 0,027 сек 0,125сек
п5 0,1 сек 24,3 сек 5,2 мин
2" 0,001 сек 17,9 мин 35,7 лет
3” 0,059 сек 6,5 лет 2 х 10е
столетий
Хотя классы Р и AfP были определены в терминах машин
Тьюринга, можно было бы использовать любую из многих дру-
гих моделей вычислений, в том числе и так называемую ма-
шину с произвольным доступом к памяти (равнодоступную
адресную машину или РАМ), которая является достаточно хо-
рошим приближением к классу обычных, традиционных вы-
числительных машин с точки зрения представления данных и
алгоритмов, целиком помещающихся в оперативной памяти и
имеющих дело с элементарными значениями, длины двоичных
представлений которых ограничены некоторой константой.
Все известные в настоящее время реалистические модели
ЭВМ (в их детерминированном и недетерминированном ва-
риантах) эквивалентны относительно полиномиальной времен-
ной сложности. Можно ожидать, что и любая иная "разумная”
модель ЭВМ будет эквивалентна в указанном смысле всем пе-
речисленным моделям.
Под словами "разумная модель” здесь главным образом име-
ется в виду то, что объем работы, выполняемой машиной в
83
Табл. 4.3
Функция временной сложности Размер наибольшей задачи, разрешимой за один час
На исходных ЭВМ На ЭВМ, в 100 раз более быстрых На ЭВМ, в 1000 раз бо- лее быстрых
п м юом 1000АГ1
п2 N, 10ЛГ2 31,6JV2
пз N3 4,64JV3 10JV3
«5 2,5ЛГ< 3,98JV«
2" Nt JVs + 6,64 TVs+ 9,97
з" Ne + 4,19 tfe + 6,29
единицу времени, ограничен (сверху) полиномом. Так, напри-
мер, модель, обладающая способностью выполнять параллель-
но произвольно много операций, не будет считаться "разум-
ной”, и в действительности ни одна из существующих (или
проектируемых) ЭВМ не обладает подобным свойством. Во
всяком случае, если ограничиться рассмотрением стандарт-
ных моделей реальных ЭВМ, то класс труднорешаемых задач
не будет зависеть от выбора конкретной модели, и такой выбор
можно осуществлять, исходя из интересов дела и не уменьшая
при этом сферы применимости полученных результатов.
4.3 Полиномиальная сводимость и Лг'Р-полнота
Определение. Язык L называется полиномиально своди-
мым (трансформируемым) к Zo, если некоторая машина Тью-
ринга с полиномиальной временной сложностью М преобразу-
ет каждую цепочку w в алфавите языка L в такую цепочку в
84
алфавите языка £0 (т.е. М, обрабатывая цепочку ш, достигает
заключительной конфигурации, в которой и>0 - непустая часть
ее ленты), что ш € L тогда и только тогда, когда G Lo. □
Определение. Язык L из ЛГР называется полным для
недетерминированного полиномиального времени (или ЛГР-
полным), если каждый язык из ЛГР полиномиально сводим к
L. □
Таким образом, Л^Р-полные задачи являются "самыми
трудными” в классе А/’Р. Если какая-нибудь АГР-полная за-
дача может быть решена за полиномиальное время, то и лю-
бая задача из А/’Р полиномиально разрешима, а если какая-то
задача из ЛГР труднорешаема, то и любая АГР-полная задача
является труднорешаемой. При этом, для того чтобы доказать
А^Р-полноту некоторой задачи из АГР, достаточно показать,
что какая-то из ЛгР-полных задач полиномиально сводится к
ней.
Вопрос о взаимоотношении классов Р и VP имеет фун-
даментальное значение, но все еще открыт. Известно, что
Р С А/’Р и если L G МР, то существует такой полином р(п)
и ДМТ М, что L допускается на М с временной сложностью
0(2р(п)) (см. упражнение 4.4). Однако до сих пор пока не до-
казано, содержит класс MP труднорешаемые задачи или нет,
т.е. MP \ Р / О или А/’Р = Р. Вместе с тем известно, что в
предположении Р / А/P класс А/’Р не просто содержит два не-
пересекающихся подкласса: класс Р и класс А/’Р-полных задач,
а также должен включать задачи, не принадлежащие ни одно-
му из этих подклассов (т.е. при Р / Ai'P должны существовать
задачи из ЛГР, которые неразрешимы за полиномиальное вре-
мя и не являтся А/’Р-полными.
Теорема 4.1. (С.А.Кук). Задача выполнимости булевой
формулы NP- полна.
Доказательство. Мы уже знаем (см. пример 4.5), что зада-
ча выполнимости булевой формулы принадлежит классу МР.
85
Осталось покатать, что всякий язык L из Л''Р полиномиально
трансформируем в задачу выполнимости. Пусть М — недетер-
минированная машина Тьюринга, распознающая L за полино-
миальное время, и пусть на ее вход подана цепочка w. Из М и
ш можно построить булеву формулу w0, выполнимую тогда и
только тогда, когда М допускает ш. Основная трудность дока-
зательства — показать, что для каждой машины М найдется
алгоритм, который построит булеву формулу w0 из ш за время,
ограниченное полиномом. Этот полином зависит от М.
Пусть состояниями М будут qi, q2,..., q,, а символами на
ленте — Пусть р(п) — временная сложность
машины М. Предположим, что цепочка и>, поданная на вход
машины М, имеет длину п.
Таким образом, если М допускает uj, то делает это не более
чем за р(п) шагов. Если М допускает о>, то найдется хотя бы
одна такая последовательность конфигурации Qo,Qi,. . ,Q^,
что Qo — начальная конфигурация, I- Qi для 1 < i <
— допускающая конфигурация, q < р(п) и ни одна конфигура-
ция не занимает более р(п) клеток на ленте.
Построим булеву формулу ш0, которая "моделирует” после-
довательность конфигураций, проходимых машиной М. Лю-
бое присвоение значений истина (число 1) и ложь (число 0)
переменным формулы и>0 соответствует самое большее одной
последовательности конфигураций, возможно незаконной (т.е.
такой, которая не может на самом деле реализоваться). Булева
формула ша примет значение 1 тогда и только тогда, когда это
присваивание значений переменным соответствует последова-
тельности конфигураций Qo,Qi, ,Q4, ведущей к допусканию
входа. Иными словами, булева формула w0 будет выполнима
тогда и только тогда, когда М допускает w. В качестве про-
позициональных переменных в употребляются следующие
переменные. Перечислим их вместе с их подразумеваемой ин-
терпретацией.
86
1- = 1 тогда и только тогда, когда »-я клетка на
входной ленте машины М содержит символ А'р момент вре-
мени t. Здесь 1 < t < р(п), 1<у<тпи0<<< р(п).
2. S(k,t) = 1 тогда и только тогда, когда М в момент вре-
мени t находится в состоянии qk. Здесь 1<Л<зиО</< р(п).
3. Н (i,t) = 1 тогда и только тогда, когда головка в момент
времени t обозревает t-ю клетку. Здесь 1 < t < р(п) и 0 < t <
р(п).
Таким образом, общее число пропозициональных перемен-
ных составляет О(р2(п)) и их можно представить двоичными
числами, содержащими не более с log п разрядов, где с — по-
стоянная, зависящая отр. В дальнейшем удобно будет предста-
влять себе пропозициональную переменную как один символ,
а не с log п символов. Эта потеря множителя с log п не мо-
жет отразиться на полиномиальной ограниченности времени,
затрачиваемого на вычисление той или иной функции.
Из этих пропозициональных переменных построим булеву
формулу Wo, следуя структуре последовательности конфигура-
ций QoiQi,... В этом построении мы воспользуемся пре-
дикатом U(xi,xj,... ,zr), принимающим значение 1, когда в
точности один из аргументов xi,x2,...,xr принимает значе-
ние 1. Предикат U можно выразить булевой формулой вида
U(Z|,z2,...,zr) = (xj + z2 + ... + хг) (ПИ1* +
Первый множитель в ней утверждает, что по крайней мере
одна из переменных Zj истинна. Остальные r(r - 1 )/2 множи-
телей утверждают, что никакие две переменные не являют-
ся истинными одновременно. Заметим, что формальная запись
формулы C7(z!,z2,...,zr) имеет длину О(г2). (Напомним, что
мы считаем переменную одним символом. Строго говоря, по-
требуется О(г2 log г) и, значит, не более 0(г3) символов).
87
Если М допускает w, то найдется допускающая последова-
тельность конфигураций проходимая машиной
М в процессе обработки цепочки ш. Для упрощения рассмотре-
ний мы будем считать, что машина М модифицирована так,
что она делает ровно р(п) шагов, а все ее конфигурации содер-
жат по р(п) клеток. Этого можно добиться, заставив М, если
нужно, работать после перехода в допускающее состояние, но
не изменяя его и не сдвигая головку, и дополнив все конфигура-
ции нужным числом пустых символов. Поэтому будем строить
Wo как произведение семи формул А, В,... , (7, которые утвер-
ждают, что Qo, Q1,..., — допускающая последовательность
конфигурации, причем каждая конфигурация Qi имеет длину
р(п) и q = р(п). Утверждение о том, что Qo,Qi, • - • ,QP(n) —
допускающая последовательность конфигураций, равносильно
совокупности утверждений:
1) в каждой конфигурации головка обозревает ровно одну
клетку;
2) в каждой конфигурации в каждой клетке ленты стоит
ровно один символ;
3) каждая конфигурация содержит в точности одно состоя-
ние;
4) при переходе от одной конфигурации к следующей изме-
няется содержимое разве что клетки, обозреваемой головкой;
5) изменение состояния, положения головки и содержимого
клетки при переходе от текущей конфигурации к следующей
происходит в соответствии с функцией переходов машины Af;
6) первая конфигурация является начальной;
7) состояние в последней конфигурации — заключительное.
Построим булевы формулы описывающие утвер-
ждения 1 — 7 соответственно.
1. А утверждает, что в каждый момент времени машина М
обозревает в точности одну клетку. Пусть Л, утверждает, что
88
в момент t обозревается в точности одна клетка. Тогда
А = Ао А\...
где
А, = ЩЯ(1,0,Я(2,/),...,Я(р(п)Л)).
Заметим, что если раскрыть выражение, обозначенное че-
рез U, то окажется, что формула А имеет длину О(р3(п)) и ее
можно записать за такое же время.
2. В утверждает, что каждая клетка ленты в каждый мо-
мент времени содержит в точности один символ. Пусть B,t
утверждает, что t-я клетка ленты в момент времени t содер-
жит ровно один символ. Тогда
«,«
где
Bit = L/(C(t,l,t),C(t,2,0...
Длина каждой формулы Вц не зависит от п, поскольку мощ-
ность тп алфавита символов на ленте зависит только от маши-
ны Тьюринга М.Таким образом, В имеет длину О(р2(п)).
3. С утверждает, что в каждый момент времени t машина
М находится в одном и только одном состоянии:
0<t<p(n)
Так как число состояний s машины М постоянно, то С име-
ет длину О(р(п)).
4. D утверждает, что в любой момент времени t можно из-
менить содержимое не более чем одной клетки:
D = П((С<», j,t) = + 1)) +
89
Формула t) = C(t, j,t + 1)) + утверждает, что
либо
(а) в момент t головка обозревает клетку t, либо
(б) j-й символ записан в клетке t в момент t + 1 тогда и
только тогда, когда он был записан там в момент t.
Поскольку А к В утверждают, что в момент t головка обо-
зревает только одну клетку и клетка i содержит лишь один
символ, то в момент времени t либо головка обозревает клет-
ку », либо содержимое клетки i не меняется. Если раскрыть
значение знака =, то длина D будет О(р2(п)).
5. Е утверждает, что очередная конфигурация машины М
получается из предыдущей одним переходом, разрешаемым
функцией переходов 6 машины М. Пусть означает од-
но из следующих утверждений:
(а) в момент t клетка i не содержит символа j,
(б) в момент t головка не обозревает клетку t,
(в) в момент t машина М не находится в состоянии к,
(г) очередная конфигурация машины М получается из пре-
дыдущей переходом, разрешаемым функцией переходов маши-
ны М.
Тогда
= П
ij.b.t
где
Eijkt = -iC(i,j,k) + +
+ + l)S{kht + + 1)].
i
Здесь / пробегает по всем шагам машины Л/, возможным в
случае, когда Л/ обозревает символ Xj в состоянии Иными
словами, для каждой тройки (g,X,d) из 6{qk,Xj) существует
одно значение /, для которого Xj, = X,qt| = q и число рав-
но i — l,i или i + 1 в зависимости от d: сдвигается ли головка
90
влево (d = L,ii = t — 1), вправо (d = R,ii = i + 1) или остается
на месте (d = S,:( = t). Здесь 6 — функция переходов для М.
Поскольку машина М в общем случае недетерминированная,
то таких троек (g,X,d) может быть несколько, но во всяком
случае их число конечно. Таким образом, имеет ограни-
ченную длину, не зависящую от п. Поэтому Е имеет длину
О(р2(п)).
6. F утверждает, что выполнены начальные условия:
Г = $(1,0)Я(1,0) J] П С(»,1,0),
1<«<п n<i<p(n)
подформулы которой имеют следующий смысл:
(а) 5(1,0) утверждает, что М в момент t = 0 находится в
состоянии gi, которое мы считаем начальным;
(б) Я (1,0) утверждает, что М в момент t = 0 обозревает
самую левую клетку ленты;
(в) II C(»,jj,0) утверждает, что первые п клеток вначале
1<«<п
содержат входную цепочку о>;
(г) П С(«, 1,0) утверждает, что остальные клетки вна-
n<i<p(n)
чале пусты.
Мы считаем, что пустым символом является Очевидно,
что F имеет длину О(р(п)).
7. G утверждает, что М в конце концов приходит в заключи-
тельное состояние. Поскольку мы потребовали, чтобы машина
М оставалась в заключительном состоянии после того, как оно
достигнуто, то G = 5(s,p(n)). Мы считаем, что заключитель-
ным состоянием является q,.
Булева формула w0 — это произведение ABCDEFG. По-
скольку каждый из семи сомножителей состоит не более чем
из О(р3(п)) символов, сама формула о>0 также состоит не более
чем из О(р3(п)) символов. Так как мы считали каждую про-
позициональную переменную за один символ, а в действитель-
ности переменные представляются цепочками длины О(1од п),
91
то на самом деле границей на | ш0 | будет O(p3(n) log п), а это
не превосходит спр3(п), где с — некоторая константа. Таким
образом, длина цепочки ш0 полиномиально зависит от длины
цепочки ш. Очевидно ясно, что если даны цепочка w и полином
р, то формулу о»о можно записать за время пропорциональное
ее длине.
По данной допускающей последовательности конфигураций
Qoi Qi, • • •, Qi можно, очевидно, найти такое присваивание зна-
чений 0 и 1 пропозициональным переменным и
что о>о примет значение истина. Обратно, если дано
присваивание значений переменным формулы при котором
она становится истинной, то легко найти допускающую по-
следовательность конфигураций. Таким образом, формула ш0
выполнима тогда и только тогда, когда М допускает цепочку
ы.
На язык L, допускаемый машиной М, не накладывалось ни-
каких ограничений, кроме того, что он из класса №Р. Поэтому
мы показали, что любой язык из МР полиномиально сводим
к задаче выполнимости булевых формул. Отсюда заключаем,
что задача выполнимости Л^Р-полна. □
На самом деле проведенные в теореме 4.1 рассуждения до-
казывают больше, чем утверждается в теореме 4.1. Напомним,
что булева формула находится в конъюнктивной нормальной
форме (КНФ), если она представляет собой произведение сумм
литералов, где каждый литерал имеет вид х или -ч для неко-
торой переменной х. Например (х j )(ага 4- 14- х3) находится
в КНФ, a XiX? 4-х3 нет. Формула w0, построенная в доказатель-
стве теоремы 4.1, практически находится в КНФ — ее можно
представить в КНФ, увеличив длину не более чем в констант-
ное число раз.
Следствие 1. Задача выполнимости булевых формул, на-
ходящихся в КНФ, МР-полна.
92
Доказательство. Достаточно показать, что каждая из
формул A,...,G, построенных в доказательстве теоремы 4.1,
либо уже находится в К НФ, либо может быть преобразована
в такую с помощью правил булевой алгебры, причем длина
формулы увеличится не более чем в константное число раз.
Формула U уже находится в КНФ. Отсюда следует, что А, В и
С тоже находятся в КНФ. F я G тривиально находятся в КНФ,
поскольку F и G — произведения литералов.
D — формула, содержащая подвыражения вида (х = у) + Z.
Если раскрыть знак =, получится выражение
ху + ->х->у + Z,
эквивалентное выражению
(х + ->у + *)(-'Х + у + z).
Подставив второе выражение вместо всех вхождений перво-
го в D, получим формулу, эквивалентную исходной, но находя-
щуюся в КНФ и превосходящую исходную формулу по длине
не более чем в 2 раза.
Наконец, Е — произведение формул Поскольку дли-
ны всех ограничены независимо от п, каждую формулу
E,ikt можно преобразовать в формулу в КНФ, причем ее длина
не будет зависеть от п. Поэтому преобразование формулы Е
в формулу в КНФ увеличивает ее длину не более чем в кон-
стантное число раз.
Итак, формулу си0 можно представить в КНФ, увеличив ее
длину не более чем в константное число раз. □
Мы только что показали, что задача выполнимости фор-
мул, находящихся в КНФ, АГР-полна. Можно показать, что
даже при более жестких ограничениях на вид формулы задача
выполнимости булевых формул также А'Р-полна.
93
Определение. Говорят, что булева формула находится в
к-конъюнктивной нормальной форме (fc-КНФ), если она пред-
ставляет собой произведение сумм, состоящих не более чем из
к литералов. Задача к-выполнимости (Л-ВЫП) состоит в вы-
яснении выполнимости формулы, находящейся в Л-КНФ. □
Для к = 1 и 2 известны детерминированные алгоритмы по-
линомиальной сложности, проверяющие fc-выполнимость (см.
упражнение 4.6). Ситуация (по-видимому) изменяется при к =
3, как видно из следующей теоремы.
Теорема 4.2. Задача 3-выполнимости Л'Р-полна.
Доказательство. Покажем, что выполнимость формул в
КНФ полиномиально сводима к задаче о 3-выполнимости. В
данном произведении сумм заменим каждую сумму
(*1 + ®2 + •• • + **)»
в которой к > 4, на
(ii + х3 + У1)(х3 + -.у, + у2)(х4 + ->у3 + Уз)---
• - - (®*-з 4- + !/*-з)(х*-1 + ** + _,У*-з),
где У1,Уз,-1/*-з — новые переменные (например, для к = 4
указанное выражение принимает вид (zj + х3 + У1)(хз + z4 +
^У1))-
Присвоить значения новым переменным так, чтобы подста-
вляемая формула приняла значение 1, можно тогда и только
тогда, когда один из литералов Zj, х3,..., х* имеет значение 1,
т.е. тогда и только тогда, когда исходная формула принима-
ет значение 1. Допустим, что z, = 1. Тогда положим у; = 1
для j < » - 2 и у} = 0 для j > t - 2. Подставляемая формула
принимает значение 1. Обратно, допустим, что при некоторых
значениях переменных у, подставляемая формула принимает
значение 1. Если у; = 0, то одна из переменных и х3 должна
94
иметь значение 1. Если щ_3 = 1, то одна из переменных i*_i
и хц должна иметь значение 1. Если у1 = 1 и yt_3 = 0, то для
некоторого i,l < t < к - 4, выполнены оба равенства у, = 1 и
1/<+1 = 0, откуда следует, что переменная г<+2 должна иметь
значение 1. В любом случае некоторая переменная должна
иметь значение 1.
Длина формулы, получаемой в результате описанной выше
замены, превосходит длину исходной формулы не более чем в
постоянное число раз. Таким образом, по данной формуле Е
в КНФ можно найти, применяя описанное выше преобразова-
ние к каждой сумме, формулу Е' в 3-КНФ, выполнимую тогда и
только тогда, когда выполнима исходная формула. Более того,
легко показать, что Е' можно найти за время, пропорциональ-
ное длине формулы Е, выполняя преобразования очевидным
образом. □
4.4 Методы доказательства VP-полноты
Если бы все доказательства NV-полноты были ли бы таки-
ми сложными, как доказательство МР-полноты задачи выпол-
нимости булевых формул, то, по-видимому, список известных
VP-полных задач не был бы столь обширным, как в насто-
ящее время. Однако, как отмечалось в предыдущем разделе,
если уже известна одна из VP-полных задач, то процедура
доказательства .VP-полноты других задач может быть суще-
ственно упрощена. Для доказательства VP-полноты задачи
Р С VP достаточно показать, что какая-нибудь из известных
VP-полных задач Р' может быть сведена к Р. Таким образом,
процесс доказательства VP-полноты задачи Р может состоять
из следующих четырех шагов:
• доказательства, что Р G VP;
• выбора подходящей известной VP-полной задачи Р'\
• построение функции /, сводящей задачу Р' к задаче Р;
95
• доказательство того, что функция f осуществляет поли-
номиальное сведение.
Покажем VP-полноту еще нескольких задач, которые наря-
ду с задачами о выполнимости булевых формул, чаще других
используются в качестве "известных VP-полных задач”.
Теорема 4.3. Задача о клике VP-полна.
Доказательство. Задача о клике входит в класс NР (см.
пример 4.3). Покажем, что задача о выполнимости булевых
формул, находящихся в КНФ, полиномиально сводима к задаче
о клике.
Пусть F = Fi F3 ... F, — формула в КНФ, где F< — сомно-
жители; каждая формула F имеет вид (хп + х< 2 + ... + 1ц,,
где Xij — литерал. Построим неориентированный граф G =
(V,£), вершинами которого служат пары целых чисел [»,j]
для 1 < 1i < q и 1 < j < к, (см. пример 4.5). Первая ком-
понента такой пары представляет сомножитель, а вторая —
литерал, входящий в него. Таким образом, каждая вершина
графа естественным образом соответствует конкретному вхо-
ждению в конкретный сомножитель.
Ребрами графа G служат пары ([»,для которых
t / к и Xij / -«Хц. Неформально, вершины [i,j] и [Л,/] смеж-
ны в G, если они соответствуют различным сомножителям и
можно так присвоить значения переменным из литералов Ху и
Xici, чтобы оба литерала приняли значения 1 (тем самым давая
значение 1 формулам F< и Ft). Иными словами, либо Ху = х*(,
либо переменные, входящие в литералы Ху и Хы, различны.
Число вершин в G, очевидно, меньше длины формулы F,
а число ребер не превосходит квадрата числа вершин. Поэто-
му граф G можно закодировать в виде цепочки, длина которой
ограничена полиномом от длины формулы F, и, что еще важ-
нее, такой код можно найти за время, ограниченное полиномом
от длины F. Можно показать (см. ниже), что G содержит q-
клику тогда и только тогда, когда формула F выполнима. От-
96
сюда будет следовать, что по данному алгоритму, решающему
задачу о клике за полиномиально ограниченное время, можно
построить алгоритм с полиномиально ограниченным временем
работы для задачи КНФ-выполнимости, построив по F граф
G, содержащий 9-клику тогда и только тогда, когда форму-
ла F выполнима. Итак, покажем, что для того чтобы граф
G содержал клику g-клику, необходимо и достаточно, чтобы
формула F была выполнима.
Достаточность. Пусть формула F выполнима. Тогда су-
ществует набор значений переменных, состоящий из нулей и
единиц, при котором F = 1. При этом наборе каждый сомножи-
тель формулы F принимает значение 1. Каждый сомножитель
Fi содержит по меньшей мере один литерал, принимающий
значение 1. Пусть таким литералом в Fi будет ximt.
Нетрудно убедиться, что q - клику образует множество вер-
шин : 1 < » < q. Если бы это было не так, то нашлись бы
такие t и j, что i / j и вершины и не соединены
ребром. Отсюда следовало бы, что xim, = (по определе-
нию множества ребер графа G). Но это невозможно, поскольку
= 1 в силу выбора переменных xjm<.
Необходимость. Пусть G содержит g-клику. Первые ком-
поненты вершин, составляющих такую клику, должны быть
различны, поскольку вершины с одинаковыми первыми ком-
понентами не соединяются ребрами. Так как в этой клике в
точности g вершин, то вершины клики взаимно однозначно со-
ответствуют сомножителям формулы F. Пусть вершины кли-
ки имеют вид < t < д. Пусть = {j/ :xjm, = у, где
1 < t < g и у — переменная } и S, = {у : х<т, = ->у, где
1 < « < g и у — переменная }. Иными словами, Sj и Sj — мно-
жества переменных и отрицаний переменных соответственно,
представленных вершинами клики. Тогда Si Г) S2 = 0, ибо в
противном случае какие-то вершины [я, mJ и [t,m(], для ко-
торых х,т, = -»х*т,, соединялись бы ребром. Если положить
97
переменные из S, равными 1, а из 52 равными 0, То каждая фор-
мула F, примет значение 1. Поэтому формула F выполнима.
□
Пример 4.в. Рассмотрим формулу F = + -iy2)(y2 +
_,Уз)(Уз + ~'У\)- Литералы в ней таковы: тп = yi,x2i =
У2,*31 = Уз» *11 = -1У2»*22 = -,Уз,*32 — -|У1-
Конструкция из теоремы 4.3 дает граф, изображенный на
рис. 4.2. Например вершина [1,1] не соединена с [1,2], потому
что первые компоненты одинаковы, и с [3,2], потому что хп =
У) и т32 = -ij/j, а с остальными тремя вершинами соединена.
Рис. 4.2
В формуле F три сомножителя, и оказывается, что в гра-
фе на рис. 4.2 две 3-клики, а именно {[1,1],[2,1],[3,1]} и
{[1,2],[2,2],[3,2]}. В первой клике представлены три литера-
ла- У1,У2 и уз- Это переменные без отрицаний, и первая кли-
ка соответствует присвоению значений yt = у2 = у3 = 1,
98
выполняющему F. Вторая клика соответствует другому набо-
ру значений, обращающему формулу F в истинную, а именно
У1 = Уз = Уз = 0. □
Определение. Задача о вершинном покрытии (ВП) фор-
мулируется следующим образом:
Условие. Дан неориентированный граф G = (V, Е) и поло-
жительное целое число k,k <| V |.
Вопрос. Имеется ли fc-вершинное покрытие в G, т.е. суще-
ствует ли такое V С V, что | V |= к и для каждого ребра
{«,«} графа хотя бы одна из вершин и или v принадлежит V'?
□
Теорема 4.4. Задача о вершинном покрытии NV-полна.
Доказательство. Легко видеть, что ВП принадлежит NV.
Покажем, что задача о клике полиномиально сводима к задаче
о вершинном покрытии.
Пусть дан неориентированный граф G = (V,E). Рассмо-
трим его дополнение G = (У,Ё), где Ё = {(v,w) | v, w G V, v /
w и (v,w) £ E}. Мы утверждаем, что множество S С V явля-
ется кликой в G тогда и только тогда, когда V\S является вер-
шинным покрытием графа G (см. пример 4.3). Действительно,
если S — клика в G, то никакое ребро в G не соединяет никакие
вершины в S. Поэтому всякое ребро в G инцидентно по мень-
шей мере одной вершине из V \ S, откуда следует, что V \ S
есть вершинное покрытие графа G. Аналогично, если V \ S
есть вершинное покрытие графа G, то каждое ребро из G ин-
цидентно по меньшей мере одной вершине из V \ S. Поэтому
никакое ребро из G не соединяет две вершины из S. Следова-
тельно, каждая пара вершин из S соединена в G, и, значит, S
— клика в G.
Таким образом, чтобы узнать, существует ли fc-клика, мож-
но построить граф G и выяснить, содержит ли он вершинное
покрытие размера | V | -к. Разумеется, по данному стандарт-
ному представлению графа G = (V,E) и числу к можно найти
99
представление графа (7 и числа | V | -k за время полиноми-
ально зависящее от длины представления G и к. □
Пример 4.7. Граф G на рис. 4.3,а содержит две 3-клики
{1,2,5} и {1,4,5}. Граф G на рис. 4.3,6 содержит соответству-
ющие вершинные покрытия {3,4} и {2,3} размера 2. Граф G
содержит (среди других) 2-клики {2,3} и {3,4}, а граф G —
соответствующие вершинные покрытия {1,4,5} и {1,2,5} раз-
мера 3. □
Определение. Задача о трехмерном сочетании (3-С) фор-
мулируется следующим образом. Верно ли, что заданное мно-
жество М С WxXxY,где IV,X иУ — непересекающиеся мно-
жества, равной мощности q, т.е. | W |=| X |=| У |= q, содер-
жит трехмерное сочетание, т.е. такое подмножество М' С М,
что | М' |= q и никакие два разных элемента из М' не имеют
ни одной равной координаты? □
Теорема 4.Б. Задача о трехмерном сочетании является
МР-полной.
Доказательство. Легко видеть, что 3-С G АГР.
100
Это следует из того, что недетерминированному алгоритму
нужно только угадать в заданном М нужное подмножество,
состоящее из q =| W |=| X |=| У | троек, и за полиноми-
альное время проверить, что любые две из угаданных троек
отличаются по всем координатам.
Сведем задачу 3-ВЫП к задаче 3-С.
Пусть U = {«i,u2,...,un) — множество переменных и С =
{С1,с2)... ,ст} — множество дизъюнкций произвольной инди-
видуальной задачи из 3-ВЫП. Нужно построить непересека-
ющиеся множества IV, X, У и М С W X X X У такие, что
|РУ|=|Х|=|У|ииИ содержит трехмерное сочетание в том и
только в том случае, когда С выполнима.
Искомое множество упорядоченных троек М будет разбито
на три различных класса в соответствии с их функциональ-
ным назначением: "набор значений истинности и развертка”,
"проверка выполнения” и ’’достройка”.
Тройки, входящие в класс ’’набор значений истинности и
развертка”, разбиваются на группы (компоненты), каждая из
которых соответствует одной переменной и 6 U, а ее строе-
ние зависит от общего числа тп дизъюнкций в С. Строение
этой компоненты для случая т = 4 показано на рис. 4.4.
В общем случае каждая такая компонента, соответствующая
переменной и,, включает "внутренние” элементы € X
и G У,1 < j < тп, которые не будут входить ни в
какую тройку вне этой компоненты, и "внешние” элементы
««[)]»"’“•Ы € W, 1 < j < тп, которые будут входить в дру-
гие тройки. Образующие эту компоненту тройки могут быть
подразделены на два множества:
= 1 < J < ”»};
Ti = {(«.ЬЬ^Ь’+ЦЛЙ): 1 <3 < ™}и{(«МтЬ«•[!],Mm])}.
Так как внутренние элементы {<чЬ'ЬМУ1 : 1 < J т}
могут входить только в тройки, принадлежащие множеству
Г, = Г* U Т/, то легко видеть, что любое трехмерное сочета-
101
ние М' должно иметь ровно т троек из 7}, а именно либо все
тройки из 7?, либо все тройки из Т/. Следовательно, можно
считать, что компонента из Т\ приводит к тому, что трехмер-
ное сочетание индуцирует присвоение переменной и, значения
"истина” или ”ложь”. Таким образом, трехмерное сочетание
М' С М определяет набор значений истинности на множестве
U, при этом переменная и, принимает значение "истина” тогда
и только тогда, когда М' П 7< = Т-. В частности, для компо-
ненты Т{, задающей значения истинности при тп = 4 и изобра-
женной на рис. 4.4 (здесь нижние индексы у переменных для
простоты опущены, а й[«] обозначает -iu[i]), должно быть вы-
брано либо множество Т- (заштрихованное множество), либо
множество Т/ (незаштрихованное множество), при этом оста-
ются непокрытыми (т.е. не объединенными в тройки) либо все
и,[;], либо все соответственно.
П[3]
Рис. 4.4
102
Каждая компонента множества Л/, предназначенная для
проверки выполнимости, соответствует одной дизъюнкции
Cj G С. Такая компонента содержит только два "внутренних”
элемента € X и s2(j] G У, а также "внешние” элементы
из множества {и,[у],->и<[у] : 1 < » < п}, выбираемые в зависи-
мости от того, какие литералы содержатся в дизъюнкции Cj.
Множество троек, образующих эту компоненту С,, определя-
ется как объединение множеств {(«.[j],3i[j],32[j]) : и,- € с,} и
: € с;}‘
Итак, любое трехмерное сочетание М' С М должно содер-
жать ровно одну тройку из С,. Но это условие может быть
выполнено только в том случае, если для некоторого литерала
щ G Cj (или -Иц G Cj) элемент u,[j] (соответственно не
войдет ни в одну из троек множества 7<ПЛ/', а это будет иметь
место тогда и только тогда, когда набор значений истинности,
определяемый множеством М', выполняет дизъюнкцию Cj.
Построение нужной индивидуальной задачи из 3-С будет за-
кончено после описания одной большой компоненты "дострой-
ки”, обозначаемой через G. Компонента включает внешние
элементы G X, <j2[fc] 6 У, где 1 < к < m(n - 1), а
также внешние элементы вида и<[У] (или из множества
W). Множество G состоит из всех троек («<[?],<j2[fc]) и
(_,«l[j]15iM,32M)» где 1 < к < т(п - 1), 1 < i < n, 1 < j < т.
Таким образом, каждая пара д\[£],<72[Л] должна войти в
трехмерное сочетание только с одним из элементов u,[j] или
не попавших в тройки из M'\G. Имеется ровно m(n-1)
таких "непокрытых” внешних элементов, и структура компо-
ненты G обеспечивает, что они всегда могут быть покрыты
с помощью выбора соответствующего подмножества М' \ G.
Следовательно, G гарантирует, что если для некоторого под-
множества из M\G выполняются все ограничения, налагаемые
компонентами набора значений истинности, тогда это подмно-
жество может быть дополнено до трехмерного сочетания в М.
103
Резюмируя сказанное, положим:
• W = : 1 < » < n,l < j < m};
• X = A U Si U Gi, где
- А = {a,[j]: 1 < « < п, 1 < j < rn},
- Si = {Э1[>]: 1 < j < mJ,
- Gi = : 1 < j < m(n - 1)};
• Y = В U Sj U G2, где
- В = {6,[j] : 1 < i < n, 1 < j < m],
- S2 = {ъЬ] = 1 < J <
- Gj = {p2[j]: 1 < j < m(n - 1)};
• m = (ur=iT<)U(ur=iCj)uG
Заметим, что каждая тройка из М есть элемент множества
W х X х У, что и требовалось. Кроме того, поскольку множе-
ство М в терминах индивидуальной задачи из 3-ВЫП опреде-
ляется явным образом | М |= 2тп 4- 3m 4- 2man(n - 1), легко
видеть, что М может быть построено за полиномиальное вре-
мя. Из пояснений, которыми сопровождалось описание множе-
ства М, непосредственно следует, что оно не может содержать
трехмерного сочетания, если набор С невыполним.
Таким образом, осталось доказать, что существование вы-
полняющего набора значений истинности для набора дизъюнк-
ций С влечет за собой существование в М трехмерного соче-
тания.
Пусть t : U —♦ {0,1} — произвольный выполняющий набор
значений истинности для С. Построим трехмерное сочетание
М' С М следующим образом. Для каждой дизъюнкции с} G С
рассмотрим некоторый литерал 2) G : 1 < : < п} П с,,
104
принимающий значение ’’истина” при отображении t (такое Zj
должно существовать, поскольку t выполняет Cj). Затем поло-
жим М' равным
(II \ / m \
U т: U U г/ U Uff.
»(u,)=l / \t(U-i)=O / \j=l /
где G' — соответствующее подмножество множества G, вы-
бранное так, что оно содержит все giи оставшиеся
“i[j] и Нетрудно проверить, что такое множество G'
всегда можно выбрать, и что полученное в результате множе-
ство М' будет трехмерным сочетанием. □
Вместо задачи 3-С для доказательства результатов об АГР-
полноте часто пользуются следующей, более общей и более на-
глядной версией этой задачи.
Определение. Задача о точном покрытии 3-множества-
ми (ТП-3) формулируется следующим образом. Верно ли, что
заданное семейство С трехэлементных подмножеств заданного
конечного множества X такого, что | X |= 3g для некоторого
натурального д, содержит точное покрытие множества X, т.е.
такое подсемейство С С С, что каждый элемент из X содер-
жится ровно в одном элементе из С? □
Теорема 4.6. Задача о точном покрытии 3-множествами
ХГР-полна.
Доказательство. Заметим, что любую индивидуальную
задачу из 3-С можно рассматривать как индивидуальную зада-
чу из ТП-3, считая, что М состоит из неупорядоченных троек
элементов множества W U X U Y. При этом трехмерные соче-
тания для индивидуальной задачи из 3-С взаимно однозначно
соответствуют точным покрытиям соответствующей индиви-
дуальной задачи из ТП-3. Таким образом, задача 3-С есть огра-
ниченная версия задачи ТП-3, и ЛТ-полнота ТП-3 следует из
естественного сведения к ней задачи 3-С. О
105
В заключение заметим, что методы, используемые при до-
казательстве результатов об А^Р-полноте конкретных задач,
меняются почти в столь же широких пределах, как и сами
.VP-полные задачи, и поэтому здесь у нас нет возможности
проиллюстрировать их все. Однако имеется три общих метода
доказательства, которые часто встречаются и могут подска-
зать путь к доказательству АГР-полноты новой задачи, кото-
рые получили названия сужение задачи, локальная замена и
построение компоненты.
Доказательство методом сужения А/P-полноты фиксиро-
ванной задачи Q € AfV заключается просто-напросто в уста-
новлении того, что задача Q включает в качестве частного
случая известную А/Р-полную задачу Q'.
Суть состоит в том, чтобы указать дополнительные огра-
ничения, которые требуется наложить на индивидуальные за-
дачи из Q, чтобы получившаяся в результате сужения зада-
ча была бы эквивалентна Q'. При этом не требуется, чтобы
возникающая в результате сужения задача была точной ко-
пией известной А/Р-полной задачи, необходимо только, что-
бы между задачами имелось "очевидное” взаимно-однозначное
соответствие, сохраняющее ответы "да” или "нет”. Взаимно-
однозначное соответствие, которое дает сведение Q' к Q, обыч-
но настолько очевидно, что его даже не требуется указывать
явно.
Именно метод сужения использовался при доказательстве
.VP-полноты задачи о точном покрытии 3-множествами (см.
теорему 4.6).
Сводимости, возникающие при доказательстве методом ло-
кальной замены, достаточно нетривиальны, чтобы их всегда
можно было с гарантией представить в стандартном виде, од-
нако они остаются относительно несложными.
Этот метод состоит в том, что выбирается некоторое ха-
рактерное свойство известной АР*-пол ной задачи, с помощью
106
него образуется семейство основных модулей, а соответству-
ющие индивидуальные задачи заданной задачи получаются
путем единообразной замены каждого основного модуля неко-
торой другой структурой.
Сводимость задачи ВЫП к задаче выполнимости булевой
формулы в КНФ из следствия 1 к теореме 4.1 относится к
этому типу. В ней основными модулями задачи ВЫП были
дизъюнкции, и каждая дизъюнкция заменялась набором дизъ-
юнкций согласно некоторому общему правилу. Важным момен-
том здесь является то, что каждая замена приводила только к
локальному изменению структуры. Эти замены, по существу,
не зависели одна от другой, за исключением тех случаев, ко-
гда они отражали не подвергавшиеся изменению части исход-
ной индивидуальной задачи. Другой пример — это сводимость
выполнимости формул в КНФ к 3-ВЫП из теоремы 4.2.
Последний и наиболее сложный из упомянутых выше ме-
тодов доказательства .VP-полноты — это построение компо-
нент. Доказательства Л'Р-полноты задач о клике, вершинном
покрытии и трехмерном сочетании представляют собой типич-
ные его примеры.
Основная идея таких доказательств заключается в том,
чтобы с помощью составных частей рассматриваемой задачи
сконструировать некоторые "компоненты”, соединяя которые
можно "реализовать” индивидуальные задачи известной ЛФ-
полной задачи. При этом можно выделить компоненты двух
основных типов. Одни из них можно рассматривать как компо-
ненты, "делающие выбор" (например, выбирающие вершины,
ыбирающие значения истинности переменных), а другие —
как компоненты, "проверяющие свойства” (например, проверя-
ющие, что каждое ребро покрыто или что каждая дизъюнкция
выполнена).
В рассматриваемой индивидуальной задаче эти компоненты
связаны так, что выбранные значения передаются компонен-
107
там, проверяющим условия, и последние проверяют, удовле-
творяют ли сделанные выборы значений необходимым услови-
ям.
Вообще говоря, любое доказательство можно считать осно-
ванным на методе построения компонент, если конструируе-
мая в нем индивидуальная задача представляет собой набор
компонент, каждая из которых выполняет определенные функ-
ции, формулируемые в терминах исходной задачи. Общая сво-
димость, использованная при доказательстве теоремы Кука,
является хорошим примером доказательств такого типа; в нем
каждая из шести групп дизъюнкций представляет собой один
из типов компонент.
Упражнения
4.1. Постройте машины Тьюринга, допускающие языки из
примера 1.7.
4.2. Покажите, что проблема "остановится ли машина Тью-
ринга, начав работу на пустой ленте” неразрешима.
4.3. Предположим, что на ленте машины Тьюринга изобра-
жен ее собственный шифр (т.е. шифр ее функции переходов),
записанный в алфавите входных символов. Если машина при-
менима к такой конфигурации, то будем называть ее само-
применимой, в противном случае — несамоприменимой. По-
кажите, что проблема распознавания самоприменимости (т.е.
проблема определения по любому заданному шифру к какому
классу относится машина, зашифрованная им: к классу само-
применимых или несамоприменимых) является алгоритмиче-
ски неразрешимой.
4.4. Докажите, что для любого языка L G Л'Р существуют
такая ДМТ М и такой полином р(п), что L допускается на М
с временной сложность 0(2р(п)).
4.5. Задача о трехмерном сочетании (3-С) обобщает следу-
ющую известную задачу о "бракосочетании”: имеется п холо-
108
стых мужчин и п незамужних женщин, а также список всех пар
мужчин и женщин, согласных вступить в брак друг с другом;
можно ли осуществить п бракосочетаний так, чтобы каждый
получил бы приемлемого супруга (или супругу), причем никто
не должен вступать в брак дважды? Покажите, что задача о
бракосочетании содержится в классе Р.
4.6. Покажите, что задача к-КНФ для к = 1 и к = 2 принад-
лежит классу Р.
4.7. Докажите Л^Р-полноту следующих задач:
(Гамильтонов цикл). Имеет ли данный неориентированный
граф гамильтонов цикл?
(Раскрашиваемостпь). Является ли данный неориентирован-
ный граф к раскрашиваемым?
(Множество вершин, разрезающих контуры). Имеет ли
данный ориентированный граф k-элементное множество вер-
шин, разрезающих все его контуры, т.е. содержащих хотя бы
по одной вершине каждого из них?
(Разбиение) Существует ли разбиение данного конечного
множества элементов, имеющих неотрицательный вес, на два
подмножества, равных по суммарному весу составляющих их
элементов
(Изоморфизм неориентированному подграфу). Содержит
ли данный неориентированный граф G подграф, изоморфный
данному н< ориентированному графу Я?
(Остовное дерево ограниченной степени). Существует ли в
данному неориентированном графе остовное дерево, в котором
все вершины имеют степень не более к?
(Минимальный эквивалентный по достижимости ориен-
тированный граф). Можно ли удалить из данного ориентиро-
ванного графа часть дуг так, чтобы отношение достижимости
между вершинами не изменилось, но результирующий граф
содержал бы не более к дуг
109
(Самый длинный путь). Имеется ли в данном неориентиро-
ванном графе путь длины не меньшей к?
(Доминирующее множество). Существует ли в данном не-
ориентированном графе доминирующее множество, состоящее
из не более к вершин?
(Расщепление множества). Существует ли разбиение дан-
ного конечного множества А на два таких, что ни одно из них
не содержит ни одного из элементов заданного семейства под-
множеств А?
4.8. Покажите, что ЛгР-полны задачи распознавания следу-
ющих свойств регулярных выражений:
(а) регулярное выражение без *, т.е. не содержащее звездо-
чек, обозначает не все цепочки длины к (в исходном алфавите);
(б) два регулярных выражения без * обозначают разные
языки;
(в) регулярное выражение над алфавитом {0} не обозначает
язык 0*.
4.9. Докажите, что задача пустоты дополнения для расши-
ренных регулярных выражений не принадлежит классу .VP.
Расширенное регулярное выражение над алфавитом Е опре-
деляется следующим образом:
1) е,0 и а из Е являются расширенными регулярными выра-
жениями, представляющими соответственно {е}, пустое мно-
жество и а.
2) Если Ei и Е2 — расширенные регулярные выражения,
представляющие соответственно языки Li и Z2, то (Е\ +
E2),(Ei • E2),(Ei),(Ei П Е2) и (Ei) — тоже расширенные ре-
гулярные выражения, представляющие соответственно языки
L\ U L\L2i L*i, L\ Г) L2 и Е \ 1ц.
Проблема для исследования:
4.10. Выяснить, какое из соотношений имеет место:
ЛФ \ V / 0 или ЛГР = Р 1
110
Библиографический список
1. Евстигнеев В.А., Касьянов В.Н. Введение в дискретную
математику, Ч. 1,2 и 3. Новосибирск: НГУ, 1994.
2. Евстигнеев В.А., Касьянов В.Н. Толковый словарь по те-
ории графов, Ч. 1. Новосибирск: НГУ, 1995.
3. Лекции по теории графов/ Емеличев В.А., Мельников
О.И. и др. М.: Наука, 1990.
4. Успенский В.А., Семенов А.Л. Теория алгоритмов: основ-
ные открытия и приложения. М.: Наука, 1987.
5. Ахо А., Ульман Дж. Теория синтаксического анализа, пе-
ревода и компиляции, Том 1. — М.: Мир, 1978.
6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ
вычислительных алгоритмов. М.: Мир, 1979.
7. Гэри М., Джонсон Д. Вычислительные машины и труд-
норешаемые задачи. М.: Мир, 1982.
8. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгорит-
мы обработки деревьев. Новосибирск: Наука, 1994.
9. Кук Д., Бейз Г. Компьютерная математика. М.: Наука,
1990.
10. Липский В. Комбинаторика для программистов. М.: Мир,
1988.
111
Оглавление
Предисловие 3
Введение 5
1. Цепочки, языки и грамматики 9
1.1. Множества цепочек 9
1.2. Грамматики составляющих 11
1.3. Грамматики с ограничениями на правила 18
Упражнения 23
2. Регулярные множества,
их распознавание и порождение 25
2.1. Регулярные множества
и регулярные выражения 25
2.2. Конечные автоматы 28
2.3. Свойства регулярных множеств 36
Упражнения 40
3. Контекстно-свободные языки
и магазинные автоматы 44
3.1. Деревья выводов и однозначность грамматик 44
3.2. Преобразование КС-грамматик 47
3.3. Автоматы с магазинной памятью 59
3.4. Свойства класса КС-языков 65
Упражнения 70
4. Сложность алгоритмов и языков 73
4.1. Машины Тьюринга 73
4.2. Классы Р и ЛР 78
4.3. Полиномиальная сводимость и ЛГР-полнота 84
4.4. Методы доказательства ЛГР-полноты 95
Упражнения 108
Библиографический список 111
112