ГЛАВА 7

Свойства контекстно- свободных языков

Наше изучение контекстно-свободных языков завершается знакомством с некоторыми из их свойств. Вначале определяются ограничения на структуру продукций КС-грамматик и доказывается, что всякий КС-язык имеет грамматику специального вида. Этот факт об­легчает доказательство утверждений о КС-языках.

Затем доказывается «лемма о накачке» для КС-языков. Эта теорема аналогична тео­реме 4.1 для регулярных языков, но может быть использована для доказательства того, что некоторые языки не являются контекстно-свободными. Далее рассматриваются свойства, изученные в главе 4 для регулярных языков, — свойства замкнутости и разре­шимости. Показывается, что некоторые, но не все, свойства замкнутости регулярных языков сохраняются и у КС-языков. Часть задач, связанных с КС-языками, разрешается с помощью обобщения проверок, построенных для регулярных языков, но есть и ряд во­просов о КС-языках, на которые нельзя дать ответ.

7.1. Нормальные формы контекстно-свободных грамматик

Цель этого раздела — показать, что каждый КС-язык (без £) порождается грамматикой, все продукции которой имеют форму А —> ВС или А а, где А, В и С— переменные, а — терминал. Эта форма называется нормальной формой Хомского. Для ее получения нужно несколько предварительных преобразований, имеющих самостоятельное значение.

• Удалить бесполезные символы, т.е. переменные или терминалы, которые не встре­чаются в порождениях терминальных цепочек из стартового символа.
• Удалить е-продукции, т.е. продукции вида А —» £ для некоторой переменной А.
• Удалить цепные продукции вида А —> В с переменными Aw В.

7.1.1. Удаление бесполезных символов

Символ X называется полезным в грамматике G = (V, Т, Р, S), если существует неко- * *

торое порождение вида S => аХр => w, где w е Т». Отметим, что X может быть как пе­ременной, так и терминалом, а выводимая цепочка аХР— первой или последней в по­рождении. Если символ X не является полезным, то называется бесполезным. Очевидно, что исключение бесполезных символов из грамматики не изменяет порождаемого языка, поэтому все бесполезные символы можно обнаружить и удалить.

Наш подход к удалению бесполезных символов начинается с определения двух свойств, присущих полезным символам.

• Символ X называется порождающим, если X => w для некоторой терминальной це­почки Заметим, что каждый терминал является порождающим, поскольку w мо­жет быть этим терминалом, порождаемым за 0 шагов.

*

• Символ X называется достижимым, если существует порождение S => схХ(3 для не­которых а и р.

Естественно, что полезный символ является одновременно и порождающим, и дос­тижимым. Если сначала удалить из грамматики непорождающие символы, а затем не­достижимые, то, как будет доказано, останутся только полезные. Пример 7.1. Рассмотрим следующую грамматику.

S-> АВ | а А^Ь

Все символы, кроме В, являются порождающими; а и b порождают самих себя, 5 порож­дает а и А порождает Ь. Если удалить В, то придется удалить и продукцию S —> АВ, что приводит к следующей грамматике.

S->a A—>b

Теперь нетрудно обнаружить, что из S достижимы только а и S. Удаление А и b ос­тавляет лишь продукцию S —> а. Она образует грамматику с языком {а}, как и у исход­ной грамматики.

Заметим, что если начать с проверки достижимости, то все символы грамматики

S АВ | а А-^Ь

оказываются достижимыми. Если затем удалить В как непорождающий символ, то оста­нется грамматика с бесполезными символами А и Ь. О

Теорема 7.2. Пусть G = (V, Т, Р, S) — КС-грамматика, и L(G) t 0, т.е. G порождает хотя бы одну цепочку. Пусть G, = (У_Л T_h Р,, S)— грамматика, полученная с помощью следующих двух шагов.

1. Вначале удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть G₇ = (V₂, Т₂, Р₂, S) — полученная в результате грамматика. Заметим, что S должен быть порождающим, так как по предположению L(G) содержит хотя бы одну цепочку, поэтому S не удаляется.
2. Затем удаляются все символы, недостижимые в G₂. Тогда G; не имеет бесполезных символов, и L(Gi) = L(G).

Доказательство. Пусть X— оставшийся символ, т.е. Хе Т_] U V_h Нам известно, что

X => w для некоторой цепочки w из Т*. Кроме того, каждый символ, использованный в

порождении w из X, также является порождающим. Таким образом, X => w.

Поскольку X не был удален на втором шаге, нам также известно, что существуют та­кие а и Д для которых S => аХр. Кроме того, каждый символ, использованный в этом

*

порождении, достижим, поэтому S => aXfi.

^Gi

Нам известно, что каждый символ в цепочке aXfi достижим, и что все эти символы принадлежат Т₂ U V₂, поэтому каждый из них является порождающим в G₂. Порождение

некоторой терминальной цепочки, скажем, аХ/З => xwy, содержит только символы, дос-

^Gz

тижимые из S, поскольку они достижимы из символов в цепочке схХ{5. Таким образом, это порождение есть также порождение в G/, т.е.

S => аХв => xwy.

g, ^ g,

Итак, X полезен в С/. Ввиду произвольности X в G/ можно заключить, что G/ не имеет бесполезных символов.

Нам осталось доказать, что L(G,) = L(G). Как обычно, покажем взаимное включение этих языков.

Включение L(G;)cL(G) очевидно, поскольку при построении G_t из G символы и продукции только удаляются.

Докажем, что L(G) с ЦС,). Если w е L(G), то S => w. Каждый символ в этом порож-

G

дении, очевидно, является как достижимым, так и порождающим, поэтому порождение в Gi также его содержит. Таким образом, S => w, и w е L(G,). □

7.1.2. Вычисление порождающих и достижимых символов

Рассмотрим, каким образом вычисляются множества порождающих и достижимых символов грамматики. В алгоритме, используемом в обеих задачах, делается макси­мум возможного, чтобы обнаружить символы этих двух типов. Докажем, что если пра­вильное индуктивное построение указанных множеств не позволяет обнаружить, что символ является, порождающим или достижимым, то он не является символом соот­ветствующего типа.

Базис. Каждый символ из Т, очевидно, является порождающим; он порождает сам себя.

Индукция. Предположим, есть продукция А —> а, и известно, что каждый символ в а является порождающим. Тогда А — порождающий. Заметим, что это правило включает и случай, когда а = е; все переменные, имеющие в в качестве тела продукции, являются порождающими.

Пример 7.3. Рассмотрим грамматику из примера 7.1. Согласно базису а и b — поро­ждающие. По индукции используем продукции А —> b и S —> а, чтобы заключить, что А и S — также порождающие. На этом индукция заканчивается. Продукцию S —» АВ исполь­зовать нельзя, поскольку не установлено, что В — порождающий. Таким образом, мно­жеством порождающих символов является {a, b, A, S}. □

Теорема 7.4. Вышеприведенный алгоритм находит все порождающие символы грам­матики G и только их.

Доказательство. В одну сторону, а именно, что каждый добавленный символ на са­мом деле является порождающим, доказать легко с помощью индукции по порядку, в ко­тором символы добавляются к множеству порождающих символов. Это оставляется в качестве упражнения.

Для доказательства в другую сторону предположим, что X— порождающий, и пусть X => vf. Докажем индукцией по длине порождения, что X будет обнаружен как порождающий.

Базис. Нуль шагов. Тогда X— терминал и находится как порождающий согласно ба­зису алгоритма.

Индукция. Если порождение имеет п шагов, где п > 0, то X— переменная. Пусть по­рождение имеет вид X =» а => vv, т.е. первой использована продукция X -> а. Из

каждого символа цепочки а выводится некоторая терминальная цепочка, образующая часть w, и это порождение имеет менее, чем п шагов. По предположению индукции каждый символ цепочки а находится как порождающий. Индуктивная часть алгоритма позволяет с помощью продукции Х—> а заключить, что X— порождающий. □

Теперь рассмотрим индуктивный алгоритм, с помощью которого находится множест­во достижимых символов грамматики G = (V, Т, Р, S). Можно доказать, что если символ не добавляется к множеству достижимых символов путем максимально возможного об­наружения, то он не является достижимым.

Базис. Очевидно, что S действительно достижим.

Индукция. Пусть обнаружено, что некоторая переменная А достижима. Тогда для всех продукций с головой А все символы тел этих продукций также достижимы.

Пример 7.5. Снова начнем с грамматики из примера 7.1. Согласно базису S дости­жим. Поскольку S имеет тела продукций АВ и а, символы А, В и а также достижимы. У В продукций нет, но А имеет А —» Ь. Делаем вывод, что b достижим. К множеству дости­жимых символов {S, А, В, а, Ь) добавить больше нечего. □

Теорема 7.6. Вышеприведенный алгоритм находит все достижимые символы грам­матики G, и только их.

Доказательство. Это доказательство представляет собой еще одну пару простых ин­дукций в духе теоремы 7.4 и оставляется в качестве упражнения.

7.1.3. Удаление е-продукций

Покажем теперь, что е-продукции, хотя и удобны в задачах построения грамматик, не являются существенными. Конечно же, без продукции с телом £ невозможно породить лустую цепочку как элемент языка. Таким образом, в действительности доказывается, что если L задается КС-грамматикой, то L — {£} имеет КС-грамматику без е-продукций. Начнем с обнаружения «£-порождающих» переменных. Переменная А называется

Е-порождающей, если А => £. Если А — £-порождающая, то где бы в продукциях она ни встречалась, например в В —> CAD, из нее можно (но не обязательно) вывести £. Продук­ция с такой переменной имеет еще одну версию без этой переменной в теле (В —> CD). Эта версия соответствует тому, что £-порождающая переменная использована для выво­да е. Используя версию В —» CAD, мы не разрешаем из А выводить £. Это не создает про­блем, так как далее мы просто удалим все продукции с телом £, предохраняя каждую пе­ременную от порождения £.

Пусть G = (V, Т, P,S) — КС-грамматика. Все £-порождающие символы G можно най­ти с помощью следующего алгоритма. Далее будет показано, что других £-порождающих символов, кроме найденных алгоритмом, нет.

Базис. Если А -> £— продукция в G, то А — £-порождающая.

Индукция. Если в G есть продукция В —> С/С₂…Сь где каждый символ С, является £-порождающим, то В — £-порождающая. Отметим, что для того, чтобы С, был ^по­рождающим, он должен быть переменной, поэтому нам нужно рассматривать продук­ции, тела которых содержат только переменные.

Теорема 7.7. В любой грамматике ^-порождающими являются только переменные, найденные вышеприведенным алгоритмом.

Доказательство. Переформулируем утверждение в виде «А является £-порождающей тогда и только тогда, когда алгоритм идентифицирует А как е-порождающую». Для дос­таточности нетрудно показать индукцией по порядку, в котором обнаруживаются £-

порождающие символы, что каждый такой символ действительно порождает £. Для не-

*

обходимости используем индукцию по длине кратчайшего порождения А ==> £.

Базис. Один шаг. Тогда А —> £ должно быть продукцией, и А обнаруживается соглас­но базису алгоритма.

Индукция. Пусть А => £ за п шагов, где п> 1. Первый шаг должен иметь вид А=> CiC₂.—C_k => £, где каждый символ С, порождает £ за число шагов, которое

меньше п. По предположению индукции каждый символ С, обнаруживается как е-порож- дающий. Тогда с помощью индуктивного шага А также обнаруживается как е-по- рождающая на основе продукции А —> С/Сг-.-С*. □

Пример 7.8. Рассмотрим следующую грамматику. S —»АВ А —> аАА | е В^ЬВВ \е

Сначала найдем е-порождающие символы. А и В непосредственно е-порождающие, так как имеют продукции сев качестве тела. Тогда и S е-порождающий, поскольку тело продукции S —> АВ состоит только из е-порождающих символов. Таким образом, все три переменные являются е-порождающими.

Построим теперь продукции грамматики G/. Сначала рассмотрим S —»АВ. Все сим­волы тела являются е-порождающими, поэтому есть 4 способа выбрать присутствие или отсутствие А и В. Однако нам нельзя удалять все символы одновременно, поэтому полу­чаем следующие три продукции.

S^AB\A\B

Далее рассмотрим продукцию А —> аАА. Вторую и третью позиции занимают е-по- рождающие символы, поэтому снова есть 4 варианта их присутствия или отсутствия. Все они допустимы, поскольку в любом из них остается терминал а. Два из них совпадают, поэтому в грамматике G/ будут следующие три продукции.

А —> аАА | аА | а

Аналогично, продукция для В приводит к следующим продукциям в G/. В —> ЪВВ\bB\b

Обе е-продукции из G не вносят в G, ничего. Таким образом, следующие продукции об­разуют G/.

S^AB\А\В А —> аАА \aA\a В ЬВВ \bB\b

□

Завершим наше изучение удаления е-продукций доказательством, что описанная кон­струкция не изменяет язык, за исключением того, что цепочки е в нем больше нет, если она была в языке грамматики G. Поскольку конструкция, очевидно, удаляет е-продук­ции, мы будем иметь полное доказательство утверждения о том, что для любой КС-грам­матики G найдется такая КС-грамматика G; без е-продукций, для которой

