«А. П. Замятин, А. М. Шур ЯЗЫКИ, ГРАММАТИКИ, РАСПОЗНАВАТЕЛИ Рекомендовано УМС по математике и механике УМО по классическому университетскому образованию РФ в качестве учебного пособия для студентов высших учебных ...»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. А. М. ГОРЬКОГО

А. П. Замятин, А. М. Шур

ЯЗЫКИ,

ГРАММАТИКИ,

РАСПОЗНАВАТЕЛИ

Рекомендовано УМС по математике и механике

УМО по классическому университетскому образованию РФ

в качестве учебного пособия для студентов

высших учебных заведений, обучающихся по группе математических направлений и специальностей Екатеринбург Издательство Уральского университета 2007 УДК 519.68+519.713+519.766.2 З269 Р е ц е н з е н т ы:

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

М. Ю. Х а ч а й, доктор физико-математических наук (Институт математики и механики УрО РАН) Замятин А. П., Шур А. М.

З269 Языки, грамматики, распознаватели : Учебное пособие. – Екатеринбург : Изд-во Урал. ун-та, 2007. – 248 с.

ISBN 5-7996-0273- В пособии систематически изложены ряд важных разделов теории формальных языков и приложения этой теории к построению компиляторов. Пособие рассчитано на математически ориентированных читателей.

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

УДК 519.68+519.713+519.766. c Замятин А. П., Шур А. М., ISBN 5-7996-0273-0 c Уральский государственный университет, Введение О чем эта книга?

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

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

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

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

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

Что такое компилятор?

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

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

';

Первый компилятор был написан Грейс Хоппер в 1952 году для языка программирования А-0. Компилятор, по структуре похожий Введение на современный, впервые был построен группой Джона Бэкуса в 1957 году (для компании IBM и языка FORTRAN). В 1960–1970-е годы произошел качественный скачок теории формальных языков, который привел к появлению новых, более мощных методов компиляции и позволил конструировать языки с гораздо более сложным синтаксисом.

Процесс обработки исходного текста компилятором состоит из тех же двух стадий, что и работа переводчика, – стадий анализа и реализации. В английском языке для них используются термины front end и back end соответственно. На стадии анализа производится проверка исходного текста ( программы ) на корректность, т. е.

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

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

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

В предлагаемой книге рассматривается только стадия анализа.

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

Языки, грамматики, распознаватели – немного истории Основные математические объекты и связи между ними, рассматриваемые в этой книге, укладываются в простую схему, приведенную на рис. 0.1.

Алгебраические Формальные Рис.0.1. Математические объекты и связи в этой книге Едва ли возможно определить, в работах каких математиков впервые изучались слова – конечные последовательности элементов фиксированного множества и формальные языки, т. е. множества слов. Пожалуй, первым ученым, систематически исследовавшим данную тематику, был норвежский математик Аксель Туэ (1863–1922). Бурное развитие теории формальных языков началось в 1950-е годы, во многом благодаря начавшейся компьютерной эре.

В этой книге мы осветим лишь малую часть данной теории, в чем несложно убедиться, например, обратившись к оглавлению трехтомного справочника [Hand].

Грамматическая модель описания естественных языков была впервые предложена американским лингвистом и психологом Ноамом Хомским (р. 1928) в середине 1950-х годов. Так, Хомский ввел понятия контекстно-свободной грамматики и контекстноВведение свободного языка, которые в дальнейшем сыграли ключевую роль в описании синтаксиса уже искусственных языков. В 1963 году в соавторстве с французским математиком Марселем Шютценберже (1920–1996) Хомский описал иерархию классов грамматик и соответствующих им классов формальных языков.

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

Исторически первую модель распознавателя формальных языков предложил в 1936 году английский математик Алан Тьюринг (1912–1954). Машина Тьюринга могла не только распознавать строки символов, но и преобразовывать одни строки в другие. На ее основе Тьюринг спроектировал один из первых в мире компьютеров.

Кстати, термин компьютер в его современном значении впервые употребил именно Тьюринг.

Что касается распознавателей, изучаемых в данной книге, то понятие конечного автомата ввел американский логик и математик Стефен Клини (1909–1994). Понятие МП-автомата в явном виде впервые сформулировал Хомский в 1962 году, хотя устройства с лентой памяти, доступ к которой организован по принципу стека, были независимо описаны разными авторами еще в середине 1950-х годов.

Математические результаты, приведенные в этой книге, получены в 1950–1970-х годах. С тех пор они переместились с переднего края науки в лекционные аудитории и университетские учебники.

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

О других учебниках Математического учебника, компактно и адекватно отображающего весь имеющийся в данной книге материал, просто нет, иначе у авторов не было бы необходимости писать данную книгу. Достаточно сложна для чтения и немного путает читателя устаревшими обозначениями безусловно ценная книга [Ги]. Ярко написанная книга [Сал] представляет лишь часть необходимого материала, к тому же она давно стала библиографической редкостью. Трехтомный [Hand] – прекрасный справочник, но в нем отсутствует большинство доказательств. Хорошо написан, но пока практически недоступен учебник по теории автоматов [Sak]. Авторы рекомендуют ознакомиться с отличным курсом лекций по автоматам и языкам [Kar] (на английском языке). В частности, в нем можно найти доказательства практически всех утверждений первых трех глав книги. Естественно, как и большинство курсов лекций, он доступен только в электронном виде.

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

Более раннее детище Ахо и Ульмана – двухтомник [АУ1], [АУ2] – занимает промежуточное положение между учебником по теории формальных языков и учебником по компиляторам. В частности, из него можно почерпнуть доказательства основных результатов, относящихся к методам синтаксического анализа.

Два недавно вышедших учебника [Ка] и [ОС] ориентированы на студентов технических вузов. Они содержат изложение основных методов анализа с содержательными примерами, но доказательства в них полностью отсутствуют.

Немного особняком стоит учебник [CT], не имеющий русского перевода. В нем очень подробно и хорошо описан back end современного компилятора, чего нет, пожалуй, ни в одном другом учебнике.

И наконец, еще одна рекомендация читателям: поищите на сайте какого-нибудь известного западного университета материалы к читаемым курсам. Немного усилий – и вы станете обладателем комплекта иллюстрирующего материала (например, PowerPoint-презентаций) курса Compiler design. Изучение этого комплекта принесет вам несомненную пользу.

Введение Структура книги и особенности изложения Учебник состоит из трех частей, разбитых на 11 глав, и содержит в общей сложности 57 параграфов. Нумерация математических утверждений, алгоритмов, примеров, таблиц, рисунков и формул внутри каждой части своя, перед номером ставится только номер главы. Все основные алгоритмы записаны при помощи псевдокода.

Чтобы улучшить читаемость формул (в которых обычно присутствуют объекты разной природы), авторы приняли решение использовать внутри формул наряду с обычным математическим шрифтом еще два:

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

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

Краткое содержание этой части прекрасно иллюстрируется при помощи рис. 0.1.

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

В третьей части рассмотрены вопросы семантического анализа:

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

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

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

Авторы благодарят Ю. В. Гамзову и В. Ю. Попова за многочисленные ценные замечания, высказанные при обсуждении материала книги. Огромное спасибо Юхани Карюмяки за любезно предоставленную возможность пользоваться записями его лекций по курсу Языки и автоматы при подготовке книги. Отдельная благодарность всем студентам, которые своими вопросами на лекциях и ответами на экзаменах помогли авторам понять, что и как следует писать в этой книге.

Часть 1.

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

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

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

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

Рассмотрим примеры.

В качестве первого примера возьмем язык логики высказываний.

Выражением (фразой) этого языка будет формула логики высказываний, например, F = X1 &X2 &X3 X4. Смысл (значение) этой фразы определяется интерпретацией – функцией, которая атомарным формулам, входящим в данную формулу (в данном случае выражениям X1, X2, X3 и X4 ), сопоставляет некоторые высказывания.

Применив к этим высказываниям имеющиеся в формуле логические операции, получим высказывание, являющееся значением всей формулы. Возьмем интерпретацию, которая атомарным формулам X1, X2, X3 и X4 ставит в соответствие высказывания X1 : функция f (x) непрерывна на отрезке [a, b], X2 : функция f (x) дифференцируема на интервале (a, b), X3 : функция f (x) в точках a и b принимает равные значения, X4 : существует точка c из интервала (a, b) такая, что f (c) = 0.

Тогда значением формулы F будет высказывание, известное в математическом анализе как теорема Ролля.

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

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

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

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

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

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

Определение. Алфавитом называется непустое конечное множеЧасть 1. Языки и способы их задания ство. Цепочкой (или словом, или строкой) над алфавитом называется конечная последовательность элементов. Такие последовательности принято записывать без запятой.

Например, если = {a, b}, то abba, aab, a – цепочки над.

Длина цепочки w – это количество символов в ней, обозначаемое через |w|. Пустую цепочку – цепочку нулевой длины – обозначим через. Множество всех цепочек над обозначается через, а множество всех непустых цепочек над – через +.

