dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 68
Текст из файла (страница 68)
Начните сНФХ-грамматики для языка L;в) (!!) Cycle, определенная в упражнении 4.2.11. Указание. Используйте конструкцию, основанную на МП-автомате.7.3.2.Рассмотрим следующие два языка:L1 = {anb2ncm | n, m ≥ 0}L2 = {anbmc2m | n, m ≥ 0}304Стр. 304ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂа) покажите, что каждый из них является контекстно-свободным, построив дляних КС-грамматики;б) (!) укажите, является ли L1 I L2 КС-языком.
Ответ обоснуйте.7.3.3.(!!) Покажите, что КС-языки не замкнуты относительно следующих операций:а) (∗) Min, определенная в упражнении 4.2.6, а;б) Max, определенная в упражнении 4.2.6, б;в) Half, определенная в упражнении 4.2.8;г) Alt, определенная в упражнении 4.2.7.7.3.4.Shuffle (Перемешивание) двух цепочек w и x является множеством всех цепочек,которые можно получить путем произвольного чередования позиций w и x.
Точнее, shuffle(w, x) есть множество цепочек z, обладающих следующими свойствами.1.Каждая позиция z может быть назначена w или x, но не обеим сразу.2.Позиции z, назначенные w, при чтении слева направо образуют w.3.Позиции z, назначенные x, при чтении слева направо образуют x.Например, если w = 01 и x = 110, то shuffle(01, 110) есть множество цепочек{01110, 01101, 10110, 10101, 11010, 11001}. Для иллюстрации рассмотрим цепочку 10110.
Ее вторая и пятая позиции назначены 01, а первая, третья и четвертая — 110. Цепочка 01110 может быть построена тремя способами: позиция 1 иодна из 2, 3, 4 назначается 01, а оставшиеся три в каждом случае — 110.Перемешивание языков, shuffle(L1, L2), определяется как объединение shuffle(w, x)по всем парам цепочек, w из L1 и x из L2:а) постройте shuffle(00, 111);б) (∗) укажите, что представляет собой shuffle(L1, L2), если L1 = L(0*) иL2 = {0n1n | n ≥ 0};в) (∗!) докажите, что если L1 и L2 — регулярные языки, то и shuffle(L1, L2) регулярен. Указание. Начните с конечных автоматов для L1 и L2;г) (!) докажите, что если L является КС-языком, а R — регулярным языком, тоshuffle(L, R) — КС-язык.
Указание. Начните с МП-автомата для L и ДКА для R;д) (!!) приведите контрпример, показывающий, что если L1 и L2 — КС-языки, тоshuffle(L1, L2) может не быть КС-языком.7.3.5.(∗!!) Цепочка y называется перестановкой цепочки x, если символы y можно переупорядочить и получить x. Например, перестановками цепочки x = 011 являются110, 101 и 011.
Если L — язык, то perm(L) — это множество цепочек, являющихсяперестановками цепочек из L. Например, если L = {0n1n | n ≥ 0}, то perm(L) представляет собой множество цепочек, в которых поровну символов 0 и 1:7.3. ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂСтр. 305305а) приведите пример регулярного языка L над алфавитом {0, 1}, для которогоperm(L) нерегулярен. Ответ обоснуйте. Указание. Попытайтесь найти регулярный язык, перестановками цепочек которого являются все цепочки с одинаковыми количествами 0 и 1;б) приведите пример регулярного языка L в алфавите {0, 1, 2}, для которогоperm(L) не является КС-языком;в) докажите, что для каждого регулярного языка L в двухсимвольном алфавитеperm(L) является КС-языком.7.3.6.Приведите формальное доказательство теоремы 7.25 о том, что КС-языки замкнуты относительно обращения.7.3.7.Дополните доказательство теоремы 7.27, показав, что*(qP, w, Z0) |− (q, ε, γ)P*∧тогда и только тогда, когда ((qP, qA), w, Z0) |− ((q, p), ε, γ) и p = δ (pA, w).P′7.4.
Ñâîéñòâà ðàçðåøèìîñòè ÊÑ-ÿçûêîâТеперь рассмотрим, на какие вопросы о контекстно-свободных языках можно датьответ. По аналогии с разделом 4.3, где речь шла о свойствах разрешимости регулярныхязыков, все начинается с представления КС-языка — с помощью грамматики или МПавтомата. Поскольку из раздела 6.3 нам известно о взаимных преобразованиях грамматик и МП-автоматов, можно предполагать, что доступны оба представления, и в каждомконкретном случае будем использовать более удобное.Мы обнаружим, что разрешимых вопросов, связанных с КС-языками, совсем немного.
Основное, что можно сделать, — это проверить, пуст ли язык, и принадлежитли данная цепочка языку. Этот раздел завершается кратким обсуждением проблем, которые являются, как будет показано в главе 9, “неразрешимыми”, т.е. не имеющимиалгоритма разрешения. Начнем этот раздел с некоторых замечаний о сложности преобразований между грамматиками и МП-автоматами, задающими язык. Эти расчетыважны в любом вопросе об эффективности разрешения свойств КС-языков по данномуих представлению.7.4.1.
Ñëîæíîñòü âçàèìíûõ ïðåîáðàçîâàíèé ÊÑ-ãðàììàòèêè ÌÏ-àâòîìàòîâПрежде чем приступать к алгоритмам разрешения вопросов о КС-языках, рассмотримсложность преобразования одного представления в другое. Время выполнения преобразования является составной частью стоимости алгоритма разрешения в тех случаях, когда алгоритм построен для одной формы представления, а язык дан в другой.306Стр.
306ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂВ дальнейшем n будет обозначать длину представления МП-автомата или КСграмматики. Использование этого параметра в качестве представления размера грамматики или автомата является “грубым”, в том смысле, что некоторые алгоритмы имеютвремя выполнения, которое описывается точнее в терминах других параметров, например, число переменных в грамматике или сумма длин магазинных цепочек, встречающихся в функции переходов МП-автомата.Однако мера общей длины достаточна для решения наиболее важных вопросов: является ли алгоритм линейным относительно длины входа (т.е.
требует ли он времени,чуть большего, чем нужно для чтения входа), экспоненциальным (т.е. преобразованиевыполнимо только для примеров малого размера) или нелинейным полиномиальным(т.е. алгоритм можно выполнить даже для больших примеров, но время будет значительным).Следующие преобразования линейны, как мы увидим далее, относительно размеравходных данных.1.Преобразование КС-грамматики в МП-автомат по алгоритму из теоремы 6.13.2.Преобразование МП-автомата, допускающего по заключительному состоянию, вМП-автомат, допускающий по пустому магазину, с помощью конструкции из теоремы 6.11.3.Преобразование МП-автомата, допускающего по пустому магазину, в МП-автомат,допускающий по заключительному состоянию, с использованием конструкции изтеоремы 6.9.С другой стороны, время преобразования МП-автомата в грамматику (теорема 6.14)существенно больше.
Заметим, что n, общая длина входа, гарантированно является верхней границей числа состояний или магазинных символов, поэтому переменных вида[pXq], построенных для грамматики, может быть не более n3. Однако время выполненияпреобразования может быть экспоненциальным, если у МП-автомата есть переход, помещающий большое число символов в магазин. Отметим, что одно правило может поместить в магазин почти n символов.Если мы вспомним построение продукций грамматики по правилу вида “δ(q, a, X) содержит (r0, Y1Y2…Yk)”, то заметим, что оно порождает набор продукций вида [qXrk] →a[r0Y1r1][r1Y2r2]…[rk–1Ykrk] для всех последовательностей состояний r1, r2, …, rk.
Поскольку k может быть близко к n, общее число продукций возрастает как nn. Такое построениеневозможно довести до конца для МП-автомата разумного размера, даже если он имеетвсего одну цепочку, записываемую в магазин.К счастью, этого наихудшего случая всегда можно избежать. Как предлагалось в упражнении 6.2.8, помещение длинной цепочки в магазин можно разбить на последовательность из не более, чем n шагов, на каждом из которых в магазин помещается всегоодин символ. Таким образом, если δ(q, a, X) содержит (r0, Y1Y2…Yk), можно ввести новые7.4.
ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÊÑ-ßÇÛÊÎÂСтр. 307307состояния p2, p3, …, pk–1. Затем изменим (r0, Y1Y2…Yk) в δ(q, a, X) на (pk–1, Yk–1Yk) и введемновые переходыδ(pk–1, ε, Yk–1) = {(pk–2, Yk–2Yk–1)}, δ(pk–2, ε, Yk–2) = {(pk–3, Yk–3Yk–2)}и так далее до δ(p2, ε, Y2) = {(r0, Y1Y2)}.Теперь в любом переходе не более двух магазинных символов.
При этом добавленоне более n новых состояний, и общая длина всех правил перехода δ выросла не более,чем в константу раз, т.е. осталась O(n). Существует O(n) правил перехода, и каждое порождает O(n2) продукций, поскольку в продукциях, порожденных каждым правилом,должны быть выбраны всего два состояния. Таким образом, грамматика имеет длинуO(n3) и может быть построена за кубическое время.
Проведенный неформальный анализрезюмируется в следующей теореме.Теорема 7.31. Существует алгоритм сложности O(n3), который по МП-автомату Pстроит КС-грамматику длиной не более O(n3). Эта грамматика порождает язык, допускаемый P по пустому магазину. В дополнение, можно построить грамматику, котораяпорождает язык, допускаемый P по заключительному состоянию. 7.4.2. Âðåìåííàÿ ñëîæíîñòü ïðåîáðàçîâàíèÿ ê íîðìàëüíîéôîðìå ÕîìñêîãîАлгоритмы могут зависеть от первичного преобразования в нормальную форму Хомского, поэтому посмотрим на время выполнения различных алгоритмов, использованныхдля приведения произвольной грамматики к НФХ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