L(G;) = L(G)-{£}-

Теорема 7.9. Если грамматика G/ построена по грамматике G с помощью описанной выше конструкции удаления е-продукций, то I(G_;) = L(G) — {е}.

Доказательство. Нужно доказать, что если w Ф е, то w е L(Gj) тогда и только тогда, когда w е ЦС). Как часто случается, проще доказать более общее утверждение. В дан­ном случае будем говорить о терминальных цепочках, порождаемых каждой перемен­ной, несмотря на то, что нас интересуют лишь порождаемые стартовым символом S. Та­ким образом, докажем следующее утверждение.

• А => w тогда и только тогда, когда А => w и w * е.

с,                                а

В обе стороны доказательство проводится индукцией по длине порождения. (Необходимость) Пусть А => w. Несомненно,

w Ф е, поскольку Cjj не имеет е-

О]

продукций. Докажем индукцией по длине порождения, что А => w.

G

Базис. Один шаг. В этом случае в G_t есть продукция А —» w. Согласно конструкции G/ в G есть продукция А а, причем а— это w, символы которой, возможно, переме­жаются ^-порождающими переменными. Тогда в G есть порождение А => а => w, где на

G G

шагах после первого, если они есть, из всех переменных в цепочке а выводится е.

Индукция. Пусть в порождении п шагов, п> 1. Тогда оно имеет вид

А => Х,Х₂.. .Х_к => w. Первая использованная продукция должна быть построена по про-

g,                     (j,

дукции А Y/Y₂…Y_m, где цепочка Y,Y₂…Y_m совпадает с цепочкой X_tX₂..Х_к, символы ко­торой, возможно, перемежаются дополнительными е-порождающими переменными. Це­почку w можно разбить на w_:w₂…w_k, где X, => w, для / = 1, 2, …, к. Если X, есть терми-

нал, то w, = Х„ а если переменная, то порождение Xj => w, содержит менее п шагов. По

*

предположению индукции X, w,.

Теперь построим соответствующее порождение в G.

А Y,Y₂…Y_m Х,Х₂..Х_к => w,w₂…w_k = w

G                                  G                                   Г,

На первом шаге применяется продукция А —> У, У₂… }’,„, которая, как мы знаем, есть в G. Следующая группа шагов представляет порождение е из тех У,, которые не являются ни одним из X_h Последняя группа шагов представляет порождения w, из X,, которые суще­ствуют по предположению индукции.

(Достаточность) Пусть А w и w Ф е. Докажем индукцией по длине п порождения,

G

*

что Л => w.

С,

Базис. Один шаг. А —> w является продукцией в G. Поскольку w Ф е, эта же продукция

есть и в G_h поэтому А => w.

а,

Индукция. Пусть в порождении п шагов, п> 1. Тогда оно имеет вид * *

А YiY₂…Y_m => w. Цепочку w можно разбить на wiw₂…w_k так, что Г, => w, для /’ = 1, 2,

G                                   G                                                                                                                                                                G

…, т. Пусть X_h Х₂, …, Х_к будут теми из Yj (в порядке записи), для которых и», Ф е. к > 1, поскольку w Ф е. Таким образом, А —^Х,Х₂…Х_к является продукцией в G/.

Утверждаем, что Х,Х₂..Х’_к => w, поскольку только Yj, которых нет среди Х_;, Х₂, …, Х_к,

G

использованы для порождения е и не вносят ничего в порождение w. Так как каждое из по­рождений Yj => w_t содержит менее п шагов, к ним можно применить предположение ин-

G

* *

дукции и заключить, что если vi’_; Ф е, то У, ==> w_r Таким образом, А => Х,Х₂.. ,Х_к => w.

О |                                                                 G[

Завершим доказательство. Нам известно, что w е L(Gj) тогда и только тогда, когда

S=>w. Полагая, что А = S в описанных выше рассуждениях, получаем, что w е L(G,) то-

*

гда и только тогда, когда S => w и w Ф е. Таким образом, w е L(Gi) тогда и только тогда,

G

когда w е L(G/) и w Ф е. □

7.1.4. Удаление цепных продукций

Цепная продукция — это продукция вида А —» В, где и А, и В являются переменными. Эти продукции могут быть полезными: в примере 5.27 мы видели, как использование цепных продукций Е—> Та Т—> F позволило построить следующую однозначную грам­матику для простых арифметических выражений.

I                а | Ъ 11а | lb 110 | Л

F Ц(Е) Т              F| Г* F

Е         Т\Е+Т

Вместе с тем, цепные продукции могут усложнять некоторые доказательства и созда­вать излишние шаги в порождениях, которые по техническим соображениям там совсем не нужны. Например, в продукции Е —> Т переменную Т можно расширить обоими воз­можными способами, заменив эту продукцию двумя: Е—»F| Т* F. Это изменение все еще не избавляет от цепных продукций из-за появления E—>F. Дальнейшая замена F да- ет Е —> 11 (Е) | Т * F, однако при этом остается Е —> I. Но если в этой продукции заменить / всеми шестью возможными способами, то получим следующие продукции.

£-> а | b | la | lb \ 10 \ 11 \ (E)\ T* F Как видно, цепных продукций для Е нет. Заметим, что продукция Е а не является цепной, единственный символ в ее теле — терминал, а не переменная.

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

включает первоначальное нахождение всех пар переменных А а В, для которых А => В получается с использованием последовательности лишь цепных продукций. Заметим, что

А => В возможно и без использования цепных продукций, например, с помощью про­дукций А —> ВС и С —> е.

Определив все подобные пары, любую последовательность шагов порождения, в ко­торой А => В_: => В₂ => … => В_п => а с нецепной продукцией В„ —> а, можно заменить продукцией А —> а. Однако вначале рассмотрим индуктивное построение пар (А, В), для

которых А => В получается с использованием лишь цепных продукций. Назовем такую пару цепной парой (unit pair).

Базис. (А, А) является цепной парой для любой переменной, т.е. А => А за нуль шагов.

Индукция. Предположим, что пара (А, В) определена как цепная, и В —> С — про­дукция с переменной С. Тогда (А, С) — цепная пара.

Пример 7.10. Рассмотрим грамматику выражений из примера 5.27, воспроизведен­ную выше. Базис дает цепные пары (Е, Е), (Т, Т), (F, F) и (/, Г). На индуктивном шаге можно сделать следующие порождения пар.

(Е, Е) и продукция Е—>Тдают пару (Е, 7).

(Е, Г) и продукция T—>F — пару (Е, F).

(£, F) и F —> / дают пару (£, Г).

(Т, 7) и Г-» F— пару (£,/).

(Т, F) н F I — пару (Т, Г).

(F, F) и F —> / — пару (F, /).

Больше пар, которые можно было бы вывести, нет. На самом деле эти десять пар пред­ставляют все порождения, использующие только цепные продукции. □

Способ построения пар теперь очевиден. Нетрудно доказать, что предложенный ал­горитм обеспечивает порождение всех нужных пар. Зная эти пары, можно удалить цепные продукции из грамматики и показать эквивалентность исходной и полученной грамматик.

Теорема 7.11. Приведенный выше алгоритм находит все цепные пары грамматики G, и только их.

Доказательство. С помощью индукции по порядку обнаружения пар нетрудно пока­зать, что если пара (А, В) обнаружена, то А => В получается с использованием лишь

G

цепных продукций. Это оставляется в качестве упражнения.

Предположим, что А => В получено с использованием лишь цепных продукций. По-

G

кажем с помощью индукции по длине порождения, что пара (А, В) будет обнаружена.

Базис. Нуль шагов. Тогда А = В, и пара (А, В) обнаруживается согласно базису.

*

Индукция. Предположим, что А => В получено за п шагов, п > 0, и на каждом из них

G

применялась цепная продукция. Тогда порождение имеет вид А => С => В. Порождение

G

*

А => С состоит из п — 1 шагов, и по предположению индукции пара (А, С) обнаружива-

G

ется. Наконец, используем индуктивную часть алгоритма, чтобы по паре (А, С) и про­дукции С —> В обеспечить обнаружение пары (А, В). □

Для удаления цепных продукций по КС-грамматике G~(V,T,P,S) построим КС- грамматику G/ = (V/, T,P_hS) следующим образом.

Найдем все цепные пары грамматики G.

Для каждой пары (А, В) добавим к Pi все продукции А а, где В —> а— нецепная продукция из Р. Заметим, что при А = В все нецепные продукции для В из Р просто добавляются к Р,.

Пример 7.12. Продолжим пример 7.10, где был выполнен шаг 1 описанного построения для грамматики выражений из примера 5.27. На рис. 7.1 представлен шаг 2 алгоритма, строя­щий новое множество продукций. При этом первый член пары становится головой продук­ций, а в качестве их тел используются все тела нецепных продукций для второго члена.

На заключительном шаге из грамматики (см. рис. 7.1) удаляются все цепные продук­ции. В итоге получается следующая грамматика без цепных продукций, которая порож­дает то же самое множество выражений, что и грамматика, изображенная на рис. 5.19.

Е Е + Т\Т* F | (£) | a j b | la | lb | /0 | Л Г —» Г * F | (£) \a\b\Ia\Ib\I0\l\ F->(E)\a\b\Ia\Ib\I0\Il I а \ b \ la \ lb \ 10 \ 1\

□

Теорема 7.13. Если грамматика G; построена по грамматике G с помощью алгоритма удаления цепных продукций, описанного выше, то L(G/) = 1(G).

Пара	Продукции
(Е,Е)	Е^Е+Т
(Е,Т)	E—>T*F
СE,F)
(£,/)	Е —> a \b \ 1а	lb	I/O	1/1
(Т,Г)	Т-> Т* F
сT,F)	Г->(£)
Ст,1)	Т^а\Ь\1а	lb	10	/1
(F,F)	F-*{E)
(F,I)	F^a\b\ la	lb	I/O	1/1
(А Г)	I—>a\b\Ia\	lb 1	10 1	/1

Рис. 7.1. Грамматика, построенная на шаге 2 алгоритма удаления цепных продукций Доказательство. Докажем, что w е L(G,) тогда и только тогда, когда w е 1(G).

(Достаточность) Предположим, S => w. Поскольку каждая продукция фамматики

Gi

G, эквивалентна последовательности из нуля или нескольких цепных продукций G, за которой следует нецепная продукция G, из а (3 следует а => (3. Таким образом, каж-

G_x                                          G

дый шаг порождения в G, может быть заменен одним или несколькими шагами в G. Со­брав эти последовательности шагов вместе, получим, что S => w.

G

(,Необходимость) Предположим, что w е 1(G). Тогда в соответствии с эквивалент- ностями из раздела 5.2 цепочка w имеет левое порождение, т.е. S => w. Где бы в левом

1т

порождении ни использовалась цепная продукция, переменная ее тела становится крайней слева в выводимой цепочке и сразу же заменяется. Таким образом, левое по­рождение в G можно разбить на последовательность «шагов», в которых нуль или не­сколько цепных продукций сопровождаются нецепной. Заметим, что любая нецепная продукция, перед которой нет цепных, сама по себе образует такой «шаг». Но по по­строению грамматики G/ каждый из этих шагов может быть выполнен одной ее про­дукцией. Таким образом, S => w. □

^Gi

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

Удалить е-продукции.

Удалить цепные продукции.

Удалить бесполезные символы.

Заметим, что подобно тому, как в разделе 7.1.1 результат удаления бесполезных симво­лов зависел от порядка соответствующих шагов, данные три шага должны быть упоря­дочены именно так, иначе в грамматике могут остаться удаляемые элементы.

Теорема 7.14. Если G— КС-грамматика, порождающая язык, в котором есть хотя бы одна непустая цепочка, то существует другая грамматика G/, не имеющая бесполезных символов, е-продукций и цепных продукций, у которой L(G/) = 1(G) — {£}.

Доказательство. Начнем с удаления е-продукций методом, описанным в разде­ле 7.1.3. Если затем удалить цепные продукции (см. раздел 7.1.4), то е-продукции не поя­вятся, поскольку каждое из тел новых продукций совпадает с некоторым телом одной из старых. Наконец, удалим бесполезные символы методом раздела 7.1.1. Поскольку это преобразование только удаляет продукции и символы, не вводя новых, то получаемая грамматика будет по-прежнему свободна от цепных и е-продукций. □

7.1.5. Нормальная форма Хомского

Завершим изучение грамматических упрощений, показав, что для каждого непустого КС-языка, не включающего е, существует грамматика G, все продукции которой имеют одну из следующих двух форм.

А —> ВС, где А, В а С — переменные.

А —> а, где А — переменная, а — терминал.

Кроме того, G не имеет бесполезных символов. Такая форма грамматик называется нор­мальной формой Хомского, или НФХ, а грамматики в такой форме — НФХ-грамматиками.

Для приведения грамматики к НФХ начнем с ее формы, удовлетворяющей теоре­ме 7.14, т.е. грамматика свободна от бесполезных символов, цепных и е-продукций. Ка­ждая продукция такой грамматики либо имеет вид А —> а, допустимый НФХ, либо имеет тело длиной не менее 2. Нужно выполнить следующие преобразования:

а)   устроить так, чтобы все тела длины 2 и более состояли только из переменных;

б)   разбить тела длины 3 и более на группу продукций, тело каждой из которых состоит из двух переменных.