Мы готовы ввести основное определение параграфа.

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

Таким образом, язык – это множество цепочек. Данное определение отражает только план выражения языка и в общем соответствует содержанию книги: в основном здесь изучаются синтаксические понятия, относящиеся к языку. Семантика языка будет рассматриваться в ограниченном виде.

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

Начнем с языка цепочек сбалансированных скобок (или короче – скобочного языка) LB. Алфавит языка состоит из двух символов [ и ].

Разумеется, понятно, какие цепочки принадлежат языку LB, а какие не принадлежат. Например, цепочки [ ], [ ] [ ], [ [ ] ] принадлежат LB, а цепочки [ ] ] [, [ ] ] не принадлежат этому языку. Тем не менее нам понадобится строгое определение сбалансированной цепочки скобок.

Наиболее удобен рекурсивный вариант определения.

Определение. 1. Пустая цепочка является сбалансированной.

2. Если цепочки скобок u и v сбалансированы, то цепочки [u] и uv также сбалансированы.

3. Других сбалансированных цепочек скобок нет.

В качестве второго примера рассмотрим язык списков, который будем обозначать через LL. Алфавитом этого языка будет множество { a, ;, [, ] }. Определимся с тем, что мы будем понимать под списком.

Определение. 1. Цепочка a является списком.

2. Если цепочки u и v – списки, то цепочки [u] и u; v также являются списками.

3. Других списков нет.

Глава 1. Языки и операции над ними Из определения видно, что цепочки [a]; a, [a; a], [ [a] ] являются списками, т. е. принадлежат языку LL, а цепочки [ ], [a] не являются.

Третьим в этом списке примеров рассмотрим язык описаний типов LD. Это язык над алфавитом { i, :, ;, real, int }. Цепочки этого языка будут иметь следующий вид: вначале идет (непустой) список букв i, разделенных точкой с запятой, затем двоеточие и заканчивает цепочку один из символов real или int. Примеры описаний:

i; i; i : real, i : int. Разумеется, язык LD лишь приблизительно отражает грамматические конструкции, используемые при описаниях типов в реальных языках программирования. Тем не менее он полезен для учебных примеров.

В качестве четвертого примера возьмем язык двоичных чисел LN.

Алфавит состоит из 0, 1 и десятичной точки. Цепочки языка LN имеют вид u, u.v или.v, где u и v – произвольные последовательности нулей и единиц. Заметим, что в языке LN есть цепочки, целая часть которых начинается нулем, а также цепочки, дробная часть которых нулем заканчивается. Если дополнительно потребовать, чтобы целая часть начиналась единицей, а дробная единицей заканчивалась, то получится язык, который мы будем обозначать через LN.

Список примеров языков завершим рассмотрением языка арифметических выражений LA. Этот язык будет содержать арифметические выражения, построенные из символа x, который символизирует переменную или константу, знаков операций + и с обычным приоритетом и скобок. Нам понадобится строгое Определение. 1. Цепочка x – арифметическое выражение.

2. Если цепочки u и v – арифметические выражения, то цепочки u + v, u v, (u) также являются арифметическими выражениями.

3. Других арифметических выражений нет.

Приведем примеры цепочек из языка LA: x + x x, (x + x) x, (x).

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

Определение. Пусть w – цепочка над некоторым алфавитом. Если w = uv для некоторых (возможно, пустых) цепочек u и v, то u называется префиксом w, а v – суффиксом w. Префикс (суффикс) цепочки w называется собственным, если он отличен от w и.

Например, если w = abc, то цепочки abc, ab, a, – префиксы цепочки w, а цепочки abc, bc, c, – ее суффиксы. Подчеркнем, что w и являются как префиксами, так и суффиксами цепочки w.

§ 2. Операции над языками В этом параграфе мы введем основные операции над языками, необходимые в дальнейшем.

Пусть K, L и M – языки над алфавитом. Отметим прежде всего, что будем использовать обычные теоретико-множественные операции: пересечение, объединение, дополнение и разность. Напомним, что Определение. Произведением языков K и L называется язык Например, для языков K = {ab, abc} и L = {cba, ba} получим KL = {abcba, abba, abccba}. Пример, в частности, показывает, что операция умножения некоммутативна. С другой стороны, легко проверить, что эта операция ассоциативна, а язык {} является нейтральным элементом. Таким образом, можно говорить о степени языка и положить дополнительно L0 = {}.

Определение. Итерацией языка L называется язык L = Li.

