Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 27
Текст из файла (страница 27)
3,1, показав, что любой язык Ц являющийся языком ЦЕ) для некоторого регулярного выражения Е, будет также языком ЦЕ) для некоторого е-НКА Е. Это доказательство проведем методом структурной индукции по выражению Е. Сначала покажем, как строить автоматы для базовых выражений: отдельных символов, в и О. Затем опишем, каким образом объединять эти автоматы в большие автоматы, которые допускают объединение, конкатенацию или итерацию языков, допускаемых меньшими автоматами. Все конструируемые автоматы представляют собой е-НКА с одним допускающим со- стоянием. Теорема 3.7.
Любой язык, определяемый регулярным выражением, можно задать некоторым конечным автоматом. Доказательство. Предположим, что Е = ЦЕ) для регулярного выражения Е. Покажем, что Е = ЦЕ) для некоторого к-НКА Е, облалаюшего следующими свойствами. !. Он имеет ровно одно допускающее состояние.
2. У него нет дуг, ведущих в начальное состояние. 3. У него нет дуг, выходящих из допускающего состояния. Доказательство проводится структурной индукцией по выражению Л', следуя рекурсивному определению регулярных выражений из раздела 3.1.2. Базис. Базис состоит из трех частей, представленных на рис.
3.1б. В части (а) рассматривается выражение е Языком такого автомата является (в), поскольку единственный путь из начального в допускающее состояние помечен выражением к. В части (б) показана конструкция для О. Понятно, что, поскольку отсутствуют пути из начального состояния в допускающее, языком этого автомата будет О. Наконец, в части (в) представлен автомат для регулярного выражения а.
Очевидно, что язык этого автомата состоит из одной цепочки а и равен Е(в). Кроме того, все эти автоматы удовлетворяют условиям (1), (2) и (3) индуктивной гипотезы. ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 120 б) Рас. 3. )б. Базис построения автомата по регулярному выражению Индукции. Три части индукции представлены на рис.
3.!7. Предположим, что утверждение теоремы истинно для непосредственных подвыражений данного регулярного выражения, т.е. языки этих подвыражений являются также языками е-НКА с единственным допускающим состоянием. Возможны четыре случая. 1. Данное выражение имеет вид и + 5 для некоторых подвыражений Рс и 5. Тогда ему соответствует автомат, представленный на рис. 3.17, а. В этом автомате из нового начального состояния можно перейти в начальное состояние автомата для выражения либо л, либо 5.
Затем мы попадаем в допускающее состояние одного из этих автоматов, следуя по пути, помеченному некоторой цепочкой из языка Цй) или ЦБ), соответственно. Попав в допускающее состояние автомата для )г или 5, можно по одному из к-путей перейти в допускающее состояние нового автомата. Следователь- но, язык автомата, представленного иа рис.
3.17, а, равен Цй) 0 Цо). 2. Выражение имеет вид Ж для некоторых подвыражений и и Б. Автомат для этой конкатенации представлен на рис. 3.17, б. Отметим, что начальное состояние первого автомата становится начальным состоянчем для всего автомата, представляющего конкатенацию, а допускающим для него будет допускающее состояние второго автомата. Идея состоит в том, что путь, ведущий из начального в допускающее состояние, сначала проходит через автомат для й по некоторому пути, помеченному цепочкой из Ц)7), а потом — через автомат для 5 по пути, помеченному цепочкой из ЦБ).
Следовательно, путями автомата, представленного на рис. 3.17, б, будут те и только те пути, которые помечены цепочками из языка Цк)ЦБ). 3. Выражение имеет вид 71 для некоторого подвыражения 71. Используем автомат, пред- ставленный на рис. 3.17, в. Этот автомат позволяет пройти по следующим путям: 3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 121 а) из начального состояния непосредственно в допускающее по пути, помеченному н Этот путь позволяет допустить цепочку е, которая принадлежит ЦЕ ) независимо от выражения )е; б) перейти в начальное состояние автомата для Л, пройти через зтот автомат один или несколько раз, и затем попасть в допускающее состояние.
Это множество путей дает возможность лопускать цепочки, которые принадлежат языкам ЦЯ), ЦКУАК), Це)))ЦЯ)Ц)е) и так далее, порождая таким образом все цепочки из Ц)г ), за исключением, возможно, цепочки н Но она получена в п. 3, а как отметка дуги непосредственно из начального в допускающее состояние. 4. Выражение имеет вид (Л) для некоторого подвыражения А'.
Автомат для й может быть автоматом и для ()г), поскольку скобки не влияют на язык, задаваемый выражением. О в) в) Рис. 317. Индуктивный гиаг нреабразования регулярного выражения в воКА Легко заметить, что построенные автоматы удовлетворяют всем трем условиям ин- дуктивной гипотезы: одно допускающее состояние, отсутствие дуг, ведущих в начальное состояние, и дуг, выходящих из допускающего состояния. П ГЛАВА 3.
РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 122 Пример 3.8. Преобразуем регулярное выражение (О ч- 1) 1(О ч- 1) в в-НКА. Построим сначала автомат для О ч- 1. Для этого используем два автомата, построенные согласно рис. 3.16, в: один с меткой О на дуге, другой — с меткой 1. Эти автоматы соединены с помощью конструкции объединения (см. рис. 3.!7, а), Результат изображен на рис. 3.18, а. а) б) Начало в) Рис. Х!8. Автомат, построенный дяя примера 3.8 Далее, применим к автомату (см. рис, 3.!8, а) конструкцию итерации (см. рис. 3.17, в).
Полученный автомат изображен на рис. 3.18, 6. На последних двух шагах применяется конструкция конкатенации (см, рис. 3.17, б). Сначала автомат, представленный на рис. 3.!8, б, соединяется с автоматом, допускаюгцим только цепочку !. Последний получается путем еще одного применения базисной конструк- 3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 123 ции (см. рис. 3.16, в) с меткой 1 на дуге. Отметим, что для распознавания цепочки 1 необходимо создать новый автомат; здесь нельзя использовать автомат для 1, являющийся частью автомата, изображенного на рис. 3.18, а.
Третьим автоматом в конкатенации будет еше один автомат для выражения О + !. Опять-таки, необходимо создать копию автомата (см. рис, 3.18, а), поскольку нельзя использовать автомат для 0 + 1, представляющий собой часть автомата (см. рис, 3.18, б). Полный автомат показан на рис. 3.18, в. Заметим, что если удалить а-переходы, то этот г-НКА будет весьма похож на более простой автомат !см. рис.
3.15), также допускающий цепочки с! на предпоследней позиции. П 3.2.4. Упражнения к разделу 3.2 3.2.!. ДКА представлен следующей таблицей переходов; а) (в) выпишите все регулярные выражения й„"'. Замечание. Состояние у можно рассматривать как состояние с целым номером 8 б) (в) выпишите все регулярные выражения З!1". Постарайтесь максимально упростить эти выражения; в) выпиши~с все регулярные выражения л„'". Постарайтесь максимально упростить эти выражения; г) напишите регулярное выражение для языка заданного автомата; д) (в) постройте диаграмму переходов для этого ДКА и напишите регулярное выРаженис длЯ его Языка, исключив состоЯние Ем 3.2.2. Повторите упражнение 3.2.1 для следующего ДКА.
Отметим, что решения для пунктов а, 6 и д непригодны в данном упражнении. 3.2.3. Преобразуйте следующий ДКА в регулярное выражение, используя технику исключения состояний из раздела 3.2.2. ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 124 3.2.4. Преобразуйте следующие регулярные выражения в НКА с а-переходами; а) (а) 01 б) (О + 1)01; в) 00(0 + 1) . (!) Пусть А = Я, Х, 6, зм (с)г)) — это такой а-НКА, в котором нет переходов в состояние д, и из состояния дя Опишите язык, допускаемый каждой из следую- щих модификаций автомата А (в терминах языка 1. = ЦА)): 3.2.6. а) (я) автомат, образованный по А путем добавления 'а-перехода из гл в до,.
б) Гя) автомат, построенный по А с помощью добавления а-перехода из состояния ггя в каждое состояние, достижимое из <уа (по путям, метки которых могут содержать как символы из а,, так и а); в) автомат, полученный по А посредством добавления гиперехода в дг из каждого состояния, из которого по какому-либо пути достижимо Еб г) автомат, построенный по А путем одновременного выполнения пунктов б и в.
3.2.7. П!) Существует несколько упрощений конструкции теоремы 3.7, в которой регулярное выражение преобразовывалось в а-НКА. Вот три из них. 1. Для оператора объединения вместо создания новых начального и допускающего состояний можно сгруппировать оба начальных состояния в одно, сохранив все их переходы. Аналогично, можно сгруппировать оба допускающих состояния в одно; к нему ведут все переходы, которые вели к каждому из исходных состояний.
2. Для оператора конкатенации можно объединять допускающее состояние первого автомата с начальным состоянием второго. 3. Для оператора итерации можно просто добавить с-переходы из допускающего состояния в начальное, и наоборот. В результате каждого из этих упрощений мы по-прежнему получаем правильную конструкцию, т.е. искомый а-НКА, который для любого регулярного выра- 3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 125 3.2.5. Исключите л-переходы из НКА, полученных вами в упражнении 3.2.4. Решение для пункта а можно найти на %еЬ-страницах этой книги, жения допускает язык этого выражения. Сочетание каких усовершенствований (1, 2 или 3) можно применить к этой конструкции, чтобы в результате получался правильный автомат для любого регулярного выражения? 3.2.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