Конструкция для а следующая. Для каждого терминала а, встречающегося в продук­ции длины 2 и более, создаем новую переменную, скажем, А. Эта переменная имеет единственную продукцию А —> а. Используем переменную А вместо а везде в телах про­дукций длины 2 и более. Теперь в теле каждой продукции либо одиночный терминал, либо как минимум две переменные и нет терминалов.

Для шага б нужно разбить каждую продукцию вида А —> В,В₂…В_к, где к > 3, на груп­пу продукций с двумя переменными в каждом теле. Введем к- 2 новых переменных С/, С;,…, и заменим исходную продукцию на к-1 следующих продукций.

—» fi/С/, С/ —> брСр, ■.., C’k j —> ₂Q. 2, Сь 2 Вк /Вк

Пример 7.15. Приведем грамматику из примера 7.12 к НФХ. Для части а заметим, что у грамматики есть восемь терминалов, я, Ь, 0, 1 ,+,*,( и ), каждый из которых встре­чается в теле, не являющемся одиночным терминалом. Таким образом, нужно ввести во­семь новых переменных, соответствующих этим терминалам, и восемь следующих про­дукций, где переменная заменяется «своим» терминалом.

А^а В^Ъ Z-> О 0-> 1 М->* L->( /?->) Введя эти продукции и заменив каждый терминал в теле, не являющемся одиночным тер­миналом, соответствующей переменной, получим грамматику, изображенную на рис. 7.2.

Е —> ЕРТ | TMF | LER \a\b\lA\lB\IZ\10 ТTMF | LER\a\b\IA\IB\IZ\IO F—»LER \a\b\IA\IB\IZ\IO I а \ b \ IA \ IB \ IZ \ Ю А^а В^Ь Z^O 0-> 1 />-» + л/->* I-K Л->)

Рис. 7.2. Преобразование тел к одиночным терминалам или нескольким переменным

Теперь все продукции находятся в НФХ, за исключением тех, тела которых имеют длину 3: ЕРТ, TMF, LER. Некоторые из этих тел встречаются в нескольких продукциях, но каждое тело преобразуется один раз.

Для тела ЕРТ вводится новая переменная С/, и продукция Е —> ЕРТ меняется на £-» £С/ и С/ —> РГ. Для тела TMF вводится переменная С₂. Две продукции с этим телом, £-4 TMF и 7’—> TMF,’меняются на Е 7’С₂, ГС₂ и С₂ MF. Для ££/? вводится С₅ и три продукции с этим телом, Е —> LER, Т —> и L£/?, меняются на Е —> T-)LC₃,F-^LC₃ и Q —> £/?. Окончательная НФХ-фамматика показана на рис. 7.3.

E-*EC,\TC₂\LC₃\a\b\IA\IB\IZ\Ю

T —» TC₂1 LC3 \a\b\IA\IB\IZ\IO

F —» LC3 \ a\b \ IA \ IB\ IZ\IO

I a\b\ IA \ IB \ IZ\ IO

A —> a

B->b

Z->0

1 *

£->( л-О

С, ->РГ C₂->MF C₃->ER

Рис. 7.3. Преобразование тел к одиночным терминалам или двум переменным

Теорема 7.16. Если G— КС-грамматика, язык которой содержит хотя бы одну не­пустую цепочку, то существует НФХ-грамматика G/, причем L(G,) = L(G) — {е}.

Доказательство. По теореме 7.14 можно найти КС-грамматику G₂, для которой L(G₂) = L(G) — {е}, причем G₂ свободна от бесполезных символов, цепных и е-продукций. Конструкция, преобразующая G₂ в НФХ

-грамматику О/, изменяет продукции таким образом, что каждая продукция из G₂ может быть проимитирована одной или несколькими продукциями из Gj. Наоборот, каждая из введенных в G, переменных соответствует лишь одной продукции, поэтому эти переменные можно использовать только надлежащим обра­зом. Более строго, докажем, что w е L(G₂) тогда и только тогда, когда w е ЦС,).

(Необходимость) Если w порождается в G₂, то легко заменить каждую использован­ную продукцию, скажем, А —^X_tX₂…Xk, последовательностью продукций из G/. Таким образом, один шаг порождения в G₂ превращается в один или несколько шагов в порож­дении w, использующем продукции G,. Во-первых, если X,— терминал, то G; имеет со­ответствующую переменную В, и продукцию В, —> X,. Во-вторых, если к > 2, то G/ имеет продукции А —> B_tC_h Ci —> В₂С₂ и так далее, где В/ есть либо переменная, введенная для терминала X_h либо сам Х„ если это переменная. Эти продукции имитируют в G/ один шаг порождения в G₂, использующий продукцию А —^Х₁Х₂…Х_к. Делаем вывод, что в G, существует порождение w, поэтому w е L(G,).

(Достаточность) -Предположим, что w е L(Gi). Тогда в G/ существует дерево разбо­ра с отметкой корня S и кроной w. Преобразуем это дерево в дерево разбора в G₂, также имеющее отметку корня S и крону w.

Сначала «сделаем откат» части б построения НФХ. Предположим, существует узел с отметкой А и сыновьями, отмеченными В, и С/, где С/ — одна из переменных, введенных в части 6. Тогда данная часть дерева разбора должна выглядеть, как на рис. 7.4, а. Поскольку каждая из этих введенных переменных соответствует лишь одной продукции, существует только один способ для их возникновения, и все эти переменные, предназначенные для об­работки продукции А —> BjB₂.. .В_к, должны появляться вместе (см. рис. 7.4, а).

Каждый такой куст узлов в дереве разбора можно заменить продукцией, которую они представляют. Преобразование дерева разбора показано на рис. 7.4, б.

Полученное дерево все еще не обязательно является деревом разбора в G₂. Причина в том, что на шаге а построения НФХ были введены другие переменные, порождающие

б) Рис. 7.4. Дерево разбора должно использовать введенные переменные специальным образом

одиночные терминалы. Однако их можно обнаружить в полученном дереве разбора и за­менить узел, отмеченный такой переменной А, и его единственного сына, отмеченного а, одиночным узлом с отметкой а. Теперь каждый внутренний узел дерева разбора образует продукцию G₂, и мы приходим к выводу, что w е ЦС72). □

Нормальная форма Грейбах

Существует еще одна интересная нормальная форма для грамматик, которая не будет обоснована. Любой непустой язык, не включающий е, есть L(G) для некоторой грам­матики G с продукциями вида А —> аа, где а — терминал, а а— цепочка из нуля или нескольких переменных. Преобразование грамматики к этой форме является слож­ным, даже если задачу упростить, скажем, начав с НФХ-грамматики. Иначе говоря, первая переменная каждой продукции расширяется до тех пор, пока не будет получен терминал. Однако на этом пути возможны циклы, в которых терминал не достигается, и этот процесс необходимо «замкнуть». Для того чтобы породить все последователь­ности переменных, которые могут появиться на пути к порождению этого терминала, создается продукция с терминалом в качестве первого символа тела и переменными вслед за ним.

Эта форма, называемая нормальной формой Грейбах, по имени Шейлы Грейбах (Sheila Greibach), которая первой дала способ построения таких грамматик, имеет не­сколько интересных следствий. Поскольку каждое использование продукции вводит ровно один терминал в выводимую цепочку, цепочка длины п порождается в точно­сти за п шагов. Кроме того, если применить конструкцию из теоремы 6.13 для по­строения МП-автомата по грамматике в нормальной форме Грейбах, то получается МП-автомат без е-переходов, показывающий, что такие переходы в МП-автомате всегда можно удалить.

7.1.6. Упражнения к разделу 7.1

(*) Найдите грамматику, не содержащую бесполезных символов и эквивалент­ную следующей грамматике.

S АВ \ СА А а В-^ВС\АВ С аВ\Ь

Рассмотрите следующую грамматику: S ASB|е

А aAS \ а В —> SbS \A\bb а) удалите е-продукции;

б)  удалите цепные продукции;

в)   есть ли здесь бесполезные символы? Если да, удалите их;

г)   приведите грамматику к нормальной форме Хомского.

Выполните упражнение 7.1.2 со следующей грамматикой.

S-*0A0 | 1В1 | ВВ Л —»С B—>Sj Л С—>51 е

Выполните упражнение 7.1.2 со следующей грамматикой.

S^AAA\B А аА j В

Выполните упражнение 7.1.2 со следующей грамматикой.

S—» аАа | ЬВЬ \ е А—>С\а

С —» CDE|е

Постройте НФХ-грамматику для множества цепочек сбалансированных скобок. Можно начать с грамматики, находящейся в НФХ.

(!!) Пусть G — КС-грамматика с р продукциями и длины тел продукций не пре­восходят п. Докажите, что если А => е, то найдется порождение £ из А, в кото-

G

ром не более, чем (и^р — 1)/(п — 1) шагов. Как близко можно на самом деле подой­ти к этой границе?

(!) Предположим, что нам дана грамматика Gen продукциями, ни одна из кото­рых не является £-продукцией, и мы преобразуем ее в НФХ:

а)  докажите, что НФХ-грамматика имеет не более, чем 0(п²) продукций;

б)  докажите, что у НФХ-грамматики число продукций может быть прямо про­порциональным п². Указание. Рассмотрите конструкцию удаления цепных продукций.

Дайте индуктивные доказательства, необходимые для завершения следующих теорем:

а) часть теоремы 7.4, в которой доказывалось, что обнаруживаемые символы действительно являются порождающими;

б)   теорема 7.6 в обе стороны, где доказывалась корректность алгоритма из раз­дела 7.1.2 для обнаружения достижимых символов;

в)   часть теоремы 7.11, где доказывалось, что все обнаруженные пары действи­тельно являются цепными парами.

(*!) Можно ли для каждого КС-языка найти грамматику, все продукции которой имеют вид или А —» BCD (тело состоит из трех переменных), или А а (тело образовано одиночным терминалом)? Приведите либо доказательство, либо контрпример.

В этом упражнении показывается, что для каждого КС-языка L, содержащего хотя бы одну непустую цепочку, найдется КС-грамматика в нормальной форме Грейбах, порождающая L — {е}. Напомним, что тела продукций грамматики в нормальной форме Грейбах (НФГ) начинаются терминалом. В построении ис­пользуется ряд лемм и конструкций.