Например, если L = {a, ab}, то L = {, a, ab, a2, a2 b, aba, abab, Свойства теоретико-множественных операций для языков совпадают со свойствами этих операций для произвольных множеств, поэтому здесь не приводятся. Отметим ряд свойств, в которых участвуют произведение и итерация. Условимся, что приоритет умножения выше приоритета всех теоретико-множественных операций, приоритет итерации выше, чем приоритет умножения.

Пусть K, L и M – языки над одним и тем же алфавитом. Тогда справедливы следующие утверждения:

Глава 1. Языки и операции над ними Докажем, например, второе утверждение. Пусть x K(LM ). Тогда следует, что uv KL и uv KM. Следовательно, x KL KM.

Мы доказали, что K(L M ) KL KM. Обратное включение неверно. Возьмем, например, K = {, b}, L = {ab}, M = {bab}. Тогда Введем еще одну операцию над языками, которую будем называть подстановкой. Пусть = {a1,..., an } и – два алфавита, – отображение, которое каждому элементу b ставит в соответствие язык над, т. е. (b). Рассмотрим два расширения отображения. Сначала расширим это отображение на, положив (b1 b2...bk ) = (b1 ) (b2 )... (bk ) и () = {}. Далее расширим полученное отображение на множество языков над. Если L – язык, он является результатом действия подстановки на язык L.

Убедимся в том, что определенные ранее операции объединения, произведения и итерации являются частными случаями подстановки. Пусть = {a1, a2 }, L1 и L2 – языки над, (a1 ) = L1, (a2 ) = L2.

Тогда легко проверить, что ({a1 a2 }) = L1 L2, ({a1, a2 }) = L1 L2 и Операции над языками будем использовать для задания языков.

Пусть F (x1, x2,..., xn ) – выражение, построенное из переменных x1, x2,..., xn, знаков операций и скобок, и L1, L2,..., Ln – некоторые языки над. Тогда говорят, что язык F (L1, L2,..., Ln ) задается выражением F (x1, x2,..., xn ). Например, если F (x1, x2 ) = x1 (x2 x3 ), L1 = {A, B,..., Z, a, b,..., z}, L2 = {0, 1,..., 9}, то язык F (L1, L2 ) состоит из цепочек, составленных из букв и цифр и начинающихся с буквы, т. е. F (L1, L2 ) – множество имен языка программирования типа Паскаль. Следовательно, множество имен задается выражением x1 (x2 x3 ).

Кроме приведенных выше традиционных операций над языками, в задачах будут использоваться еще и операции, приведенные ниже. Пусть L – язык над, a – элемент из. Тогда Первые две операции называются соответственно правым и леЧасть 1. Языки и способы их задания вым делением на a. Префиксное замыкание init строит множество всех префиксов цепочек из L. Наконец, min(L) – множество цепочек из L, никакой собственный префикс которых не принадлежит L. Приведем пример. Пусть L = {aba, aaba, abab, aa, bbb}. Тогда L\a = {ab, aab, a}, a\L = {ba, aba, bab, a}, min(L) = {aba, aa, bbb}, init(L) = {, a, b, aa, ab, bb, aab, aba, bbb, aaba, abab}.

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

Определение. Отображение : называется гомоморфизмом, если (uv) = (u)(v) для любых u, v. Язык (L) = = {(w) | w L} называется гомоморфным образом языка L (при гомоморфизме ).

Например, если L = {aba, aa, bbb}, (a) = ac, (b) = ca, то (L) = {accaac, acac, cacaca}.

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

Задачи 1. Пусть K, L и M – языки над алфавитом. Доказать следующие утверждения:

Можно ли в пунктах б и в включение заменить на равенство?

2. Пусть A = {a}, B = {b}, C = {ai bi | i N}. Выразить следующие языки через A, B и C с помощью операций объединения, произведения, итерации и подстановки:

3. Проверить следующие равенства:

Глава 2. Распознаватели Глава 2. Распознаватели Распознавателем языка L над алфавитом называется алгоритм (или физическое устройство), который по произвольной цепочке w определяет, принадлежит ли w языку L или не принадлежит. Иными словами, распознаватель вычисляет предикат w L.

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

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

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

§ 3. Конечные автоматы Определение. Детерминированным конечным автоматом (сокращенно ДКА) называется пятерка A = (Q,,, q0, F ), где Q – непустое конечное множество состояний, – конечный алфавит, q0 Q – начальное состояние, F Q – множество заключительных (или допускающих) состояний, : Q Q – (всюду определенная) функция переходов.

Слово автомат в этом и следующем параграфе используется как синоним ДКА. В § 5 будут введены два типа недетерминированных конечных автоматов, обобщающих ДКА.

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

Рис.2.1. Cхематическое устройство ДКА ДКА, как и любой распознаватель, работает дискретно, тактами. Такт работы ДКА состоит в переходе из текущего состояния q при текущем входном символе a в состояние q = (q, a). Далее под переходом в автомате мы всегда понимаем тройку вида (q, a, q ).

Для записи последовательности тактов работы автомата удобно доопределить функцию переходов на всем множестве Q естественным образом:

Таким образом, (q, w) – это состояние, в которое придет ДКА, если, находясь в состоянии q, обработает в результате последовательности тактов цепочку w. Автомат начинает работу, обозревая самую Глава 2. Распознаватели левую ячейку ленты и находясь в состоянии q0. Поскольку – всюду определенная функция, то автомат просмотрит всю цепочку, записанную на входной ленте.

Определение. ДКА A = (Q,,, q0, F ) распознает (или допускает) цепочку w, если (q, w) F. Языком, распознаваемым A (обозначается через L(A)), называется множество всех цепочек, распознаваемых этим автоматом.

Будем использовать два способа задания конечного автомата:

расширенную таблицу переходов и диаграмму переходов. Расширенная таблица переходов представляет собой таблицу значений функции переходов, первая строка которой соответствует начальному состоянию, а заключительные состояния помечены единицами в дополнительном столбце (табл. 2.1). Диаграммой переходов называется ориентированный граф, вершины которого – состояния автомата, а дуги помечены элементами алфавита. Данный граф содержит дугу из q в q, помеченную символом x, если и только если (q, x) = q.

Начальное состояние будет обозначаться двойным кружком, а заключительные состояния – жирным кружком (рис. 2.2). Поясним оба способа на примере.

Пример 2.1. Пусть A1 =(Q,,, q0, F ), Q={q0, q1, q2, q3 }, ={a, b}, F = {q2 }, а задана при помощи табл. 2.1, а. Значение (q, x) – элемент этой таблицы, находящийся в клетке с координатами [q, x].

Диаграмма переходов автомата A1 приведена на рис. 2.2.

Таблица 2.1. Расширенные таблицы переходов автоматов A1 (а), A2 (б) и A3 (в) Цепочки aba, a2ba3 распознаются этим автоматом, а цепочки a, abab не распознаются. Нетрудно понять, что Рис.2.2. Диаграмма переходов автомата A Замечание 2.1. Часто в определении ДКА функцию переходов считают частичной, а ДКА со всюду определенной функцией переходов считают частным случаем и называют полным ДКА (мы же будем называть ДКА с частичной функцией переходов неполным). Если неполный автомат не может выполнить очередной такт, то он останавливается (и входная цепочка при этом не распознается). Доопределение функции переходов на произвольные слова производится так же, как это проделано выше, при этом определение распознаваемой цепочки не изменяется. Нетрудно видеть, что всякий неполный ДКА можно доопределить до полного с сохранением распознаваемого языка. Для этого достаточно ввести одно новое незаключительное состояние s и значения всех неопределенных переходов (включая переходы из s) положить равными s (рис. 2.3).

Рис.2.3. Неполный (а) и полный (б) автоматы для языка {ab n | n 0} Замечание 2.2. Для произвольной цепочки w и произвольного состояния q автомата A в диаграмме переходов A существует единГлава 2. Распознаватели ственный путь, начинающийся в q и помеченный w. Для произвольной цепочки w и произвольного состояния q неполного автомата A в диаграмме переходов A существует не более одного пути из q, помеченного w.

§ 4. Приведенные конечные автоматы Ясно, что язык может распознаваться не одним автоматом. Например, если таблицу переходов автомата A1 немного изменить (табл. 2.1, б и в), то мы получим автоматы A2 и A3, распознающие тот же самый язык L(A1 ). Эти два автомата в определенном смысле хуже автомата A1. Действительно, автомат A2 содержит состояние q4, в которое он никогда не перейдет при анализе цепочки.

Такое состояние является, следовательно, лишним. В автомате A состояния q3 и q4 при анализе любой цепочки ведут себя одинаково, и поэтому одно из них также является лишним. Возникает естественный вопрос: как для автомата A найти автомат B, минимальный по числу состояний и распознающий тот же язык, что и A? Прежде чем ответить на него, дадим точные определения. Через Aq будем обозначать автомат, полученный из автомата A заменой начального состояния на состояние q.

Определение. Состояние s автомата A называется достижимым, если существует цепочка w такая, что (q0, w) = s, и недостижимым в противном случае. Состояния s и t автомата A эквивалентны (обозначается s t), если L(As ) = L(At ). Автомат называется приведенным, если он не имеет (различных) эквивалентных состояний и любое его состояние достижимо.

Определение. Автомат A1 = (Q1,, 1, q1, F1 ) изоморфен автомату A2 = (Q2,, 2, q2, F2 ), если существует биекция h : Q1 Q2, сохраняющая переходы, т. е. такая, что h(1 (q, a)) = 2 (h(q), a) для произвольных q Q1, a.

Замечание 2.3. Автоматы A1 и A2 изоморфны тогда и только тогда, когда их диаграммы переходов изоморфны как помеченные орграфы.

Определение. Два автомата эквивалентны, если они имеют общий алфавит и распознают один и тот же язык†.

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

Замечание 2.4. Понятие эквивалентности состояний можно рассматривать в более широком контексте, положив, что состояние s автомата A1 и состояние t автомата A2 эквивалентны, если выполняется условие L(As ) = L(At ). В частности, автоматы A1 и A2 с общим алфавитом эквивалентны тогда и только тогда, когда эквивалентны их начальные состояния.

Лемма 2.1. Пусть A1 = (Q1,, 1, q1, F1 ) и A2 = (Q2,, 2, q2, F2 ) – ДКА с общим алфавитом, s Q1, t Q2 и s t. Тогда для любого a выполняется равенство 1 (s, a) 2 (t, a).

определению имеем откуда aw As. Поскольку L(As ) = L(At ), выполнено условие Рис.2.4. Иллюстрация стабильности отношения Описанное в лемме 2.1 свойство отношения называется стабильностью. Используя это свойство, мы можем дать ответ на вопрос о минимальном автомате.

Теорема 2.1. Пусть A – произвольный автомат. Среди автоматов, эквивалентных A, существует единственный с точностью до изоморфизма приведенный автомат B. Количество состояний автомата B строго меньше количества состояний любого другого автомата, эквивалентного A.

Глава 2. Распознаватели Доказательство. Вначале докажем существование приведенного автомата, эквивалентного автомату A.

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

Поэтому далее предполагается, что A = (Q,,, q0, F ) – ДКА, все состояния которого достижимы. Поскольку очевидно является отношением эквивалентности на Q, рассмотрим соответствующее разбиение Q = K1... Km. Определим ДКА R(A) = (K,,, Kq0, FK ) следующим образом: K = {K1,..., Km }, Kq0 – класс, содержащий состояние q0, множество FK состоит из всех классов, содержащих только состояния из F, а Автомат R(A) определен корректно, так как из леммы 2.1 следует (при A1 = A2 = A), что условие (2.1) однозначно задает функцию переходов. Действительно, если взять другую вершину q Ki, то q q и (q, a) Kj ввиду стабильности отношения.

Заметим, что s F тогда и только тогда, когда As. Следовательно, каждый класс Ki содержит либо только заключительные, либо только незаключительные состояния. В частности, все заключительные состояния принадлежат классам из FK.

Из стабильности отношения следует, что для q Ki, q Kj равенство (q, a) = q влечет (Ki, a) = Kj. По индукции это свойство выполняется не только для букв, но и для произвольного слова w. Обратное тоже верно: если (Ki, w) = Kj, то для любого q Ki имеем (q, w) Kj. Следовательно, условие (q0, w) F выполняется тогда и только тогда, когда (Kq0, w) FK, т. е. языки, распознаваемые автоматами A и R(A), совпадают.

Осталось проверить, что автомат R(A) приведенный. Все его состояния достижимы, поскольку в автомате A нет недостижимых состояний; в качестве слова, по которому данное состояние Ki может быть достигнуто из Kq0, можно взять любое слово, по которому некоторая вершина из Ki достигается в автомате A. Далее, возьмем два произвольных состояния Ki = Kj автомата R(A) и докажем, что они не эквивалентны. Пусть q Ki, q Kj. Поскольку q q, существует слово w такое, что ровно одно из состояний (q, w), (q, w) автомата A является заключительным. Тогда ровно одно из состояний (Ki, w), (Kj, w) автомата R(A) заключительное, откуда следует неэквивалентность Ki и Kj.

Теперь докажем единственность приведенного автомата, эквивалентного данному. Рассмотрим эквивалентные приведенные автоматы B1 = (Q1,, 1, q1, F1 ) и B2 = (Q2,, 2, q2, F2 ) и докажем, что они изоморфны. Состояния q1 и q2 эквивалентны (замечание 2.4).

Возьмем произвольное состояние s Q1. По определению приведенного автомата оно достижимо, т. е. существует цепочка w такая, что 1 (q1, w) = s. Положим t = 2 (q2, w). Снова пользуясь стабильностью отношения, устанавливаем, что s t.

Итак, каждое состояние автомата B1 имеет эквивалентное состояние в автомате B2, и притом единственное, так как B2 не содержит различных эквивалентных состояний по определению. Следовательно, мы имеем биекцию между множествами Q1 и Q2. Эта биекция сохраняет переходы в силу стабильности отношения, т. е. является изоморфизмом автоматов B1 и B2.

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

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

Будем говорить, что слово w является разделяющим для состояний s и t автомата A, если w принадлежит ровно одному из языков L(As ), L(At ). Наименьшую длину разделяющего слова обозначим через sep(s, t) (если s t, то sep(s, t) = ).

Лемма 2.2. Пусть A = (Q,,, q0, F ) – ДКА, k N. Тогда либо sep(s, t) = k для некоторых s, t Q, либо sep(s, t) < k для любых неэквивалентных s, t Q.

Доказательство. Утверждение леммы вытекает из следующего наблюдения: слово aw разделяет состояния s и t тогда и только тогда, когда w разделяет состояния (s, a) и (t, a) (рис. 2.5).

Алгоритм 2.1. Построение классов эквивалентных состояний.

Вход. ДКА A = (Q,,, q0, F ).

Глава 2. Распознаватели Выход. Множество P = {K1,..., Km } классов разбиения Q на эквивалентные состояния.

1. P0 {F, Q\F }; n 2. Pn+1 separate(Pn, K) 3. если (Pn = Pn+1 ) 5. иначе P Pn Используемая в строке 2 функция separate(P, K) возвращает разбиение класса K разбиения P на подклассы в соответствии со следующим условием: два состояния s и t попадают в один подкласс тогда и только тогда, когда для любого a состояния (s, a) и (t, a) находятся в одном классе разбиения P.

Докажем корректность алгоритма. Пусть n – минимальное число такое, что состояния s и t принадлежат разным классам разбиения Pn. Покажем, что sep(s, t) = n. База индукции: n = 0. Очевидно, что состояние из F и состояние из Q\F разделяются пустым словом.

Проверим шаг индукции. По выбору числа n состояния s и t принадлежат одному классу разбиения Pn1. Следовательно, для любого a состояния (s, a) и (t, a) находятся в одном классе разбиения Pn2. В то же время для некоторого a эти состояния принадлежат разным классам Pn1. Значит, к состояниям (s, a) и (t, a) применимо предположение индукции и sep((s, a), (t, a)) = n 1.

Но тогда sep(s, t) = n (ср. доказательство леммы 2.2).

Таким образом, если алгоритм разделяет два состояния, то они не эквивалентны. Если алгоритм закончил работу, положив P = Pn, то Pn+1 = Pn, т. е. не существует состояний с условием sep(s, t) = n+1.

Согласно лемме 2.2 все неэквивалентные состояния уже разделены.

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

Пример 2.2. Построим классы эквивалентных состояний для автомата A4, заданного табл. 2.2.

Таблица 2.2. Таблица переходов автомата A Исходное разбиение имеет вид P0 = { {0, 1, 2, 3, 4, 6}, {5, 7} }.

При первой итерации первый класс разобьется на подклассы {0, 2, 3} (переходы по любой букве приводят в первый класс разбиения P0 ) и {1, 4, 6} (переход по a во второй, а по b – в первый класс разбиения P0 ). Второй класс разобьется на два одноэлементных подкласса. Получаем P1 = { {0, 2, 3}, {1, 4, 6}, {5}, {7} }.

При второй итерации произойдет только одно изменение: из класса {1, 4, 6} выделится состояние 4 (благодаря переходу по b). Вследствие этого на третьем шаге разделится класс {0, 2, 3}, и это будет последним изменением разбиения. В итоге Замечание 2.5. Алгоритм 2.1 может быть реализован на практике следующим образом. Для хранения текущего класса каждого состояния автомата используем статический массив Class длины |Q|, а множество классов сформируем в виде очереди. Основным шагом является разбиение класса K (первого в очереди) на подклассы, производимое следующим образом. В конец очереди добавляется новый класс и в него переносится произвольный элемент из K. Далее, пока K не пуст, берем его произвольный элемент q, удаляем из K Глава 2. Распознаватели и сравниваем с одним представителем каждого из вновь построенных классов. Если для представителя r некоторого из этих классов выполняется Class[(q, a)] = Class[(r, a)] для любого a, то q помещаем в данный класс. Если же q нельзя поместить ни в один из вновь созданных классов, то создаем для q новый класс в конце очереди. Когда K становится пустым, удаляем его, после чего проходим по вновь созданным классам и обновляем для их элементов значения массива Class.

Пусть счетчик num хранит число классов. Условие остановки алгоритма 2.1 эквивалентно тому, что значение num останется неизменным в течение num шагов. Для контроля этого условия удобно использовать счетчик f ails, значение которого увеличивается на 1, если на очередном шаге значение num не изменилось, и обнуляется, если это значение увеличилось. При условии num = f ails алгоритм заканчивает работу.

§ 5. Недетерминированные конечные автоматы Определение. Недетерминированным конечным автоматом (сокращенно НКА) называется пятерка B=(Q,,, Q0, F ), где Q,, F – те же, что и в случае ДКА, Q0 – множество начальных состояний, а : Q 2Q – недетерминированная функция переходов.

Замечание 2.6. Функция переходов может быть эквивалентно определена условием Q Q, т. е. есть произвольное множество переходов. Такое определение, в частности, показывает, что любой помеченный орграф является диаграммой переходов некоторого НКА (элементы, т. е. тройки вида (q, a, q ), суть помеченные ребра орграфа).

На НКА можно смотреть, аналогично ДКА, как на физическое устройство. Разница состоит в следующем. НКА, находящийся в начале такта в состоянии q и обозревающий ячейку с символом а, может перейти в любое состояние из множества (q, a). Если (q, a) =, то автомат останавливается. Как и для ДКА, доопределим функцию переходов на произвольных словах w естественным образом:

Определение. НКА B = (Q,,, Q0, F ) распознает (или допускает) цепочку w, если ( (q, w) ) F =. (Другими словаqQ ми, существует последовательность тактов автомата B, в результате которой он просмотрит всю цепочку w и перейдет из некоторого начального состояния в некоторое заключительное.) Языком, распознаваемым B (обозначается через L(B)), называется множество всех цепочек, допускаемых этим автоматом.

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

Пример 2.3. Рассмотрим НКА B, заданный табл. 2.3.

Таблица 2.3. Расширенная таблица переходов НКА B Цепочка a2 b допускается этим автоматом. Действительно, имеем В то же время для цепочки abba вычисляем (q0, abba) = {q0, q1 }, т. е. B не распознает эту цепочку. Диаграмма переходов автомата B изображена на рис. 2.6.

Распознаваемость цепочки w означает существование на диаграмме пути из q0 в q2, помеченного w.

Глава 2. Распознаватели Ясно, что ДКА является частным случаем НКА. Следовательно, класс языков, распознаваемых ДКА, содержится в классе языков, распознаваемых НКА.

Теорема 2.2 (Рабина–Скотта). Класс языков, распознаваемых НКА, совпадает с классом языков, распознаваемых ДКА.

Доказательство. Возьмем произвольный НКА B = (Q,,, Q0, F ).

Для доказательства теоремы достаточно показать, что существует ДКА A такой, что L(A) = L(B).

Возьмем автомат A = (2Q,,, Q0, F ), где и докажем, что этот автомат – искомый. Для этого индукцией по длине произвольной цепочки w покажем, что База индукции (|w| = 0) немедленно следует из определений. Рассмотрим шаг индукции. Пусть w = ua:

(P, ua) = ( (P, u), a) = [по предположению индукции] Шаг индукции доказан. Осталось заметить, что Теорема доказана.

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

Алгоритм 2.2. Переход от НКА к ДКА построением подмножеств.

Вход. НКА B = (Q,,, Q0, F ).

Выход. Эквивалентный ДКА A = (Q,,, Q0, F ) без недостижимых состояний.

1. для каждого P Q label(P ) 2. Q {Q0 } 3. пока (P Q : label(P ) = 0), повторять Поскольку каждое состояние в Q, кроме начального, получено переходом из ранее построенного состояния, то все состояния A очевидно достижимы.

Пример 2.4. Проиллюстрируем построение автомата A для автомата B из примера 2.3. Автомат A задан расширенной таблицей переходов; порядок строк в ней соответствует порядку появления состояний в Q.

Таблица 2.4. Результат детерминирования НКА B Введем еще один вид автомата, обобщающий как ДКА, так и НКА.

Определение. Недетерминированным конечным автоматом с переходами (-НКА) называется пятерка B = (Q,,, Q0, F ), где Q, недетерминированная функция переходов.

Глава 2. Распознаватели Основным отличием -НКА от рассмотренных ранее конечных автоматов является возможность не сдвигаться по входной цепочке по окончании некоторых тактов (на таком такте автомат читает пустое слово ). Соответственно диаграмма переходов -НКА может содержать дуги, помеченные. В дальнейшем мы увидим, что -НКА очень удобно строить по заданному языку.

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

Замечание 2.7. Произвольный -НКА эквивалентен -НКА с единственным начальным и единственным заключительным состоянием.

Действительно, достаточно добавить к исходному автомату два состояния, q0 и f, как показано на рис. 2.7; -НКА вида (Q,,, q0, f) мы будем называть нормальными. В дальнейшем рассматриваются только нормальные -НКА.

Рис.2.7. Построение нормального -НКА Пусть B = (Q,,, q0, f) – нормальный -НКА. Рассмотрим бинарное отношение на множестве состояний:

Заметим, что пара (q, p) лежит в рефлексивно-транзитивном замыкании отношения тогда и только тогда, когда автомат может перейти из состояния q в состояние p, не сдвигаясь по входной цепочке.

Множество состояний p таких, что (q, p), будем называть замыканием q и обозначать Clo(q). Замыкание множества состояний P зададим равенством Clo(P ) = Clo(q). Определим обобщенную функцию переходов для произвольных слов:

Легко заметить, что r (q,w) тогда и только тогда, когда в диаграмме автомата B существует путь из q в r, помеченный w. Таким образом, распознаваемость цепочки w автоматом B можно эквивалентно определить условием f (q0,w).

Теорема 2.3. Класс языков, распознаваемых -НКА, совпадает с классом языков, распознаваемых НКА.

Доказательство. Рассмотрим произвольный нормальный -НКА B = (Q,,, q0, f) и построим НКА B = (Q,,, Q0, f) такой, что Q0 = Clo(q0 ), (q, a) = (q, a). Сравним пути, помеченные цепочкой w = a1... an, в соответствующих диаграммах переходов (рис. 2.8).

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

Теорема доказана.

Рис.2.8. Сравнение путей в -НКА и обычном НКА Алгоритм 2.2 можно немного видоизменить для построения ДКА, эквивалентного данному -НКА. Заметим, что замыкание Clo(q) легко вычисляется любым поиском из состояния q.

Алгоритм 2.3. Построение ДКА по -НКА.

Вход. -НКА B = (Q,,, q0, F ).

Выход. Эквивалентный ДКА A = (Q,,, Q0, F ) без недостижимых состояний.

Глава 2. Распознаватели 1. для каждого P Q label(P ) 2. Q0 Clo(q0 ); Q {Clo(q0 )} 3. пока (P Q : label(P ) = 0), повторять § 6. Операции над языками, распознаваемыми конечными автоматами Обозначим через A класс всех языков над фиксированным алфавитом, распознаваемых конечными автоматами. Естественно возникает вопрос о замкнутости класса A относительно операций над языками. Ответ на этот вопрос содержится в следующем утверждении.

Теорема 2.4. Класс A замкнут относительно объединения, пересечения, дополнения, произведения и итерации.

Доказательство. Рассмотрим произвольные нормальные -НКА B1 = (Q1,, 1, q1, f1 ) и B2 = (Q2,, 2, q2, f2 ), считая, что Q1 Q2 =.

Пусть L1 = L(B1 ), L2 = L(B2 ). Тогда язык L1 L2 распознается автоматом B3 = (Q1 Q2 {q0, f},, 3, q0, f), получаемым параллельным соединением автоматов B1 и B2 (рис. 2.9). В самом деле, существование в диаграмме переходов B3 пути из q0 в f, помеченного словом w, равносильно существованию пути, помеченного этим словом, либо в автомате B1 из q1 в f1, либо в автомате B2 из q2 в f2 ;

отсюда L(B3 ) = L(B1 ) L(B2 ). Аналогичные рассуждения справедливы для автомата B4, распознающего язык L1 L2 и представленного на рис. 2.10, а также для автомата B5, распознающего язык L (рис. 2.11). Таким образом, замкнутость класса языков A относительно объединения, произведения и итерации доказана. Отметим, что автоматы B3, B4 и B5 также являются нормальными -НКА.

Теперь заметим, что если язык L распознается детерминированным конечным автоматом A = (Q,,, q0, F ), то его дополнение L но пересечения следует из замкнутости относительно объединения и дополнения. Теорема доказана.

Рис.2.9. Параллельное соединение нормальных -НКА Рис.2.10. Последовательное соединение нормальных -НКА Предложение 2.1. Любой конечный язык распознаваем конечным автоматом.

Доказательство. Автоматы, распознающие языки, {} и {a}, приведены на рис. 2.12, а–в.

Рис.2.12. Автоматы, распознающие простейшие языки Глава 2. Распознаватели Язык {w}, состоящий из одной цепочки, либо совпадает с {}, либо является конечным произведением языков вида {a}. Любой конечный язык либо совпадает с, либо является конечным объединением языков вида {w}. Таким образом, предложение следует из теоремы 2.4.

§ 7. Регулярные языки. Теорема Клини В этом параграфе доказывается основополагающий результат теории конечных автоматов, утверждающий совпадение класса автоматных языков A с классом языков, задаваемых при помощи регулярных операций – объединения, произведения и итерации.

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

Нетрудно понять, что словосочетание конечных языков в определении регулярности можно заменить на языков вида, {} и {a}, где a – буква. Класс регулярных языков обозначим через R.

Теорема 2.5 (Клини). Класс регулярных языков совпадает с классом языков, распознаваемых конечными автоматами.

Доказательство. Из предложения 2.1 и теоремы 2.4 немедленно следует, что всякий регулярный язык распознается некоторым конечным автоматом, т. е. R A. Для доказательства обратного включения нужно установить, что всякий язык, распознаваемый конечным автоматом, является регулярным. В качестве класса автоматов возьмем неполные ДКА (см. замечание 2.1). В этом замечании установлена эквивалентность каждого неполного ДКА обычному ДКА. Поскольку обычный ДКА является частным случаем неполного, отсюда следует, что неполные ДКА распознают в точности класс языков A. Доказательство проведем индукцией по числу переходов автомата A = (Q,,, q0, F ), распознающего язык L.

База индукции. Если функция переходов нигде не определена, то автомат не в состоянии проработать ни одного такта; очевидно, что L(A) = {}, если q0 F, и L(A) = в противном случае. Предположим теперь, что в A определен единственный переход (q, a) = r и разберем возможные варианты. Если q = q0, то A снова не выполнит ни одного такта и мы получаем случай, разобранный выше. Для q = q0 все возможные случаи сведены в табл. 2.5.

Таблица 2.5. Возможные случаи для ДКА с единственным переходом Языки, {a}, {}, {, a} и {a} являются регулярными. База индукции рассмотрена.

Шаг индукции. Пусть автомат A = (Q,,, q0, F ) имеет k переходов, k > 1. Зафиксируем переход (q, a) = r. Через обозначим функцию переходов на Q, значение которой не определено на паре (q, a) и совпадает со значением на всех остальных парах. Рассмотрим автоматы Данные автоматы имеют (k1) переходов, откуда языки L(A0 ), L(A1 ), L(A2 ) и L(A3 ) регулярны по предположению индукции. Доказав, что мы покажем регулярность языка L и завершим доказательство теоремы.

Возьмем цепочку w из L. Если автомат, проработав на w, ни разу не воспользовался переходом (q, a) = r, то w L(A0 ). Если же этот переход использовался, то цепочку можно представить в виде w = w0 aw1 a... wn1 awn (n 1), где все указанные буквы a соответствуют переходам из q в r (рис. 2.13).

Получаем w0 L(A1 ), w1,..., wn1 L(A2 ), wn L(A3 ), откуда w L(A1 )a[L(A2 )a] L(A3 ). Тем самым мы показали включение слева направо в формуле (2.2).

Обратное включение практически очевидно. Так, L(A0 ) L по определению, а если w L(A1 )a[L(A2 )a] L(A3 ), то w можно записать в виде w0 aw1 a... wn1 awn, где n 1, w0 L(A1 ), Глава 2. Распознаватели w1,..., wn1 L(A2 ), wn L(A3 ), откуда w L (рис. 2.13). Итак, равенство (2.2) доказано.

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

Определение. Пусть – произвольный алфавит.

1. Символы и, а также буквы из являются регулярными выражениями над.

2. Выражения r|s, (r)·(s), (r), где r и s – регулярные выражения над, являются регулярными выражениями над.

3. Других регулярных выражений над нет.

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

Регулярные выражения, и x, где x, определяют соответственно языки, {} и {x}. Если R и S – языки, определяемые регулярными выражениями r и s, то выражения r|s, (r)·(s) и (r) определяют соответственно языки R S, RS и R. Знак |, общеупотребительный в значении или, когда речь идет о перечислении альтернатив, в нашем случае естественно соответствует объединению языков.

Язык, определяемый регулярным выражением r, будем обозначать через L(r). Таким образом, класс R можно рассматривать как класс языков, определяемых регулярными выражениями.

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

Кроме того, можно пользоваться тем, что объединение и умножение – ассоциативные, а итерация – идемпотентная операция (т. е.

(L ) = L для любого языка L). Символы, и буквы не будем заключать в скобки, а знак операции умножения (т. е. точку) чаще всего будем опускать. Эти соглашения позволяют, например, регулярное выражение (((a) (b)) ((b) · (c))) записать как (a b bc).

Приведем пример. Пусть = {a, b}, r = aa b2 bb a, s = (ab) a.

В завершение параграфа обсудим вопрос о том, как по регулярному выражению r построить конечный автомат, распознающий язык L(r). Удобнее всего строить нормальный -НКА. Для этого достаточно воспользоваться результатами предложения 2.1 и теоремы 2. (см. рис. 2.9–2.12). Чтобы получить ДКА, можно затем использовать алгоритм 2.3.

Пример 2.5. На рис. 2.14 изображен нормальный -НКА, распознающий язык, заданный регулярным выражением r = a(a b) ab.

Автомат построен в соответствии с изложенным выше способом.

Рис.2.14. Нормальный -НКА, распознающий язык L(a(a b) ab) § 8. Фрагменты языков программирования, распознаваемые конечными автоматами Практически в каждом языке есть понятие имени или идентификатора. С синтаксической точки зрения имя чаще всего представляет собой последовательность букв и цифр, начинающуюся с буквы†, т. е. множество имен задается регулярным выражением и поэтому распознается конечным автоматом (для простоты мы полагаем, что алфавит языка содержит только строчные латинские буквы). Если ввести предварительно регулярные выражения † Альтернативный синтаксис имени обычно такой: именем считается непустая цепочка, начинающаяся с предписанного символа, например символа $.

Глава 2. Распознаватели то регулярное выражение для множества имен будет выглядеть как Также просто усмотреть, что множество целых чисел без знака распознается конечным автоматом, поскольку задается регулярным выражением† Чтобы определить регулярным выражением число без знака, надо предусмотреть (возможную) дробную часть и (возможный) порядок.

Соответствующее регулярное выражение будет иметь вид Регулярное выражение для констант в языке Паскаль имеет следующий вид:

Отметим еще понятие простого типа из того же языка Паскаль.

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

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

Замечание 2.8. Было бы в высшей степени ошибочно сделать на основании последнего абзаца вывод о незначительной роли конечных автоматов в программировании. Их непосредственная роль в процессе компиляции программ (см. ч. 2, гл. 1) действительно невелика, но они играют очень важную вспомогательную роль при построении компилятора (ч. 2, гл. 4). К тому же центр применения автоматов в программировании совсем не здесь – они давно применяМы немного упростили ситуацию. На самом деле такое используется ниже в дробной части и экспоненте числа, а для целой части числа нужно дополнительно учесть, что она не начинается с 0, если не равна 0.

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

§ 9. Автоматы с магазинной памятью Изученные выше конечные автоматы обладают довольно слабыми распознающими возможностями. Продемонстрируем это на следующем классическом примере.

Предложение 2.2. Скобочный язык LB не является регулярным.

Доказательство. Предположим противное: пусть LB распознается конечным автоматом A. Количество состояний автомата A обозначим через n. Поскольку A распознает все правильные расстановки скобок, он распознает расстановку Автомат начинает чтение цепочки w в начальном состоянии q0 и в процессе чтения n открывающих скобок последовательно попадает в n состояний, которые мы обозначим через q1,..., qn. Поскольку в автомате только n состояний, то найдутся такие числа i и j, что 0 i < j n и qi = qj. С учетом этого замечания путь в автомате, помеченный цепочкой w, можно представить как на рис. 2.15. Но тогда A, очевидно, распознает некорректную расстановку скобок так как путь, помеченный этой цепочкой, получается из пути на рис. 2.15 удалением цикла у вершины qi = qj. Тем самым A не распознает LB. Полученное противоречие завершает доказательство.

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

Глава 2. Распознаватели Замечание 2.9. Именно скобки представляют основную сложность распознавания выражений. Если из описания языка LA убрать скобки, то получившийся язык распознается конечным автоматом с двумя состояниями. Проверку этого простого факта мы оставляем читателю.

Язык арифметических выражений с точки зрения сложности его цепочек является очень простым по сравнению, скажем, с языками программирования. Это означает, что для проверки синтаксической корректности программ необходим более сильный распознаватель, нежели конечный автомат. В качестве такого распознавателя обычно используется автомат с магазинной памятью (сокращенно МПавтомат, МПА; в оригинале – push-down automaton, PDA). Понятие МП-автомата является одним из центральных в данной книге. Мы начнем его обсуждение с модели МПА как физического устройства (рис. 2.16).

Рис.2.16. Схема устройства МП-автомата. Для цепочки допускается только чтение, а для стека – чтение и запись Как и конечный автомат, МПА содержит устройство управления, которое в каждый момент времени находится в некотором состоянии (из конечного набора), и входную ленту, предназначенную для посимвольного чтения слева направо входной цепочки. Но в отличие от КА добавляется еще одна лента – лента памяти (иногда называемая магазином). Как и входная лента, лента памяти потенциально неограничена в одну сторону, но предназначена как для считывания, так и для записи. Доступ к ней организован по принципу стека:

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

Опишем функционирование МП-автомата. Как и конечный автомат, МПА работает тактами. В ходе каждого такта устройство управления анализирует свое текущее состояние q, обозреваемый входной символ a, символ B на вершине стека и принимает решение о том, в какое состояние q перейти, какую цепочку записать в стек вместо символа B, следует ли сдвинуть указатель вправо по входной ленте ( ) Данный процесс мы будем рассматривать как выполнение автоматом команды соответственно.

Автомат допускает цепочку, записанную на входной ленте, если он дошел до ее конца и оказался при этом в одном из заключительных состояний. Недопуск цепочки происходит в одном из двух случаев: если автомат дочитал цепочку, но не пришел в заключительное состояние, либо если он не дочитал ее до конца (способность не сдвигаться вправо по входной ленте означает возможность зацикливания автомата, даже если считать, что автомат имеет команду для любой возможной тройки (q, a, B)).

Теперь дадим формальное Глава 2. Распознаватели Определение. Автоматом с магазинной памятью (МП-автоматом) называется семерка M = (Q,,,, q0, F, 0 ), где Q – конечное множество состояний, – конечный входной алфавит, – конечный стековый алфавит, q0 Q – начальное состояние, F Q – множество заключительных состояний, 0 – начальное содержимое стека, а – конечное множество команд вида (2.3).

Для удобства формализации обработки цепочек МП-автоматом принято считать, что входной и стековый алфавит содержат по специальному символу-ограничителю. Символ – символ конца строки – размещается на входной ленте непосредственно справа от входной цепочки (и не встречается внутри самой цепочки). Считается, что указатель на входной ленте видит этот символ тогда и только тогда, когда прочтение входной цепочки завершено. Символ – символ дна стека – размещается под нижним символом в стеке (и более нигде не встречается). Когда стек пуст, его верхним символом является как раз. На таком такте при записи в стек символ дна остается на своем месте, т. е. при выполнении команды с левой частью (q, a, ) цепочка символов будет записана в стек поверх символа.

Определение. Пусть МП-автомат M = (Q,,,, q0, F, 0 ) зафиксирован. Конфигурацией M называется тройка [q, w, ], где q Q – текущее состояние автомата, w – суффикс входной цепочки, начинающийся в позиции указателя, – содержимое стека (начиная с верхнего символа, не считая символа дна). Тот факт, что после выполнения команды в конфигурации [q, w, ] автомат перешел в конфигурацию [q, w, ], мы записываем в виде [q, w, ] |= [q, w, ] и говорим, что вторая конфигурация следует за первой. Запись [q, w, ] |= [q, w, ] означает, что автомат может перейти из первой конфигурации во вторую за конечное число (в том числе нуль) шагов.

Пример 2.6. Автомат, находящийся в конфигурации [q, aw, B], на очередном такте может выполнить только команду с левой частью (q, a, B). Если такая команда имеет вид (q, a, B) (q,, ), то имеем [q, aw, B] |= [q, w, ]; если же правая часть команды равна (q,, _), то получим [q, aw, B] |= [q, aw, ].

Автомат, находящийся в конфигурации [q, aw, ], может выполнить только команду с левой частью (q, a, ). При этом следующая конфигурация будет иметь вид [q, w, ] или [q, aw, ].

Определение. МП-автомат M = (Q,,,, q0, F, 0 ) распознает (или допускает) цепочку w, если [q0, w, 0 ] |= [f,, ] для некоторых f F,. Язык, состоящий из всех цепочек, распознаваемых M, называется языком, распознаваемым этим автоматом, и обозначается L(M). Два МП-автомата эквивалентны, если они распознают один и тот же язык.

Из приведенного выше описания МПА видно, что можно рассматривать как детерминированную, так и недетерминированную версию такого автомата. Детерминированный МПА (ДМПА) в любой конфигурации имеет единственную возможность для продолжения работы: либо он переходит в строго определенную следующую конфигурацию, либо – в отсутствие такой конфигурации – останавливается. Следовательно, такой автомат имеет не более одной команды для каждой тройки (q, a, B). Для некоторых троек команды могут отсутствовать†, т. е. автомат является неполным – ср. замечание 2. о неполных ДКА. Множество команд ДМПА можно представлять в более привычном виде (частичной) функции переходов Недетерминированный МП-автомат (НМПА) может иметь несколько команд с одинаковой левой частью; тем самым для некоторых его конфигураций следующая конфигурация определяется не единственным образом. Данное нами формальное определение МПА не накладывает специальных ограничений на систему команд‡, а следовательно задает именно НМПА. Отметим, что систему команд НМПА можно рассматривать как функцию переходов где индекс f in указывает на рассмотрение только конечных подмножеств.

Что касается распознающих возможностей детерминированных и недетерминированных МПА, то ситуация здесь резко отличается † Отсутствие команды равносильно (с точки зрения распознавания цепочек) наличию команды ничего не делать, имеющей вид (q, a, B) (q, B, _). Далее мы предполагаем без ограничения общности, что команд ничего не делать в автомате нет.

‡ Кроме требования конечности. Это требование автоматически выполняется для детерминированного автомата, поскольку число команд не превосходит мощности конечного множества Q, но должно быть оговорено явно для недетерминированного автомата ввиду бесконечности множества.

Глава 2. Распознаватели от внешне похожей ситуации с конечными автоматами. Класс языков, распознаваемых НМПА, как мы увидим в дальнейшем, строго больше класса языков, распознаваемых ДМПА. Более того, класс языков, распознаваемых НМПА, совпадает с одним из самых известных и важных классов в теории формальных языков. Этот класс допускает простую и эффективную характеризацию, в то время как его подкласс, состоящий из языков, распознаваемых ДМПА, охарактеризовать существенно сложнее. Вообще, для решения теоретических вопросов удобно рассматривать именно НМПА. Наоборот, с точки зрения практической применимости НМПА почти бесполезны, а ДМПА очень важны. Связано это с отсутствием эффективного алгоритма для моделирования работы первых и наличием такого (очевидного) алгоритма для моделирования работы вторых.

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

Эффективному моделированию НМПА препятствует тот факт, что текущих конфигураций НМПА может быть сколь угодно много†.

Поскольку в данной книге нас интересует в первую очередь практическое применение автоматов, мы в дальнейшем будем почти всегда рассматривать ДМПА и термин МП-автомат использовать в значении ДМПА, если иное не оговорено явно.

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

Пример 2.7. Построим МП-автомат, который распознает скобочный язык LB. Имеем = { [, ] }. Нам потребуются два состояния, начальное q и заключительное f и единственный стековый символ [, при помощи которого мы будем запоминать незакрытые левые скобки. Автомат начинает работу с пустым стеком. Управляющая таблица приведена в табл. 2.6.

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

Таблица 2.6. Управляющая таблица МП-автомата для языка LB жит в точности все незакрытые левые скобки в прочитанной части цепочки. Цепочка распознается автоматом тогда и только тогда, когда в момент обнаружения ограничителя стек пуст, т. е. все скобки являются парными. При обнаружении лишней правой скобки автомат останавливается, не прочитав цепочку до конца, так как клетка (q, ], ) пуста. Если по завершении чтения цепочки останутся незакрытые левые скобки, то автомат останется в незаключительном состоянии q.

В приведенном примере состояние f с содержательной точки зрения не нужно вообще – соответствующая часть таблицы пуста, и вместо перехода в состояние f в клетке (q,, ) достаточно было бы поместить указание допустить цепочку. Такая ситуация, как мы увидим, является общей (хотя далеко не для каждого автомата это очевидно). В связи с этим представляется целесообразным использование в МП-автоматах специальной команды допустить цепочку, которую мы будем записывать в виде (q, a, B).

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

При конструировании МП-автоматов в данной книге мы будем постоянно пользоваться этой дополнительной командой. Как мы увидим в дальнейшем, использование команды допуска позволяет всегда в случае НМПА, и достаточно часто в случае ДМПА, Глава 2. Распознаватели обойтись автоматами с одним состоянием, тем самым делая моделирование МП-автоматов более эффективным как по используемой памяти, так и по времени работы. Рассмотрим еще один пример.

Пример 2.8. МП-автомат, задаваемый таблицей 2.7, начинает работу с пустым стеком и распознает язык {an bn | n 0}. Состояние q является начальным и единственным заключительным.

Таблица 2.7. Управляющая таблица МП-автомата для языка {an bn |n0} В отличие от предыдущего примера оба состояния этого автомата играют нетривиальную роль: переход в r означает, что символы a больше появляться в цепочке не должны. Тем не менее, введя один дополнительный стековый символ, мы можем модифицировать автомат, обойдясь единственным состоянием (и единственным применением специальной команды допустить цепочку ). Результат модификации показан в табл. 2.8. Поскольку состояние автомата единственно, оно нигде в таблице не фигурирует. В начале работы в стеке находится символ X. Он снимается со стека, когда найдена первая буква b; после этого автомат не может прочитать больше ни одной буквы a.

Таблица 2.8. Модификация управляющей таблицы МП-автомата для языка {an bn | n 0} В заключение параграфа покажем, что НМПА распознают более широкий класс языков, чем ДМПА. Для произвольной цепочки w = a1... an через w обозначим цепочку an... a1.

Предложение 2.3. Если алфавит содержит более одной буквы, то язык {w w | w } распознается недетерминированным МПавтоматом, но не распознается детерминированным МП-автоматом.

Доказательство. Вначале построим НМПА, распознающий указанный язык. Возьмем произвольный символ X. Множество {X} будет стековым алфавитом, а X – начальным содержимым стека.

Автомат имеет единственное состояние, а его управляющая таблица схематично представлена в табл. 2.9. Здесь x означает произвольный элемент из, y – произвольный элемент из, отличный от x.

Автомат является недетерминированным, так как паре (x, X) соответствуют две различные команды.

Таблица 2.9. Управляющая таблица НМПА для языка {w w | w } Обработка цепочки построенным автоматом, очевидно, происходит в два этапа – накопления символов в стеке (пока верхушкой стека является символ X) и удаления символов из стека (после того как X снят со стека). Если к тому моменту, когда автомат выбрал команду (x, X), он обработал префикс u входной цепочки, то содержимое стека в этот момент равно, очевидно, u. На второй стадии автомат может выполнить очередной такт тогда и только тогда, когда очередной символ входа совпадает с текущим верхним символом в стеке (клетка (x, x) содержит команду, а клетка (x, y) пуста). Следовательно, цепочка будет допущена в том и только в том случае, когда ее часть, оставшаяся необработанной к моменту снятия X со стека, равна u. Мы показали, что построенный автомат распознает язык {w w | w }. Отметим, что недетерминизм в данном случае является существенным – автомат угадывает местонахождение середины цепочки, длина которой неизвестна.

Теперь покажем, что никакой ДМПА не может распознать данный язык. В самом деле, поскольку алфавит содержит более одГлава 2. Распознаватели ной буквы, МПА, распознающий все цепочки вида w w и только их, должен побуквенно сравнивать вторую половину цепочки с первой.

Значит, при обработке первой половины цепочки вся информация о прочитанных символах накапливается в стеке, а при обработке второй половины – извлекается из него для сравнения. Пусть некоторый ДМПА распознает цепочку waa w и после обработки ее префикса wa находится в состоянии q с символом B на вершине стека. Тогда у этого ДМПА есть команда с левой частью (q, a, B), указывающая на переход к сравнению обработанной и необработанной частей цепочки. Поскольку команда с такой левой частью единственна, автомат не сможет распознать цепочку waaaaw, принадлежащую рассматриваемому языку, так как приступит к сравнению уже после прочтения префикса wa. Доказательство теоремы завершено.

§ 10. Фрагменты языков программирования, распознаваемые МП-автоматами При помощи МП-автоматов можно распознать бльшую часть конструкций языков программирования. Подробно это обсуждается во второй части книги. Здесь мы ограничимся двумя примерами.

Первый из примеров – это МП-автомат A1, распознающий язык списков LL. Автомат имеет единственное состояние; его управляющая таблица приведена ниже (табл. 2.10). В начале работы стек содержит единственный символ L.

Таблица 2.10. Управляющая таблица МП-автомата A Проиллюстрируем работу МП-автомата A1 по распознаванию цепочки a;[a;a;a] (табл. 2.11). Символ отделяет обработанную часть входной цепочки от необработанной.

Из табл. 2.11 видно, что автомат распознает цепочку a;[a;a;a].

Доказать, что язык, распознаваемый автоматом A1, равен LL, имея Таблица 2.11. Протокол обработки цепочки a;[a;a;a] автоматом A Такт Позиция указателя Содержимое стека только управляющую таблицу автомата, довольно трудно. Это утверждение будет следовать из результатов ч. 2, гл. 2 этой книги. Там же будет указан алгоритм построения управляющей таблицы.

Второй пример – МП-автомат A2, распознающий язык арифметических выражений LA. Этот автомат также имеет единственное состояние, а его управляющая таблица приведена в табл. 2.12. В начале работы стек содержит единственный символ E.

Таблица 2.12. Управляющая таблица МП-автомата A Если обработать при помощи автомата A2 цепочку (x+x)*x (табл. 2.13), то можно убедиться, что она распознаваема. Как и Глава 2. Распознаватели в предыдущем примере, равенство L(A2 ) = LA затруднительно доказать непосредственно; мы покажем этот факт в ч. 2, гл. 2.

Таблица 2.13. Протокол обработки цепочки (x+x)*x автоматом A Такт Позиция указателя Содержимое стека Задачи 1. Конечный автомат задан расширенной таблицей переходов. Начертить диаграмму переходов, задающую этот автомат (табл. 2.14).

Таблица 2.14. Таблицы переходов (к задаче 1) 2. Конечный автомат задан диаграммой переходов. Составить таблицу переходов, задающую этот автомат (рис. 2.17).

3. Для каждого из автоматов, указанных в задачах 1 и 2, найти:

а) самую короткую цепочку, допускаемую автоматом;

