XVYggbpFw2

8. НОРМАЛЬНАЯ ФОРМА ХОМСКОГО

Определение 8.1. Говорим, что контекстно-свободная грамматика G имеет нормальную форму Хомского, если каждое ее правило имеет один из следующих двух видов:

A	a
A	BC

где A, B, C – нетерминалы, a – терминал.

Теорема 8.1. Каждая КС-грамматика, не содержащая –правил, эквивалентна некоторой КС-грамматике в нормальной форме Хомского.

Доказательство. Пусть G – контекстно-свободная грамматика, в языке которой нет пустого слова. Грамматика G переделывается в эквивалентную грамматику G’ в три этапа.

1)Избавляемся от цепочных правил.

2)Если в полученной на этапе 1) грамматике имеется правило вида A

, где слово имеет длину больше 1 и содержит терминалы, то для ка-

ждого терминала a из		добавляем в алфавит один новый нетерминал Aa.
В слове	правила A	заменим все буквы a на Aa, а к множеству про-
дукций добавим все Aa		а. Полученная грамматика опять с очевидностью
эквивалентна исходной.
3) Если в новой грамматике взять правило A				, где слово не яв-
ляется	терминалом, то	это	будет цепочкой нетерминалов длины не
меньше двух. Для нормальности надо, чтобы длина				точно равнялась

двум. Добавляем новые нетерминалы с соответствующими правилами и получаем этот результат. Например, правило

A BCDE

заменяется на правила

A BF, F CG, G DE

Теорема доказана.

Замечание 8.1. Если G – произвольная КС –грамматика, то приведя ее к –свободной, можно преобразовать ее часть без –правила к нормальной форме Хомского. В результате получим, что любая КСграмматика эквивалентна -свободной КС-грамматике в нормальной форме Хомского с той лишь оговоркой, что среди ее правил может быть единственное -правило S .

Упражнения

8.1.Привести к нормальной форме Хомского следующие КСграмматики:

a) S ABS

AAabcS|bcB

BbcS|

b) S abAB

Aaa|B

Bbb|A

c) S ABC

AaS|B|

BbS|C|

CcS|A|

8.2.Привести к нормальной форме Хомского следующие КСграмматики:

a) S aSb| ab

AAabcS|bcS

b)S abcd| AS

ASSSS|bc

c) S ABCDEFGH|SS

Aa

Bb

Cc

Dd

Ee

Ff

Gg

Hh

i. По

9.	ДЕРЕВО РАЗБОРА
Пусть G – КС-грамматика. Пусть в G выводимо
	S
где - цепочка терминалов. Такие		называются сентенциями. Рассмот-
рим какой-нибудь вывод этой сентенции.
S = 0	1	2 …	n =

Благодаря тому, что на каждом шаге в очередной цепочке происходит замена только одной нетерминальной буквы на новое слово, этот вывод можно изобразить в виде дерева. С точки зрения теории графов – это связный граф без циклов. Однако здесь нужное нам дерево, которое далее называется деревом разбора, имеет дополнительные структурные элементы. Во-первых, все его вершины будут помечены нетерминалами или терминалами. Во-вторых, накладываются определенные требования на расположение вершин. Они распределяются по уровням (этажам) сверху вниз. На самом верхнем (первом) уровне располагается одна вершина с меткой S. От нее, как из корня, строится дерево (правда, обычно в перевернутом виде - сверху вниз).

Каждому	i	вывода соответствуют вершины дерева с метками – сим-

волами из i. Они располагаются на одном уровне рядом друг с другом и в том же порядке, в каком стоят соответствующие буквы i строится фрагмент для i+1. Вершины для i+1 располагаются на следующем

уровне под вершинами для	i	и соединяются ребрами с тем нетерминалом

из i (точнее его вершиной), который заменяется при переходе к i+1 со-

гласно одному из правил грамматики. В случае, когда это есть -правило, строится одна вершина с меткой . Новые вершины на очередном уровне при этом надо располагать так, чтобы не было пересечений ребер.

Это мудреное описание проще всего понять на примере.

Пример 9.1. Грамматика определена правилами

S A| SbS