Пусть КС-грамматика G имеет продукцию А —> аВ(3, и всеми продукциями для В являются В —» у/1 у₂1 … | у„. Заменив А —> осВ/З всеми продукциями, у которых вместо В подставлены тела всех б-продукций, получим А —> осуф\ ауф1 … | ау„Д Построенная грамматика порождает тот же язык, что и G.

Далее будем предполагать, что грамматика G для L находится в нормальной форме Хомского, а ее переменные обозначены A_h А₂, …, А_к.

(*!) Докажите, что путем повторных применений преобразования из части 1 грамматику G можно превратить в эквивалентную грамматику, у которой тело каждой продукции для А, начинается или терминалом, или A_t для неко­торого j > i. В обоих случаях все символы после первого в теле продукции — переменные.

(!) Пусть G/— грамматика, полученная из G путем выполнения шага 2. Пусть А,— произвольная переменная и А, —» А,а,\ … | А,а_т— все А,- продукции, тело которых начинается с А,. Пусть А, —» Д1 … | Д,— все ос­тальные Aj-продукции. Заметим, что каждое Д начинается либо терминалом, либо переменной с индексом больше /. Введем новую переменную В/ и заме­ним первую группу из т продукций следующими:

-^РЛ-ЛРп

а/В, I а, I … I а_тВ, | а_т

Докажите, что полученная грамматика порождает тот же язык, что и G или G,.

(*!) Пусть после шага 3 получена грамматика G₂. Отметим, что тела всех А,- продукций начинаются или терминалом, или Aj с j > i. Кроме того, тела В,- продукций начинаются или терминалом, или некоторым Aj. Докажите, что G₂ имеет эквивалентную грамматику в НФГ. Указание. Сначала преобразуй-

те должным образом продукции для А_к, затем для _; и так далее до A _h ис­пользуя часть 1. Затем снова с помощью части 1 преобразуйте продукции для В, в любом порядке. 7.1.12. Используйте построения из упражнения 7.1.11 для преобразования в НФГ сле­дующей грамматики.

S-+AA |0 А SS | 1

7.2. Лемма о накачке для контекстно-свободных языков

В этом разделе развивается инструмент доказательства, что некоторые языки не яв­ляются контекстно-свободными. Теорема, называемая «леммой о накачке для контекст­но-свободных языков»^[1], гласит, что в любой достаточно длинной цепочке КС-языка можно найти две близлежащие короткие подцепочки (одна из них может быть пустой) и совместно их «накачивать». Таким образом, обе подцепочки можно повторить / раз для любого целого /, и полученная цепочка также будет принадлежать языку.

Эта теорема отличается от аналогичной для регулярных языков (теорема 4.1), глася­щей, что всегда можно найти одну короткую цепочку для ее накачки. Разница видна, ес­ли рассмотреть язык типа L= {0″lⁿ | и > 1}. Можно показать, что он нерегулярен, если зафиксировать п и накачать подцепочку из нулей, получив цепочку, в которой символов О больше, чем 1. Однако лемма о накачке для КС-языков утверждает, что можно найти две короткие цепочки, поэтому нам пришлось бы использовать для накачки цепочку из нулей и цепочку из единиц, порождая таким образом только цепочки из L. Этот резуль­тат нас устраивает, так как L — КС-язык, а для построения цепочек, не принадлежащих языку L, лемма о накачке для КС-языков использоваться и не должна.

7.2.1. Размер деревьев разбора

Первый шаг на пути к лемме о накачке для КС-языков состоит в том, чтобы рассмот­реть вид и размер деревьев разбора. Одно из применений НФХ — преобразовывать де­ревья разбора в бинарные (двоичные). Такие деревья имеют ряд удобных свойств, и одно из них используется здесь.

Теорема 7.17. Пусть дано дерево разбора, соответствующее НФХ-грамматике G= (V, Т, Р, S), и пусть кроной дерева является терминальная цепочка w. Если п — наи­большая длина пути (от корня к листьям), то |w| < 2″ ¹.

Доказательство. Докажем с помощью простой индукции по п.

Базис. и= 1. Напомним, что длина пути есть число ребер, т.е. на 1 меньше числа узлов. Таким образом, дерево с максимальной длиной пути 1 состоит из корня и листа, отмеченного терминалом. Цепочка w является этим терминалом, и |w| = 1. Поскольку = 2° = 1, базис доказан.

Индукция. Предположим, самый длинный путь имеет длину п, и п> 1. Корень де-‘ рева использует продукцию, которая должна иметь вид А —> ВС, поскольку п > 1, т.е. нельзя начать дерево, использовав продукцию с терминалом. Ни один из путей в под­деревьях с корнями в В и С не может иметь длину больше, чем п— 1, так как в этих пу­тях исключено ребро от корня к сыну, отмеченному В или С. Таким образом, по пред­положению индукции эти два поддерева имеют кроны длины не более 2″~². Крона все­го дерева представляет собой конкатенацию этих двух крон, поэтому имеет длину не более 2^П~² + 2″~² = 2″~². Шаг индукции доказан. □

7.2.2. Утверждение леммы о накачке

Лемма о накачке для КС-языков подобна лемме о накачке для регулярных языков, но каждая цепочка z КС-языка L разбивается на пять частей, и совместно накачиваются вто­рая и четвертая из них.

Теорема 7.18. (Лемма о накачке для КС-языков.) Пусть L — КС-язык. Тогда сущест­вует такая константа п, что если z— произвольная цепочка из L, длина которой не меньше п, то можно записать z = uvwxy, причем выполняются следующие условия.

\vwx\ < п. Таким образом, средняя часть не слишком длинная.

vx Ф е. Поскольку v и х — подцепочки, которые должны «накачиваться», это условие гласит, что хотя бы одна из них непуста.

uv’wx’y е L для всех i > 0. Две цепочки, v и х, могут быть «накачаны» произвольное число раз, включая 0, и полученная при этом цепочка также будет принадлежать L.

Доказательство. Вначале для L найдем грамматику G в нормальной форме Хомско­го. Технически это невозможно, если L есть КС-язык 0 или {£}. Однако при L = 0 ут­верждение теоремы, которое говорит о цепочке z, не может быть нарушено, поскольку такой цепочки z нет в 0. НФХ-грамматика G в действительности порождает L- {£}, но это также не имеет значения, поскольку выбирается п > 0, и z никак не сможет быть £.

Итак, пусть НФХ-грамматика G = (V, T,P,S) имеет т переменных и порождает язык L(G)= L~ {£}. Выберем п = 2™. Предположим, что z из L имеет длину не менее п. По теореме 7.17 любое дерево разбора, наибольшая длина путей в котором не превышает т, должно иметь крону длиной не более 2^т~¹ = и/2. Такое дерево разбора не может иметь крону z, так как z для этого слишком длинная. Таким образом, любое дерево разбора с кроной z имеет путь длиной не менее т + 1.

На рис. 7.5 представлен самый длинный путь в дереве для z, где к не менее т, и путь имеет длину к + 1. Поскольку к > т, на этом пути встречается не менее т + 1 переменных Ао, А/, …, А_к. Но V содержит всего т различных переменных, поэтому хотя бы две из т+ 1 последних переменных на пути (т.е. от _т до А* включительно) должны совпа­дать. Пусть Л,- = Ар где к- т< i <] < к.

Тогда дерево можно разделить так, как показано на рис. 7.6. Цепочка w является кро­ной поддерева с корнем Aj. Цепочки v и х — это цепочки соответственно слева и справа от w в кроне большего поддерева с корнем А/. Заметим, что цепных продукций нет, по­этому v и х не могут одновременно быть е, хотя одна из них и может. Наконец, и и у об­разуют части z, лежащие соответственно слева и справа от поддерева с корнем А,.

Рис. 7.5. Каждая достаточно длинная цепочка в L должна иметь длинный путь в своем дереве разбора

Если Л, = Aj = А, то по исходному дереву можно построить новое дерево разбора, как показано на рис. 7.7, а. Сначала можно заменить поддерево с корнем А,-, имеющее крону vwx, поддеревом с корнем А„ у которого крона w. Это допустимо, поскольку корни обоих поддеревьев отмечены одной и той же переменной А. Полученное дерево представлено на рис. 7.7, б. Оно имеет крону и соответствует случаю / = 0 в шаблоне цепочек uv’wx’y.

Еще одна возможность представлена на рис. 7.7, в. Там поддерево с корнем Aj заме­нено поддеревом с корнем А,. Допустимость этой замены также обусловлена тем, что отметки корней совпадают. Кроной этого дерева является uv^zwx²y. Если бы мы затем за­менили поддерево с кроной w (см. рис. 7.7, в) большим поддеревом с кроной vwx, то по­лучили бы дерево с кроной uvⁱwx²‘y и так далее для любого показателя i. Итак, в G суще­ствуют деревья разбора для всех цепочек вида uv’wx’y, и лемма о накачке почти доказана.

Осталось условие 1, гласящее, что \vwx\ < п. Мы выбирали А, как можно ближе к кро­не дерева, поэтому k — i<m. Таким образом, самый длинный путь в поддереве с корнем

S ———————— z                                                            ► Рис. 7.6. Разделение цепочки z для накачивания

7.2.3. Приложения леллллы о накачке к КС-языкам

Отметим, что лемма о накачке для КС-языков, как и для регулярных языков, исполь­зуется в виде «игры с противником» следующим образом.

Мы выбираем язык L, желая доказать, что он не контекстно-свободный.

Наш «противник» выбирает заранее неизвестное нам п, поэтому мы должны рассчи­тывать на любое возможное значение.

Мы выбираем z и при этом можем использовать п как параметр.

Противник разбивает z на uvwxy, соблюдая ограничения |vwx| < п и vx * е.

Мы «выигрываем», если можем, выбирая i и показывая, что uvwx’y не принадле­жит языку L.

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

Aj имеет длину не более т + 1. По теореме 7.17 поддерево с корнем At имеет крону, дли­на которой не больше, чем 2™ = п. □

Пример 7.19. Пусть L = {0″Г2^П | п > 1}, т.е. L состоит из цепочек вида 0⁺1⁺2⁺ с оди­наковыми количествами каждого из символов, например, 012, 001122 и т.д. Предполо­
жим, что L контекстно-свободный. Тогда существует целое п из леммы о накачке.^[2] Вы­берем 0″ 1 «2».

Рис. 7.7. Накачивание цепочек v их 0 раз и 2 раза

Предположим, что «противник» разбивает z как г = uvwxy, где |vwx| < п и v и х не равны е одновременно. Тогда нам известно, что vwx не может включать одновременно нули и двой­ки, поскольку последний нуль и первая двойка разделены п + 1 позициями. Докажем, что L содержит некоторую цепочку, которая не может быть в L, получив тем самым противоре­чие к предположению, что L контекстно-свободный. Возможны следующие случаи.

1. vwx не имеет двоек, т.е.vx состоит только из нулей и единиц и содержит хотя бы один из этих символов. Тогда цепочкаuwy, которая по лемме о накачке должна быть в L, имеет п двоек, но меньше, чем п нулей или единиц. Следовательно, она не при­надлежит L, и в этом случае L не контекстно-свободен.
2. vwx не имеет нулей. Аналогично,uwy имеет п нулей, но меньше двоек или единиц,

поэтому не принадлежит L. В любом случае приходим к выводу, что L содержит цепочку, которая не может ему принадлежать. Это противоречие позволяет заключить, что наше предположение ложно, т.е. L не является КС-языком. □

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

Пример 7.20. Пусть L = {0’l^j2’3^j | i > 1 и у > 1}. Если он контекстно-свободен, то пусть п — константа для L, и выберем г = 0ⁿlⁿ2ⁿ3″. Можно записать z = uvwxy, соблюдая обыч­ные ограничения \vwx\ < п и vx Ф г. Тогда vwx или состоит из символов одного вида, или захватывает символы двух различных соседних видов.

Если vwx состоит из символов одного вида, то uwy имеет по п символов трех различ­ных видов и меньше, чем п символов четвертого вида. Таким образом, uwy не может быть в L. Если vwx захватывает символы двух различных соседних видов, скажем, еди­ницы и двойки, то в uwy их не хватает. Если не хватает единиц, то, поскольку там есть п троек, эта цепочка не может быть в L. Если же не хватает двоек, то uwy также не может быть в L, поскольку содержит п нулей. Получаем противоречие к предположению о том, что L — КС-язык, и приходим к выводу, что он таковым не является. □

В заключительном примере покажем, что в цепочках КС-языков не может быть двух одинаковых цепочек произвольной длины, если они выбираются в алфавите, состоящем более чем из одного символа. Следствием этого замечания, между прочим, является то, что КС-грамматики не являются подходящим механизмом для описания определенных «семантических» ограничений в языках программирования, например, что идентифика­тор должен быть объявлен до его использования. На практике для запоминания объяв­ленных идентификаторов используется другой механизм, «таблица символов», и никто не пытается строить синтаксический анализатор, который проверял бы соблюдение принципа «определение до использования».

Пример 7.21. Пусть L — {ww | we {0, 1 }*}, т.е. L состоит из повторяющихся цепо­чек, например, е, 0101, 00100010 или 110110. Если он контекстно-свободный, то пусть п— константа из леммы о накачке для L. Рассмотрим цепочку z = 0ⁿlⁿ0ⁿlⁿ. Очевидно, z е L.

Следуя шаблону предыдущих примеров, можно записать z = uvwxy, причем |vwx| < п и vx Ф е. Покажем, что uwy не принадлежит L, тем самым доказав от противного, что L не может быть КС-языком.

Заметим сразу, что, поскольку |vwx| < п, то \uwy\ > Ъп. Таким образом, если uwy явля­ется повторением цепочки, скажем, tt, то t имеет длину не менее Зи/2. Возможны не­сколько вариантов в зависимости от расположения vwx в пределах z.

Предположим, vwx находится в пределах первых п нулей. Для определенности пусть vx состоит из к нулей, где к>0. Тогда uwy начинается с 0″~^к1^п. Поскольку \uwy\ = 4п-к и по предположению uwy = tt, то = 2п — к/2. Таким образом, t не заканчивается в первом блоке из единиц, т.е. заканчивается символом 0. Но uwy заканчивается единицей, поэтому не может равняться tt.

Предположим, vwx захватывает первый блок нулей и первый блок единиц. Воз­можно, vx состоит только из нулей, если х = е. Тогда uwy не может быть вида tt по той же причине, что и в случае 1. Если же vx содержит хотя бы одну единицу, то t, длина которой не менее Зп/2, должна заканчиваться на 1″, поскольку uwy заканчи­вается на 1″. Однако из п единиц состоит только последний блок в uwy, поэтому t не может повторяться в uwy.

Если vwx содержится в первом блоке единиц, то uwy не может быть в L по тем же причинам, что и во второй части случая 2.

Предположим, vwx захватывает первый блок единиц и второй блок нулей. Если vx не имеет нулей, то все получается так же, как если бы vwx содержалась в первом блоке единиц. Если vx содержит хотя бы один нуль, то uwy начинается блоком из п нулей, как и t, если uwy = tt. Однако в uwy второго блока из п нулей для t нет, по­этому uwy не может быть в L.

В остальных случаях, когда vwx находится во второй части z, аргументы симметрич­ны по отношению к случаям, когда vwx содержится в первой части z.

Итак, в любом случае uwy не принадлежит L, и мы приходим к выводу, что L не контек­стно-свободный.

7.2.4. Упражнения к разделу 7.2

7.2.1. Используйте лемму о накачке для КС-языков, чтобы показать, что каждый из

следующих языков не контекстно-свободный.

а)  (*) {dVc^k\i<j <к}-,

б)  {aⁿbⁿc’\i<n}-,

в)   {0^р|/>— простое}. Указание. Используйте те же идеи, что и в примере 4.3, где доказывалась нерегулярность этого языка;

г)   (*!){0’1 ^j|y = /²};

д)  (!) {a»Z>V|rc</<2rc};

е)   (!) {vfvf^Rvf | w— цепочка из нулей и единиц}, т.е. множество цепочек, со­стоящих из цепочки w, за которой записаны ее обращение и она же еще раз, например 001100001.