б) две другие цепочки, допускаемые автоматом;

в) две цепочки длины 4, не допускаемые автоматом.

4. Построить приведенный автомат, эквивалентный заданному таблицей 2.15, а–в.

5. Построить приведенный автомат, распознающий множество:

Глава 2. Распознаватели г) {and, or, not, false, true};

д) двоичных чисел с плавающей точкой;

е) двоичных слов четной длины;

ж) двоичных слов с четным числом и нулей, и единиц;

з) двоичных слов, не содержащих подслова 01;

и) двоичных слов, не содержащих подпоследовательности 101.

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

7. Построить ДКА, эквивалентный данному НКА (табл. 2.16).

Таблица 2.16. Таблицы переходов (к задаче 7) 8. Построить стандартный -НКА, распознающий язык, заданный регулярным выражением. По -НКА построить приведенный ДКА, используя алгоритм 2.3:

9*. Пусть L – регулярный язык. Проверить, обязательно ли регулярны следующие языки:

а) init(L);

д) min(L);

10. Доказать, что следующие языки нерегулярны:

11. Пусть L – регулярный язык и S(L) = {|w| | w L}. Доказать, что S(L) – объединение конечного числа (возможно бесконечных) арифметических прогрессий.

12. Какие из цепочек a3, ba2 b2, b3 ab2, b3 a2 b2 a допускаются МПавтоматом с управляющей таблицей, приведенной в табл. 2.17, а?

