XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 78
Текст из файла (страница 78)
Из определения регулярного языка, теоремы 7.4 и следствия 7.1 немедленно вытекает, что и нозитииеная итвераиил Регулярного языка регулярна. Далее мы зачастую будем говорить просто о регулярных языках (или регулярных множествах), подразумевая, что фиксирован некоторый алфавит У. Алгебраические операции над регулярными языками удобно пРедставлять с помощью так называемых регуялрнык выРаэкениб. Каждое регулярное выражение представляет (или 492 7.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ обозначает) некоторый (однозначно определяемый) регулярный язык, причем языки И, (Л) и (а), где а Н 'т', обозначаются выражениями И, Л и а соответственно, и если регулярное выражение р обозначает регулярный язык Р, а регулярное выражение д обозначает регулярный язык Я, то регулярные выражения (р+ д), (рд) и (р') обозначают регулярные множества РОЯ, РЯ и Р' соответственно. Таким образом, в регулярных выражениях для обозначения операции объединения языков используют знак „+е (плюс). Условимся также для регулярного выражения шл' или а'а использовать обозначение а+ и называть это выражение позитивной итерацией выражения а. Замечание 7.4.
Введенные вьппе обозначения регулярных выражений создают при использовании символа Л некий „конфликт" обозначений. А именно мы можем, в зависимости от контекста, понимать этот символ и как обозначение самой пустой цепочки, и как обозначение языка, состоящего вз одной пустой цепочки (это и будет собственно регулярное выражение Л). Эти интерпретации символа Л следует тщательно разграничивать. В то же время (и такова традиция изложения теории формальных языков) вряд ли целесообразно вводить для регулярного выражения, обозначающего язык (Л~, какое-то новое обозначение. Можно сократить количество скобок в регулярных выражениях', приняв следующее соглашение о приоритетах: самый высокий приоритет имеет операция итерации, затем — соединения и,наконец, — объединения.
Так, регулярное выражение а' + (Ьс)' обозначает множество цепочек, состоящее из цепочек вида ао, и > О, и цепочек вида (Ьс)", п ) О, где а, Ь, с е т'. Использование регулярных выражений позволяет получать более наглядную и простую нотацию для регулярных языков. 'По алалогвв с тем, лак иы делаля это в формрлеа, вредставллющвх орлеем фрвваие (ем. 8.4).
7.4. Регулярные языка я регуллрвые вырамеввл 493 Так, вместо рассмотренного вьппе регулярного выражения мы должны были бы использовать гораздо менее выразительную и более громоздкую формулу: (а)' О ((6) . (с))'. Соответствие между регулярными множествами и регулярными выражениями не является взаимно однозначным: одно и то же регулярное множество может представляться многими регулярными выражениями.
Продемонстрируем это на таком примере. Рассмотрим регулярное выражение х = (Ь+а)'(Ь+а+6'), а,Ь,с Е К Используя аксиомы полукольца (см. 3), преобразуем х следую- щим образом: х = (Ь+ а)+ + (Ь+а) 'Ь' = (Ь+а)+ + (Ь+а)' + (Ь+ а)'6+ = = (Ь+а)'+(Ь+а)'Ь+ = (Ь+а)'Ь'. Все рееуляркые вырахсекия, фигурирующие в этих преобразованиях, эквиваленпзкы, т.е. все они обозначают один и тот же регулярный язык. Проблемы распознавания эквивалентности двух произвольных регулярных выражений, автоматизации тождественных преобразований регулярных выражений и поиск самого короткого („оптимвяьного") регулярного выражения, обозначающего данный регулярный язык, весьма трудны и здесь не обсуждаются.
В целом соотношение между регулярными выражениями и регулярными языками вполне аналогично соотношению между формулами и булевыми функциями (см. 6.4). В частности, если переход от формулы к эквивалентной формуле в теории булевых функций совершается согласно аксиомам булевой алгебры и другим тождествам, выводимым из этих аксиом, то переход от заданного регулярного выражения к эквивалентному регулярному выражению производится согласно аксиомам полукольца и тождествам, выводимым иэ них. 494 7. кОнечные АВтОмАты и РеГУлЯРные Языки Зачастую в дальнейшем, если зто не повлечет непонимания, мы будем отождествлять регулярный язьпс с обозначающим его регулярным выражением (любым!), что позволит не вводить новых обозначений и пояснений. Так, для рассмотренного выше примера мы можем написать ЬЬаЬа6ЬЬ е (6+а)'Ь*, что, строго говоря, обозначает факт принадлежности цепочки ЬЬаЬа66Ь языку, обозначенному регулярным выражением (Ь+а)'Ь'.
Разумеется, следует воздерживаться, например, от употребления такой записи: Л е Л, хотя, если подумать, и здесь все понятно: пустая цепочка Л принадлежит языку (Л), обозначаемому регулярным выражением Л. Т.б. Конечные автоматы. Теорема Клннн Одной из наиболее важных задач, решаемых в теории формальных языков, является следующая. Пусть задана некоторая порождающая грамматика 0 с терминальным алфавитом У и цепочка х в алфавите У. Спрашивается: принадлежит ли цепочка я языку, порождаемому ерамматикой С? Эту задачу называют проблемой принадлененосши для грамматики С.
В теории формальных языков доказывается, что проблема принадлежности разрешима для КЗ-грамматик и для КС-грамматик, но в общем случае не разрешима для грамматик типа О. Решение проблемы принадлежности состоит в разработке распознающего алгоритма, который для произвольных грамматики 0 (из заданного класса грамматик) и цепочки я за конечное число шагов выдает ответ на поставленный вьппе вопрос.
В основе подобного рода алгоритмов лежит математическая модель языка, называемел распознающей моделью или анализирующей моделью и являющаяся как бы зеркальной к порождающей модели, примером которой служит порождающая грамматика. Традиционно анализирующие модели языков называют автоматами. В каждом классе языков может быть определена пара 7.о. Конечные автоматы. Теорема Клнан 495 порождающая модель — анализирующая модель" или, другими сдовами, пара „грамматика — автомат", где автомат в определенном смысле анализирует (распознает) цепочки,порождаемые грамматикой. Неформально автомат можно описать как устройсгво, состснпцее из блока управления, входной ленты, золовки автпомата и блока внутпренней памлти автомата (рис. 7.2). На ленте, которал предполагается полубесконечной (не ограниченной справа) и разделена на ячейки, записываются цепочки во входном алфавите (обозначаемом далее т ) так, что буквы цепочки занимают последовательно, начиная с первой и без пропусков, ячейки ленты — по одной букве в каждой ячейке.
Цепочку, записанную таким образом на входной ленте автомата, будем называть входной кепочкой. Блок управления может в каждый момент времени находиться в одном из конечного множества саста,аний (обозначим его через Я), а головка может быть установдена в точности на одну ячейку входной ленты. В таком случае говорят, что автомат обозревает данную ячейку. Автомат, читая входную цепочку, работает по шагам (или по тактам). Пусть в некоторый момент времени автомат обозревает какую-то ячейку ленты, а блок управления находится в некотором состоянии д Е Я. Тактп работпы автпоматпа Входная лента 496 7.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ состоит в том, что в зависимости от содержимого обозреваемой ячейки, состояния д, а также содержимого внутренней памяти автомат сдвигает головку вправо или влево на одну ячейку либо оставляет ее на прежнем месте, его блок управления переходит в некоторое новое состояние г (возможно, что зто состояние совпадет с исходным состоянием д), а содержимое внутренней памяти определенным образом модифицируется. В общем случае автомат может и поменять содержимое той ячейки ленты, которую он обозревает (т.е.
автомат может работать с лентой или только в режиме чтения, не меняя ее содержимого, а лишь определенным образом продвигая головку, или в режиме чтения/записи). Вводят понятие монфивурации авгполеатпа: она определяется состоянием блока управления, содержимым обозреваемой ячейки и содержимым внутренней памяти'. Автомат в общем случае не является детерминированным устройством, т.е.
для него из заданной конфигурации возможны переходы в несколько различных конфигураций. Правила, согласно которым автомат переходит из одной конфигурации в другую, составляют в совокупности его сисгпему ыолеонд аептоматпв. Каждая команда разрешает переход из некоторой конфигурации в какую-то другую конфигурацию. Это напоминает игру, например шахматную, когда нз текущей позиции на доске можно, сделав ход, получить новую позицию — одну из множества всех позиций, в которые можно попасть из текущей позиции, сделав ход согласно правилам игры. В данном случае правила игры аналогичны системе команд, а позиция на доске — конфигурации автомата.
Автоматы классифицируются в соответствии со структурой своей внутренней памяти, с режимом работы с лентой (только чтение или чтение/запись), а также с типом движения *дал автоматов конкретных классов понатие конфигурации несколько модифицируется: так, например, в конфигурацию входит не только символ обоэреваемой ачейки, но и вел подцепочка входной цепочки, включаюпны символ обозреваемой лчейки и все символы справа от него.
7.о. Конечные автоматы. Теорема Канин 497 головки по ленте (одностороннее, двусторонее,число ячеек,на которые эа один такт можно сдвинуть головку). Множество команд предполагается конечным, т.е. автомат, как и грамматнка, имеет конечное описание. Представим теперь следующую ситуацию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