• (!) Когда мы пытаемся применить лемму о накачке к КС-языку, «выигрывает противник», и нам не удается завершить доказательство. Покажите, что является ошибочным, когда в качестве L выбирается один из следующих языков:

а)   {00,11};

б)   (*) {0^ПГ|«> 1};

в)   (*) множество палиндромов в алфавите {0, 1}.

• (!) Существует более сильная версия леммы о накачке для КС-языков, известная как лемма Огдена. Она отличается от доказанной леммы о накачке тем, что по­зволяет нам сосредоточиться на любых п «выделенных» позициях цепочки z и гарантирует, что накачиваемые цепочки содержат от 1 до п выделенных пози­ций. Преимущество этого свойства в том, что язык может иметь цепочки, со­стоящие из двух частей, одна из которых может быть накачана без создания це­почек, не принадлежащих языку, тогда как вторая при накачке обязательно по­рождает цепочки вне языка. Если мы не можем утверждать, что накачка имеет место во второй части, то мы не можем завершить доказательство того, что язык не контекстно-свободный. Формальное утверждение леммы Огдена состоит в следующем. Для любого КС-языка L существует такая константа п, что если z — произвольная цепочка из L длиной не менее п, в которой выделено не менее п различных позиций, то 2 можно записать в виде uvwxy, причем выполняются следующие условия.
  • vwx имеет не более п выделенных позиций.
  • vx имеет хотя бы одну выделенную позицию.
  • uv’wx’y е L для всех i >

Докажите лемму Огдена. Указание. Доказательство на самом деле весьма похо­же на доказательство леммы о накачке (теорема 7.18), если мы представим себе, что в том доказательстве невыделенные позиции цепочки 2 отсутствуют, когда выбирается длинный путь в дереве разбора для z.

• (*) Используйте лемму Огдена (упражнение 7.2.3) для упрощения доказательст­ва того, что L = {ww | we {0, 1 }*} —не КС-язык (см. пример 7.21). Указание. В выбранной цепочке z сделайте выделенной только одну группу из п последова­тельных символов.
• Используйте лемму Огдена (упражнение 7.2.3) для доказательства того, что сле­дующие языки не являются контекстно-свободными:

а)   (!) {0’1-«0^к \j = шах(/, к)};

б)  (!!) {a»b»c \ i Ф п). Указание. Рассмотрите цепочку z = aⁿbⁿcⁿ‘, где п— кон­станта из леммы Огдена.

7.3. Свойства замкнутости контекстно-свободных языков

Рассмотрим некоторые операции над контекстно-свободными языками, которые га­рантированно порождают КС-языки. Многие из этих свойств замкнутости соответствуют теоремам для регулярных языков из раздела 4.2. Однако есть и отличия.

Вначале введем операцию подстановки, по которой каждый символ в цепочках из од­ного языка заменяется целым языком. Эта операция обобщает гомоморфизм, рассмот­ренный в разделе 4.2.3, и является полезной в доказательстве свойств замкнутости КС- языков, относительно некоторых других операций, например, регулярных (объединение, конкатенация и замыкание). Покажем, что КС-языки замкнуты относительно гомомор­физма и обратного гомоморфизма. В отличие от регулярных языков, КС-языки не замк­нуты относительно пересечения и разности. Однако пересечение или разность КС-языка и регулярного языка всегда является КС-языком.

7.3.1. Подстановки

Пусть 2 — алфавит. Предположим, для каждого символа а из 2 выбран язык L_a. Вы­бранные языки могут быть в любых алфавитах, не обязательно 2 и не обязательно оди­наковых. Выбор языков определяет функцию s (подстановка, substitution) на 2, и L_a обо­значается как s(a) для каждого символа а.

Если w = а,а₂…а„— цепочка из 2*, то s(w) представляет собой язык всех цепочек xix₂…x„, у которых для /’ = 1,2, …, п цепочка х, принадлежит языку s(a,). Иными словами, s(w) является конкатенацией языков s(ai)s(a₂)…s(a„). Определение 5 можно распростра­нить на языки: s(L) — это объединение s(w) по всем цепочкам w из L.

Пример 7.22. Пусть s(0) = {aⁿbⁿ \ п > 1} и s(l) = {аа, bb), т.е. 5 — подстановка на ал­фавите 2= {0, 1}. Язык i(0) представляет собой множество цепочек с одним или не­сколькими символами а, за которыми следует такое же количество b, а.?(1) — конечный язык, состоящий из двух цепочек аа и bb.

Пусть w = 01. Тогда s(vv) есть конкатенация языков .s(0).s(l). Точнее, s(w) состоит из всех цепочек вида <fbⁿaa и <?Ь^п+г, где п > 1.

Теперь предположим, что L = 7.(0 ), т.е. множество всех цепочек из нулей. Тогда s(L) = (s(0))*. Этот язык представляет собой множество всех цепочек вида

a'»b'»a»>b’^h …c^b'»

для некоторого k>0 и произвольной последовательности положительных целых п,, п₂, …, щ. Он включает, например, цепочки £, aabbaaabbb и abaabbabab. □

Теорема 7.23. Если L — КС-язык в алфавите 2, а 5 — подстановка на 2, при которой i(a) является КС-языком для каждого а из 2, то s(L) также является КС-языком.

Доказательство. Основная идея состоит в том, что мы можем взять КС-грамматику для £ и заменить каждый терминал а стартовым символом грамматики для языка s(a). В результате получим единственную грамматику, порождающую s(L). Однако тут нужно быть аккуратным.

Более формально, пусть грамматика G = (V, X, Р, S) задает язык L, а грамматика G_a ⁼ (К, Т_а, Р_а, S_a) — язык, подставляемый вместо каждого а из X. Поскольку для пере­менных можно выбирать любые имена, обеспечим, чтобы множества имен переменных V и V_a (для всех а) не пересекались. Цель такого выбора имен — гарантировать, что при сборе продукций разных грамматик в одно множество невозможно случайно смешать продукции двух грамматик, и, таким образом, получить порождения, невозможные в данных грамматиках.

Построим новую грамматику G’~ (V, Т\ Р’, S) для s(L) следующим образом.

• V’ представляет собой объединение V и всех V_a по а из X.
• Т’ является объединением Т_а по а из X.
• Р’ состоит из следующих продукций.
  • Все продукции каждого из Р_а для а из X.
  • Все продукции Р, но с изменением везде в их телах каждого терминала а на S_a.

Таким образом, все деревья разбора в грамматике G’ начинаются как деревья разбора в G, но вместо того, чтобы порождать крону в X , они содержат границу, на которой все узлы отмечены переменными S_a вместо а из X. Каждый такой узел является корнем дере­ва в G_a, крона которого представляет собой терминальную цепочку из s(a) (рис. 7.8).

s Рис. 7.8. Дерево разбора в G’ начинается деревом разбора в G и заканчивается многими деревьями, соответствующими грамматикам Ga

Докажем, что описанная конструкция правильна в том смысле, что G’ порождает язык s(L). Формально будет доказано следующее утверждение.

• Цепочка w принадлежит L(G’) тогда и только тогда, когда w принадлежит s{L).

(Достаточность) Пусть w принадлежит s(L). Тогда существует цепочка х = а,а₂…а„ в L и такие цепочких, в s(a,) при i= 1, 2, …, п, для которых vv = х,х₂…х„. Тогда часть G’, образованная продукциями из G с подстановками S_a вместо каждого а, порождает цепоч­ку, которая выглядит, как х, но с S_a вместо каждого а, т.е. цепочку S_a,S_a2…S_an. Эта часть порождения w представлена верхним треугольником на рис. 7.8.

Продукции каждой G_a являются также продукциями G’ поэтому порождение х, из S_a, есть также порождение в G’. Деревья разбора для этих порождений представлены на рис. 7.8 нижними треугольниками. Поскольку крона этого дерева разбора в G’ есть xix₂…x„ = w, приходим к выводу, что w принадлежит L(G’).

(Необходимость) Предположим, что w принадлежит L(G’). Утверждаем, что дерево разбора для w должно выглядеть, как дерево на рис. 7.8. Причина в том, что перемен­ные каждой из грамматик G и G_a для а из £ попарно различны. Таким образом, вер­хушка дерева, начинающаяся переменной S, должна использовать только продукции G до тех пор, пока не будет порожден некоторый символ S_a, а под этим символом могут использоваться только продукции грамматики G_a. В результате, если w имеет дерево разбора Т, можно выделить цепочку а₁а₂…а„ в L(G) и цепочки х, в языках s(a,), для ко­торых верно следующее.

• и> = х/х₂…х„.
• Цепочка S_alS_a2…S_a„ является кроной дерева, образованного из Г удалением некото­рых поддеревьев (см. рис. 7.8).

Но цепочка xix₂…x„ принадлежит s(L), поскольку образована подстановкой цепочек х, вместо каждого из а,. Таким образом, делаем вывод, что w принадлежит s(L). □

7.3.2. Приложения теоремы о подстановке

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

Теорема 7.24. Контекстно-свободные языки замкнуты относительно следующих операций.

• Объединение.
• Конкатенация.
• Замыкание (*) и транзитивное замыкание (⁺).
• Гомоморфизм.

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

• Объединение. ПустьLi иL₂— КС-языки. Тогда L,{J L₂ является языком s(L), где L — язык {1, 2}, as — подстановка, определяемая как.s(l) = L, и s(2) = L₂.
• Конкатенация. ПустьL_t и L₂ — КС-языки. Тогда LiL₂ представляет собой язык s(L), где L — язык {12}, a s — такая же подстановка, как и в п. 1.
• Замыкание и транзитивное замыкание. ЕслиLj — КС-язык,L — язык {1 }*, a s — подстановка s(l) =L_h то L* = s(L). Аналогично, если в качестве L взять язык {1}⁺, то Li = s(L).
• Пусть L — КС-язык над алфавитом X, и h — гомоморфизм на X. Пусть s — подста­новка, заменяющая каждый символ а из X языком, состоящим из единственной це­почки h(a), т.е. s(a) = {h(a)} для всех а из X. Тогда h(L) = s(L).

□

Обращение

КС-языки замкнуты также относительно обращения. Для доказательства этого факта использовать теорему о подстановках нельзя, но существует простая конструкция на ос­нове грамматик.

Теорема 7.25. Если L — КС-язык, то и L^K — КС-язык.

Доказательство. Пусть L— L(G) для некоторой КС-грамматики G = (V, Т, Р, S). По­строим G^r = (V, Т, P^R, S), где продукции P^R представляют собой «обращения» продукций из Р. Таким образом, если А а — продукция G, то А —»с/ — продукция G^R. С помо­щью индукции по длине порождений bGh6^r нетрудно показать, что ЦС^Я) = I^я. По су­ти, все выводимые в G^R цепочки являются обращениями цепочек, выводимых в G, и на­оборот. Формальное доказательство оставляется в качестве упражнения. □

Пересечение с регулярным языком

КС-языки не замкнуты по пересечению. Это доказывает следующий простой пример. Пример 7.26. В примере 7.19 было выяснено, что язык

L = {0^П1″2^П | и > 1}

не является контекстно-свободным. Однако следующие два — контекстно-свободные. L = {0″1^п2′ | л > 1, i> 1} L = {0’1^П2^П | л > 1, i > 1} Первый из них порождается следующей грамматикой. S—>AB Л->0Л1 | 01 В-+2В\2

В этой грамматике А порождает все цепочки вида 0^П1^П, а В— все последовательности двоек. Аналогична и грамматика для второго языка.

S->AB А OA | 0 В->\В2\ 12

Здесь А порождает все последовательности нулей, а В — цепочки вида 1^П2^П.

Однако L = L/f)L₂. Чтобы в этом убедиться, заметим, что L_t требует равных коли­честв нулей и единиц в цепочках, тогда как L₂ — равных количеств единиц и двоек. По­этому цепочка из пересечения этих языков должна иметь поровну каждого из символов и, следовательно, принадлежать L.

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

Вместе с тем, есть более слабое утверждение о пересечении. КС-языки замкнуты от­носительно операции «пересечение с регулярным языком». Формальное утверждение и его доказательство представлены в следующей теореме.

Теорема 7.27. Если L — КС-язык, a R — регулярный язык, то L П R является КС- языком.

Доказательство. Нам понадобится представление КС-языков с помощью МП- автоматов, а также конечноавтоматное представление регулярных языков. Данное до­казательство обобщает доказательство теоремы 4.8, где для получения пересечения регулярных языков «параллельно запускались» два конечных автомата. Здесь конеч­ный автомат запускается параллельно с МП-автоматом, и в результате получается еще один МП-автомат (рис. 7.9).

Магазин

Рис. 7.9. Для создания нового МП-автомата конечный автомат и МП-автомат запускаются параллельно

Формально, пусть

Р = (а, X, Г, <5;., q_r, Z<), F_t.) — МП-автомат, допускающий L по заключительному состоянию, и пусть

А = (Qa, q_A, F_a) — ДКА для R. Построим МП-автомат