Автомат начинает работу с пустым стеком.

Таблица 2.17. Управляющие таблицы МП-автоматов для задач 12, 13. Управляющая таблица МП-автомата приведена в табл. 2.17, б.

Найти цепочки, допускаемые этим автоматом:

а) цепочку длины, большей 4, не содержащую букву b;

б) цепочку длины, большей 5, с тремя переменами букв a и c;

в) цепочку длины, большей 3, содержащую букву b.

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

14. Построить МП-автоматы, допускающие следующие языки:

15. Какой из языков L1 = {an bn | n > 0}, L2 = {al cbm | l, m > 0} или L3 = {an cbn | n > 0} допускается МП-автоматом с управляющей таблицей, приведенной в табл. 2.18, а? В начале работы стек содержит символ D.

Таблица 2.18. Управляющая таблица МП-автомата для задачи Глава 3.Контекстно-свободные грамматики Глава 3. Контекстно-свободные грамматики Данная глава посвящена основному способу задания используемых на практике формализованных языков – контекстно-свободным грамматикам. Контекстно-свободные грамматики представляют значительный теоретический интерес и широко используются в практике программирования. Глава начинается с обсуждения более широкого понятия – понятия порождающей грамматики.

§ 11. Порождающие грамматики Определение. Порождающей грамматикой (или просто грамматикой) называется четверка G = (,, P, S), где – основной (или терминальный) алфавит, элементы которого называются терминалами, – вспомогательный (или нетерминальный) алфавит, элементы которого называются нетерминалами, S – выделенный нетерминал, называемый аксиомой, P – множество формальных выражений вида, где, ( ) и содержит хотя бы один нетерминал, называемых правилами вывода.

