Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 68
Текст из файла (страница 68)
2, а. о((о), «), б 2) = (((7, з), 22)). 3, б. Щ), «), е, 2) = (((д, г), я)) . 4, фд, «), я, Х,) = ((г, «), а)). Отметим, что это правило никогда не будет применяться, поскольку невозможно вытолкнуть символ из магазина без е на входе, но как только Р видит е, вторым компонентом его состояния становится а З, в, б((<), г), е, 2) = (((д, «), я)). 4, Е((д, «), Е, Хо) = И(О Г), Я)). Язык 7.
П Е представляет собой множество цепочек с некоторым количеством символов б за которыми записаны символы е (на один больше), т,е, (Ре" ' ( л > О). Как видим, говне блоки символов ~ с блоками символов е нарушают правила записи слов Тб и е1ве а языке С. Этот язык, очевидно, является КС-языком, порождаемым грамматикой с прояукциями о -о ьзе ~ е.
Заметим, что МП-автомат Р допускает язык 7. П л. После помещения У в магазин он заносит новые символы «в магазин при чтении символов б оставаясь в состоянии (7, «). Как только на входе появляется е, он переходит в состояние (д, г) и начинает выталкивавяе нз магазина. Он умирает, если видит ( до того, как Хо оказывается на вершине магазвяа. В последнем же случае он спонтанно переходит в состояние (г, ~) и допускает. СЗ Поскольку КС-языки не замкнуты по пересечению, но замкнуты по пересечению с рпуляриым языком, то становятся понятными и свойства замкнутости относительно оверацнй разности и дополнения. Перечислим эти свойства в следующей теореме.
2.3. СВОЙСТВА ЗАМКНУТОСТИ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 301 Теорема 7.29. Пусть Еь Е, и Е обозначают КС-языки, а Я вЂ” регулярный язык. Справедливы следующие утверждения. 1. Š— 17 является контекстно-свободным языком. 2. Е может не быть КС-языком. 3. Е~ — Еэ может не быть КС-языком. Доказательство. Для п. 1 заметим, что Š— й=ЕП и. Если й регулярно, то по тео- реме 4.5 регулярно и А .
Тогда по теореме 7.27 Š— Р— КС-язык. Для п. 2 предположим, что если Е является КС-языком, то Š— КС-язык. Но поскольку Е, ПЕ, = Е, нЕ,, и КС-языки замкнуты по объединению, получаем, что они замкнуты и по пересечению. Однако это невозможно (см. пример 7.26). Наконец„докажем п. 3. Очевидно, Х* является КС-языком для любого алфавита з.; нетрудно построить КС-грамматику или МП-автомат для этого регулярного языка. Таким образом, если бы язык Е~ — Еэ был контекстно-свободным для любых КС-языков Е, и Е„ то и Š— Е должен быть КС-языком, если Š— КС-язык.
Однако Х вЂ” Е = Е при соответствующем алфавите Е. Полученное противоречие к утверждению 2 доказывает, что Е~— Е, не обязательно является КС-языком. С) 7.3.5, Обратный гомоморфнзм Вспомним операцию "обратного гомоморфизма" из раздела 4.2.4. Если Ь вЂ” гомоморфизм, а Š— произвольный язык, то 6 '(Е) представляет собой множество таких цепочек эг, для которых Ь(и) и Е.
Доказательство того, что регулярные языки замкнуты относительно обратного гомоморфизма, представлено на рис. 4.6. Там показано, как строится конечный автомат, обрабатывающий свои входные символы а путем применения к ним гомоморфизма Ь и имитации другого конечного автомата на цепочках Ь(а). Замкнутость относительно обратного гомоморфизма можно доказать подобным путем, используя МП-автоматы вместо конечных автоматов. Однако при использовании МП-автоматов возникает проблема, которой не было с конечными автоматами.
Действие конечного автомата при обработке входной цепочки заключается в изменении состояния, и это выглядит так же, как переход по одиночному входному символу. Однако для МП-автоматов последовательность переходов может быть не похожа на переход по одному входному символу. В частности, за и переходов МП-автомат может вытолкнуть л символов из своего магазина, тогда как при одном переходе выталкивается только один. Таким образом, конструкция МП-автоматов, аналогичная представленной на рис. 4.6, будет существенно сложнее; она изображена эскизно на рис. 7.10.
Дополнительная ключевая идея заключается в том, что, когда прочитан вход а, цепочка Ь(а) помещается в "буфер". Символы Ь(а) используются по одному и подаются на вход имитируемому МП-автомату. Когда буфер опустошается, основной МП-автомат читает свой ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 302 Вход Допустить/отвергнуть Рис. 7.!О. Построение дтП-автомата, допускающего обратный гомоморфизм того, нто допускает данный йППавтомат Теорема 7.30.
Пусть Š— КС-язык, !т — гомоморфизм. Тогда гт '(А) является КС- языком. Доказательство. Пусть гг применяется к символам из алфавита г, и порождает цепочек из 1г. Предположим также, что т'. — язык в атфавите Т, допускаемый по заключительввыу состоянию МП-автоматом Р = Я, Г, Г, б, д„2о, Р).
Построим следующий новый 1у)П-автомат Р'. Р' = (Д', гн Г, д, (до„Е), Хо, Р' х ( с) ) Обозначения в определении Р'имеют следующий смысл. (7.1) 1, Д'есть множество пар (д, х), где д — состояние из Д, а х — суффикс (не обязательно собственный) некоторой цепочки Уг(а) для символа а из г,. Таким образом, первый компонент состояния Р' является состоянием Р, а второй — компонентом буфера. Предполагается, что буфер периодически загружается цепочкой Ь(а), а затем сокращается с головы по мере чтения его символов, которые подаются на вход имитируемому МП-автомату Р. б'определяется следующими правилами: !.з.
Овойствл злмкнутости контвкстно-своводных языков ЗОЗ следующий входной символ и применяет гомоморфизм к нему. Эта конструкция уточня- ется в следукнцей теореме. а) 6'((Г(, е), а, Х) = (((д, Ь(а)), Х) ) для всех символов а из Е, всех состояний о из Д и магазинных символов Х из Г.
Отметим, что здесь а не может быть ж Когда буфер пуст, Р' можа~ прочитать свой следующий входной символ а и поместить Ь(а) в буфер; б) если фд, Ь, Х) содержит (Р, у), где Ь и Г или Ь = г., то д'((су, Ьх), д Х) содержит ((р, х), у). Таким образом, Р'всегда имеет возможность имитации перехода Р, используя голову буфера. Если Ь и Т, то буфер должен быть непустым, но если Ь = е, то буфер может быть пустым. 3. Отметим, что в соответствии с определением (7.1) начальным состоянием Р'является (д„е), т,е. Р' стартует в начальном состоянии Р с пустым буфером.
4. Аналогично, допускающими состояниями Р'являются такие состояния (д, е), у которых д — допускающее состояние Р, Следующее утверждение характеризует взаимосвязь Р' и Р. (йо, ь(н') У0) )~ (Р, а у) тогда и только тогда, когда ((йм е), н, с,) ~- ((Р, е), в, у). 7.3.6. Упражнения к разделу 7.3 7.3.1. Докажите, что КС-языки замкнуты относительно следующих операций: а) (ч)Ьй, определенная в упражнении4.2.б,в.
Указание. Начните с НФХ- грамматики для языка Ь; б) (в!) операция Ь/а, определенная в упражнении4.2.2. Указание. Начните с НФХ-грамматики для языка Рл в) (и) Сус!е, определенная в упражнении 4.2.11. Указание. Используйте конструкцию, основанную на МП-автомате. рассмотрим следующие два языка: Ь~ = (а"Ь~ с ( и, т > О) Ьз= (а"Ь с~ ) и, т>0) 7.3.2.
ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 304 Доказательство в обоих направлениях проводится индукцией по числу переходов, совершаемых автоматами. Прн доказательстве достаточности заметим, что если буфер Р' не пуст, то он не может читать свой следующий входной символ, а должен имитировать Р до тех пор, пока буфер не опустошится (хотя когда буфер пуст, он все еще может имитировать Р). Детали оставляются в качестве упражнения. Приняв указанную взаимосвязь Р и Р; заметим, что вследствие способа, которым определены допускающие состояния Р; Р допускает Ь(ж) тогда и только тогда, когда Р'допускает гг.
Таким образом, Ь(Р') = Ь '(Ь(Р)). П а) покажите, что каждый из них является контекстно-свободным, построив для них КС-грамматики; б) (!) укажите, является ли Е, () Ез КС-языком. Ответ обоснуйте. 7.3.3. (1!) Покажите, что КС-языки не заико)злы относительно следующих операций: а) (э) Мпь определенная в упражнении 4.2.6, гй б) Мах, определенная в упражнении 4.2.6, б; в) На(Е определенная в упражнении 4.2.8; г) А16 определенная в упражнении 42.7.
7,3.4. олифе (Перемешивпнне) двух цепочек зг и х является множеством всех цепочек, которые можно получить путем произвольного чередования позиций ю и х. Точнее, арифе(ш, х) есть множество цепочек, обладающих следующими свойствами. 1. Каждая позиция может быть назначена и или х, но не обеим сразу. 2. Позиции ж назначенные ш, при чтении слева направо образуют и. 3. Позиции з, назначенные х, при чтении слева направо образуютх. Например, если и = 01 и х = 110, то злифе(01, 110) есть множество цепочек (01110, 01101, 10110, 10101, 11010, 11001). Для иллюстрации рассмотрим цепочку 10110.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