Р’ = (Qr х а, X, Г, <5, (ф, Z₀, Fp х

л

где S((q,p), a, JO определяется как множество всех пар ((г, s), у), где s = 8 _А(р, а) и пара (г, у) принадлежит 8p(q, А, X).

Таким образом, для каждого перехода МП-автомата Р мы можем совершить такой же переход в МП-автомате Р\ дополнительно отслеживая состояние ДКА А во втором ком­поненте состояния Р’. Отметим, что а может быть символом из X или е. В первом случае

Л                                                                                                                                                                                                                Л

8 _А{р, а) = 8_А(р, а), но если а = £, то 8 _А(р, а) =р, т.е. А не меняет состояние, когда Р со­вершает е-переход.

С помощью простой индукции по числу переходов, совершаемых МП-автоматами, нетрудно доказать, что (q_r, w, Z₀) f^ (q, e, у) тогда и только тогда, когда ((q,,, q_A), w, Z₀) |-

Л

((q,p), £, У), где p = 8 _A{p,w). Эти индукции оставляются в качестве упражнения. Но (q,p) является допускающим состоянием Я’тогда и только тогда, когда q— допускаю­щее состояние Р и р — допускающее состояние А. Отсюда заключаем, что Р’ допускает w тогда и только тогда, когда его допускают Р и А вместе, т.е. w принадлежит L П R- О

Пример 7.28. На рис. 6.6 был определен МП-автомат F, допускающий по заключи­тельному состоянию множество цепочек, которые состоят из i и е. Такие цепочки представляют минимальные нарушения правил, определяющих, в каком порядке слова if и else могут встречаться в С-программах. Назовем этот язык L. МП-автомат F был определен так:

Pf = ({p, q, г}, {/’, е}, {Z,x₀}, s_F,p,x₀, {г}), где 8;. состоит из следующих правил.

S_t(p,e,Xo)=[(q,ZXo)}.

S_F(q,i,Z)={(q,ZZ)}.

{(<7,£)}.

_7> е,*₀) = {(/■,£)}.

Теперь определим конечный автомат A = ({s, t), {/, е}, S_A, s, {.?, t}), допускающий цепочки языка i’e*, т.е. все цепочки, в которых символы е следуют за i. На­зовем этот язык R. Функция переходов 8_А определяется следующими правилами:

а)  S_A(s, i) =

б)  S_A(s,e) = t;

в)   8_A(t,e)-t.

Строго говоря, А не является ДКА, как предполагается в теореме 7.27, поскольку в нем отсутствует дьявольское состояние для случая, когда вход / получен в состоянии t. Одна­ко такая же конструкция работает даже для НКА, так как МП-автомат, который строится, может быть недетерминированным. В данном же случае МП-автомат на самом деле де­терминирован, хотя и «умирает» на некоторых входных последовательностях. Построим следующий МП-автомат.

Р = ({/>, д, г] х {s, t}, {/, е}, {Z, X₀j, S, (р, s), Х₀, {/■} х {_s, t}) Переходы 8 перечислены ниже и проиндексированы номерами правил для МП-автомата F (числа от 1 до 4) и правил для ДКА А (буквы а, б, в). Если МП-автомат F совершает е- переход, правило для А не используется. Отметим, что правила для автомата Р строятся «ленивым» способом: правила для состояния строятся только тогда, когда обнаружено, что оно достигается из начального состояния Р.

1. 8((p,s),E,X₀)={((g,s),ZX₀)}.
2. 5{{q,s\i,Z) = {((g, s),ZZ)j.

3,6. %(q,s), e,Z)= {((<?, !),£)}.

4. 5{(q, s), £,X₀) = {(r, s), e)}. Отметим, что это правило никогда не будет применяться, поскольку невозможно вытолкнуть символ из магазина без е на входе, но как только Р видит е, вторым компонентом его состояния становится t.

в. S((g, l), e,Z)={((q,t),£)}. 4. 5{(д, t),£,X_fl)={((r, !),£)}.

Язык L П R представляет собой множество цепочек с некоторым количеством симво­лов /, за которыми записаны символы е (на один больше), т.е. {z’ⁿeⁿ⁺¹1 п > 0}. Как видим, такие блоки символов i с блоками символов е нарушают правила записи слов if и else в языке С. Этот язык, очевидно, является КС-языком, порождаемым грамматикой с про­дукциями S —> iSe | е.

Заметим, что МП-автомат Р допускает язык Lf]R. После помещения Z в магазин он заносит новые символы Z в магазин при чтении символов /’, оставаясь в состоянии (q, s). Как только на входе появляется е, он переходит в состояние (д, t) и начинает выталкива­ние из магазина. Он умирает, если видит i до того, как Х₀ оказывается на вершине мага­зина. В последнем же случае он спонтанно переходит в состояние (г, t) и допускает. □

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

Теорема 7.29. Пусть L_h L₂ и L обозначают КС-языки, a R — регулярный язык. Спра­ведливы следующие утверждения.

L-R является контекстно-свободным языком.

L может не быть КС-языком.

L\-L₂ может не быть КС-языком.

Доказательство. Для п. 1 заметим, что L — R = L П R ■ Если R регулярно, то по тео­реме 4.5 регулярно и R . Тогда по теореме 7.27 L — R — КС-язык.

Для п. 2 предположим, что если L является КС-языком, то L — КС-язык. Но по­скольку Li{\L₂= 1_л и Ц , и КС-языки замкнуты по объединению, получаем, что они

замкнуты и по пересечению. Однако это невозможно (см. пример 7.26).

Наконец, докажем п. 3. Очевидно, X* является КС-языком для любого алфавита X; не­трудно построить КС-грамматику или МП-автомат для этого регулярного языка. Таким образом, если бы язык Lj- L₂ был контекстно-свободным для любых КС-языков L_; и Ь₂, то и X* — L должен быть КС-языком, если L — КС-язык. Однако X* — L = L при соответ­ствующем алфавите X. Полученное противоречие к утверждению 2 доказывает, что Li — L₂ не обязательно является КС-языком. □

7.3.5. Обратный гомоморфизм

Вспомним операцию «обратного гомоморфизма» из раздела 4.2.4. Если h— гомо­морфизм, a L — произвольный язык, то h~\L) представляет собой множество таких це­почек w, для которых h(w) е L. Доказательство того, что регулярные языки замкнуты от­носительно обратного гомоморфизма, представлено на рис. 4.6. Там показано, как стро­ится конечный автомат, обрабатывающий свои входные символы а путем применения к ним гомоморфизма h и имитации другого конечного автомата на цепочках h(a).

Замкнутость относительно обратного гомоморфизма можно доказать подобным пу­тем, используя МП-автоматы вместо конечных автоматов. Однако при использовании МП-автоматов возникает проблема, которой не было с конечными автоматами. Действие конечного автомата при обработке входной цепочки заключается в изменении состояния, и это выглядит так же, как переход по одиночному входному символу.

Однако для МП-автоматов последовательность переходов может быть не похожа на переход по одному входному символу. В частности, за п переходов МП-автомат может вытолкнуть п символов из своего магазина, тогда как при одном переходе выталкивается только один. Таким образом, конструкция МП-автоматов, аналогичная представленной на рис. 4.6, будет существенно сложнее; она изображена эскизно на рис. 7.10. Дополни­тельная ключевая идея заключается в том, что, когда прочитан вход а, цепочка h(a) по­мещается в «буфер». Символы h(a) используются по одному и подаются на вход имити­руемому МП-автомату. Когда буфер опустошается, основной МП-автомат читает свой следующий входной символ и применяет гомоморфизм к нему. Эта конструкция уточня­ется в следующей теореме.

Рис. 7.10. Построение МП-автомата, допускающего обратный гомоморфизм того, что допускает данный МП-автомат

Теорема 7.30. Пусть L — КС-язык, h — гомоморфизм. Тогда h ‘(/,) является КС- языком.

Доказательство. Пусть h применяется к символам из алфавита X и порождает цепоч­ки из 7’. Предположим также, что L — язык в алфавите Т, допускаемый по заключитель­ному состоянию МП-автоматом Р = (Q, Т, Г, S, q₀, Z₀, F). Построим следующий новый МП-автомат Р’.

F = (Q’, X, Г, <У, (q₀, £), Z₀, F х {£})                                                   (7.1)

Обозначения в определении Р’имеют следующий смысл.

g’есть множество пар (q, х), где q — состояние из Q, а х — суффикс (не обязательно собственный) некоторой цепочки h(a) для символа а из X. Таким образом, первый компонент состояния Р’ является состоянием Р, а второй— компонентом буфера. Предполагается, что буфер периодически загружается цепочкой h(a), а затем сокра­щается с головы по мере чтения его символов, которые подаются на вход имитируе­мому МП-автомату Р.

8′ определяется следующими правилами:

а)  8\(q, е), а,Х)= {((q, h(a)), X)} для всех символов а из Z, всех состояний q из Q и магазинных символов X из Г. Отметим, что здесь а не может быть е. Ко­гда буфер пуст, Р’может прочитать свой следующий входной символ а и по­местить h(a) в буфер;

б)  если <5(7/, /;, X) содержит (р, у), где b е Т или b = е, то 8′((q, bx), е, X) содержит ((р, .г), у). Таким образом, Р’всегда имеет возможность имитации перехода Р, используя голову буфера. Если fee Т, то буфер должен быть непустым, но если b = е, то буфер может быть пустым.

Отметим, что в соответствии с определением (7.1) начальным состоянием Р’ являет­ся (q„, е), т.е. Р’стартует в начальном состоянии Р с пустым буфером.

Аналогично, допускающими состояниями Р’являются такие состояния (q, е), у кото­рых q — допускающее состояние Р.

Следующее утверждение характеризует взаимосвязь Р» и Р.

* *

• (q₀, h(w), Zo) |- (р, е, у) тогда и только тогда, когда ((q,_h е), w, Z„) \-_t ((р, е), е, у).

Доказательство в обоих направлениях проводится индукцией по числу переходов, со­вершаемых автоматами. При доказательстве достаточности заметим, что если буфер Р’ не пуст, то он не может читать свой следующий входной символ, а должен имитировать Р до тех пор, пока буфер не опустошится (хотя когда буфер пуст, он все еще может ими­тировать Р). Детали оставляются в качестве упражнения.

Приняв указанную взаимосвязь Р и Р\ заметим, что вследствие способа, которым оп­ределены допускающие состояния Р\ Р допускает h(w) тогда и только тогда, когда /»до­пускает w. Таким образом, ЦР’) = h’^x(L(P)). □

7.3.6. Упражнения к разделу 7.3

Докажите, что КС-языки замкнуты относительно следующих операций:

а)  (#) Init, определенная в упражнении 4.2.6, в. Указание. Начните с НФХ- грамматики для языка L;

б)  (*!) операция L/a, определенная в упражнении 4.2.2. Указание. Начните с НФХ-грамматики для языка Z,;

в)   (!!) Cycle, определенная в упражнении 4.2.11. Указание. Используйте конст­рукцию, основанную на МП-автомате.

Рассмотрим следующие два языка:

L_t = {aⁿb²ⁿc^m \n,m>0}

L₂ = {aⁿb^mc^2m \n,m>Q}

а)  покажите, что каждый из них является контекстно-свободным, построив для них КС-грамматики;

б)  (!) укажите, является ли L_t f| L₂ КС-языком. Ответ обоснуйте.

(!!) Покажите, что КС-языки не замкнуты относительно следующих операций:

а)  (#) Мл, определенная в упражнении 4.2.6, а;

б)  Мах, определенная в упражнении 4.2.6, б;

в)   Half, определенная в упражнении 4.2.8;

г)   Alt, определенная в упражнении 4.2.7.

Shuffle (Перемешивание) двух цепочек w их является множеством всех цепочек, которые можно получить путем произвольного чередования позиций w их. Точ­нее, shuffle(w, х) есть множество цепочек z, обладающих следующими свойствами.

Каждая позиция z может быть назначена w или х, но не обеим сразу.

Позиции z, назначенные w, при чтении слева направо образуют w.

Позиции z, назначенные х, при чтении слева направо образуют х. Например, если w = 01 и х= 110, то shuffle{0\, 110) есть множество цепочек {01110, 01101, 10110, 10101, 11010, 11001}. Для иллюстрации рассмотрим це­почку 10110. Ее вторая и пятая позиции назначены 01, а первая, третья и четвер­тая — 110. Цепочка 01110 может быть построена тремя способами: позиция 1 и одна из 2, 3, 4 назначается 01, а оставшиеся три в каждом случае — 110. Перемешивание языков, shuffle{L_h Ь₂), определяется как объединение shuffle(w, х) по всем парам цепочек, w из L_t их из L₂.

а)  постройте shuffle(00, 111);

б)  (*) укажите, что представляет собой shuffle(L,, L₂), если L, -1(0*) и L₂ = {0ⁿlⁿ | и > 0};

в)   (*!) докажите, что если L, и L₂ — регулярные языки, то и shuffle(L_h L₂) регу­лярен. Указание. Начните с конечных автоматов для Z,/ и L₂;

г)   (!) докажите, что если L является КС-языком, a R — регулярным языком, то shuffle(L, R) — КС-язык. Указание. Начните с МП-автомата для L и ДКА для R;

д)  (!!) приведите контрпример, показывающий, что если Li mL₂ — КС-языки, то shuffle(L_h L₂) может не быть КС-языком.