Приведем пример: пусть = {a, b}, = {S, D} (S – аксиома), P = {S aSDa, S aba, aD Da, bD bb}. Полученную грамматику обозначим через G3,1 †.

Грамматика, как было сказано выше, – способ задания языка.

Дадим соответствующие определения.

Определение. Пусть G = (,, P, S) – грамматика,, ( ).

Цепочка непосредственно выводима в G из цепочки (обозначается G ), если существуют такие цепочки,, 1, 2 ( ), Когда понятно, о какой грамматике идет речь, мы будем писать просто. Приведем примеры непосредственной выводимости в грамматике G3,1 : aSDa aabaDa (1 = a, 2 = Da, S aba P );

aDbSa DabSa (1 =, 2 = bSa, aD Da P ); S aba Определение. Пусть G = (,, P, S) – грамматика,, ( ).

Цепочка выводима в G из цепочки (обозначается ), если † Для грамматик, используемых в книге локально, мы будем применять здесь и далее двойную индексацию (номер главы, номер примера).

существуют число n 0 и цепочки 0, 1,..., n такие, что Последовательность цепочек 0, 1,..., n называется выводом, число n – длиной вывода.

Замечание 3.1. Отношение выводимости в G есть рефлексивнотранзитивное замыкание отношения непосредственной выводимости в G, этим и объясняется выбор обозначения. Мы будем также использовать транзитивное замыкание непосредственной выводимости + G (отношение нетривиальной выводимости в G).

