AUTOMATEN THEORIE Eine Einfuhrung in die Theorie endlicherAutomaten Von Dr. rer. nat.Wilfried Brauer Professor an der Universitat Hamburg B. G. Teubner Stuttgart 1984 В.Брауэр ВВЕДЕНИЕ В ТЕОРИЮ КОНЕЧНЫХ АВТОМАТОВ Перевод с немецкого К. В. Рудакова под редакцией чл.-корр. АН СССР Ю. И. Журавлева Москва «Радио и связь» 1987 ББК 32.815 Б 87 УДК 007.52 Брауэр В. Б87 Введение в теорию конечных автоматов: Пер. с нем.—М.: Радио и связь, 1987.—392 с.: ил. В книге профессора Гамбургского университета описаны основные клас- сические модели теории конечных автоматов (автоматы Мили и Мура) и бо- лее сложные модели (автоматы Рабина — Скотта, многоленточные автоматы, конечные преобразователи). Рассмотрены преобразования конечных автоматов и регулярные множества. Существенную часть книги составляют упраж- нения, Для инженерно-технических работников, связанных с приложениями теории конечных автоматов, а также работающих в области информатики и вычислительной техники. Б 1502000000-123 046(01)-87 53-87 ББК 32.815 Редакция переводной литературы Производственное издание ВИЛЬФРИД БРАУЭР ВВЕДЕНИЕ В ТЕОРИЮ КОНЕЧНЫХ АВТОМАТОВ Заведующая редакцией О. В. Толкачева. Редактор С. Т. Симонова Переплет художника Н. А. П а ш у р о. Художественный редактор Т. В. Б у- с а ров а. Технические редакторы Г. И. Колосова, Т. Н. Зыкина. Корректор Л. А. Буданцева ИБ № 1401 Сдано в набор 5.08.86 Подписано в печать 16.02.87 Формат 60 X 90'/,, Бумага тип. № 2 Гарнитура литературная Печать высокая Усл. печ. л. 24,5 Усл. кр.-отт. 24,5 Уч.-изд. л. 27,23 Тираж 10000 экз. Изд. № 21635 Зак. № 5260 Цена 2 р. 10 к. Издательство «Радио и связь», 101000 Москва. Почтамт, а/я 693 Ордена Октябрьской Революции и ордена Трудового Красного Знамени МПО «Первая Образцовая типография имени А. А. Жданова» Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 113054, Москва, Валовая, 28. © В. G. Teubner, Stuttgart 1984 Перевод на русский язык, примечания переводчика, издательство «Радио и- связь», 1987 ПРЕДИСЛОВИЕ Конечные автоматы и такие тесно связанные с ними конструк- ции, как, например, линейные грамматики и регулярные выраже- ния, относятся к важнейшим основным понятиям информатики. Различные варианты конечных автоматов и близкие им матема- тические объекты служат для описания и анализа технических уст- ройств, различных систем и процессов, программ и алгоритмов. Многие сложные концепции теоретической информатики — и при- том относящиеся не только к более общим моделям автоматов, таким как автоматы с магазинной памятью и машины Тьюрин- га,—были выработаны на базе теории конечных автоматов. Тео- рия автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем. Они приводят к весьма сложным алго- ритмам и отчасти проясняют причины, по которым необходимо систематическое развитие математического программирования и теории алгоритмов, сопровождаемое подробным анализом коррект- ности и сложности. Теория конечных автоматов имеет многочис- ленные приложения в технической и практической информатике и составляет существенную часть теоретической информатики. Это делает знание основ теории автоматов необходимым каждому спе- циалисту по информатике. Данная книга дает начальные представления о важнейших классических основных моделях, концепциях, методах и резуль- татах теории конечных автоматов. Поскольку теория автоматов является одним из старейших раз- делов теоретической информатики, широко развитым во многих направлениях, возможны целый ряд подходов и изложение разных аспектов этой теории различными методами и с различными целя- ми. В данной книге избран «средний путь» между чисто матема- тическим и направленным только на .приложения подходами. Мы будем рассматривать конечные автоматы как абстрактные модели простейших устройств, обрабатывающих данные, обращая в основном внимание на входно-выходное поведение, т. е. на оп- ределяемое автоматом отображение или соответствие между вход- ным и выходным множествами слов. При этом особое значение будет придаваться конструктивным и алгоритмическим аспектам проблемы. Способ изложения ориентирован прежде всего на теорию фор- мальных языков, однако не предполагается, что у читателя име- ются какие-либо специальные познания в этой области. Кроме 5 того, от читателя не требуются особые познания в математике или в других разделах информатики, выходящие за пределы материа- ла, который изучается на первом курсе студентами, специализиру- ющимися в области информатики '. Используемые в книге математические понятия, обозначения и методы кратко описаны в гл. 1. Некоторые простые и обычные по- нятия, кроме того, поясняются в том месте текста, где они упот- ребляются впервые, так что после введения к гл. 1 можно пере- ходить к чтению гл. 2 и только при необходимости использовать гл. 1 для справок. Каждая из гл. 2—8 относительно независима: в гл. 2—5 и 8 рассматриваются основные модели автоматов, в гл. б изучается некоторая специальная конструкция и в гл. 7 представлен иной подход к проблеме. Все эти главы начинаются одним или несколь- кими вводными примерами и завершаются наборами упражнений и разделами, содержащими обзор литературы к данной главе. Список литературы дан в конце книги. Вводные и ряд других при- меров в тексте взяты из различных разделов информатики. Они должны, с одной стороны, мотивировать введение абстрактных по- нятий и конструкций и, с другой стороны, демонстрировать воз- можности их применения. Все теоремы, леммы и следствия (за исключением теорем о соответствиях Поста и о полноте системы аксиом для рациональ- ных равенств) сопровождаются полными доказательствами. Эти доказательства по мере возможности конструктивны и неформаль- ны (скажем, в доказательствах не используются методы формаль- ной логики). 'В книге принята простая система терминов, которую автор пы- тался составить так, чтобы разумно сочетать как ставшие уже историей, так и современные точки зрения. Данная терминология возникла в результате рассмотрения различных и, отметим, часто противоречивых систем понятий, встречающихся в литературе. В некоторых случаях в обзорах литературы после соответствующих глав содержатся комментарии по этому поводу. Эти обзоры вклю- чены в книгу прежде всего для указания авторов излагаемых идей и результатов и, кроме того, в них цитируются некоторые дополни- тельные работы и многие учебники. В тексте книги специальных ссылок на литературу нет. Многочисленные задания предназначены для упражнений и более глубокого изучения материала, а также и для дополнения основного содержания книги (особенно трудные задания помечены звездочкой). Они являются важнейшей составной частью книги и должны быть внимательно прочтены и обдуманы читателем, даже если их и не удается выполнить полностью. ' Все же для понимания некоторых конструкций желательно знакомство читателя с проблематикой вычислимости, см., например, книги Роджерс X. Тео- рия рекурсивных функций и эффективная вычислимость: Пер. с англ.—М.: Мир, 1972.—624 с. и Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ.—М.: Мир, 1983.—256 с.—Прим. перев. В соответствии с принятой в книге точкой зрения, в ней не представлены многие разделы теории автоматов. В частности, не рассматриваются вопросы, связанные с технической реализацией конечных автоматов (такие, как теория контактных схем и пере- ключательных схем с памятью, теория разложения автоматов, теория линейных автоматов и т. д.). Также не изучается широкий круг сложных проблем, относящихся к теории формальных языков и теории сложности (например, не рассматриваются более общие модели автоматов такие, как машины Тьюринга, автоматы с мага- зинной памятью, пакетные автоматы, древовидные автоматы). Наконец, в книге не представлены сложные, преимущественно чисто математические теории (такие, как алгебраическая теория решеток, теории стохастических и топологических автоматов, тео- рия рациональных степенных рядов, алгебраическая теория коди- рования и т. д.). Я выражаю глубокую благодарность 'проф. Г. Хольцу и д-ру П. Шпулеру за их предложение написать эту книгу и за прояв- ленное ими при этом терпение. Доктор К. и. Ланге основательно проработал многие варианты рукописи, сделав при этом ряд цен- ных предложений и внеся ряд поправок. Специалист по информа- тике К. Буттлер крайне тщательно прочитал окончательную ре- дакцию текста и сделал при этом несколько предложений для дальнейшего его улучшения. Кроме того, он составил списки тер- минов и обозначений. Двум последним я особенно признателен. Я также благодарен всем, с кем работал, в том числе и ряду сту- дентов, за стимулирующие обсуждения и критику. За выдержку и аккуратность, проявленные при подготовке рукописи, я крайне признателен моей секретарше А. Цильц. Но более всего я благода- рен моей жене за ее сотрудничество и помощь. То, что она дала мне целый ряд советов в отношении дидактики, методики и сти- листики, выполнила рисунки, отпечатала многие варианты руко- писи и прочитала корректуру, является лишь малой частью ее вклада. Я смог работать над этой книгой, не ограничивая препо- давательской и научной деятельности, только благодаря тому, что моя жена взяла на себя многие из моих разнообразных обязанно- стей и освободила меня от многих нагрузок. И при этом она с по- ниманием относилась к тому, что я и без того небольшое свобод- ное время посвящал в основном этой рукописи. Без дружеской по- мощи эта книга не была бы написана. В. Брауэр ГЛАВА 1. ОСНОВНЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ ВВЕДЕНИЕ Рассматриваемые в книге модели автоматов явля- ются абстрактными описаниями технических устройств, социально- экономических, биологических и других динамических систем или описаниями программ, алгоритмов и вычислительных процессов. В основе таких моделей лежит предположение о том, что эти «ав- томаты» работают дискретным образом: находятся перед и после каждого шага в совершенно определенном состоянии и за каждый шаг воспринимают некий «вход» или порождают некий «выход». Предполагается также, что каждый автомат может иметь только одно из конечного множества состояний и что его входы и выходы могут быть описаны символами из некоторого конечного алфавита. То, что происходит с автоматом за отдельный шаг, будет описы- ваться с помощью отображений или соответствий. Таким образом, нам понадобятся сведения с множествах, отоб- ражениях, соответствиях (многозначных отображениях), отноше- ниях и графах. Эти сведения не выходят за пределы материала, изучаемого на 'первом курсе и даже в средней школе. Они содер- жатся в разд. 1.1—1.3. При изучении конечного автомата интересны не только его по- ведение за отдельный шаг, обработка конкретного входа и порож- дение конкретного выхода, но и поведение на протяжении длитель- ных промежутков времени. Для формального описания такого по- ведения нам будут нужны сведения о конечных последовательно- стях отображений конечного множества в себя. Это означает, что нам понадобятся понятия полугруппы и моноида, приведенные в разд. 1.4 (определения этих понятий не будут повторяться в пос- ледующих главах). Поскольку у читателя не 'предполагается наличие особых ма- тематических знаний и навыков, в разд. 1.5 дается обзор основных необходимых для дальнейшего изложения методов доказательств. Утверждения, приведенные в разд. 1.1—1.5 без доказательств, могут быть проверены читателем на базе вводимых определений посредством простых выкладок. Во многих же случаях даются наб- рсски доказательств или указания. Формальная логика в книге непосредственно использоваться не будет, логические связки и кванторы будут записываться сло- вами. В то же время предполагается, что читатель имеет пред- ставление об алгоритмах и проблематике вычислимости и разре- шимости. Поэтому такие понятия, как эффективная конструкция, эффективная вычислимость и т. п., будут использоваться без даль- нейших пояснений. Скажем только, что мы считаем некоторую проблему разрешимой (неразрешимой), если существует (не су- ществует) решающий ее алгоритм. Пример неразрешимой пробле- мы в первый раз появится в гл. 8, а неэффективная конструкция будет описана в гл. 5 (теорема 5.5.7). Для понимания некоторых примеров и соответствующих мето- дов желательно, чтобы читатель имел определенные познания в области практического программирования и в теории языков прог- раммирования. Следует также иметь в виду, что для некоторых сложных алгоритмов необходимы доказательства корректности и оценки времени работы и объема памяти. 1.1. МНОЖЕСТВА Далее понадобятся только представления наив- ной теории множеств в смысле Г. Кантора: «Под множеством мы понимаем собрание определенных отличных друг от друга объектод (реальных или воображаемых), называемых элементами множест- ва, в их общности». Поскольку мы начинаем с конечных множеств и формируем бесконечные множества на базе конечных с исполь- зованием вполне определенных операций, нам не приходится опа- саться 'появления возможных в наивной теории множеств антино- мий. При желании можно считать, что все рассматриваемые мно- жества являются подмножествами некоторого универсума, за пре- делы которого не выводят все используемые операции. _ ТЕОРЕТИКО-МНОЖЕСТВЕННЫЕ ОБОЗНАЧЕНИЯ Будем обозначать множества прописными латинскими буквами типа М, AV, Mi, множества множеств — прописными рукописными буквами типа Л, 31, а элементы множеств—строчными латински' ми буквами типа m, m' mi. теМ означает высказывание «m является элементом множе- ства М»; в этом случае мы также говорим «m принадлежит мно- жеству М »или« из М» и т. п. т^М означает отрицание высказывания msM, т. е. высказы- вание «m не принадлежит М». Mi?M2 означает высказывание «каждый элемент множества Mi является также элементом множества Ма», в этом случае мы также пишем «M[ является подмножеством множества Мд» или «имеет место включение MiSMa». Mi=Mz означает высказывание «Mi^Ma и M2=Mi», в этом случае мы также говорим «множества Mi и М2 равны». ' : ~ Mi^Ma является отрицанием высказывания Mi==M2. MicM.? эквивалентно высказыванию «MicM2 и Mi^M's», a этом случае мы также говорим «Mi является собственным, подмно- жеством множества М.2». 22 Мили Мура частичных автоматов Мили — — однозначности минимального PC-автомата 248 — — периодичности 62 — — разложении отображений сокращении автоматов сокращении автоматов 41 77 136 — Полла, Унгера 150 — Рабина — Скотта (о НРС- и PC- автоматах) 195 — — — (об экспоненциальном авто- мате) 241 — Саломаа—Урпонена 219 — Уоляспера 361 — Урпонена 221 — Хаффмана — Мили 39 — Хиббарда 110 — Хомского — Шютценбергера 285 — Чена 60 — Шютценбергера 303 — Эйленберга — Элго — Шефердсо- на 336 — Элго — Мезея — Розенберга 333 У-автомат 360 У-отображение 362 Фактормножество 22 Фундаментальное свойство автома- тов Мили 70 Функция (отображение) 15 — последовательностная словарная 67 — характеристическая 17 Характер состояния автомата Мили 68 Частичная реакция (U-реакция) 127 Частное (правое, левое) множество 196 Эквивалентность (отношение эквива- лентности) 20 — автоматов Мили 38 — локальная 243 — множеств состояний 243 — НРС-автоматов 194 — рациональных выражений 216 — состояний автоматов Мили 38 — 2-ЭМ-автоматов 328 — а-преобразователей 322 Эксперименты с автоматами 97 Элемент минимальный 21 — наименьший 21 Эпиморфизм 26, 85 Ядро префиксное 287 Язык асинхронный 227 0-доопределение 135 2-РС-автомат 352 2-ЭМ-автомат 328 — алфавитный 341 — детерминированный 339 — — полностью определенный 346 — локально детерминированный 339 — с маркерами 369 — с программой чтения 369 2-ЭЭШ-автомат 336 а-преобразователь 314 — алфавитный 315 — Л-свободный 315 k-префикс 300 k-суффикс 62 L-эквивалентность 128 LW-последовательность 209 U-изоморфизм 133 U-реакция состояния частичного ав- томата Мили 127 — частичного автомата Мили 133 U-эквивалентность 128 U-эпиморфизм 133 uv w-теорема 192 V-эквивалентность 128 Z-гомоморфизм 85 ZXY-гомоморфизм 85 ОГЛАВЛЕНИЕ Предисловие ................. 5 Глава 1. Основные математические пэнятия ........ 8 Введение .................. ^ 1.1. Множества ................. 9 1.2. Соответствия и отображения ............ I4 1.3. Отношения и графы .............. IS 1.4. Моноиды и гомоморфизмы ............ 23 1.5. Методы доказательств .............. 29 Глава 2. Автоматы Мили ............. 33 2.1. Вводный пример ............... 33 2.2. Определение, пример и контрпример .......... 36 2.3. Реакция, эквивалентность,, сокращение ......... 37 2.4. О способе определения эквивалентности состояний ...... 41 2.5. Метод Хопкрофта — Гриса ............ 45 2.6. Различимость входных последовательностей ....... 58 2.7. Автоматы Мили с конечной памятью ......... 64 Упражнения ................ 67 Обзор литературы ............... 70 Глава 3. Автоматы Мура ............. 71 3.1. Вводный пример ............... 3.2. Определение и первое сравнение с автоматами Мили ..... 74 3.3. Реакция, эквивалентность, сокращение ......... 77 3.4. Равносильность автоматов Мили и Мура ..... . . 79 3.5. Дальнейшие примеры .............. 82 3.6. Гомоморфизмы и изоморфизмы ........... 85 3.7. Аппроксимация отображений ........... 89 3.8. Эксперименты ................ 96 3.9. Однократные автономные диагностические эксперименты с дополни- тельной информацией . ............ 101 Упражнения ................ II9 Обзор литературы ............... 117 Глава 4. Частичные автоматы Мили . . ........ 1)8 4.1. Вводные примеры ............... 118 4.2. Определение, различные понятия реакции и эквивалентности, совме- стность . . . .............. 12.1'' 4.3. Доопределение и сокращение ............ 132 4.4. Покрытие и минимизация ............. 137 4.5. Алгебраическая постановка проблемы минимизации . . . . . 145 Упражнения ................ 153 Обзор литературы . . ............ 157 Глава 5. Автоматы Рабина—Скотта . ......... 158 5.1. Вводные примеры ............... 158 5.2. Недетерминированные автоматы Рабина — Скотта (НРС-автоматы) 168 5.3. Реакция, допустимые множества .......... 175 391 5.4. Детерминированные автоматы и различимые множества .... 185 5.5. Эквивалентность различных понятий .......... 194 5.6. Равенства и системы равенств . .......... 201 5.7. Рациональные выражения . . .......... 212 Упражнения ................ 224 Обзор литературы ............... 231 Глава 6. Преобразования автоматов .......... 232 6.1. Вводные примеры ............... 233 6.2. Преобразование НРС-автомата в PC-автомат ....... 237 6.3. Минимизация детерминированных автоматов . ...... 243 6.4. Проблема минимизации для НРС-автоматов ....... 251 6.5. Методы уменьшения числа состояний ......... 257 6.6. Частные и производные . . ........... 261 Упражнения ................ 268 Обзор литературы ............... 274 Глава 7. Дальнейшие характеризации допустимых множеств .... 274 7.1. Последовательности вычислений программ, схемы Янова .... 275 7.2. Графы Майхплла ............... 279 7.3. Стандартные множества . . ........... 285 7.4. Двусторонние автоматы . . . .......... 289 7.5. Автоматы с предварительным просмотром ........ 297 7.6. Матричные представления ............. 302 7.7. НРС-автоматы с одноэлементным входным алфавитом ..... 304 Упражнения ................ 306 Обзор литературы ............... 310 Глава 8. Преобразователи и двуленточные автоматы . . . . . . 310 8.1. Ретроспекция . . .............. 310 8.2. а-преобразователи ............... 313 8.3. Неразрешимость проблемы эквивалентности a-иреооразователей . . 322 8.4. Двуленточные автоматы Элго—Мезея ......... 328 8.5. Двуленточные автоматы Элго—Эйленберга—Шефердсона . . . 335 8.6. Детерминированные двуленточные автоматы . ...... 339 8.7. Двуленточные автоматы Рабина—Скотта . ....... 351 8.8. Обобщения ................ 358 Упражнения . ............... 364 Обзор литературы ............... 371 Список литературы .............. 373 Список работ советских авторов и работ, переведенных на русский язык .................. 386 Предметный указатель . . ........... 387