(*!!) Цепочка у называется перестановкой цепочки х, если символы у можно пере­упорядочить и получить х. Например, перестановками цепочки х = 011 являются 110, 101 и 011. Если L — язык, то perm(L) — это множество цепочек, являющихся перестановками цепочек из L. Например, если L = {0″Г | п > 0}, то perm(L) пред­ставляет собой множество цепочек, в которых поровну символов 0 и 1:

а)   приведите пример регулярного языка L над алфавитом {0, 1}, для которого perm(L) нерегулярен. Ответ обоснуйте. Указание. Попытайтесь найти регу­лярный язык, перестановками цепочек которого являются все цепочки с оди­наковыми количествами 0 и 1;

б)   приведите пример регулярного языка L в алфавите {0, 1, 2}, для которого perm(L) не является КС-языком;

в)   докажите, что для каждого регулярного языка L в двухсимвольном алфавите perm(L) является КС-языком.

Приведите формальное доказательство теоремы 7.25 о том, что КС-языки замк­нуты относительно обращения.

Дополните доказательство теоремы 7.27, показав, что (q_Р, w, Z₀) (<7, е, у)

тогда и только тогда, когда {(q_r, q_A), w, Z„) ((<7, p), e, 7) и p = S (p_A, w).

7.4. Свойства разрешимости КС-языков

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

Мы обнаружим, что разрешимых вопросов, связанных с КС-языками, совсем не­много. Основное, что можно сделать, — это проверить, пуст ли язык, и принадлежит ли данная цепочка языку. Этот раздел завершается кратким обсуждением проблем, ко­торые являются, как будет показано в главе 9, «неразрешимыми», т.е. не имеющими алгоритма разрешения. Начнем этот раздел с некоторых замечаний о сложности пре­образований между грамматиками и МП-автоматами, задающими язык. Эти расчеты важны в любом вопросе об эффективности разрешения свойств КС-языков по данному их представлению.

7.4.1. Сложность взаимных преобразований КС-грамматик и МП-автоматов

Прежде чем приступать к алгоритмам разрешения вопросов о КС-языках, рассмотрим сложность преобразования одного представления в другое. Время выполнения преобра­зования является составной частью стоимости алгоритма разрешения в тех случаях, ко­гда алгоритм построен для одной формы представления, а язык дан в другой.

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

Однако мера общей длины достаточна для решения наиболее важных вопросов: яв­ляется ли алгоритм линейным относительно длины входа (т.е. требует ли он времени, чуть большего, чем нужно для чтения входа), экспоненциальным (т.е. преобразование выполнимо только для примеров малого размера) или нелинейным полиномиальным (т.е. алгоритм можно выполнить даже для больших примеров, но время будет значи­тельным).

Следующие преобразования линейны, как мы увидим далее, относительно размера входных данных.

Преобразование КС-грамматики в МП-автомат по алгоритму из теоремы 6.13.

Преобразование МП-автомата, допускающего по заключительному состоянию, в МП-автомат, допускающий по пустому магазину, с помощью конструкции из тео­ремы 6.11.

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

С другой стороны, время преобразования МП-автомата в грамматику (теорема 6,14) существенно больше. Заметим, что п, общая длина входа, гарантированно является верх­ней границей числа состояний или магазинных символов, поэтому переменных вида [pXq], построенных для грамматики, может быть не более п. Однако время выполнения преобразования может быть экспоненциальным, если у МП-автомата есть переход, по­мещающий большое число символов в магазин. Отметим, что одно правило может по­местить в магазин почти п символов.

Если мы вспомним построение продукций грамматики по правилу вида «5(q, а, X) со­держит (г₀, YiY₂… У\у\ то заметим, что оно порождает набор продукций вида [qXr/,] —» «[^roYiri][r_tY₂r₂]…[г/с.lY^k] для всех последовательностей состояний r_h …, г_к. Посколь­ку к может быть близко к п, общее число продукций возрастает как п». Такое построение невозможно довести до конца для МП-автомата разумного размера, даже если он имеет всего одну цепочку, записываемую в магазин.

К счастью, этого наихудшего случая всегда можно избежать. Как предлагалось в уп­ражнении 6.2.8, помещение длинной цепочки в магазин можно разбить на последова­тельность из не более, чем п шагов, на каждом из которых в магазин помещается всего один символ. Таким образом, если 5(q, а,Х) содержит (r₀, Y,Y₂…Y_k), можно ввести новые состояния р₂, р₃, …, рк I■ Затем изменим (r₀, YiY₂…Y_t) в 5{q, а,Х) на (pk-i, Y_k ,Yk) и введем новые переходы

3(рк I, Е, Ук i) = {(Рк 2, Yk 2?к Л}, S(pk-2, е, Yk ₂) = {{рк-з, Yk Л 2)} и так далее до S(p₂, е, У₂) = {(r₀, Y,Y₃)}.

Теперь в любом переходе не более двух магазинных символов. При этом добавлено не более п новых состояний, и общая длина всех правил перехода 8 выросла не более, чем в константу раз, т.е. осталась 0(п). Существует 0(п) правил перехода, и каждое по­рождает 0(п²) продукций, поскольку в продукциях, порожденных каждым правилом, должны быть выбраны всего два состояния. Таким образом, грамматика имеет длину 0(n^J) и может быть построена за кубическое время. Проведенный неформальный анализ резюмируется в следующей теореме.

Теорема 7.31. Существует алгоритм сложности 0(«³), который по МП-автомату Р строит КС-грамматику длиной не более 0(п). Эта грамматика порождает язык, допус­каемый Р по пустому магазину. В дополнение, можно построить грамматику, которая порождает язык, допускаемый Р по заключительному состоянию. □

7.4.2. Временная сложность преобразования к нормальной форме Хомского

Алгоритмы могут зависеть от первичного преобразования в нормальную форму Хом­ского, поэтому посмотрим на время выполнения различных алгоритмов, использованных для приведения произвольной грамматики к НФХ. Большинство шагов сохраняют, с точностью до константного сомножителя, длину описания грамматики, т.е. по граммати­ке длиной п они строят другую длиной 0(п). «Хорошие» (с точки зрения затрат времени) преобразования перечислены в следующем списке.

С использованием подходящего алгоритма (см. раздел 7.4.3) определение достижи­мых и порождающих символов грамматики может быть выполнено за линейное время, 0(п). Удаление получившихся бесполезных символов требует О(п) времени и не увеличивает размер грамматики.

Построение цепных пар и удаление цепных продукций, как в разделе 7.1.4, требует времени 0(п²), и получаемая грамматика имеет размер 0(п²).

Замена терминалов переменными в телах продукций, как в разделе 7.1.5 (нормальная форма Хомского), требует времени 0{п) и приводит к грамматике дли­ной 0(п).

Разделение тел продукций длины 3 и более на тела длины 2 (раздел 7.1.5) также тре­бует времени 0(п) и приводит к грамматике длиной О(п).

«Плохой» является конструкция из раздела 7.1.3, где удаляются е-продукции. По телу продукции длиной к можно построить 2^k — 1 продукций новой грамматики. Поскольку к может быть пропорционально п, эта часть построения может занимать 0(2″) времени и приводить к грамматике длиной 0(2″).

Во избежание этого экспоненциального взрыва достаточно ограничить длины тел продукций. К каждому телу продукции можно применить прием из раздела 7.1.5, но только если в теле нет терминалов. Таким образом, в качестве предварительного шага перед удалением е-продукций рекомендуется разделить все продукции с длинными те­лами на последовательность продукций с телами длины 2. Этот шаг требует времени 0(п) и увеличивает грамматику только линейно. Конструкция из раздела 7.1.3 для удале­ния £-продукций будет работать с телами длиной не более 2 так, что время выполнения будет О(п) и полученная грамматика будет длиной 0(п).

С такой модификацией общего построения НФХ единственным нелинейным шагом будет удаление цепных продукций. Поскольку этот шаг требует 0(п²) времени, можно заключить следующее.

Теорема 7.32. По грамматике G длиной п можно найти грамматику в нормальной форме Хомского, эквивалентную G, за время 0(п²); полученная грамматика будет иметь длину 0(п²). □

7.4.3. Проверка пустоты КС-языков

Алгоритм проверки пустоты КС-языка L нам уже знаком. Чтобы определить, явля­ется ли стартовый символ S данной грамматики G для языка L порождающим, можно использовать алгоритм из раздела 7.1.2. L пуст тогда и только тогда, когда S не являет­ся порождающим.

Поскольку эта проверка весьма важна, рассмотрим детальнее, сколько времени тре­буется для поиска всех порождающих символов грамматики G. Пусть G имеет длину п. Тогда у нее может быть порядка п переменных, и каждый проход индуктивного обнару­жения порождающих переменных может занимать 0(п) времени для проверки всех про­дукций G. Если на каждом проходе обнаруживается только одна новая порождающая пе­ременная, то может понадобиться 0(п) проходов. Таким образом, простая реализация проверки на порождающие символы требует 0(п²) времени, т.е. является квадратичной.

Однако существует более аккуратный алгоритм, который заранее устанавливает структуру данных для того, чтобы обнаружить порождающие символы всего за СНп) времени. Структура данных (рис. 7.11) начинает с массива, индексированного перемен­ными, как показано слева, который говорит, установлено ли, что переменная является порождающей. Массив на рис. 7.11 показывает, что переменная В уже обнаружена как порождающая, но о переменной А это еще неизвестно. В конце алгоритма каждая отмет­ка «?» превращается в «нет», поскольку каждая переменная, не обнаруженная алгорит­мом как порождающая, на самом деле является непорождающей.

Порождающая? Рис. 7.11. Структуры данных для линейной проверки пустоты

Для продукций предварительно устанавливается несколько видов полезных ссы­лок. Во-первых, для каждой переменной заводится список всех возможных позиций, в которых эта переменная встречается. Например, список для переменной В пред­ставлен сплошными линиями. Во-вторых, для каждой продукции ведется счетчик числа позиций, содержащих переменные, способность которых породить терми­нальную цепочку еще не учтена. Пунктирные линии представляют связи, ведущие от продукций к их счетчикам. Счетчики, показанные на рис. 7.11, предполагают, что ни одна из переменных в телах продукций еще не учитывалась, хотя уже и установлено, что В — порождающая.

Предположим, мы уже обнаружили, что В — порождающая. Мы спускаемся по спи­ску позиций в телах, содержащих В. Для каждой такой позиции счетчик ее продукции уменьшаем на 1; позиций, которые нужны для заключения, что переменная в голове про­дукции тоже порождающая, остается на одну меньше.

Если счетчик достигает 0, то понятно, что переменная в голове продукции является порождающей. Связь, представленная точечными линиями, приводит к переменной, и эту переменную можно поместить в очередь переменных, о которых еще неизвестно, по­рождают ли они (переменная В уже исследована). Эта очередь не показана.

Обоснуем, что этот алгоритм требует 0(п) времени. Важными являются следующие утверждения.

Поскольку грамматика размера п имеет не более п переменных, создание и ини­циализация массива требует времени 0(п).

Есть не более п продукций, и их общая длина не превосходит п, поэтому инициа­лизация связей и счетчиков, представленных на рис. 7.11, может быть выполнена за время 0(п).

Когда обнаруживается, что счетчик продукции получил значение 0, т.е. все пози­ции в ее теле являются порождающими, вся проделанная работа может быть раз­делена на следующие два вида.

Работа, выполненная для продукции: обнаружение, что счетчик обнулен, поиск пе­ременной, скажем, А, в голове продукции, проверка, установлено ли, что эта пере­менная является порождающей, и помещение ее в очередь, если это не так. Все эти шаги требуют 0( 1) времени для каждой продукции, поэтому вся такая работа в це­лом требует 0(п) времени.

Работа, выполненная при посещении позиций в телах продукций, имеющих пере­менную А в голове. Эта работа пропорциональна числу позиций с переменной А. Следовательно, совокупная работа, выполненная со всеми порождающими перемен­ными, пропорциональна сумме длин тел продукций, а это 0(п).

Отсюда делаем вывод, что общая работа, выполненная этим алгоритмом, есть 0(п).

Другие способы использования линейной проверки пустоты

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

Какие символы достижимы?

Какие символы являются е-порождающими?

7.4.4. Проверка принадлежности КС-языку

Проблема принадлежности цепочки w КС-языку L также разрешима. Есть несколько неэффективных способов такой проверки; они требуют времени, экспоненциального от­носительно \w\, в предположении, что язык L представлен заданной грамматикой или МП-автоматом, и размер представления считается константой, не зависящей от w. Например, начнем с преобразования какого-либо данного нам представления в НФХ-грамматику. По­скольку дерево разбора в такой грамматике является бинарным, при длине п слова w в дереве будет ровно 2п — 1 узлов, отмеченных переменными. Несложное индуктивное доказательство этого факта оставляется в качестве упражнения. Количество возможных деревьев и разметок их узлов, таким образом, «всего лишь» экспоненциально относительно п, поэтому в принципе их можно перечислить, и проверить, имеет ли какое-нибудь из деревьев крону w.

Существует гораздо более эффективный метод, основанный на идее «динамического программирования» и известный также, как «алгоритм заполнения таблицы» или «табуляция». Данный алгоритм известен как CYK-алгоритм^[3] (алгоритм Кока-Янгера- Касами). Он начинает с НФХ-грамматики G = (У, Т, P,S) для языка L. На вход алгоритма подается цепочка w = aia₂…a„ из Т*. За время 0{п^х) алгоритм строит таблицу, которая говорит, принадлежит ли w языку L. Отметим, что при вычислении этого времени сама по себе грамматика рассматривается фиксированной, и ее размер вносит лишь констант­ный сомножитель в оценку времени, измеряемого в терминах длины цепочки, проверяе­мой на принадлежность L.

В CYK-алгоритме строится треугольная таблица (рис. 7.12). Горизонтальная ось со­ответствует позициям цепочки w = aia₂…a_m имеющей в нашем примере длину 5. Содер­жимое клетки, или вход таблицы X,j, есть множество таких переменных А, для которых

А => a,a, i…a_t. Заметим, в частности, что нас интересует, принадлежит ли S множеству

Х]„, поскольку это то же самое, что S => w, т.е. w е L.