Пример: S 3,1 a2 b2 a2 ; соответствующий вывод имеет длину 4:

Введем основное определение этого параграфа.

Определение. Языком, порождаемым грамматикой G (обозначается через L(G)), называется множество цепочек над основным алфавитом, выводимых из аксиомы грамматики.

Из приведенных выше примеров следует, что aba, a2 b2 a2 L(G3,1 ).

Нетрудно показать, что L(G3,1 ) = {an bn an | n N}.

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

Какую же лингвистическую роль играет вспомогательный алфавит? Для того чтобы ответить на этот вопрос, рассмотрим еще один пример порождающей грамматики, которую будем обозначать через G3,2. Пусть вспомогательный алфавит грамматики G3,2 состоит из элементов,,, символ является аксиомой, основной алфавит содержит строчные буквы латинского алфавита и десятичные цифры. Правилами вывода этой грамматики являются следующие правила:,,, a, b,..., z, 0, 1,..., 9. Легко видеть, что язык, порожденный грамматикой G3,2, состоит из последовательностей букв и цифр, начинающихся с буквы, т. е. L(G3,2 ) – множество имен языка программирования типа Паскаль. Этот пример показывает, что элементы вспомогательного алфавита обозначают грамматические классы языка, а именно, элемент – класс имен, – класс букв, – класс цифр.

