Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 34
Текст из файла (страница 34)
Если бы некоторые переходы отсутствовали, то определенные цепочки не вели бы ни в допускающее, ни в недопускающее состояния автомата А, т.е. отсутствовали бы как в ЦА), так и ЦВ). К счастью, ДКА определен так, что в любом состоянии у него есть переход ло каждому символу алфавита Х, так что каждая цепочка приводит в состояние либо изб;либо из Д-Р'. Пример 4.6.
Пусть А — автомат, изображенный на рис. 2.14. Напомним, что этот ДКА допускает те и только те цепочки символов 0 и 1, которые заканчиваются на 01. В терминах регулярных выражений 1.(А) =(0 + 1) 01. Таким образом, дополнение к 1(А) содержит все те цепочки из нулей и единиц, которые не заканчиваются на О!. На рис.
4.2 представлен автомат для (О, 1) — ЦА). Он совпадает с автоматом на рис. 2,14, за исключением того, что допускающие состояния стали недопускающими, а два недопускающих состояния стали допускающими. П Пример 4.7. Используем теорему 4.5 для доказательства нерегулярности определениого языка. В примере 4,2 была доказана нерегулярность языка Е„е, состоящего из цепочек с равными количествами символов 0 и 1. Это доказательство было непосредственным применением леммы о накачке.
Теперь рассмотрим язык М, состоящий из цепочек с неравными количествами нулей и единиц. Нича Рис. 42 ДКА, дояуекающий допоянение языка (д + 1) 01 В данном случае для доказательства нерегулярности языка М лемму о накачке применить трудно. Интуиция подсказывает, что если начать с некоторой цепочки и из М, разбить ее на и =- хух и "накачать" у, то может оказаться, что у — это цепочка вроде 01, в которой поровну символов 0 и 1. В этом случае не существует такого 1г, для которого цепочка ху"з имела бы поровну нулей и единиц, поскольку ху- содержит неравные количества нулей и единиц, а при "накачивании" у эти количества изменяются одинаково. Следовательно, мы не можем использовать лемму о накачке для того, чтобы прийти к противоречию с предположением, что язык М регулярен.
Но все-таки язык М нерегулярен. Объясняется это тем, что М = Хм. Поскольку дополнение к дополнению некоторого множества равно этому же множеству, то Е, = М . 4.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ Если М регулярен, то по теореме 4.5 язык Ум также регулярен. Но мы знаем, что У„лв регулярен, и полученное противоречие доказывает нерегулярность языка М. (.3 Замкнутость относительно пересечении Рассмотрим пересечение двух регулярньгх языков. Здесь почти нечего делать, поскольку операции объединения, дополнения и пересечения не являются независимыми.
Пересечение языков У, и М выражается через объединение и пополнение следующим тождеством. (4.1) ь'г~М = ь' ~ ~М Вообще, пересечение двух множеств — это множество элементов, не принадлежащих дополнениям каждого из ннх. Это замечание, записанное в виде равенства (4.1), представляет один из закаиов УУе Моргана. Другой закон имеет аналогичный вид, только объединение и пересечение меняются местами, т.е. у.
н М = у. л М . Вместе с тем, для пересечения двух регулярных языков можно построить ДКА непосредственно. Такая конструкция, в которой, по существу, параллельно работают два ДКА, весьма полезна сама по себе. Например, она использовалась для построения автомата (см. рис. 2.3), представляющего "произведение" действий двух участников — банка и магазина. Конструкция ироизведения формально представлена в следующей теореме. Теорема 4.8. Если У.
и М вЂ” регулярные языки, то язык У. П М также регулярен. Доказательство. Пусть У. и М вЂ” языки автоматов Аь=Щ,,Е, бс, доРь) и Аи= (Дм, Е, бкьгуььгм). Заметим, что алфавиты автоматов считаются одинаковыми, т.е. Е есть объединение алфавитов языков У, и М, если эти алфавиты различаются. В действительности конструкция произведения работает для НКА точно так же, как и для ДКА, но для максимального упрощения предположим, что Аг и Ам — ДКА. Для У, П М построим автомат А, моделирующий автоматы Аь и Аи одновременно.
Состояниями автомата А будут пары состояний, первое из которых принадлежит Аь, а второе — Ам. Чтобы построить переходы автомата А, предположим, что он находится в состоянии (р, д), где р — состояние автол1ата Аь а д — состояние Ам. Нам известно, как ведет себя автомат Аъ, получая на входе символ а. Пусть он переходит в состояние в. Также допустим, что автомат Ам по входному символу а совершает переход в состояние ь Тогда следующим состоянием автомата А будет (в, у). Таким образом, автомат А моделирует работу автоматов Аг и Аи, Эта идея в общих чертах представлена на рис.
4.3. Остальные детали доказательства очень просты. Начальным состоянием автомата А будет пара начальных состояний автоматов А~ и Ам. Поскольку автомат А допускает тогда и только тогда, когда допускают оба автомата А~ и Аьь в качестве допускающих состояний автомата А выбираем все пары (р, д), где р — допускающее состояние автомата Аь, а д — Ам.
Формально автомат А определяется как А = Щ х Я~„Е, б, (Ць Ци), (Рь х Рм), где б((р, су), а) = (бь(р, а), бм(су, а)). ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 152 Вход в Начало Допустить Рис. 43. Автомат, имитирующий два других автомата и допускающий тогда и только тогда, когда допускают оба автомата Чтобы увидеть, почему ЦА) =ЦАс)П Р(Ам), сначала заметим, что индукцней по ~и4 легко доказать равенство 6 ((дс, сум), тв) = (6 л(ас, ту), 6 м(сум, ю)). Но А допускает ту тогда и только тогда, когда 6((омам),ту) является парой допускающих состояний, т.е. б л(с)ц ти) должно принадлежать Р;, а 6 м(сум, и) — Рьл Иными словами, цепочка тс допускается автоматом А тогда и только тогда, когда ее допускают оба автомата Ас и Ам.
Итак, А допускает пересечение языковб и М. С) Пример 4.9. На рис. 4.4 представлены два ДКА, Автомат на рис. 4.4, а допускает все цепочки, имеющие О, а автомат на рис. 4.4, б — все цепочки, имеющие 1. На рис. 4.4, в представлен автомат — произведение двух данных автоматов. Его состояния помечены как пары состояний исходных автоматов. Легко доказать, что этот автомат допускает пересечение первых двух языков, т.е. те цепочки, которые содержат как О, так и 1. Состояние рг представляет начальное условие, когда на вход автомата пока не поступили ни О, ни 1. Состояние т)г означает, что поступили только нули, а состояние рв — только единицы. Допускающее состояние с(в представляет условие того, что на вход автомата поступили и нули, и единицы.
С) Замкнутость относительно разности Существует еще одна, четвертая, операция, часто применяемая к множествам и связанная с булевыми операциями, а именно, разность множеств. В терминах языков разностью 1 — М языков 6 и М называют множество цепочек, которые принадлежат Е и не принадлежат М.
Регулярные языки замкнуты относительно втой операции. Доказательство замкнутости относительно разности следует из доказанных выше теорем. 4.2. СВОЙСТВА ЗАМКНУТОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ о,! Нача о,! Нача Начал о,! в) Рис. 4.4. Конструкция произведения Теорема 4.10. Если 1. и М вЂ” регулярные языки, то язык Т. — М также регулярен. Доказательство.
Заметим, что Т, — М = 1,П М . По теореме 4.5 регулярен язык М, а по теореме 4.8 — Е П 14 . Следовательно, язык 1, — Мрегулярен. Е) 4.2.2. Обращение Обращением цепочки а,аз...а„называется цепочка, записанная в обратном порядке, т.е. а„а„о..ап Обращение ж обозначается жк. Таким образом, 0010 есть 0100, а ек = ж Обращение языка Ь, обозначаемое з",~, состоит из всех цепочек, обратных цепочкам языка 4.. Например, если б = (001, 10, 111), то з~ = (100, 01,!! 1). Обращение является еще одной операцией, сохраняющей регулярность языков, т.е. если язык б регулярен, то ь~ также регулярен. Это легко доказать двумя способами, первый из которых основан на автоматах, а второй — на регулярных выражениях.
Доказательство, основанное на автоматах, приводится неформально, так что читатель при желании может восполнить детали. Затем приводится формальное доказательство, исполь- зующее регулярные выражения. Если задан язык Т., который есть ЦА) лля некоторого конечного автомата А, вероятно, с недетерминизмом и е-переходами, то можно построить автомат для Т, следующим образом. !.
Обратить все дуги на диаграмме переходов автомата А. 2. Сделать начальное состояние автомата А единственным допускающим состоянием нового автомата. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 154 3. Создать новое начальное состояние рд с е-переходами во все допускающие состояния автомата А. В результате получим автомат, имитируюший автомат А "в обратном порядке'* и, следовательно, допускающий цепочку и тогда и только тогда, кода А допускает и . Теперь докажем теорему для обрашения формально. Теорема 4.11. Если язык Е регулярен, то язык Ек также регулярен. Доказательство.
Предположим, что язык Е определяется регулярным выражением Е. Доказательство проводится структурной индукцией по длине выражения Е. Покажем, что существует еше одно регулярное выражение Ек, для которого Е(Ек) = (ЦЕ))к, т.е. язык выражения Е является обращением языка выражения Е. Базис, Если Е равно е, И или а, где а — некоторый символ, то Ек совпадает с Е, т.е. (а) = (е),Я = из и (а) = (а). Индукции. В зависимости от вида выражения Е возможны три варианта. 1.
Е = Е, + Ел Тогда Ек = Е~ + Е,к, Доказательство состоит в том, что обРаШение объединения двух языков получается, если сначала вычислить, а затем объединить об- ращения этих языков. 2. Е = ЕзЕь Тогда Е = Е, Е, . Заметим, что необходимо обратить не только сами языки, но и их порядок. Например, если Е(Е~) = (01, 111), а ЦЕ,) = (00, 1О), то ЦЕ,Ез) = (0100, 01!О, 11100, 1!110). Обрашение этого языка есть (00!О, 0110, 00111, О!111).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