Таблица заполняется построчно снизу вверх. Отметим, что каждая строка соответст­вует определенной длине подцепочек; нижняя— подцепочкам длины 1, вторая снизу — подцепочкам длины 2 и так далее до верхней строки, соответствующей одной подцепоч­ке длиной п, т.е. w. Ниже обсуждается метод, с помощью которого вычисление одного входа требует времени 0(п). Поскольку всего входов п{п + 1)/2, весь процесс построения таблицы занимает 0(п³) времени. Алгоритм вычисления Х_:/ таков.

Х[5
Хы	х25
Х,3	Х2v	х35
Х,2	X»	Хи	х45
Х„	х22	х33	х44	Xss
аI	а2	а3	а4	а5

Рис. 7.12. Таблица, построенная алгоритмом Кока-Янгера-Касами

Базис. Вычисляем первую строку следующим образом. Поскольку цепочка, которая начинается и заканчивается в позиции /, представляет собой просто терминал а„ а грам­матика находится в НФХ, единственный способ породить а, заключается в использова­нии продукции вида А —» а, грамматики G. Итак, Х„ является множеством переменных А, для которых А —> а, — продукция G.

Индукция. Пусть нужно вычислить X,, в (/ — /+ 1)-й строке, и все множества X в нижних строках уже вычислены, т.е. известны для всех подцепочек, более коротких, чем a,a, i…a_n и в частности, для всех собственных префиксов и суффиксов этой цепочки. Можно предполагать, что j — i > 0, поскольку случай j = i рассмотрен в базисе. Поэтому

любое порождение А => а,о,-/—0/ должно начинаться шагом А ВС. Тогда В порож­дает некоторый префикс строки а,а, /—Я/, скажем, В => ад,- для некоторого k < j. Кроме того, С порождает остаток a,a, t…a_p т.е. С а^ iat,₂…aj.

Приходим к выводу, что для того, чтобы А попало в Х_у, нужно найти переменные В и Си целое к, при которых справедливы следующие условия.

1. i<k<j.

В принадлежит Х,_к.

С принадлежит Х_к. д _г

Л —> ВС — продукция в G.

Поиск таких переменных А требует обработки не более п пар вычисленных ранее множеств: (Хц, X_hi_:J), (Хц-i, X^₂,j) и т.д. до (X,j._h Х_п). Таким образом, мы поднимаемся по колонке, расположенной под Х_ц, и одновременно спускаемся по диагонали (рис. 7.13).

Рис. 7.13. Вычисление Xjj требует совместной обработки столбца под Ху и диагонали справа от него

Теорема 7.33. Вышеописанный алгоритм корректно вычисляет Х_ц для всех /’ и у. Та­ким образом, w б L(G) тогда и только тогда, когда S е Х,„. Кроме того, время выполне­ния алгоритма есть 0(п^ъ).

Доказательство. Представив базис и индуктивную часть алгоритма, мы объяснили, почему алгоритм находит корректные множества переменных. Рассмотрим время вы­полнения. Заметим, что нужно вычислить 0(п²) элементов таблицы, и каждое вычисле­ние вовлекает сравнение и вычисление не более, чем п пар элементов. Важно помнить, что, хотя в каждом множестве Ху может быть много переменных, грамматика G зафик­сирована и число ее переменных не зависит от п — длины проверяемой цепочки w. Та­ким образом, время сравнения элементов Х,_к и Xt-ij и поиска переменных, входящих в Xjj, есть 0(1). Поскольку для каждого Х_ц возможно не более п таких пар, общее время со­ставляет 0(п). □

Пример 7.34. Рассмотрим следующие продукции грамматики G в НФХ. S^AB\BC А->ВА\ а В СС | b С->АВ\а

Проверим, принадлежит ли цепочка baaba языку L(G). На рис. 7.14 показана таблица, за­полненная для этой строки.

Для построения первой (нижней) строки используется базисное правило. Нужно рас­смотреть лишь переменные с телом продукции а (это А и С) и телом b (это В). Таким об­разом, Х„ = Х₄₄ = {В}, Х₂₂ = Х₃₃ = Х₅₅ = {А, С}.

Во второй строке показаны значения X_t2, Х₂₃, Х₃₄ и Х₄₅. Рассмотрим, например, как вычисляется Х,₂. Цепочку Ьа, занимающую позиции 1 и 2, можно разбить на непустые подцепочки единственным способом. Первая должна занимать позицию 1, вторая— по­зицию 2. Для того чтобы переменная порождала Ьа, она должна иметь продукцию с те­лом, первая переменная которого принадлежит Хц = {6} (т.е. порождает Ь), а вторая — Х₂₂ = {А, С} (т.е. порождает а). Таким телом может быть только ВА или ВС. Просмотрев грамматику, находим, что с такими телами там есть только продукции А ВА и S —> ВС. Таким образом, две головы, А и S, образуют Х₁₂.

{S, A, Q

{S, А, С}

{В}                       {В}

{В}                     {S, С}

{В} {A, Q                     {A, Q {В} {A, Q

b a                                          a b а

Рис. 7.14. Таблица для цепочки baaba, построенная алгоритмом Кока-Янгера-Касами

В качестве более сложного примера рассмотрим вычисление Х₂₄. Цепочку aab в по­зициях с 2 по 4 можно разбить, заканчивая первую подцепочку в 2 или в 3, т.е. в опреде­лении Х₂₄ можно выбрать к = 2 или к = 3. Таким образом, нужно рассмотреть все тела в ХпХ₃₄ U Х₂₃Х₄₄. Этим множеством цепочек является {А, С}{5, С} U {В}{В} = {AS, AC, CS,

СС, ВВ}. Из пяти цепочек этого множества только СС является телом; его голова — В. Таким образом, Х₂₄ = {В}. □

7.4.5. Обзор неразрешимых проблем КС-языков

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

• Неоднозначна ли данная КС-грамматика G?
• Является ли данный КС-язык существенно неоднозначным?
• Пусто ли пересечение двух КС-языков?
• Равны ли два данных КС-языка?
• Равен ли 2* данный КС-язык, где 2 — алфавит этого языка?

Отметим, что вопрос 1 о неоднозначности отличается от остальных тем, что это во­прос о грамматике, а не о языке. Все остальные вопросы предполагают, что язык пред­ставлен грамматикой или МП-автоматом, но это все равно вопросы о языке (или языках). Например, в противоположность вопросу 1 вопрос 2 требует по данной грамматике G (или МП-автомату) определить, существует ли некоторая эквивалентная ей однозначная грамматика G’. Если G сама по себе однозначна, то ответом, безусловно, будет «да», но если G неоднозначна, то для языка грамматики G может существовать другая граммати­ка G’, которая однозначна, как было с грамматиками выражений в примере 5.27.

7.4.6. Упражнения к разделу 7.4

7.4.1. Постройте алгоритмы разрешения следующих проблем:

а) (*) конечен ли язык L(G) данной грамматики G? Указание. Используйте лемму о накачке;

б) (!) определить, содержит ли язык L(G) данной грамматики G не менее 100 цепочек;

в) (!!) по данной грамматике G и ее переменной А определить, существует ли выводимая цепочка, которая начинается символом А. Указание. Напомним, что переменная А может впервые появиться в середине некоторой выводи­мой цепочки, а затем все символы слева от нее могут породить е.

1А.1. Используйте технику, описанную в разделе 7.4.3, для построения линейных по времени алгоритмов разрешения следующих вопросов о КС-грамматиках.

• Какие символы встречаются в выводимых цепочках?
• Какие символы являются £-порождающими?

Примените CYK-алгоритм к грамматике G из примера 7.34, чтобы определить, принадлежат ли L(G) следующие цепочки:

а) (*) ababa;

б)    baaab;

в) aabab.

(*) Покажите, что для любой НФХ-грамматики все деревья разбора цепочек длиной п имеют 2/7-1 внутренних узлов (отмеченных переменными).

7.4.5. (!) Измените CYK-алгоритм так, чтобы он сообщал, сколько различных деревьев вывода у данной цепочки, а не просто, принадлежит ли она языку грамматики.

Резюме

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

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

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

Лемма о накачке. В любой достаточно длинной цепочке КС-языка можно найти короткую подцепочку, два конца которой можно синхронно «накачивать», т.е по­вторять произвольное число раз. Хотя бы одна из накачиваемых цепочек не равна £. Эта лемма, а также ее более мощная версия, которая называется леммой Огдена и приводится в упражнении 7.2.3, дают возможность доказывать, что многие язы­ки не являются контекстно-свободными.

Операции, сохраняющие контекстно-свободные языки. КС-языки замкнуты относительно подстановки, объединения, конкатенации, замыкания (*), обра­щения и обратного гомоморфизма. КС-языки не замкнуты относительно пере­сечения и дополнения, но пересечение КС-языка с регулярным всегда являет­ся КС-языком.

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

Проверка принадлежности КС-языку. Алгоритм Кока-Янгера-Касами определяет, принадлежит ли данная цепочка данному КС-языку. Если язык зафиксирован, эта проверка требует времени 0(п³), где п — длина проверяемой цепочки.

Литература

Нормальная форма Хомского впервые описана в [2], нормальная форма Грейбах— в [4], хотя конструкция, описанная в упражнении 7.1.11, принадлежит Полу (М. С. Paull).

Многие фундаментальные свойства контекстно-свободных языков установлены в [1]. Среди них лемма о накачке, основные свойства замкнутости, а также проверки для про­стых вопросов, таких как пустота и конечность КС-языка. Результаты о незамкнутости относительно пересечения и дополнения происходят из работы [6], а дополнительные ре­зультаты о замкнутости, включая замкнутость КС-языков относительно обратного гомо­морфизма, — из [3]. Лемма Огдена предложена в [5].

Алгоритм Кока-Янгера-Касами имеет три независимых источника. Работа Кока рас­пространялась частным образом и не была опубликована. Версия по сути того же алго­ритма, записанная Касами, появилась только в закрытом докладе Воздушных Сил США. И лишь работа Янгера была опубликована в [7].

172. Bar-Hillel, М. Perles, and Е. Shamir, «On formal properties of simple phrase-structure grammars», Z. Phonetic. Sprachwiss. Kommunikationsforsch. 14 (1961), pp. 143-172.
173. Chomsky, «On certain formal properties of grammars», Information and Control2:2 (1959), pp. 137-167. (Хомский H. О некоторых формальных свойствах грамматик. — Кибернетический сборник, вып. 5. — М.: ИЛ, 1962. — С. 279-311.)
174. Ginsburg and G. Rose, «Operations which preserve definability in languages», J. ACM 10:2 (1963), pp. 175-195. (Гинзбург С., Роуз Дж. Об инвариантности классов языков относительно некоторых преобразований. — Кибернетический сборник, Новая се­рия, вып. 5, — М.: Мир, 1968, —С. 138-166.)
175. Greibach, «A new normal-form theorem for context-free phrase structure grammars», J. ACM 12:1 (1965), pp. 42-52.
176. Ogden, «A helpful result for proving inherent ambiguity», Mathematical Systems Theory 2:3 (1969), pp. 31^12. (ОгденУ. Результат, полезный для доказательства существенной неоднозначности. — сб. «Языки и автоматы». — М.: Мир, 1975. — С. 109-113.)
177. Scheinberg, «Note on the boolean properties of context-free languages», Information and Control 3:4 (1960), pp. 372-375.
178. H. Younger, «Recognition and parsing of context-free languages in time n³«, Informa­tion and Control 10:2 (1967), pp. 189-208. (Янгер Д. Распознавание и анализ контек­стно-свободных языков за время п . — Сб. «Проблемы математической логики». — М.: Мир, 1970. — С. 344-362.)

^[1] Напомним, что в русскоязычной литературе был принят термин «лемма о разрастании», но «накачка», на наш взгляд, точнее отражает суть происходящего. — Прим. ред.

^[2] Напомним, что это п есть константа, обеспеченная леммой о накачке и не имеющая ничего общего с локальной переменной п, использованной в определении языка!.

^[3] Он назван по фамилиям трех авторов (J. Cocke, D. Younger и Т. Kasami), независимо при­шедших к одной и той же, по сути, идее.