На примере грамматики G3,2 сделаем еще одно полезное наблюдение. Мы видим, что у этой грамматики есть довольно много праГлава 3.Контекстно-свободные грамматики вил с одной и той же левой частью. Такие правила вывода называются альтернативами. Множество правил {A 1, A 2,..., A k } чаще всего записывают в виде обобщенного правила A 1 | 2 |... | k (ср. запись регулярных выражений, § 7). Этот способ записи позволит представить 39 правил грамматики G3,2 в виде трех обобщенных правил:

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

1) терминалы обозначаем малыми буквами начала латиницы;

2) нетерминалы – большими буквами начала латиницы или строками символов в угловых скобках; в левой части первого правила вывода стоит аксиома;

3) произвольные грамматические символы из – большими буквами конца латиницы;

4) цепочки терминалов – малыми буквами конца латиницы;

5) цепочки произвольных грамматических символов из – малыми греческими буквами.

Во всех случаях можно использовать индексы.

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

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

Вначале рассмотрим язык L = {an bn cn | n N}, который похож на язык, порожденный грамматикой G3,1. Напишем грамматику для этого языка (будем ее обозначать через G3,3 ), используя в качестве аналога грамматику G3,1. В последней грамматике (n1)-кратное применение правила S aSDa и последующее применение правила S aba дает цепочку an b(aD)n1 a. Правило вывода aD Da дает возможность переставлять a и D и группировать символы D после b. Затем с помощью правила bD bb ближайший к b символ D превращается в b.

Построение грамматики G3,3 начнем с двух правил: S aSBC и S abC. Применение первого правила (n1) раз и последующее применение второго правила даст цепочку an bC n B n1. Добавим правила CB BC и bB bb. Первое обеспечивает перестановку C и B, второе – превращение B в b (если слева стоит b). После применения этих правил получается цепочка an bn C n. Осталось добавить правила bC cc и cC cc, с помощью которых из C n можно получить cn. Итак, G3,3 = {S aSBC | abC, CB BC, bB bb, bC cc, cC cc}.

В качестве второго языка рассмотрим язык L {a, b}, состоящий из всех слов с равным количеством a и b.