Восходящий синтаксический анализ

ВОСХОДЯЩИЙ  СИНТАКСИЧЕСКИЙ АНАЛИЗ

   Второй  фазой процесса компиляции обычно является фаза синтаксического анализа или разбора. В данном реферате рассмотрен один из распространенных типов разбора – восходящий синтаксический анализ, а также родственный ему нисходящий синтаксический анализ (для сравнения), т.о. в этой работе кратко сопоставлены их возможности.

1. Определение разбора

     Считается, что для некоторой КС-грамматики G цепочка ωL(G) разобрана или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно “физически” построить в памяти машины, но вероятнее, что будет использован какой-нибудь более оптимальный способ представления. Прослеживая шаг за шагом работу синтаксического анализатора, можно получить дерево разбора, хотя связь между этими процессами становится очевидной далеко не сразу.

     К счастью, большинство компиляторов осуществляют разбор моделированием МП-автомата, анализирующего входные цепочки  либо сверху вниз, либо снизу вверх. Способность МП-автомата проводить нисходящий анализ связана со способностью МП-преобразователя отображать входные цепочки в соответствующие левые выводы. Аналогично восходящий анализ связан с отображением входных цепочек в их обращенные правые выводы. Таким образом, проблема разбора трактуется как проблема отображения цепочек в их левые или правые выводы. Стоит заметить, что существует разнообразное множество стратегий разбора помимо рассмотренных в этой работе.

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика, правила которой занумерованы 1, 2, ..., р. Пусть α (N Σ)*. Тогда:

a) левым разбором цепочки α называется последовательность правил, примененных при левом выводе цепочки α из S,

b) правым разбором цепочки α называется обращение последовательности правил, примененных при правом выводе цепочки α из S.

     Эти разборы можно представить в  виде последовательности номеров из множества {1, 2, . . . , p}.