A a| cSd

Вывод:

S SbS AbS AbSbS AbAbS AbAbA AbcSdbA abcSdbA abcAdbA abcadbA abcadba.

Дерево разбора этого вывода:

На схеме, вершины, помеченные нетерминалами, изображены кружками, а вершины, помеченные терминалами – просто буквами. Все терминалы являются концевыми вершинами (имеют степень 1). Красная линия обходит их и, двигаясь вдоль нее слева направо, мы читаем выведенное терминальное слово abcadba.

Дерево разбора хорошо иллюстрирует вывод. Но одно и то же дерево может соответствовать разным выводам одной и той же сентенции. Так в нашем примере после SbS можно сначала левое S заменить на A, а затем второе S - на SbS , а можно и наоборот. Дерево разбора будет одно и то же. Это говорит о том, что понятие дерева глубже отражает суть выводимости, чем просто цепочка преобразований. Было бы идеально, если бы всегда разным выводам одной и той же сентенции отвечало одно и то же дерево разбора. Но это не так. В нашем примере для сентенции abcadba дерево разбора единственно возможное. Но, к примеру, сентенция ababa имеет два разных дерева разбора:

и

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

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

Грамматика в приведенном выше примере 9.1 однозначной не является. Однако это не значит, что язык, определяемый этой грамматикой, тоже не однозначен. Напротив, он является однозначным, т.к. может быть задан однозначной грамматикой

S A| AbS

A a| cSd

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

Пример 9.2. Грамматика

S aSS |b

является однозначной.

Пример 9.3. Примером неоднозначного КС-языка может служить множество цепочек алфавита {a,b,c}, объединяющее все слова вида

anbncm и все слова вида anbmcm, где n 1, m 1.

10. ОГРАНИЧЕННОСТЬ КОНТЕКСТНО-СВОБОДНОЙ ГРАММАТИКИ

Теорема 10.1. (о накачке КС-языка). Пусть L - произвольный кон-

текстно-свободный язык. Тогда существует такое целое число k, что для любого слова L с длиной | | k cлово можно представить в виде

= uxvyw ,

где u, x, v, y, w – цепочки терминалов, причем:

1)слово xy - не пустое;

2)|xvy| k;

3)вместе с в языке L лежат все слова вида u xi v yi w (i =

0,1,2,…).

Доказательство. Не ограничивая общности можем считать, что КСграмматика G не имеет –правил. Приведем G к нормальной форме Хомского. Пусть N – множество ее нетерминалов. Пусть n – количество элементов в N. Полагаем:

k = 2n

Пусть : L и | | k. Тогда | | 2n -1. Дерево разбора для вывода является бинарным и только на самых нижних переходах от нетерминала к терминалу ведет одна ветка. Если высотой дерева считать число ребер в его самой длинной ветке, то вполне очевидно, что это то же самое, что число нетерминалов на его самой длинной ветке. Если высота строго больше n, то некоторые нетерминалы на ветке неизбежно будут повторяться. Если высоту ограничить числом n, то вдоль каждой ветви раздвоения происходят во всех нетерминальных вершинах, кроме самых нижних, на предпоследних уровнях. Например, при n = 3 дерево может иметь вид:

Длина заключительного слова в таком дереве может иметь максимальную

дину 2n-1, что происходит в случае, когда все ветви имеют максимальную длину n. Это иллюстрируется на схеме:

Таким образом длина заключительного слова в дереве высоты n не

может превзойти 2n-1. Следовательно для нашего высота дерева разбора больше n. А, значит, на самой длинной ветви этого дерева какой-то нетерминал A встретится более одного раза. Следующая схема иллюстрирует ситуацию и что такое u, x, v, y, w:

Выберем парочку этих A так, что в выделенной ветви под верхним A больше нет повторяющихся нетерминалов (эта часть выделена красным цветом). Тогда высота поддерева под этим верхним A будет не больше

n+1. Значит |xvy| 2n=k. Вполне очевидно, что из нижнего A можно вывести не только v, но и xvy – также, как это выводится из верхнего A. Зна-

чит ux2vy2w L. Аналогично ux3vy3w L и т.д. uxivyiw L для i 1. На-

