Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 29
Текст из файла (страница 29)
Множество всех достижимых состояний автомата М' вместе с функцией 6' приведено на рис. 2.4. Начальным состоянием автомата М' является А, а множество заключительных состояний — (Е, Н, 1, К, М, У, Р). Е) !40 2.2.4. Конечные автоматы н регулярные множестве Покажем, что язык является регулярным множеством тогда и только тогда, когда он определяется конечным автоматом. Для этого мы докажем сначала, что конечпо-автоматный язык определяется праволииейиой грамматикой, а затем — что множество конечио-автоматных языков содержит языки 8, (е), (а) для всех символов а и замкнуто относительно объединения, конкатенации и итерации. Таким образом, каждое регулярное множество оказывается конечно-автоматным языком. Лемма 2,8.
Если Е=1.(М) для некоторого конечного аепгсмата М, тп 1. = Е (6) для некоторой праволинейной грамматики б. Доказательство. Пусть М=(!г, Х, 6, а„р) — конечный автомат (детсрминированный, разумеется). Возьмем грамматику 6'= — ((г, г., Р, д,), где Р определяется так: (1) Если 6(а, а) =г, то Р содержит правило а- аг. (2) Если р ЕР, то р — еЕ Р. Можно показать, что каждый шаг вывода в грамматике б имитирует такт автомата М.
Докажем индукцией по !', что (2.2.17) а=>'+'!е для дЕ!г тогда и только тогда, когда (а, те) ) — ' (г, е) для некоторого г Е Р, Базис. Для ! =О очевидно, что 4 ~с тогда и только тогда, когда (д, е) ) — "(д, е) для дар. Шаг индукции. Предположим, что (2.2,17) истинно для 4, и возьмем в==ах, где !х)=!. Тогда т)~а+'ю равносильно тому, что у~аз~'ах для некоторого зЕЯ. Но д=>аз равносильно 6(а, а) =- з. По предположению индукции з~'х тогда и только тогда, когда (в, х) ! — ' ' (г, е) для некоторого г Е Р. Следовательно, а=>п"т ап равносильно (а, !и) ) — ' (г, е) для некоторого г ЕР.
Итак, утверждение (2.2.17) истинно для всех 1~~0. Отсюда заключаем, что аа ~ !в тогда и только тогда, когда (у„ю)) — *(г, е) для некоторого гЕР. Таким образом, Е(6) = Е (М). Е) Лемма 2.9. Луста Х вЂ” конечный алфавип!. Мнолсеспгва (!) 8, (й) (е) и (ш) (а) д.гя всех а Е В явлжотся конечно-автоматными языками. Доказательство. (!) Любой конечный автомат с пустым множеством заключительных состояний допускает !3!. (1!) Пусть М=((д,), Х, 6, д„(д,)), где 6(д„а) ие определено ни для каких аЕХ. Тогда Е(М) =(е).
!4! ГЛ. З, ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ УПРАЖИЕ НИЯ (Ш) ПуетЬ М=-((дм д,), Х„б, дм (д,)), ГдЕ 6(и„а)=до а в остальных случаях функция 6 не определена. Тогда Е (М) — -- (а). Лемма 2.10. Пусть Е,=Е(М,) и Е,=.Е(М,) для конечных автоматов М, и М,. Множества (1) Е,ОЕ„(О) Е.,Е, и (!О) Е," являются конечно-автоматными языками Доказательство. Пусть М,=(Я, Х 6, у, Г ) и М, = Е,б,, Р— 1 у~ ~) и 2 (Дм, л, О„Г,). Без потери общности можно считать, что 1Е, 01Е,= Йл, так как в противном случае состояния можно было бы переименовать. (1) Усть М = (1~~1~ 0 Ов 0 (чо), Б, 6> д„р) — недетерминирован- ный конечный автомат, где (1) о,— новое состояние, (2) Г=Г,ОГ„если в~Е,ОЕ„И Г=-Г ОГ 0(о ) если (3) (а) 6(о, а) =6(до а)0 6(д„а) для всех а Е2, (б) 6(у, а) =:6,(д, а) для всех у ~Я, и аЕ Х, (в) 6(о, а)=6,(о, а) для всех ОРИ, и аЕ а, Таким образом, автомат М вначале как бы угадывает, какой мии в из автоматов М„М, ему моделировать.
Так как М— иро анный автомат, то фактически он моделирует и тот, и а †недетер- другой. Можно показать индукпией по 1-л 1, что (о„гв) ) — 'м (о, е) тОГда И ТОЛЬКО тОГда, КОГда у Р Е)а И (у1, и) ) — 'М,(д, В) ИЛИ дЕ14, и (дм в) ~ — м,(д, е). Отсюда и из определения множества Г вы- текает, что Е(М) =Е(М„) 0Е. (М,). (О) Чтобы построить конечный автомат М, распозн Язык Е,Е,„полОжим М=(Я,О Ям Е, 6, У„Г), гле аспознающий Г„если д, ( Гл, Г,ОГ„если У,ЕГН а функция 6 определяется равенствами (1) 6 (д, а) = 6, (д, а) для всех д Е (е, — Г1, (2) 6(д, а) =6,(О, а) 06,(ом а) дли всех оЕ Г, (3) 6 (д, а) = 6, (о, а) для всех о К 1Е,. Таким образом, М начинает работать, моделируя М,. Когда М та „, он может достигает заключительного состояния автома а М, недетерминированно вообразить, что находится в начальном состоянии автомата М, (равенство (2)), и модели овать М .
и уЕЕ,. Тогда (ом ху) ( — 'м(о, у) для некоторого дар,. Если х=е, то о=о„. Если уФе, то, применяя один раз равенство (2) и нуль или более раз равенство (3), 1голучаем (о, у) ) — 'м(г, е) для некоторого г Ерм Если у=в, то дар, так как у,ЕГН Отсюда хуЕЕ. (М). Допустим, что шЕЕ(М).
Тогда 142 (Ч1 ю)( — "м(у, е) для некоторого дар. Рассмотрим отдельно два случая: д ~ Г, и дар,. Пусть д Е Г,. Тогда ю — хау для некоторого а Е 2, удовлетворяющего условиям (у„хау) ) — *м (г, ау) у-м (з, у) '— 'м (д, е) где г Е Г„в Е 1с', и 6, (г, а) содержит з. Следовательно, х Е Е, и ауЕЕ, Пусть теперь дЕГ,. Тогда д,ЕГ„и еЕЕ,. Таким образом, шЕЕ, Отсюда заключаем, что Е.(М)=Е,Е,. (ш) Построим автомат М=- (1с,0(д')„Х, 6, д', Г,О(д')), где о' — новое состояние, ие принадлежащее Я„который допускает язык Ц.
Определим функцию 6 равенствами (1) 6(д, а)=-6,(у, а), если д ЕЕ) — Г, и або, (2) 6(д, а)-.:..6,(д, а) 06,(дм а), если у ЕГ, и аЕ2, (3) 6(ц', а) =6,(д, а) для аЕ Х. Таким образом, когда М попадает в заключительное состояние автомата М„он может на выбор либо продолжать моделирование М„ либо начать заново моделирование М, с начального состояния. Доказательство того, что Е.(М) =.-Е.,", аналогично доказательству части (й).
Заметим, что в ЕЕ (М), так как у'— заключнтельиое состояние. () Теорема 2.4. Язык допускается конечным автоматом тогда и только тогда, когда он является регулярным множеством, До к аз а тел ь ство. Теорема непосредственно следует из теоремы 2.2 и лемм 2.8 — 2.10. () 2.2.5. Резюме Результаты разд. 2,2 можно сформулировать в виде следую- щей теоремы. Теорема 2.5. Утвврждвния (1) Е. — регулярное лсножество, (2) 1 — праволинейный язык, (3) Е.— конвчно-овтонолпный язык, (4) Š— нвдетвриинированный конечно-автоматный язык, (5) Е.
обозначается регулярным выражением зквивалентны ( ) УПРАЖНЕНИЯ 2.2.1. Какие из следующих множеств регулярны? Для тех, которые регулярны, напишите регулярные выражения. (а) Множество цепочек с равным числом нулей и единиц. (б) Множество цепочек из (О, 11' с четным числом нулей н нечетным числом единиц.
143 ГЛ. Э. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ упРАжне ния А- В|С В вЂ” ОВ ! 1В ! 011 С вЂ” 017)1С)е Р— ОС)1В !45 (в) Множество цепочек из (О, 1)', длины которых делятся на 3. (г) Множество цепочек пз (О, 1)", не содержащих подцепочки 101. 2.2.2. Покажите, что множество регулярных выражений в алфавите Х является КС-языком. 2.2.3.
Покажите, что если 7.— произвольное регулярное множество, то существует бесконечно много регулярных выражений, обозначающих В. 2.2.4. Пусть 7.— регулярное множество. Прямо из определения регулярного множества получите, что 7.а — регулярное множество. Указание: Докажите это индукцией по числу применений определения регулярного множества, использованных прн' построении 7. как регулярного множества. 2.2.5. Докажите следующие тождества для произвольных регулярных выражений а, 5 и у: (а) и ((1 + у) ==- сф + ссу, (ж) (а+()) у= ау+137, (б) и+(()+у)=(и+())+7 (з) Я"=е, (в) и(ру) (йр)у, (н) а'=и=и', (г) ае=еа=-и, (к) (а')" =а", (д) Да= ао = 8, (л) (а+())'= (и'(Р)', (е) сс + сс -.- а, (м) а+ 8 = а. 2.2.6.
Решите систему уравнений с регулярными коэффи- циентами А,--(01*+1) А,+А, А., =- 11+ 1А, + ООА, А,=е — А,+А, 2.2.7. Рассмотрите уравнение (2.2. ГВ) Х = иХ+(1 где и и 11 — регулярные выражения в алфавите Х и Х(Х. Покажите, что (а) если е(а, то Х вЂ” а'5 — единственное решение уравнепия (2.2.18); (б) если е ~ а, то а*5 — наименьшая неподвижная точка уравнения (2.2.18), но решений бесконечно много; (в) в любом случае каждое решение уравнения (2.2.18) имеет вид а" ((1(1Ь), где 7.— некоторый (не обязательно регулярный) язык. 2.2.8.
Решите стандартную систему, состоящую из двух уравнений общего вида Х= — и,Х+а,)'+ив 1 =~,сХ+йс1.+~с' 2.2.9. Восполните детали доказательства леммы 2.4. 2.2.10, Докажите лемму 2.5. 2.2.11. Найдите праволинейные грамматики для тех множеств упр. 2.2.1, которые регулярны. Определение. Грамматика 6=(Р1, Е, Р, В) называется лево- линейной, если каждое правило множества Р имеет вид А — Все или А- св, 2.2.12.
Покажите, что язык является регулярным множеством тогда и только тогда, когда он порождается леволинейной грамматикой. Укаэание: Воспользуйтесь упр. 2.2.4. Определение. Праволииейная грамматика 6=(71, г'„Р, В) называется регулярной (нли автоматной), если (1) все ее правила, эа исключением  — е, имеют вид А — аВ илн А- а, где В~!э', а~И, (2) если  — е принадлежит Р, то В не встречается в правых частях правил.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
