dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 67
Текст из файла (страница 67)
КС-языки замкнуты относительно операции “пересечение с регулярным языком”. Формальное утверждение иего доказательство представлены в следующей теореме.Теорема 7.27. Если L — КС-язык, а R — регулярный язык, то L I R является КСязыком.Доказательство. Нам понадобится представление КС-языков с помощью МПавтоматов, а также конечноавтоматное представление регулярных языков.
Данное доказательство обобщает доказательство теоремы 4.8, где для получения пересечениярегулярных языков “параллельно запускались” два конечных автомата. Здесь конечный автомат запускается параллельно с МП-автоматом, и в результате получается ещеодин МП-автомат (рис. 7.9).СостояниеКАИВходДопустить/отвергнутьСостояниеМПАМагазинРис. 7.9. Для создания нового МП-автомата конечный автомати МП-автомат запускаются параллельно7.3. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 299299Формально, пустьP = (QP, Σ, Γ, δP, qP, Z0, FP) —МП-автомат, допускающий L по заключительному состоянию, и пустьA = (QA, Σ, δA, qA, FA) —ДКА для R.
Построим МП-автоматP′ = (QP × QA, Σ, Γ, δ, (qP, qA), Z0, FP × FA),∧где δ((q, p), a, X) определяется как множество всех пар ((r, s), γ), где s = δ A(p, a) и пара(r, γ) принадлежит δP(q, A, X).Таким образом, для каждого перехода МП-автомата P мы можем совершить такой жепереход в МП-автомате P′, дополнительно отслеживая состояние ДКА A во втором компоненте состояния P′. Отметим, что a может быть символом из Σ или ε. В первом случае∧∧δ A(p, a) = δA(p, a), но если a = ε, то δ A(p, a) = p, т.е. A не меняет состояние, когда P совершает ε-переход.С помощью простой индукции по числу переходов, совершаемых МП-автоматами,**PP′нетрудно доказать, что (qP, w, Z0) |− (q, ε, γ) тогда и только тогда, когда ((qP, qA), w, Z0) |−∧((q, p), ε, γ), где p = δ A(p, w).
Эти индукции оставляются в качестве упражнения. Но(q, p) является допускающим состоянием P′ тогда и только тогда, когда q — допускающее состояние P и p — допускающее состояние A. Отсюда заключаем, что P′ допускаетw тогда и только тогда, когда его допускают P и A вместе, т.е. w принадлежит L I R. Пример 7.28. На рис. 6.6 был определен МП-автомат F, допускающий по заключительному состоянию множество цепочек, которые состоят из i и e. Такие цепочкипредставляют минимальные нарушения правил, определяющих, в каком порядке словаif и else могут встречаться в С-программах. Назовем этот язык L. МП-автомат Fбыл определен так:PF = ({p, q, r}, {i, e}, {Z, X0}, δF, p, X0, {r}),где δF состоит из следующих правил.1.δF(p, ε, X0) = {(q, ZX0)}.2.δF(q, i, Z) = {(q, ZZ)}.3.δF(q, e, Z) = {(q, ε)}.4.δF(q, e, X0) = {(r, ε)}.Теперь определим конечный автоматA = ({s, t}, {i, e}, δA, s, {s, t}),300Стр.
300ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂдопускающий цепочки языка i*e*, т.е. все цепочки, в которых символы e следуют за i. Назовем этот язык R. Функция переходов δA определяется следующими правилами:а) δA(s, i) = s;б) δA(s, e) = t;в) δA(t, e) = t.Строго говоря, A не является ДКА, как предполагается в теореме 7.27, поскольку в немотсутствует дьявольское состояние для случая, когда вход i получен в состоянии t. Однако такая же конструкция работает даже для НКА, так как МП-автомат, который строится,может быть недетерминированным. В данном же случае МП-автомат на самом деле детерминирован, хотя и “умирает” на некоторых входных последовательностях.Построим следующий МП-автомат.P = ({p, q, r} × {s, t}, {i, e}, {Z, X0}, δ, (p, s), X0, {r} × {s, t})Переходы δ перечислены ниже и проиндексированы номерами правил для МП-автоматаF (числа от 1 до 4) и правил для ДКА A (буквы а, б, в).
Если МП-автомат F совершает εпереход, правило для A не используется. Отметим, что правила для автомата P строятся“ленивым” способом: правила для состояния строятся только тогда, когда обнаружено,что оно достигается из начального состояния P.1. δ((p, s), ε, X0) = {((q, s), ZX0)}.2, а. δ((q, s), i, Z) = {((q, s), ZZ)}.3, б. δ((q, s), e, Z) = {((q, t), ε)}.4. δ((q, s), ε, X0) = {(r, s), ε)}. Отметим, что это правило никогда не будет применяться,поскольку невозможно вытолкнуть символ из магазина без e на входе, но как толькоP видит e, вторым компонентом его состояния становится t.3, в.
δ((q, t), e, Z) = {((q, t), ε)}.4. δ((q, t), ε, X0) = {((r, t), ε)}.Язык L I R представляет собой множество цепочек с некоторым количеством симво-лов i, за которыми записаны символы e (на один больше), т.е. {inen+1 | n ≥ 0}. Как видим,такие блоки символов i с блоками символов e нарушают правила записи слов if и elseв языке С. Этот язык, очевидно, является КС-языком, порождаемым грамматикой с продукциями S → iSe | e.Заметим, что МП-автомат P допускает язык L I R. После помещения Z в магазин онзаносит новые символы Z в магазин при чтении символов i, оставаясь в состоянии (q, s).Как только на входе появляется e, он переходит в состояние (q, t) и начинает выталкивание из магазина.
Он умирает, если видит i до того, как X0 оказывается на вершине магазина. В последнем же случае он спонтанно переходит в состояние (r, t) и допускает. 7.3. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 301301Поскольку КС-языки не замкнуты по пересечению, но замкнуты по пересечению срегулярным языком, то становятся понятными и свойства замкнутости относительноопераций разности и дополнения. Перечислим эти свойства в следующей теореме.Теорема 7.29.
Пусть L1, L2 и L обозначают КС-языки, а R — регулярный язык. Справедливы следующие утверждения.1.L – R является контекстно-свободным языком.2.L может не быть КС-языком.3.L1 – L2 может не быть КС-языком.Доказательство. Для п. 1 заметим, что L – R = L I R . Если R регулярно, то по тео-реме 4.5 регулярно и R . Тогда по теореме 7.27 L – R — КС-язык.Для п. 2 предположим, что если L является КС-языком, то L — КС-язык. Но поскольку L1 I L2 = L1 ∪ L2 , и КС-языки замкнуты по объединению, получаем, что онизамкнуты и по пересечению.
Однако это невозможно (см. пример 7.26).Наконец, докажем п. 3. Очевидно, Σ* является КС-языком для любого алфавита Σ; нетрудно построить КС-грамматику или МП-автомат для этого регулярного языка. Такимобразом, если бы язык L1 – L2 был контекстно-свободным для любых КС-языков L1 и L2,то и Σ* – L должен быть КС-языком, если L — КС-язык. Однако Σ* – L = L при соответствующем алфавите Σ. Полученное противоречие к утверждению 2 доказывает, что L1 –L2 не обязательно является КС-языком. 7.3.5. Îáðàòíûé ãîìîìîðôèçìВспомним операцию “обратного гомоморфизма” из раздела 4.2.4.
Если h — гомоморфизм, а L — произвольный язык, то h–1(L) представляет собой множество таких цепочек w, для которых h(w) ∈ L. Доказательство того, что регулярные языки замкнуты относительно обратного гомоморфизма, представлено на рис. 4.6. Там показано, как строится конечный автомат, обрабатывающий свои входные символы a путем применения кним гомоморфизма h и имитации другого конечного автомата на цепочках h(a).Замкнутость относительно обратного гомоморфизма можно доказать подобным путем, используя МП-автоматы вместо конечных автоматов. Однако при использованииМП-автоматов возникает проблема, которой не было с конечными автоматами. Действиеконечного автомата при обработке входной цепочки заключается в изменении состояния,и это выглядит так же, как переход по одиночному входному символу.Однако для МП-автоматов последовательность переходов может быть не похожа напереход по одному входному символу.
В частности, за n переходов МП-автомат можетвытолкнуть n символов из своего магазина, тогда как при одном переходе выталкиваетсятолько один. Таким образом, конструкция МП-автоматов, аналогичная представленнойна рис. 4.6, будет существенно сложнее; она изображена эскизно на рис. 7.10. Дополни302Стр. 302ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂтельная ключевая идея заключается в том, что, когда прочитан вход a, цепочка h(a) помещается в “буфер”. Символы h(a) используются по одному и подаются на вход имитируемому МП-автомату. Когда буфер опустошается, основной МП-автомат читает свойследующий входной символ и применяет гомоморфизм к нему. Эта конструкция уточняется в следующей теореме.БуферВходahh(a)СостояниеМПАДопустить/отвергнутьМагазинРис.
7.10. Построение МП-автомата, допускающего обратный гомоморфизмтого, что допускает данный МП-автоматТеорема 7.30. Пусть L — КС-язык, h — гомоморфизм. Тогда h–1(L) является КСязыком.Доказательство. Пусть h применяется к символам из алфавита Σ и порождает цепочки из T*. Предположим также, что L — язык в алфавите T, допускаемый по заключительному состоянию МП-автоматом P = (Q, T, Γ, δ, q0, Z0, F). Построим следующий новыйМП-автомат P′.P′ = (Q′, Σ, Γ, δ′, (q0, ε), Z0, F × {ε})(7.1)Обозначения в определении P′ имеют следующий смысл.1.Q′ есть множество пар (q, x), где q — состояние из Q, а x — суффикс (не обязательнособственный) некоторой цепочки h(a) для символа a из Σ. Таким образом, первыйкомпонент состояния P′ является состоянием P, а второй — компонентом буфера.Предполагается, что буфер периодически загружается цепочкой h(a), а затем сокращается с головы по мере чтения его символов, которые подаются на вход имитируемому МП-автомату P.7.3.
ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 303303δ′ определяется следующими правилами:2.а) δ′((q, ε), a, X) = {((q, h(a)), X)} для всех символов a из Σ, всех состояний q изQ и магазинных символов X из Γ. Отметим, что здесь a не может быть ε. Когда буфер пуст, P′ может прочитать свой следующий входной символ a и поместить h(a) в буфер;б) если δ(q, b, X) содержит (p, γ), где b ∈ T или b = ε, то δ′((q, bx), ε, X) содержит((p, x), γ). Таким образом, P′ всегда имеет возможность имитации перехода P,используя голову буфера. Если b ∈ T, то буфер должен быть непустым, ноесли b = ε, то буфер может быть пустым.3.Отметим, что в соответствии с определением (7.1) начальным состоянием P′ является (q0, ε), т.е.
P′ стартует в начальном состоянии P с пустым буфером.4.Аналогично, допускающими состояниями P′ являются такие состояния (q, ε), у которых q — допускающее состояние P.Следующее утверждение характеризует взаимосвязь P′ и P.**PP′• (q0, h(w), Z0) |− (p, ε, γ) тогда и только тогда, когда ((q0, ε), w, Z0) |− ((p, ε), ε, γ).Доказательство в обоих направлениях проводится индукцией по числу переходов, совершаемых автоматами. При доказательстве достаточности заметим, что если буфер P′не пуст, то он не может читать свой следующий входной символ, а должен имитироватьP до тех пор, пока буфер не опустошится (хотя когда буфер пуст, он все еще может имитировать P).
Детали оставляются в качестве упражнения.Приняв указанную взаимосвязь P и P′, заметим, что вследствие способа, которым определены допускающие состояния P′, P допускает h(w) тогда и только тогда, когда P′ допускает w. Таким образом, L(P′) = h–1(L(P)). 7.3.6. Óïðàæíåíèÿ ê ðàçäåëó 7.37.3.1.Докажите, что КС-языки замкнуты относительно следующих операций:а) (∗) Init, определенная в упражнении 4.2.6, в. Указание. Начните с НФХграмматики для языка L;б) (∗!) операция L/a, определенная в упражнении 4.2.2. Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