конец, из верхнего A можно вывести v также, как оно выводится из нижнего. Значит, uxivyiw L для i = 0. Теорема доказана.

Теорема позволяет доказать для ряда языков, что они не являются контекстно-свободными.

Пример 10.1. Язык всех слов вида anbncn (n 1), N={a,b,c} не является контекстно-свободным. Действительно, если это не так, то согласно

теореме бесконечная серия слов вида uxivyiw при одних и тех же u, x, v, y, w должна иметь вид anbncn. Нетрудно видеть, что это невозможно.

Упражнения

10.1. Доказать, что следующие языки не являются КС-языками:

a) L = { an b an b an | n 0 } b) L = { an bm an bm | n, m 0 }

c) L = { an bm am bn | n m 0 } d) L = { an bm am bn | m n 0 }

10.2. Доказать, что следующие языки не являются КС-языками:

a) L = { an bm an | n m 0 } b) L = { an bm an | 0 < n < m }

c) L = { an bn am | m n 0 } d) L = { an bn am | 0 < n < m }

11. РЕГУЛЯРНЫЕ ГРАММАТИКИ

Напомним, что КС-грамматика называется регулярной, если все ее правила имеют один из видов: A , A a, A aB.

Язык L называется регулярным, если он определяется некоторой регулярной грамматикой.

Правила вида Aкак и в контекстно-свободных грамматиках, не играют существенной роли. Алгоритм избавления от –правил оставляет регулярную грамматику регулярной. Поэтому утверждения о регулярных грамматиках без -правил – это фактически утверждения обо всех регулярных грамматиках. Это же касается и цепочных правил.

Предложение 11.1. Грамматика, все правила которой имеют один из видов: A , A a, A aB, A B, является регулярной.

Доказательство. Вспомним алгоритм избавления от цепочных правил. Он состоит из двух этапов. Сначала по любой паре правил A B, B к правилам добавляется A . Очевидно, что добавляемые правила будут иметь один из тех же четырех видов. На втором этапе все цепочные правила выкидываются. Ясно, что получится регулярная грамматика.

Пример 11.1. Грамматика S pA, A i | iS определяет множество слов вида pipipi… Рассмотрим для иллюстрации дерево разбора сентенции pipi в данной регулярной грамматике:

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

Теорема 11.1. (О накачке регулярного языка). Пусть L - произ-

вольный регулярный язык. Тогда существует такое натуральное число n, что для любого слова L с длиной | | n cлово можно представить в виде:

= uxv ,

где u, x, v – цепочки терминалов, причем: 1) слово x - не пустое;

2)|ux| n;

3)вместе с в языке L лежат все слова вида uxiv (i = 0,1,2,…).

Доказательство. Найдем –свободную регулярную грамматику, определяющую L. Пусть n – число нетерминалов этой грамматики. Допустим, что | | n для L и рассмотрим дерево разбора при выводе этой цепочки:

Очевидно, что число нетерминалов в дереве – это длина выводимой цепочки. Значит, какой-то нетерминал встречается дважды. Рассмотрим самую “верхнюю” пару таких нетерминалов A, в том смысле, что над нижним A этой пары уже нет повторяющихся нетерминалов. Рисунок иллюстрирует, что такое u, x, v. Ясно, что вместе с из S выводятся все слова ви-

да uxiv (i = 0,1,2,…). А т.к. в последовательности нетерминалов, из которой получается ux, нет одинаковых букв, длина этой последовательности и, вместе с ней, слова ux не превосходит n. Теорема доказана.

Из теоремы о накачке в частности очевидно, что язык, состоящий из всех слов вида anbn (n 1) не является регулярным. Интересно, что при

этом язык anbm (n,m 1) регулярен (S aA, A aA|bB|b, B bB|b).

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

Пример 11.1.

S <Число> | <Знак><Число>

<Знак>	+ | –
<Число>	<Цифра><Число>|<Цифра>
<Цифра>	0|1|2|3|4|5|6|7|8|9

Эта грамматика очевидно определяет язык целочисленных числовых констант. По виду она не является регулярной. Однако цепное правило S