В качестве примера  рассмотрим грамматику G₀ с такой нумерацией правил:  1)   E→E+T

            2)   E→T

            3)   T→ T*F

            4)   T→ F

            5)   F→ E

            6)   F→ a

    Левый разбор цепочки а*(а + а) — это последовательность 23465124646, а правый разбор —64642641532.

     Для описания левых и правых разборов введем дополнительные обозначения.

     Пусть G = (N, Σ, Р, S) — КС-грамматика, правила которой занумерованы числами от 1 до р. Будем считать, что α _i=>β, если α =>_iβ и применено i-e правило. Аналогично будем считать, что α =>_iβ, если α =>_rβ и применено i-e правило. Расширим эти обозначения, положив   (1)   α_π1 => γ,  если  α_π1 => β и β _π2 => γ,

     (2)   α => _{π1 π2}γ,  если  α => _π1β  и  β => _π2γ.

   2. Нисходящий разбор

     В этой части работы исследуется проблема левого анализа для КС-грамматик. Пусть π = i₁…i_n — левый разбор цепочки ωL(G), где G — КС-грамматика. Зная π, можно построить дерево разбора цепочки ω следующим “нисходящим” образом. Начнем с корня, помеченного S. Тогда i₁ дает правило, которое надо применить к S. Допустим, что i₁ — номер правила S→X₁. . .X_k. Присоединим k потомков к вершине, помеченной S, и пометим их Х₁, Х₂, . . ., X_k. Если X_i— первый слева нетерминал в цепочке X₁...X_k, то первыми i—1 символами цепочки ω должны быть X₁. . . X_i-1. Правило с номером i₂ должно тогда иметь вид X_i→Y_l. . .Y_i, и можно продолжить построение дерева разбора цепочки ω, применяя ту же процедуру к вершине, помеченной X_i. Продолжая в том же духе, можно построить все дерево разбора цепочки ω, соответствующее левому разбору π.

     Допустим  теперь, что даны КС-грамматика G = (N, Σ, Р, S), в которой правила занумерованы от 1 до р, и цепочка ω Σ *, для которой мы хотим построить левый разбор. Можно считать, что известны корень и крона дерева разбора и нам остается восполнить промежуточные вершины. Стратегия левого нисходящего разбора предлагает пытаться заполнять дерево разбора, начиная с корня, и двигаться слева направо, направляясь к кроне.

     Можно показать, что существует простая СУ-схема, отображающая цепочки языка L(G) в их левые (или правые) разборы. Мы определим здесь такую СУ-схему, хотя предпочитаем исследовать МП-преобразователь, реализующий соответствующий перевод, потому что от него легко перейти к реальному выполнению этого перевода.

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика, где правила занумерованы от 1 до р. Определим СУ-схему Т_l^G (или Т_l, если G подразумевается) как пятерку (N, Σ, {1, . . ., р}, R, S), где R состоит из таких правил А→ α, β, что А→ α —правило из Р с номером i, а β = i α ', где α ' — цепочка α, из которой устранены все терминалы.

     В качестве примера возьмем Go — с правилами, занумерованными, как в предыдущих примерах. Тогда Т_i = ({E, T, F}, { + , *, (, ), а}, {1, . . . , 6}, R, Е), где R состоит из правил:  1)   E→E+T, 1ET

                        2)   E→T, 2T

                        3)   T→ T*F, 3TF

                        4)   T→ F, 4F

                        5)   F→ E, 5E

                        6)   F→ a, 6

      Пара деревьев, изображенная на рис. 1, задает перевод цепочки а*(а+а).  
 

                             а       б 
 
 
 

     Рис. 1. Перевод схемой Т_i : а—вход; б—выход.

     Теорема. Пусть G = (N, Σ, Р, S) — КС-грамматика. Тогда T_l = {(ω,π)|S_π => ω}

     Доказательство. С помощью индукции можно доказать, что (A, A) => *τ_i (ω, π) тогда и только тогда, когда A_π => _G ω.

     Для любой грамматики G можно построить недетерминированный МП-преобразователь, работающий как левый анализатор для G.

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика, в которой правила занумерованы от 1 до р. Пусть М_l^G (или М_l, если G подразумевается) — недетерминированный МП-преобразователь ({q}, Σ, N Σ, {1, 2, . . . , р}, δ, q, S, Ø), где δ определяется так:

     (1) δ {q, е, А) содержит (q, α, i), если А→ α — правило из Р с номером i,

     (2) δ {q, а, а) = {(q, e, е)} для всех αΣ.

     Назовем М_l^G левым анализатором для G.

     Для входа ω анализатор M_l моделирует левый вывод в грамматике G цепочки ω из S. По правилам (1) M_l каждый раз “развертывает” нетерминал, расположенный наверху магазина, в соответствии с некоторым правилом из Р и одновременно выдает номер этого правила. Если наверху магазина находится терминальный символ, то M_l по правилу (2) проверяет, совпадает ли он с текущим входным символом. Таким образом, M_l может производить только левый вывод цепочки ω.

     Теорема. Пусть G = (N, Σ, Р, S) — КС-грамматика. Тогда τ_e (M_l) = {( ω, π)|S_π => ω}.

     Доказательство. Доказательство производится с помощью метода индукции. Предположение индукции состоит в том, что (q, ω, А, е) |— *(q, е, е, π) тогда и только тогда, когда А_π => ω.

     Заметим, что М_l^G — это почти, но не совсем МП-преобразователь, который получается из СУ-схемы T_l^G.

     В качестве примера построим левый анализатор для грамматики G₀.

     Здесь  М_l = ({q}, Σ, N Σ, {1, 2, . . . , 6}, δ, q, E, Ø}, где

     δ (q, e, E) = {(q, E + T, 1), (q, T, 2)}

     δ (q, e, T) = {(q, T*F, 3), (q, F, 4)}

     δ (q, e, F) = {(q, (Е), 5), (q, a, 6)}

     δ (q, b, b) = {(q, e, e)} для всех b Σ

     Для входной цепочки а + а*а левый анализатор М_l^G может среди других сделать такую последовательность тактов:

     (q, a+a*a, E, e) |— (q, a+a*a, E+T, 1)

                  |— (q, a+a*a, T+T, 12)

                  |— (q, a+a*a, E+T, 124)

                  |— (q, a+a*a, E+T, 1246)

                  |— (q, a+a*a, E+T, 1246)

                  |— (q, a+a*a, E+T, 1246)

                  |— (q, a+a*a, E+T, 12463)

                  |— (q, a+a*a, E+T, 124634)

                  |— (q, a+a*a, E+T, 1246346)

                  |— (q, a+a*a, E+T, 1246346)

                  |— (q, a+a*a, E+T, 1246346)

                  |— (q, a+a*a, E+T, 12463466)

                  |— (q, a+a*a, E+T, 12463466)

     Левый анализатор представляет собой, вообще говоря, недетерминированное устройство. Чтобы пользоваться им на практике нужно уметь моделировать его  детерминированно. Для некоторых грамматик (например, для тех, что содержат циклы) полное моделирование невозможно (в данном случае потому, что некоторые цепочки имеют бесконечно много левых разборов). Кроме того, естественное моделирование непригодно для более широкого класса грамматик, а именно для леворекурсивных грамматик. Нисходящий анализ налагает существенное ограничение: должна быть устранена левая рекурсия.

     Существует  естественный класс грамматик — они называются LL-грамматиками (вход читается слева (left) направо и выдается левый (left) разбор) — для которых левый разбор можно сделать детерминированным с помощью простого приема, состоящего в том, что анализатор заглядывает на входе на несколько символов вперед и делает очередной шаг на основе того, что он при этом видит. LL-грамматики — это те грамматики, которые “естественным образом” анализируются детерминированным левым анализатором.

     Можно рассмотреть более широкий класс  грамматик, для каждой из которых  возможен ДМП-преобразователь, реализующий  СУ-схему T_l. Он содержит все LL-грамматики и некоторые другие, которые можно анализировать только “неестественным” способом, т. е. таким, когда содержимое магазина не отражает в отличие от анализатора M_l последовательности шагов левого вывода. С точки зрения нисходящего анализа такие грамматики представляют только теоретический интерес.

     3. Восходящий разбор

     В этой части реферата будет рассмотрен правый разбор. Возьмем правый вывод в грамматике G₀ цепочки а+а*а из Е:

                        E => E + T

     => E + T*F

     => E + T*a

     => E + F*a

     => E + a*a

     => T + a*a

     => F + a*a

     => a + a*a

     Записывая в обратном порядке последовательность правил, участвующих в этом выводе, получаем правый разбор 64264631 цепочки а+а*а.

     Вообще  правый разбор цепочки ω в грамматике G = (N, Σ, Р, S) — это последовательность правил, с помощью которых можно свернуть цепочку ω к начальному символу S. В терминах деревьев выводов правый анализ цепочки ω представляет собой последовательность отсечений основ, сводящую дерево вывода с кроной ω к одной вершине, помеченной S. В сущности это равносильно процессу “заполнения” дерева вывода, начинающемуся с одной только кроны и идущему от листьев к корню. Поэтому с процессом порождения правого разбора часто ассоциируется термин “восходящий” анализ.

     По  аналогии с СУ-схемой T_l отображающей цепочки из L(G) в их левые разборы, можно определить СУ-схему Т_r, отображающую цепочки в правые разборы. В ней из элементов перевода устранены терминалы, а номера правил выводов пишутся справа.

     Далее рассмотрим МП-преобразователь, реализующий схему Т_r. По аналогии с расширенным МП-автоматом определим расширенный МП-преобразователь.

     Определение. Расширенным МП-преобразователем называется восьмерка P = (Q, Σ, Г, Δ, δ, q₀, Z₀, F), где все символы понимаются так же, как прежде, но только δ теперь обозначает отображение конечного подмножества множества Q (Σ {е})Г* в множество конечных подмножеств множества Q Г* *. Конфигурации определяются так же, как прежде, но обычно подразумевается, что верх магазина расположен справа, и запись (q, aω, βα, х) |— (р, ω, βγ , ху) означает, что δ(q, а, α) содержит (p, γ, y).

     Расширенный МП-преобразователь Р называется детерминированным, если

     1)  #δ(q, a, α)≤1 для всех qQ, aΣ {e} и αГ*,

     2)  цепочки α и β не являются суффиксами одна другой, если δ(q, a, α) Ø и δ(q, b, β) Ø для b=а или b=е. 

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика. Обозначим через М_r^G расширенный недетерминированный МП-преобразователь ({q}, Σ, N Σ {$}, {1, . . . , p}, δ, q, $, Ø), причем верх магазина расположен справа и δ определяется так:

1. δ(q, e, α) содержит (q, A, i), если А→α — правило из Р с номером I,

     2) δ(q, a, e) = {(q, а, е)} для всех а Σ,

     3)  δ(q, e, $S) = {(q, e, е)}

     Этот МП-преобразователь содержит элементы алгоритма разбора, называемого алгоритмом типа перенос—свертка. На такте, соответствующем правилу 2), М_r переносит входной символ в магазин. Всякий раз, когда наверху магазина появляется основа М_r может свернуть ее по правилу 1) и выдать номер правила, использованного при свертке. Затем М_r может продолжать переносить в магазин входные символы, пока в его верхней части не появится новая основа. Эта основа свертывается, а на выход выдается номер соответствующего правила. М_r действует так до тех пор, пока в магазине не останется только начальный символ с маркером дна магазина. По правилу 3) М_r может перейти тогда в конфигурацию с пустым магазином.

     Теорема. Пусть G = (N, Σ, Р, S) — КС-грамматика. Тогда τ_e (M_r) = {( ω, π^R)|S => _πω}.

     Приведем  пример:

     Правым анализатором для грамматики G₀ будет

     М_r^G0  = ({q}, Σ, N Σ, {1, 2, . . . , 6}, δ, q, $, Ø}, где

     δ (q, e, E+T) = {(q, E, 1)}

     δ (q, e, T) = {( q, E, 2)}

     δ (q, e, T*F) = {(q, T, 3)}

     δ (q, e, F) = {(q, T, 4)}

     δ (q, e, a) = {(q, F, 5)}

     δ (q, e, (E)) = {(q, F, 6)}

     δ (q, b, e) = {(q, b, e)} для всех b Σ

     δ (q, e, $E) = {(q, e, e)}

     Для входной цепочки а + а*а левый анализатор М_r^G0 может среди других сделать такую последовательность тактов:

     (q, a+a*a, $, e) |— (q, +a*a, $a, e)

                  |— (q, +a*a, $F, 6)

                  |— (q, +a*a, $T, 64)

                  |— (q, +a*a, $E, 642)

                  |— (q, a*a, $E+, 642)

                  |— (q, *a, $E+a, 642)

                  |— (q, *a, $E+F, 6426)

                |— (q, *a, $E +T, 64264)

       |— (q, a, $E +T*, 64264)

                  |— (q, e, $E +T*a, 64264)

                  |— (q, e, $E+T*F, 642646)

                  |— (q, e, $E+T, 6426463)

                  |— (q, e, $E, 64264631)

                  |— (q, e, e, 64264631)

     Таким образом, для входной цепочки  a+a*a анализатор М_r^G0 выдает правый разбор 64264631.

     4. Сравнение нисходящего  разбора с восходящим

     Если  рассматривать недетерминированные  анализаторы, то сравнивать по существу нечего, так как для каждой КС-грамматики возможен как левый, так и правый анализ. Но если поставить важный вопрос о том, существуют ли для данной грамматики детерминированные анализаторы, то тут дело обстоит не так просто.

     Определение. Назовем КС-грамматику G левоанализируемой, если существует такой ДМП-преобразователь Р, что τ (P) = {(x$, π)|(х, π) T_l^G} и правоанализируемой, если существует такой ДМП-преобразователь Р, что τ (P) = {(x$, π)|(х, π) T_r^G}

     В обоих случаях ДМП-преобразователю  разрешается использовать концевой маркер для указания правого конца  входной цепочки.

     Заметим, что все КС-грамматики лево- и правоанализируемы в неформальном смысле, но в данном формальном определении отражен именно детерминизм.

     Мы  обнаружим, что классы лево- и правоанализируемых грамматик несравнимы, т. е. ни один из них не является подмножеством другого. Это удивительно с той точки зрения что LL-грамматики, которые можно детерминированно левоанализировать естественным образом, образуют подмножество LR-грамматик, которые можно детерминированно правоанализировать естественным образом. Приведем примеры грамматик, лево- (право-) анализируемых, но не право- (лево-) анализируемых.

     Пусть грамматика G₁ определена правилами

     1) S→ВАb  2) S→CАc

     3) А→ВА  4)  А→а

     5) В→а   6)  С→а

     L(G₁) = aa⁺b+aa⁺c. Можно показать, что G₁ не является ни LL-, ни LR-грамматикой, потому что до тех пор, пока мы не увидим последний символ цепочки, неизвестно, каким нетерминалом В или С порождается первый символ а.

     Однако  можно “неестественно” получить левый разбор произвольной входной цепочки с помощью ДМП-преобразователя. Рассмотрим в качестве входной цепочки aⁿ⁺²b (n≥0). Тогда ДМП-преобразователь может сделать левый разбор 15(35)ⁿ4, помещая в магазин все символы а до тех пор, пока он не увидит b. При этом на выходе ничего не порождается. Когда b появится, ДМП-преобразователь может выдать 15(35)ⁿ4, подсчитав n с помощью занесенных в магазин символов а. Подобным же образом для входа aⁿ⁺²c можно получить 26(35)ⁿ4 на выходе. В любом случае вся хитрость в том, чтобы отложить порождение выхода до того, как появится b или с.

     Теперь  докажем, что не существует ДМП-преобразователя, способного порождать правильные правые разборы для всех входных цепочек. Допустим, что ДМП-преобразователь М порождает правые разборы 55ⁿ43ⁿ1 для цепочки aⁿ⁺²b и 65ⁿ43ⁿ2 для цепочки aⁿ⁺²c . Докажем неформально, что такой преобразователь невозможен. Это доказательство существенно опирается на результаты работы Гинзбурга и Грейбах [1966], где показано, что {aⁿbⁿ| n≥1} {aⁿb²ⁿ| n≥1} не является детерминированным КС-языком. Можно доказать следующие утверждения:

     1) Пусть aⁱ поступает на вход преобразователя М. Тогда либо его выход пуст, либо он выдает 5 или 6, и преобразователь М можно “обмануть”, подав на вход с или b соответственно и сделав тем самым его выход ошибочным.

     2) По мере того как символы а поступают на вход М, они должны так или иначе запасаться в магазине. Точнее, можно показать, что найдутся такие числа j и k, магазинные цепочки α и β и состояние q, что (q₀, а^k+jp, Z_o, e)|—* (q, e, β^pα, е) для всех р≥0, где q₀ и Z_o — начальные состояние и магазинный символ преобразователя М.

     3) Если после k+jр символов а на входе М появляется один символ b, то М не может выдать 4 до тех пор, пока не сотрет магазинную ленту вплоть до α. В противном случае мы могли бы “обмануть” М, предварительно поместив на вход дополнительные j символов а, в то время как М будет выдавать то же количество чисел 5, которое он выдавал раньше, так что оба выхода правильными быть не могут.

     4) После того как магазин сократится до цепочки α, преобразователь М уже не может “помнить”, сколько символов было на входе, потому что теперь конфигурации преобразователя М для разных значений р (где k+jp — число символов a) отличаются только их состояниями. Таким образом, М не знает, сколько теперь надо выдать чисел 3.

     Приведем  пример. Пусть G₂ определяется правилами

     1) S→Аb  2) S→Аc

     3) А→B  4)  А→а

     5) В→а  

     L(G₂) = a⁺b+a⁺c. Легко показать, что G₂— правоанализируемая грамматика. С помощью рассуждений, аналогичных проведенным в предыдущем упражнении, можно показать, что G₂ нелевоанализируема.

     Теорема. Классы лево- и правоанализируемых грамматик несравнимы.

     Доказательство. Два предыдущих примера.

     Несмотря  на эту теорему, восходящий синтаксический анализ, как правило, привлекательнее  нисходящего, так как для данного  языка программирования часто легче  написать правоанализируемую грамматику, чем левоанализируемую. К тому же, как отмечалось, LL-грамматики содержатся в классе LR-грамматик. Также естественное моделирование недетерминированного МП-преобразователя в случае, когда он является правым анализатором, работает для более общего класса грамматик, чем в случае левого анализатора.

     Однако с точки зрения процесса трансляции левый анализ предпочтительнее. Мы покажем, что каждый простой СУ-перевод можно выполнить с помощью

     1) МП-преобразователя, дающего левые разборы входных цепочек, за которым следует

     2) ДМП-преобразование, отображающее левые разборы в выходные цепочки данного СУ-перевода.

     Интересно, что существуют простые СУ-переводы, для которых в приведенном  выше утверждении нельзя заменить «левый разбор» на «правый разбор».

     Если  компилятор транслирует так, что  вначале строится полный разбор, который  потом превращается в объектный  код, то указанное обстоятельство достаточно для доказательства того, что существуют переводы, требующие на промежуточной  стадии именно левого разбора. Однако многие компиляторы строят дерево разбора  вершина за вершиной и вычисляют  перевод в каждой вершине, когда  она построена. Мы утверждаем, что если перевод нельзя вычислить прямо по дереву разбора, то его нельзя вычислять вершина за вершиной, когда само построение вершин идет снизу вверх.

     Определение. Пусть G = (N, Σ, Р, S) — КС-грамматика. Определим язык L_l^G левых и язык L_r^G правых разборов грамматики G:

     L_l^G = {π|S_π => ω для переходной ω L(G)}

     L_r^G = {π^R|S => _πω для переходной ω L(G)}

     Обозначения _π=> и =>_π можно распространить на СУ-схемы, договорившись, что (α, β) _π=>(γ, δ) тогда и только тогда, когда (α, β)=>*(γ, δ), причем на каждом шаге этого вывода заменяется самый левый нетерминал первой компоненты выводимой пары и примененные при этом правила, из которых удалены элементы перевода, образуют последовательность π. Аналогично для СУ-схемы определяется =>_π.

     Определение. СУ-схема называется семантически однозначной, если в ней нет двух различных правил вида А →α, β и А →α, γ.

     В семантически однозначной СУ-схеме для каждого правила входной грамматики есть точно один элемент перевода.

     Теорема. Пусть T = (N, Σ, Δ, R, S)—семантически однозначная простая СУ-схема. Тогда существует такой ДМП-преобразователь P, что τ_е(P) ={(π, у)|(S, S) _π=> (x,у) для некоторой цепочки хΣ^*}.

     Доказательство. Пусть P = ({q), {1, . . . , p}, NΔ, Δ, δ, q, S,Ø), где 1, . . . , p - номера правил входной грамматики, a δ определяется так:

     1) Пусть А→а — правило входной грамматики с номером i и А→α, β—единственное соответствующее правило схемы. Тогда δ (q, i, A) = (q, β, е).

     2) δ (q, e, b) = (q, e, b) для всех bΔ.

     МП-преобразователь  P детерминированный, потому что правило 1) применяется только тогда, когда наверху магазина находится нетерминал, а правило 2) применяется только тогда, когда наверху выходной символ. Корректность преобразователя Р следует из утверждения, которое легко доказывается с помощью метода индукции:

(q, π, А, е) |— * (q, е, е, у) тогда и только тогда, когда существует такая цепочка xΣ*, что (A, A)_π=> (x, у).

     Чтобы описать СУ-перевод, не выполнимый никаким ДМП-преобразователем, отображающим L_r^G, где G—входная грамматика, в соответствующие выходы этого перевода, нам понадобится следующая лемма.

     Лемма.  Не существует такого ДМП-преобразователя Р, что τ(R) = {(ωс, ω^Rcω) | ω {а, b}*}.

     Доказательство. Здесь символ с играет роль правого концевого маркера. Допустим, что Р для входа ω выдает некоторую непустую цепочку, скажем dx, где d {а, b}. Пусть означает символ, противоположный d. Посмотрим, как работает Р с цепочкой ωc в качестве входа. Он должен выдать некоторую цепочку, но эта цепочка должна начинаться символом d. Следовательно, Р не отображает ωc в ω^Rcω, как требуется. Таким образом, Р не может ничего выдать на выходе, пока не будет достигнут правый концевой маркер с. В этот момент Р будет находиться в состоянии q_ω и хранить в магазине цепочку α_ω.

     Неформально α_ω должна быть по существу цепочкой ω, и тогда, стирая α_ω, P может выдать ω^R. Но стоит ему стереть α_ω, как он уже не может “вспомнить” всю цепочку ω, чтобы напечатать ее на выходе.

     Рассмотрим  входные цепочки вида ω — aⁱ. Существуют такие числа j и k, состояние q и цепочки α и β, что, прочитав на входе a^j+nkc, P помещает в магазин αβⁿ и переходит в состояние q. Тогда Р должен стереть содержимое магазина вплоть до α к тому моменту, когда он выдает ω^Rc. Но так как α от ω не зависит, то выдать ω уже невозможно. 

     Теорема. Существует простая СУ-схема T = (N, Σ, Δ, R, S), для которой нет такого ДМП-преобразователя P, что τ(P) ={(π^R, x)|(S, S)=>_π(ω, x) для некоторой цепочки ω}.

     Доказательство. Пусть Т определяется правилами

     1) S→Sa, aSa

     2) S→Sb, bSb