1 Глава 4. Контекстно-свободные грамматики Теория формальных языков и трансляций

2 § 4.1. Упрощение контекстно-свободных грамматик В этой главе мы опишем некоторые основные упрощения КС-грамматик; докажем несколько важных теорем о нормальных формах Хомского (N. Chomsky) и Грейбах (S. Greibach);N. Chomsky покажем, что существуют алгоритмы для определения, является ли язык, порождае- мый КС-грамматикой, пустым, конечным или бесконечным.

Avram Noam Chomsky 3 born December 7, 1928

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

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

6 Теорема 4.1. Существует алгоритм для определения, является ли язык, порождае- мый данной КС-грамматикой, пустым. Доказательство. Пусть G = (V N, V T, P, S) cfg, и L = L (G). Предположим, что L, т. е. существует вывод S x, где x V T +. Рассмотрим дерево, представляющее этот вывод. Пусть в нём есть путь с узлами n 1 и n 2, имеющими одну и ту же метку A V N, причём узел n 1 расположен ближе к корню S, чем узел n 2 (рис. 4.1, a). Ret 141

7 G = ({S, A, B}, {a, b}, {S Aa, A aB, B Aa, B b}, S) b B n1n1 n2n2 (a)(a) (б)(б) x 1 = aaba S A a a a S a A B a A B b a Рис n2n2 x 2 = ab. Ret 9 x 3 = ; x 4 = a x = x 3 x 1 x 4

8 Алгоритмическая разрешимость проблемы пустоты языка, порождаемого данной КС-грамматикой Поддерево с корнем n 1 представляет вывод A x 1. Поддерево с корнем n 2 представляет вывод A x 2. Заметим, что x 2 является подцепочкой цепочки x 1, которая, впрочем, может совпадать с x 1. Кроме того, x = x 3 x 1 x 4, где x 3,x 4 V T *, причём одна из них или обе могут быть пустыми цепочками.

9 Алгоритмическая разрешимость проблемы пустоты языка, порождаемого данной КС-грамматикой Если в дереве с корнем S заменить поддерево с корнем n 1 поддеревом с корнем n 2, то получим дерево (см. рис. 4.1, б ), представляющее вывод S x 3 x 2 x 4. Так мы исключили, по крайней мере, один узел (n 1 ) из исходного дерева вывода. Если в полученном дереве имеется путь с двумя узлами, помеченными одним и тем же нетерминалом, процесс может быть повторен с деревом вывода S x 3 x 2 x 4.

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

11 Если в грамматике G имеется m нетерминалов, то в полученном дереве все ветви будут иметь длину (подразумевается, что длина ветви измеряется числом дуг, её составляющих) не больше m, ибо в противном случае на длинной ветви неминуемо встретились бы два узла с идентичными метками. Алгоритмическая разрешимость проблемы пустоты языка, порождаемого данной КС-грамматикой

12 Алгоритм, определяющий, является ли язык L(G) пустым, можно организовать следующим образом. Шаг 1. Начать построение коллекции деревьев вывода с единственного дерева, представленного только корнем узлом с меткой S. Алгоритмическая разрешимость проблемы пустоты языка, порождаемого данной КС-грамматикой

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

14 Шаг 3. Если в построенной коллекции есть хотя бы одно дерево, представляющее вывод терминальной цепочки, то язык L(G) не пуст. Иначе язык L(G) пуст. Требуемый алгоритм построен и теорема доказана. Алгоритмическая разрешимость проблемы пустоты языка, порождаемого данной КС-грамматикой

15 О продуктивости нетерминалов в cfg Теорема 4.2 о продуктивности. Для любой КС-грамматики G=(V N,V T,P,S), порождающей непустой язык, можно найти эквивалентную КС-грамматику G 1, в которой для любого нетерминала A существует терминальная цепочка x, такая, что Доказательство. Для каждого нетерми- нала A V N рассмотрим грамматику G A = (V N, V T, P, A). Ret 88Ret 102Ret 20

16 О продуктивости нетерминалов в cfg Если язык L(G A ) пуст, то мы удалим A из алфавита V N, а также все правила, использующие A в правой или левой части. После удаления из G всех таких нетерминалов и правил мы получим новую грамматику G 1 = (, V T, P 1, S ), где и P 1 оставшиеся нетерминалы и правила. Ясно, что L(G 1 ) L(G), поскольку вывод в G 1 есть также вывод в G.

17 О продуктивости нетерминалов в cfg Предположим теперь, что существует терминальная цепочка x L(G), но x L(G 1 ). Тогда вывод должен включать сен- тенциальную форму вида 1 A 2, в которой т. е. Однако тогда должна существовать некоторая терминальная цепочка x 2, такая, что, факт, противоречащий пред- положению о том, что L(G A ) =. Что и требовалось доказать.

18 Определение 4.1. Нетерминалы из при- нято называть продуктивными. В дополнение к исключению нетерми- налов, из которых невозможно вывести ни одной терминальной цепочки, мы можем также исключать нетерминалы, которые не участвуют ни в каком выводе сентенциаль- ной цепочки. Такие нетерминалы называют- ся недостижимыми. О продуктивости нетерминалов в cfg

19 О приведённых cfg Теорема 4.3 о приведённости. Для любой данной КС-грамматики, порождающей непустой язык L, можно найти КС-грамматику G = (V N, V T, P, S), порождающую язык L, такую, что для каждого её нетерминала A существует вывод вида S x 1 Ax 3 x 1 x 2 x 3, где x 1, x 2, x 3. Ret 25 Ret 124

20 О приведённых cfg Доказательство. Принимая во внима- ние теорему 4.2, пусть L = L(G 1 ), где4.2 G 1 = (, V T, P 1, S ) КС-грамматика, все нетерминалы которой продуктивные. Если S 1 A 2, где 1, 2 то суще- ствует вывод S 1 A 2 x 1 Ax 3 x 1 x 2 x 3, поскольку терминальные цепочки могут быть выведены из A и из всех нетерминалов, появляющихся в 1 и 2.

21 О приведённых cfg Мы можем эффективно построить множество всех нетерминалов A, таких, что будет существовать вывод S 1 A 2, следующим образом. Для начала поместим S в искомое множество. Затем последовательно будем добавлять к этому множеству любой нетерминал, который появляется в правой части любого правила из P 1, определяющего нетерминал, уже имеющийся в этом множестве. Процесс завершается, когда никакие новые элементы не могут быть добавлены к упомянутому множеству.

22 О приведённых cfg Положим G 2 = (, V T, P 2, S), где P 2 множество правил, оставшихся после исключения всех правил из P 1, которые используют символы из V N \ слева или справа. G 2 требуемая грамматика. Покажем, что L(G 1 ) = L(G 2 ) и G 2 удовлет- воряет условию теоремы.

23 О приведённых cfg I. L(G 1 ) L(G 2 ). Пусть x L(G 1 ), т. е. S x. Очевидно, что все нетерминалы, встреча- ющиеся в сентенциальных формах этого вывода достижимы, т. е. принадлежат алфавиту, и соответственно в нём участвуют только правила из P 2. Следовательно, S x и x L(G 2 ).

24 О приведённых cfg II. L(G 2 ) L(G 1 ). Это очевидно, так как P 2 P 1. Из I и II следует, что L(G 1 ) = L(G 2 ). Если A (т. е. A достижим), то существует вывод вида S 1 A 2, и поскольку все нетерминалы продуктивны, то S 1 A 2 x 1 Ax 3 x 1 x 2 x 3, где x 1, x 2, x 3 V T *. КС-грамматика G, о которой идёт речь в теореме, есть G 2. Что и требовалось доказать.

25 Определение 4.2. Контекстно-свободные грамматики, удовлетворяющие условию теоремы 4.3, принято называть приведёнными.4.3 О приведённых cfg

26 Левосторонний вывод в КС-грамматике Определение 4.3. Вывод в КС-грамматике назовем левосторонним, если на каждом его шаге производится замена крайнего левого вхождения нетерминала. Формально: пусть G = (V N, V T, P, S) КС- грамматика. Вывод в грамматике G вида S n левосторонний, если для i = 1, 2,..., n – 1 имеет место i = x i A i i, i +1 = x i i i, где A i i P, x i, A i V N, i, i

27 Левосторонний вывод в КС-грамматике Для обозначения одного шага левосто- роннего вывода будем использовать значок., а нескольких шагов значок. Лемма 4.1 о левостороннем выводе. Пусть G = (V N, V T, P, S) контекстно- свободная грамматика. Если S x, где x, то существует и левосторонний вывод S x в той же грамматике.

28 Левосторонний вывод в КС-грамматике Доказательство. Индукцией по длине вывода l докажем более общее утверж- дение: если для любого нетерминала A V N существует вывод A x, то существует и левосторонний вывод A x. Утверждение леммы будет следовать как частный случай при S = A. База. Пусть l = 1. Для одношагового вывода утверждение выполняется тривиальным образом.

29 Левосторонний вывод в КС-грамматике Индукционная гипотеза. Предположим, что утверждение справедливо для любых выводов длиной l n (n 1). Индукционный переход. Докажем, что оно справедливо и для l = n + 1. Пусть A x вывод длиной n + 1, и пусть = B 1 B 2... B m, а x = x 1 x 2 …x m, где B i, x i, 1 i m.

30 т. е. вывод имеет вид A B 1 B 2... B m x 1 x 2... x m, причём B i x i, l i n, 1 i m. Заметим, что некоторые B i могут быть терминалами, и в этом случае B i = x i и вывод не занимает никаких шагов: B i x i. Если же B i V N, то согласно индукцион- ному предположению B i x i. Левосторонний вывод в КС-грамматике

31 Левосторонний вывод в КС-грамматике Таким образом, мы можем выстроить левосторонний вывод A B 1 B 2... B m x 1 B 2... B m … … x 1 x 2... B m x 1 x 2... x m = x (l 1 +l 2 +…+l m = n) *), воспользовавшись частич- ными левосторонними выводами для тех B i, которые являются нетерминалами, приме- няя их в последовательности слева направо. Что и требовалось доказать. *) Может быть некоторые l i равны 0.

32 Теорема 4.4 о цепных правилах. Любой контекстно-свободный язык может быть порождён контекстно-свободной грам- матикой, не содержащей цепных правил, т. е. правил вида A B, где A и B нетерминалы. Доказательство. Пусть G = (V N, V T, P, S) cfg и L = L(G). Мы построим новое множество правил P 1, прежде всего включив в него все нецепные правила из P. Цепные правила в КС-грамматиках Ret 39

33 Цепные правила в КС-грамматиках Затем мы добавим в P 1 правила вида A при условии, что существуют выводы вида A B, где A и B нетерминалы, а B нецепное правило из P. Заметим, что мы легко можем проверить, существует ли вывод вида A B, поскольку, если A B 1 B 2... B m B и некоторый нетерминал появляется дважды в этом выводе, то мы можем найти более короткую последовательность цепных правил, которая даёт результат A B. Таким образом, достаточно рассматривать только те цепные выводы, длина которых меньше, чем число нетерминалов в V N.

34 Цепные правила в КС-грамматиках Мы теперь имеем модифицированную грамматику G 1 = (V N, V T, P 1, S). I. Покажем, что L(G 1 ) L(G). Пусть x L(G 1 ), т. е. S x. Правила, применяемые в этом выводе, все не цепные: либо изначально взятые из P, либо новые вида A, B i,i=1,2,...,m, появившиеся благодаря выводу A B 1 B 2... B m. Следовательно, терминальная цепочка x, вы- водимая в G 1, выводима и в G: S x.

35 Цепные правила в КС-грамматиках II. Покажем теперь, что L(G) L(G 1 ). Пусть x L(G). Рассмотрим левосторонний вывод S = n = x. Если i i+1 для 0 i < n посредством нецепного правила, то i i+1. Предположим, что i i+1 посредством цепного правила, но что i–1 i с помощью нецепного правила при условии, конечно, что i 0.

36 Цепные правила в КС-грамматиках Предположим также, что i+1 i+2... i+m 1 все посредством цепных правил, а i+m при помощи нецепного правила. Тогда все i+1, i+2,..., i+m 1 одинаковой длины, и поскольку вывод левосторон- ний, то нетерминал, заменяемый в каждой из них, должен быть в одной и той же позиции.

37 Цепные правила в КС-грамматиках S = 0 … i 1 B 1 B 2... i+1 i B m i+m 1 i+m B 1 B 2, B 2 B 3, …, B m 1 B m, B m = B; B P не цепное правило. … Следовательно, B 1 S = 0 … i i+m … P 1 и Но тогда i i+m посредством одного из правил из P 1 \ P. Подобные рассуждения на всех участках лево- стороннего вывода с цепными правилами, приво- дят в заключению, что x L(G 1 ). Из утверждений I и II следует L(G 1 ) = L(G). Что и требовалось доказать. и одни и те же на цепном участке!

38 § 4.2. Нормальная форма Хомского Докажем первую из двух теорем о нормальных формах КС-грамматик. Каждая из них утверждает, что все КС-грамматики эквивалентны грамматикам с ограничениями на вид правил в этих нормальных формах. Теорема 4.5 НФХ. Любой КС-язык может быть порождён грамматикой, в которой все правила имеют вид A BC или A a (A, B, C нетерминалы, a терминал).

39 Нормальная форма Хомского Доказательство. Пусть G КС-грамматика и L = L(G). В соответствии с теоремой 4.4 мы можем найти эквивалентную cfgтеоремой 4.4 G 1 = (, V T, P 1, S), такую, что множество её правил P 1 не содержит ни одного цепного правила. Построим промежуточную грамматику G 2 = (, V T, P 2, S) следующим образом.

40 Нормальная форма Хомского Рассмотрим правило из P 1 вида A B 1 B 2... B m, где B i V T, i = 1, 2,..., m, m 2. Если в нём есть вхождения терминалов, то заменим их на новые нетерминальные символы, для которых введём новые правила с правой частью, представленной этими терминалами. Пусть пополненное множество нетерми- налов, а пополненное множество правил P 2.

41 Нормальная форма Хомского Итак, в P 2 находятся: правила грамматики G 1 вида (1) A a, (2) A B 1 B 2 … B m, и новые правила вида (3) A С 1 С 2 … С m, m 2, (4) С a, где а V T общие терминалы; A, B i (1 i m) нетерминалы G 1 ; C \ новые нетерминалы G 2 ; C j (1 j m) нетерминалы, но не все старые, т. е. из. Ret 44 Ret 123

42 Пока не все правила грамматики G 2 удовлетворяют нормальной форме Хомского: именно правила с длиной правых частей больше 2. Прежде, чем продолжить преобразование грамматики G 2, покажем, что она эквивалентна грамматике G 1. Нормальная форма Хомского

43 Нормальная форма Хомского I. Докажем, что L(G 1 ) L(G 2 ). Пусть S x. Любой шаг этого вывода в грамматике G 1, на котором используется правило A B 1 B 2... B m P 1, m 2, где не все B j (1 j m) нетерминалы (в нём есть и терминалы), равносилен в грам- матике G 2 применению нового правила A C 1 C 2... C m P 2 и нескольких правил вида C j B j P 2, где B j V T (1 j m). Поэтому S x.

44 Нормальная форма Хомского II. Докажем, что L(G 2 ) L(G 1 ). Индукцией по длине вывода l покажем, что если для любого A существует вывод A x, где x, то A x. База. Пусть l = 1. Так как в выводе A x применятся правило вида (1) A x P 2, где x V T, единственно возможное, дающее терминал, то оно имеется также и во множестве правил грамматики G 1, а тогда A x.(1)

45 Нормальная форма Хомского Индукционная гипотеза. Предположим, что утверждение выполняется для всех 1 l n (n 1). Индукционный переход. Пусть A x, где l = n + 1. Этот вывод имеет вид: A C 1 C 2... C m x, где m 2. Очевидно, что x = x 1 x 2 … x m, причём C j x j, 1 l j n, j =1, 2,..., m.

46 Нормальная форма Хомского Если C j \, то существует только одно правило из множества правил P 2, которое определяет этот нетерминал: C j a j для некоторого a j V T. В этом случае a j = x j. По построению правило A C 1 C 2... C m P 2, используемое на первом шаге вывода, обязано своим происхождением правилу A B 1 B 2...B m P 1, где B j = C j, если C j, и B j = a j, если C j \.

47 Нормальная форма Хомского Для C j мы имеем выводы C j x j, 1 l j n, и по индукционному предположению существуют выводы B j x j (1 j m). Итак, имеем: A B 1 B 2... B m x 1 B 2... B m x 1 x 2 … B m x 1 x 2 … x m = x. При A = S получаем, как частный случай, что x L(G 1 ).

48 Итак, мы доказали промежуточный результат: любой КС-язык может быть порожден КС-грамматикой, каждое правило которой имеет форму A a или A B 1 B 2... B m, где m 2; A, B 1, B 2,..., B m нетерминалы; a терминал. Очевидно, что все правила при m 2 имеют такой вид, какого требует нормальная форма Хомского. Нормальная форма Хомского

49 Остается преобразовать правила для m 3 к надлежащему виду. Модифицируем G 2, добавляя некоторые дополнительные нетерминалы и заменяя некоторые её правила. Нормальная форма Хомского

50 Нормальная форма Хомского Именно, по каждому правилу вида A B 1 B 2... B m P 2, где m 3, создаются новые нетерминалы D 1, D 2,..., D m – 2, и оно заменяется множеством правил { A B 1 D 1, D 1 B 2 D 2, … D m – 3 B m – 2 D m – 2, D m – 2 B m – 1 B m }. Ret 123

51 Нормальная форма Хомского Пусть пополненный нетерминальный словарь, а P 3 расширенное множество правил. Рассмотрим КС-грамматику G 3 = (,, P 3, S). Докажем, что G 3 эквивалентна G 2.

52 Нормальная форма Хомского III. Докажем, что L(G 2 ) L(G 3 ). Пусть S x. Один шаг этого вывода в грамматике G 2, на котором используются правила вида A a или A B 1 B 2, является и шагом вывода в грамматике G 3, так как по построению эти правила также входят в грамматику G 3.

53 Нормальная форма Хомского Шаг вывода в грамматике G 2, на котором используется правило A B 1 B 2... B m P 2, m 3, равносилен последовательному применению правил A B 1 D 1, D 1 B 2 D 2, D m – 3 B m – 2 D m – 2, D m – 2 B m – 1 B m P 3. Поэтому имеем S x....

54 Нормальная форма Хомского IV. Докажем, что L(G 3 ) L(G 2 ). Индукцией по длине вывода l покажем, что если для любого A существует вывод A x, x, то A x. База. Пусть l = 1. Если A x, A, x, то согласно построению G 3 использованное правило A x P 3 содержится также и во множестве правил P 2, так как в этом случае x V T, а тогда A x.

55 Нормальная форма Хомского Индукционная гипотеза. Предположим, что утверждение выполняется для всех 1 l n (n 1). Индукционный переход. Пусть A x, где l = n + 1. Этот вывод в случае, требующем доказательства, имеет следующий вид: B 1 D 1 B 1 B 2 D 2... B 1 B 2... B m–2 D m–2 x. Правило-прототип A B 1 B 2... B m P 2, которое по индукции даёт тот же результат x. A B 1 B 2... B m–1 B m

56 Нормальная форма Хомского Очевидно, что x = x 1 x 2... x m, где B j x j, 1 l j n, j = 1, 2,..., m. По индукционной гипотезе B j x j. Следовательно, A x. В частности, при A = S получаем S x. Утверждение IV доказано, а вместе с ним доказано равенство L(G 2 ) = L(G 3 ), и сама теорема.

57 Пример 4.1. Рассмотрим грамматику G = ({S, A, B}, {a, b}, P, S), в которой P = {S aB, A a, A aS, A bAA, S bA, B b, B bS, B aBB}. Построим эквивалентную грамматику в НФХ. Во-первых, два правила, а именно: A a (1) и B b (2) уже имеют требуемый вид. Нормальная форма Хомского Ret 159

58 Нет никаких цепных правил, так что мы можем начать с замены терминалов в правых частях остальных правил на новые нетерминалы и построения правил для них. Правило S aB заменяется двумя правилами S С 1 B (3), С 1 a (4) Аналогично правило S bA заменяется правилами S С 2 A (5), С 2 b (6) Пример 4.1. Нормальная форма Хомского

59 Вместо A aS вводится правило A С 1 S (7). Правило A bAA заменяется на A С 2 D 1 (8), D 1 AA (9). Правило B bS заменяется на B С 2 S (10). Правило B aBB заменяется на B С 1 D 2 (11), D 2 BB (12). Пример 4.1. Нормальная форма Хомского

60 Пример 4.1. Нормальная форма Хомского Итак, G = ({S, A, B, С 1, С 2, D 1, D 2 }, {a, b}, P, S), где P правила (1) (12). G КС-грамматика в НФХ, эквивалент- ная грамматике G.

61 § 4.3. Нормальная форма Грейбах Определение 4.4. Говорят, что КС- грамматика G = (V N, V T, P, S) представлена в нормальной форме Грейбах, если каждое её правило имеет вид A a, где a V T,. Для доказательства того, что всякая КС- грамматика может быть приведена к нормальной форме Грейбах, нам потребу- ется обосновать эквивалентность исполь- зуемых при этом преобразований.

62 Лемма 4.2 о подстановке. Пусть G = (V N, V T, P, S) cfg, A 1 B 2 P, A, B, 1, 2, и {B i i, i =1, 2,..., m} множе- ство всех B-порождений, т. е. правил с нетерминалом B в левой части. Пусть грамматика G 1 = (V N, V T, P 1, S) получается из грамматики G отбрасыва- нием правила A 1 B 2 и добавлением правил вида A 1 i 2, i =1, 2,..., m. Тогда L(G) = L(G 1 ). Ret 75Ret 78Ret 80Ret 122Ret 81

63 Лемма о подстановке Доказательство. I. Докажем, что L(G 1 ) L(G). Пусть S x, x. Использование в этом выводе правила A 1 i 2 P 1 \ P равносильно двум шагам вывода в G: A 1 B 2 1 i 2. Шаги вывода в грамматике G 1, на которых используются другие правила, общие для двух этих грамматик, являются шагами вывода в грамматике G. Поэтому S x.

64 Лемма о подстановке II. Докажем, что L(G) L(G 1 ). Пусть S x. Если в этом выводе используется правило A 1 B 2 P \ P 1, то рано или поздно для замены B будет использовано правило вида B i P.. Эти два шага вывода в грамматике G равносильны одному шагу вывода в G 1 : A 1 i 2.

65 Шаги вывода в грамматике G, на которых используются другие правила, общие для двух грамматик, являются шагами вывода в грамматике G 1. Поэтому S x. Что и требовалось доказать. Лемма о подстановке

66 Лемма 4.3 об устранении левой рекурсии. Пусть G = (V N, V T, P, S) КС- грамматика, {A A i A V N, i, i = 1, 2,..., m} множество всех леворекурсивных A-порождений, {A j j = 1, 2,..., n} множество всех прочих A-порождений. Пусть G 1 = (V N {Z}, V T, P 1, S) КС- грамматика, образованная добавлением нового нетерминала Z и заменой всех A-порождений правилами: 1) A j, 2) Z i, A j Z, j = 1, 2,..., n; Z i Z, i = 1, 2,..., m. Тогда L(G 1 ) = L(G). Ret 74Ret 76Ret 124Ret 80Ret 81 Ret 84

67 Доказательство. Прежде всего заметим, что посредством левосторонних выводов в грамматике G при использовании одних лишь A-порождений порождаются множе- ства вида { 1, 2,..., n }{ 1, 2,..., m } *, и это является в точности множеством, порождаемым правилами грамматики G 1, имеющими A или Z в левых частях. Об устранении левой рекурсии

68 Об устранении левой рекурсии I. Докажем, что L(G) L(G 1 ). Пусть x L(G). Левосторонний вывод S x мы можем перестроить в вывод S x. Именно, каждый раз, когда в левостороннем выводе встречается последовательность шагов: tA tA i 1 tA i 2 i 1... tA i p... i 2 i 1 t j i p... i 2 i 1 (t, ), заменим их последовательностью шагов: tA t j Z t j i p Z... t j i p... i 2 Z t j i p... i 2 i 1. Полученный таким образом вывод является выводом цепочки x в грамматике G 1, хотя и не левосторонним. Следовательно, x L(G 1 ).

69 Об устранении левой рекурсии II. Докажем, что L(G 1 ) L(G). Пусть x L(G 1 ). Рассмотрим левосторонний вывод S x, и перестроим его в вывод в грамматике G следующим образом. Всякий раз, как Z появляется в сентен- циальной форме, мы приостанавливаем левосторонний порядок вывода, и вместо того, чтобы производить замены нетерми- налов в цепочке, предшествующей Z, займемся замещением Z с помощью правил вида Z Z.

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

71 Об устранении левой рекурсии В общем случае вся последовательность шагов этого перестроенного участка вывода, в которых участвует Z, имеет вид tA t j Z t j i p Z... t j i p... i 2 Z t j i p... i 2 i 1. Очевидно, что такой же результат может быть получен в грамматике G: tA tA i 1 tA i 2 i 1... tA i p... i 2 i 1 t j i p... i 2 i 1. Таким образом, L(G 1 ) = L(G). Что и требовалось доказать.

72 Теорема 4.6 нормальная форма Грейбах. Каждый КС-язык может быть порож- ден КС-грамматикой в нормальной форме Грейбах. Доказательство. Пусть G = (V N, V T, P, S) КС-грамматика в нормальной форме Хомского, порождающая КС-язык L, где V N = {A 1, A 2,..., A m }.

73 Первый этап построения новой грамматики состоит в том, чтобы в её правилах вида A i A j, где цепочка нетерминалов, всегда было j > i. Этот шаг выполняется последовательно для i = 1, 2,..., m следующим образом. При i = 1 правило для A 1 может иметь вид A 1 a, где a V T, который не нуждается в преобразованиях, либо оно имеет вид A 1 A j A k, где A j, A k V N, j 1. Нормальная форма Грейбах Прямой ход метода Гаусса для систем линейных алгебраических уравнений: Приведение матрицы системы к треугольному виду!

74 Если j > 1, то правило уже имеет требуемый вид. Если j = 1, то оно леворекурсивно, и в соответствии с леммой об устранении левой рекурсии 4.3 может быть заменено правилами вида4.3 A 1, A 1 Z 1, Z 1 A k, Z 1 A k Z 1, где = a, a V T, Z 1 новый нетерминал, или = BC, причём B A 1. Нормальная форма Грейбах

75 Предположим, что для i = 1, 2,..., k (k i. Покажем, как добиться выполнения этого условия для A k+1 -порождений. Если A k+1 A j есть правило, в котором j

76 Повторив этот процесс самое большее k раз, получим порождения вида A k+1 A p, p k + 1. Порождения с p = k + 1 затем преобразу- ются согласно лемме 4.3 введением новой переменной Z k Повторив описанный процесс для каждого из оставшихся нетерминалов исходной грамматики, мы получим правила только одного из трёх следующих видов: Нормальная форма Грейбах

77 1. A k A p, где A k, A p V N, p > k, (V N {Z 1, Z 2,..., Z m }) + ; 2. A k a, где a V T, A k V N, (V N {Z 1, Z 2,..., Z m }) * ; 3. Z k, где (V N {Z 1, Z 2,..., Z m }) +. Цель второго этапа добиться, чтобы правые части правил вида (1) начинались с терминалов. Нормальная форма Грейбах Ret 79

78 Заметим, что первый символ правой части правила для A m по необходимости является терминалом, так как нетерминала с большим номером не существует. Первый символ правой части правила для A m–1 может быть терминалом, либо нетер- миналом A m. В последнем случае мы можем построить новые правила, заменяя A m правыми частями A m -порождений согласно лемме 4.2 о подстановке. Эти новые правила будут иметь правые части, начинающиеся с терминального символа.4.2 Нормальная форма Грейбах

79 Подобным же образом преобразуем правила для A m – 2, A m – 3,..., A 1. В результате все правила вида 1 будут преобразованы к виду 2. виду 2 Остается преобразовать правила вида 3 для новых переменных Z 1, Z 2,..., Z m, так чтобы правые части этих правил тоже начинались с терминалов. Эти преобразования составляют третий, последний, этап. Нормальная форма Грейбах Обратный ход метода Гаусса для систем линейных алгебраических уравнений !

80 Пусть имеется правило вида Z i A k. Достаточно ещё раз применить к нему преобразования леммы о подстановке 4.2, заменив A k правыми частями A k - порождений, чтобы получить требуемую форму правил, поскольку правые части правил для A k уже начинаются с терминалов.4.2 На этом построение грамматики в нормальной форме Грейбах, эквивалентной исходной грамматике G, завершается. Нормальная форма Грейбах

81 Поскольку все преобразования (подста- новка и исключение левой рекурсии) исходной грамматики являются эквива- лентными (см. леммы 4.2 и 4.3), то доказывать больше нечего Что и требовалось доказать. Нормальная форма Грейбах

82 Пример 4.2. Преобразуем грамматику G = ({A 1, A 2, A 3 }, {a, b}, P, A 1 ), где P = {A 1 A 2 A 3, A 2 A 3 A 1, A 2 b, A 3 A 1 A 2, A 3 a}, к нормальной форме Грейбах. Этап 1. Поскольку правые части правил для A 1 и A 2, начинаются с нетерминалов с большими номерами или с терминала, то мы начинаем с правила A 3 A 1 A 2 и подставляем цепочку A 2 A 3 вместо A 1. Заметим, что A 1 A 2 A 3 является един- ственным A 1 –порождением в грамматике G.

83 В результате получаем следующее множество правил {A 1 A 2 A 3, A 2 A 3 A 1, A 2 b, A 3 A 2 A 3 A 2, A 3 a}. Поскольку правая часть правила A 3 A 2 A 3 A 2 начинается с нетерминала с меньшим номером, чем надо, мы подставляем вместо первого вхождения A 2 либо A 3 A 1, либо b. Таким образом, правило A 3 A 2 A 3 A 2 заменяется на A 3 A 3 A 1 A 3 A 2 и A 3 bA 3 A 2. Новое множество правил есть {A 1 A 2 A 3, A 2 A 3 A 1, A 2 b, A 3 A 3 A 1 A 3 A 2, A 3 bA 3 A 2, A 3 a}. Пример 4.2. Нормальная форма Грейбах

84 Пример 4.2. Нормальная форма Грейбах Теперь применим лемму 4.3 к правилам4.3 A 3 A 3 A 1 A 3 A 2, A 3 bA 3 A 2 и A 3 a. Введем символ Z 3 и заменим правило A 3 A 3 A 1 A 3 A 2 правилами A 3 bA 3 A 2 Z 3, A 3 aZ 3, Z 3 A 1 A 3 A 2 и Z 3 A 1 A 3 A 2 Z 3. Теперь мы имеем множество правил: {A 1 A 2 A 3, A 2 A 3 A 1, A 2 b, A 3 bA 3 A 2, A 3 a, A 3 bA 3 A 2 Z 3, A 3 aZ 3, Z 3 A 1 A 3 A 2 Z 3, Z 3 A 1 A 3 A 2 }

85 Этап 2. Все правила с A 3 слева начинаются с терминалов. Они используются для замены A 3 в правиле A 2 A 3 A 1, а затем полученные правила для A 2 используются для того, чтобы заменить A 2 в правой части правила A 1 A 2 A 3. Получаем: A 3 bA 3 A 2, A 2 bA 3 A 2 A 1, A 1 bA 3 A 2 A 1 A 3, Z 3 A 1 A 3 A 2 Z 3, A 3 a, A 2 aA 1, A 1 aA 1 A 3, Z 3 A 1 A 3 A 2. A 3 bA 3 A 2 Z 3, A 2 bA 3 A 2 Z 3 A 1, A 1 bA 3 A 2 Z 3 A 1 A 3, A 3 aZ 3 ; A 2 aZ 3 A 1, A 1 aZ 3 A 1 A 3, A 2 b; A 1 bA 3 ; Пример 4.2. Нормальная форма Грейбах

86 Этап 3. Два правила для Z 3 заменяются на десять новых в результате подстановки в них вместо A 1 правых частей правил для A 1 : Z 3 bA 3 A 2 A 1 A 3 A 3 A 2 Z 3,Z 3 bA 3 A 2 A 1 A 3 A 3 A 2, Z 3 aA 1 A 3 A 3 A 2 Z 3, Z 3 aA 1 A 3 A 3 A 2, Z 3 bA 3 A 2 Z 3 A 1 A 3 A 3 A 2 Z 3, Z 3 bA 3 A 2 Z 3 A 1 A 3 A 3 A 2, Z 3 aZ 3 A 1 A 3 A 3 A 2 Z 3, Z 3 aZ 3 A 1 A 3 A 3 A 2, Z 3 bA 3 A 3 A 2 Z 3, Z 3 bA 3 A 3 A 2. Пример 4.2. Нормальная форма Грейбах

87 Окончательно, получаем следующее множество правил эквивалентной грамматики в нормальной форме Грейбах: A 3 bA 3 A 2, A 2 bA 3 A 2 A 1, A 1 bA 3 A 2 A 1 A 3, A 3 a, A 2 aA 1, A 1 aA 1 A 3, A 3 bA 3 A 2 Z 3, A 2 bA 3 A 2 Z 3 A 1, A 1 bA 3 A 2 Z 3 A 1 A 3, A 3 aZ 3 ; A 2 aZ 3 A 1, A 1 aZ 3 A 1 A 3, A 2 b; A 1 bA 3; Z 3 bA 3 A 2 A 1 A 3 A 3 A 2 Z 3, Z 3 bA 3 A 2 A 1 A 3 A 3 A 2, Z 3 aA 1 A 3 A 3 A 2 Z 3, Z 3 aA 1 A 3 A 3 A 2, Z 3 bA 3 A 2 Z 3 A 1 A 3 A 3 A 2 Z 3, Z 3 bA 3 A 2 Z 3 A 1 A 3 A 3 A 2, Z 3 aZ 3 A 1 A 3 A 3 A 2 Z 3, Z 3 aZ 3 A 1 A 3 A 3 A 2, Z 3 bA 3 A 3 A 2 Z 3, Z 3 bA 3 A 3 A 2. Пример 4.2. Нормальная форма Грейбах

88 § 4.4. Разрешимость конечности контекстно-свободных языков В теореме 4.2 было показано, что из КС-грам- матики можно исключить непродуктивные нетер- миналы, то есть порождающие пустые языки.4.2 Фактически можно добиться большего. Мы можем протестировать, порождает ли данный нетерминал конечный или бесконечный язык (см. теорему 4.8 далее), и исключить те из них, которые порождают конечные языки разу- меется, это не касается начального нетерминала (см. теорему 4.9 далее) Для построения алгоритма такого тестирования требуется обоснование утверждения теоремы 4.7, интересного самого по себе.4.7 Ret 103

89 Теорема 4.7 uvwxy. Пусть L cfl. Существуют постоянные p и q, зависящие только от языка L, такие, что если существует z L при z > p, то цепочка z представима в виде z = uvwxy, где vwx q, причём v, x одновременно не пусты, так что для любого целого i 0 цепочка uv i wx i y L. Доказательство. Пусть G = (V N, V T, P, S) какая-нибудь КС-грамматика в нормаль- ной форме Хомского для языка L. Ret 98Ret 88

90 Теорема 4.7 uvwxy Если #V N = k, положим p = 2 k–1 и q = 2 k. Докажем теорему для этих значений p и q. Заметим, что дерево вывода любой терминальной цепочки в грамматике G является почти бинарным *). Поэтому, если в нём нет пути, длиннее j, то выводимая терминальная цепочка не длиннее 2 j–1. *) Ибо не определено, ветвь, представляющая использование правила вида A a, левая или правая. a S j = 1, z = a, | z | = 2 0 a b j = 2, z = ab, | z | = 2 1 = 2 S A B Рис Иллюстрация: | z | 2 j при j = 1, 2.

91 Пусть существует цепочка z L, причём z > p, где p = 2 k–1. Тогда самый длинный путь в дереве вывода цепочки z длиннее k, ибо в противном случае z 2 k–1, и это противо- речило бы предположению, что z > p. Рассмотрим самый длинный путь R в дереве вывода z от корня до листа (см. рис. 4.3). 4.3 Теорема 4.7 uvwxy Ret 94

92 В нём должны быть два узла n 1 и n 2 такие, что 1) они имеют одинаковые метки A V N ; 2) узел n 1 ближе к корню, чем узел n 2 ; 3) часть пути R от узла n 1 до листа имеет длину, рав- ную самое большее k + 1. Теорема 4.7 uvwxy Рис Дерево вывода S z. n1n1 n2n2 R R R R R z2z2 z 1 = z 3 z 2 z 4 T1T1 T2T2 u y S a A A Рис Дерево вывода S z. n1n1 n2n2 R R R R R z2z2 z 1 = z 3 z 2 z 4 T1T1 T2T2 u y S a A A

93 Такие узлы всегда можно найти. Действительно, прой- дём путь R от листа в сторону корня. Из первых k + 2 прой- денных узлов только один имеет терминальную метку. Остальные k + 1 узлов могут быть помечены только нетер- миналами. Рассмотрим поддерево T 1 с корнем n 1. Его результат, являющийся подсловом слова z, обозначим через z 1. Теорема 4.7 uvwxy Рис Дерево вывода S z. n1n1 n2n2 R R R R R z2z2 z 1 = z 3 z 2 z 4 T1T1 T2T2 u y S a A A

94 В поддереве T 1 не может быть пути, длиннее k+1, так как R является самым длинным путём во всём дереве. Действительно, пусть R = Sn 1 + n 1 a. Если допустить, что в T 1 существует другой, более длинный, путь, скажем n 1 b, то путь R = Sn 1 + n 1 b окажется длиннее R, так как n 1 b длиннее n 1 a. Однако это противоречило бы первоначальному предполо- жению, что R является одним из самых длинных путей во всём дереве T. Потому z 1 2 k = q.путей Теорема 4.7 uvwxy Рис Дерево вывода S z. n1n1 n2n2 R R R R R z2z2 z 1 = z 3 z 2 z 4 T1T1 T2T2 u y S R R R R R b a A A

95 Обозначим через T 2 поддерево с корнем n 2, а его результат через z 2. Ясно, что цепочка z 1 представима в форме z 1 = z 3 z 2 z 4, где z 3 и z 4 одновременно не пусты. Действительно, если первое правило, ис- пользуемое в выводе z 1, имеет вид A BC, то поддерево T 2 должно быть полностью в пределах либо поддерева с корнем B, либо поддерева с корнем C, в крайнем случае совпадать с одним из них (см. рис. 4.4). Теорема 4.7 uvwxy

96 Теорема 4.7 uvwxy BC A z2z2 z4z4 z2z2 BC A z3z3 z2z2 BC A z2z2 z4z4 z3z3 n1n1 n1n1 n1n1 n2n2 n2n2 n2n2 B = A, z 3 = C = A, z 4 = B A, C A, z 3, z 4 (a)(a) (б)(б) (в)(в) Рис Три случая (из возможных четырёх) расположения деревьев T 1 и T 2.

97 Теорема 4.7 uvwxy Теперь мы знаем, что A z 1, A z 3 Az 4 и A z 2. Поэтому A z 3 Az 4 z 3 i Az 4 i z 3 i z 2 z 4 i для любого i 0, и цепочка z представима в виде z = u z 3 z 2 z 4 y для некоторых u, y. Чтобы закончить доказательство, положим v = z 3, w = z 2 и x = z 4.

98 Теорема 4.8. Существует алгоритм для определения, порождает ли данная КС- грамматика G конечный или бесконечный язык. Доказательство. Пусть p и q констан- ты, определяемые теоремой uvwxy Если z L(G) и z > p, то z = uvwxy при некоторых u, v, w, x, y V T *, v + x 0, и для любого i 0 цепочка uv i wx i y L(G). Следовательно, если в языке L(G) су- ществует цепочка длины больше p, то язык L(G) бесконечен. Ret 88

99 Пусть язык L = L(G) бесконечен. Тогда в нём имеются сколь угодно длинные цепочки и, в частности, цепочка длины больше p+q. Эта цепочка может быть представлена как uvwxy, где vwx q, v + x 0, и цепочка uv i wx i y L для любого i 0. В частности, при i = 0 цепочка uwy L и uwy < uvwxy. Алгоритмическая разрешимость проблемы конечности или бесконечности языка, порождаемого cfg

100 Убедимся в том, что uwy > p. Так как p + q < uvwxy и q vwx, то p < uy uwy. Если uwy > p + q, то эту процедуру можно повторять снова до тех пор, пока мы не найдём в языке L цепочку, длина которой l не будет удовлетворять неравенству p < l p + q. Таким образом, язык L бесконечен тогда и только тогда, когда он содержит цепочку длиной l, где p < l p + q. Алгоритмическая разрешимость проблемы конечности или бесконечности языка, порождаемого cfg

101 Поскольку мы можем проверить, имеется ли данная цепочка в данном КС- языке L (см. теорему 2.3 о рекурсивности контекстно-зависимых грамматик), то мы просто должны проверять все цепочки в интервале длин l, удовлетворяющих неравенству p < l p + q, на принадлеж- ность языку L(G).2.3 Если такая цепочка имеется, то язык L бесконечен; если в языке L нет цепочек длины больше, чем p, то язык L конечен. Что и требовалось доказать. Алгоритмическая разрешимость проблемы конечности или бесконечности языка, порождаемого cfg

102 В теореме 4.2 доказывалось, что из КС- грамматики можно исключить все нетерми- налы, из которых не выводится ни одной терминальной цепочки.4.2 Теперь мы докажем возможность исключения нетерминалов, из которых выводится только конечное число терми- нальных цепочек. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

103 Теорема 4.9. Для всякой КС-грамматики G 1 можно найти эквивалентную ей КС- грамматику G 2, такую, что если A нетерминал грамматики G 2, не являющий- ся начальным нетерминалом, то из A выводимо бесконечно много терминальных цепочек. Доказательство. Если язык L(G 1 ) = {x 1, x 2,..., x n } конечен, то утверждение очевидно. Ret 88

104 Действительно, положим G 2 = ({S}, V T, P 2, S), где P 2 = {S x i i = 1, 2,..., n}. В этой грамматике совсем нет нетерми- налов, отличных от S. Пусть теперь грамматика есть G 1 = (V N, V T, P 1, S), и язык L(G 1 ) бесконечен. Рассмотрим грамматики G A = (V N, V T, P 1, A) для всех A V N. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

105 Так как существует алгоритм, позволяющий узнать, бесконечен ли порождаемый грамматикой G A язык, то словарь V N мы можем разбить на две части: V N ={A 1, A 2,..., A k } {B 1, B 2,..., B m }, где A i (i = 1, 2,..., k) нетерминалы, порождаю- щие бесконечно много терминальных цепочек, причём начальный нетерминал S среди них, поскольку язык L бесконечен; B j ( j = 1, 2,..., m) нетерминалы, порождаю- щие конечные множества терминальных цепочек. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

106 Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек Построим грамматику G 2 = ({A 1, A 2,..., A k }, V T, P 2, S), где P 2 ={A i u 1 u 2... u r A i C 1 C 2... C r P 1, (1) u i = C i, если C i V T {A 1, A 2,..., A k }, (2) C i u i, u i, если C i {B 1, B 2,..., B m }}.

107 Короче говоря, правила P 2 получаются из правил P 1 посредством отбрасывания всех правил с нетерминалами B j в левых частях, а в правых частях оставшихся правил все вхождения нетерминалов B j надо заменить какими-нибудь их терминальными порож- дениями. Поскольку число таких терминальных порождений конечно, то и число получа- ющихся правил в P 2 тоже конечно. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

108 Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек Покажем теперь, что L(G 1 ) = L(G 2 ). I. L(G 1 ) L(G 2 ). Индукцией по длине вывода l докажем, что если A i w, то A i w, w (i = 1, 2,..., k). База. Пусть l = 1 и пусть A i w. При этом применялось правило A i w P 1, где w. Но это же правило есть в P 2 по построению (в правой части этого правила вовсе нет вхождений нетерминалов, в том числе и B j ). Поэтому A i w.

109 Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек Индукционная гипотеза. Предположим, что утверждение выполняется для всех выводов длины l n (n 1). Индукционный переход. Рассмотрим вывод длины l = n + 1: A i C 1 C 2... C r w 1 w 2... w r, где C p w p, w p, l p n. На первом шаге применяется правило A i C 1 C 2... C r P 1.

110 Возьмём во множестве правил P 2 соответ- ствующее правило, которое получается из данного заменой в нём всех нетерминалов типа B на соответствующие цепочки w, выводимые из них, т. е. правило A i u 1 u 2... u r P 2, в котором u p = w p, если C p V T {B 1, B 2,..., B k }, u p = C p, если C p {A 1, A 2,..., A k }, p =1, 2,..., r. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

111 Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек Таким образом, имеем A i u 1 u 2... u r, причём здесь все u p = w p, кроме тех u p, которые равны C p {A 1, A 2,..., A k }. Но для них C p w p, где l p n, по индукционному предположению C p w p. Поэтому A i u 1 u 2... u r w 1 w 2... w r. Итак, из A i w следует вывод A i w. Поскольку S {A 1, A 2,..., A k }, то L(G 1 ) L(G 2 ).

112 II. L(G 2 ) L(G 1 ). Пусть. Покажем, что. Шаг вывода, на котором используется правило вида A i u 1 u 2...u r P 2, производное от A i C 1 C 2... C r P 1, предполагает, что (1) C i = u i, если u i V T ; (2) C i нетерминал типа A, и C i = u i ; (3) C i нетерминал типа B и C i u i (i = 1, 2,..., r). Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

113 Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек Следовательно, A i C 1 C 2... C r u 1 u 2... u r. Таким образом, применение одного правила A i u 1 u 2...u r P 2 в выводе равносильно применению нескольких правил из множества P 1, позволяющих в цепочке заменить A i на u 1 u 2...u r, что дает.

114 Итак, каждый шаг вывода терминальной цепочки в грамматике G 2 может быть заменён несколькими шагами вывода в грамматике G 1, т. е. L(G 2 ) L(G 1 ). Из рассуждений I и II следует, что L(G 1 ) = L(G 2 ). Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

115 Пример 4.3. Рассмотрим грамматику G 1 = ({S, A, B}, {a, b, c, d }, P 1, S), где P 1 = {S ASB, S AB, A a, A b, B c, B d }. Легко видеть, что A порождает только цепочки a и b, а B порождает только цепочки c и d. Однако, S порождает бесконечно много цепочек. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

116 Правило S ASB заменяется правилами S aSc, S aSd, S bSc, S bSd. Аналогично, правило S AB заменяется правилами S ac, S ad, S bc, S bd. Новая грамматика есть G 2 = ({S}, {a, b, c, d}, P 2, S), где P 2 ={S aSc, S aSd, S bSc, S bSd, S ac, S ad, S bc, S bd}. Пример 4.3. Исключение нетерминалов из cfg, из которых выводится только конечное число терминальных цепочек

117 § 4.5. Свойство самовставленности Определение 4.5. Говорят, что КС- грамматика G является самовставленной 1), если существует нетерминал A, такой, что A 1 A 2, где 1, 2. Говорят также, что нетерминал A является самовставленным. 1) self-embedding grammar.

118 Заметим, что именно свойство само- вставленности является причиной появле- ния цепочек вида uv i wx i y. Это свойство самовставленности отличает строго контек- стно-свободные языки от регулярных множеств. Но отметим и то, что просто из- за свойства самовставленности данной грамматики порождаемый ею язык не обязан быть нерегулярным. Свойство самовставленности

119 Например, грамматика G = ({S}, {a, b}, P, S), где P = {S aSa, S aS, S a, S bS, S b}, несмотря на то, что она самовставленная, порождает регулярное множество. Действительно, L(G) = {a, b} +, т. к. первое правило эквивалентно второму + третьему, и первое может быть удалено без изменения языка. Свойство самовставленности

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

121 Теорема Пусть G несамо- вставленная КС-грамматика. Тогда L(G) регулярное множество. Доказательство. Нетрудно убедиться в том, что если исходная грамматика не является самовставленной, то и эквивалент- ные ей грамматики в нормальной форме Хомского и Грейбах тоже несамовстав- ленные.

122 Поэтому, если G несамовставленная грамматика, то мы можем найти грамматику G 1 = (, V T, P 1, S 1 ) в нормальной форме Грейбах, эквивалентную грамматике G, которая тоже будет несамовставленной. Регулярность языка, порождаемого несамовставленной cfg

123 Регулярность языка, порождаемого несамовставленной cfg Действительно, при получение НФХ исключение цепных правил, замена вхождений терминалов в правых частях правил на новые нетерминалы вида C, а затем ввод новых нетерминалов вида D, не вносит самовложенности относительно этих нетерминалов.вида Cвида D

124 Регулярность языка, порождаемого несамовставленной cfg Что касается получения нормальной формы Грейбах из НФХ, то подстановки на место крайнего слева нетерминала A j в правилах вида A i A j (i j) только повышает индекс j, но не вносит самовставенности. Исключение левой рекурсии из правил вида A A вводит новый нетерминал Z, который может быть самовставленым, если только нетерминал A самовставлен, чего нет.вида Учитывая теорему 4.3 о приводимости любой cfg, ложные признаки самовставенности могут быть исключены из рассуждений.4.3

125 Регулярность языка, порождаемого несамовставленной cfg Рассмотрим левосторонний вывод в грамматике G 1 некоторой сентенциальной формы x, где x, а. Докажем сначала, что если G 1 имеет m нетерминалов и l длина самой длинной правой части правил, то никакая сентенциальная форма не может иметь больше, чем ml нетерминалов.

126 Чтобы убедиться в этом, предположим противное, что в некоторой сентенциальной форме x левостороннего вывода появляется больше, чем ml нетерминалов. В дереве вывода цепочки x рассмотрим путь от корня к крайнему левому листу, помеченному нетерминалом (рис. 4.5).4.5 Регулярность языка, порождаемого несамовставленной cfg

127 Регулярность языка, порождаемого несамовставленной cfg Рис. 4.5 X 1 X 2 … X p 1 X p = … … … … S X1X1 A x = x 1 x 2 … x k X2X2 XpXp X p-1 Терминалы Нетерминалы Ур. 1 Ур. 2 Ур. k … A

128 Регулярность языка, порождаемого несамовставленной cfg Узлы одного уровня представляют правую часть одного правила грамматики, породив- шего эти узлы. Все узлы, расположенные справа от этого пути, также как и упомянутый лист, ещё не раскрывались с помощью правил. Именно они и образуют цепочку, состоящую из нетерминалов. На каждом уровне, кроме самого нижнего, таких узлов не больше, чем l – 2. На нижнем же уровне их не больше, чем l – 1.

129 Предположим, что в нашем дереве вывода k уровней. Тогда на всех уровнях узлов, порождающих, не больше, чем (l – 2)(k – 1) + l – 1. Всего таких узлов на всех k уровнях по предположению больше ml. Следовательно, (l – 2)(k – 1) + l – 1 ml + 1, откуда k (ml–l+2) / (l–2) +1 = ml / (l–2) > ml / l = m. Это, естественно, предполагает, что l > 2. Регулярность языка, порождаемого несамовставленной cfg

130 Регулярность языка, порождаемого несамовставленной cfg Итак, уровней k в дереве вывода (длина пути, о котором шла речь) больше m, т. е. по крайней мере их m + 1. Следовательно, на этом пути найдутся, по крайней мере, два узла, помеченных одним и тем же нетерминалом A. В этом случае существует левосторонний вывод вида A zA, где z,, т. е. z, (l > 2). А это значит, что A самовставленный нетерминал, что противоречит условию теоремы.

131 Регулярность языка, порождаемого несамовставленной cfg Теперь, если в любой сентенциальной форме самое большее ml нетерминалов, мы можем построить грамматику типа 3 G 2 = (, V T, P 2, S 2 ), порождающую язык L(G) следующим образом. Нетерминалы грамматики G 2 соответствуют цепочкам нетерминалов грамматики G 1, длина которых не больше ml, т. е. = {[ ], ml}; S 2 = [S]; P 2 = {[A ] b[ ] A b P 1 }.

132 Регулярность языка, порождаемого несамовставленной cfg Из построения должно быть очевидно, что грамматика G 2 моделирует все левосто- ронние выводы в грамматике G 1, так что L(G 2 ) = L(G 1 ). Действительно, индукцией по длине вывода легко показать, что S x посред- ством левостороннего вывода тогда и только тогда, когда [S] x[ ]. Здесь x закрытая, а откры- тая часть данной сентенциальной формы.

133 Регулярность языка, порождаемого несамовставленной cfg I. Докажем сначала, что если S x, то [S] x[ ]. База. Пусть l = 1. Имеем S x, S x P 1, x V T,. Следовательно, существует правило [S] x[ ] P 2 и потому [S] x[ ]. Индукционная гипотеза. Предположим, что аналогичное утверждение имеет место при всех l n (n 1).

134 Регулярность языка, порождаемого несамовставленной cfg Индукционный переход. Докажем утвержде- ние при l n +1. Пусть S xA xb = x, т. е. x = xb, =. По индукционной гипотезе из существова- ния вывода S xA следует, что [S] x[A ], а поскольку на последнем шаге вывода использовано правило A b P 1, то суще- ствует правило [A ] b[ ] P 2, с помощью которого можно завершить имеющийся вывод [S] x [A ] xb[ ] = x[ ].

135 Регулярность языка, порождаемого несамовставленной cfg II. Докажем теперь, что если [S] x[ ], то S x. База. Пусть l = 1. Имеем [S] x[ ]. Существует правило [S] x[ ] P 2, x V T,, которое обусловлено существованием правила S x P 1, и потому S x. Индукционная гипотеза. Предположим, что аналогичное утверждение имеет место при всех l n (n 1).

136 Регулярность языка, порождаемого несамовставленной cfg Индукционный переход. Докажем утвержде- ние при l = n + 1. Пусть [S] x [A ] x b[ ] = x[ ], здесь x = x b,. По индукционной гипотезе из существова- ния вывода [S] x [A ] следует, что S x A.

137 Регулярность языка, порождаемого несамовставленной cfg На последнем шаге вывода использовано правило [A ] b[ ] P 2, существование которого обусловлено существованием правила A b P 1, где =, которое можно использовать для завершения имеющегося вывода в грамматике G 1. S x A x b = x. Из рассуждений I и II при = получаем L(G 1 ) = L(G 2 ). Таким образом, язык L(G) регулярен. Что и требовалось доказать.

138 § Правила в КС- грамматиках Ранее мы показали, что на правила КС- грамматик можно накладывать некоторые ограничения, не сужая класс языков, которые могут порождаться. Теперь мы рассмотрим расширения КС- грамматик, которые разрешают использо- вать правила вида A для любого нетерминала. Многие описания синтаксиса языков программирования допускают такие продукции (т. е. правила).

139 Мы покажем, что язык, порождаемый КС-грамматикой с -правилами, всегда КС-язык, т. е. может быть порождён без правил вида A, где A S. Понятия, касающиеся деревьев вывода для КС-грамматик, непосредственно пере- носятся на эти расширенные грамматики. Просто разрешается использовать обозна- чение в качестве метки узла. Ясно, что такой узел может быть только листом. -Правила в cfg

140 Теорема Если L язык, порождае- мый грамматикой G = (V N, V T, P, S), где каждое правило в P имеет вид A, где A нетерминал, а ( = допустимо), то L может быть порождён грамматикой, в которой каждое правило имеет вид A, где A нетерминал, а, либо S, и, кроме того, начальный нетерминал грамматики S не появляется в правой части никакого правила. Ret 150

141 Доказательство. При помощи тривиаль- ного расширения леммы 2.1 мы можем предположить, что S не появляется справа ни в одном правиле в P.2.1 Для любого нетерминала A V N мы можем решить, существует ли вывод A, поскольку, если такой вывод существует, то существует и дерево вывода, ветви которого не длиннее, чем число нетерминалов грамматики G (этот аргумент использовался в теореме 4.1).4.1 -Правила в cfg

142 -Правила в cfg Пусть A 1, A 2,..., A k те нетерминалы из словаря V N, из которых цепочка может быть выведена, а B 1, B 2,..., B m те нетерминалы, из которых цепочка не выводима. Мы построим новое множество правил P 1 следующим образом: (1) Если S, то в P 1 включим правило S. (2) Никакие правила грамматики G вида A в P 1 не включаются.

143 -Правила в cfg (3) Если A C 1 C 2 …C r P, r 1, то в P 1 включаются правила вида A r, однако не все i = (1 i r). C i, если C i V T {B 1, B 2,..., B m }, C i или, при C i {A 1, A 2,..., A k }, где i =

144 Другими словами, преобразования на шаге 3 состоят в том, что в правой части A-правила исходной грамматики G каждое вхождение C i {A 1, A 2,..., A k }, альтернативно либо под- меняется на, либо остается, как есть. Вхождения других символов (терминаль- ных и нетерминальных из множества {B 1, B 2,..., B m }) не затрагиваются. При этом не допускается, чтобы правая часть полученного правила обратилась в. -Правила в cfg

145 -Правила в cfg Ясно, что новая грамматика G 1 = (V N, V T, P 1, S) отличается от грамматики G только набором правил, причём все они имеют требуемый вид. I. Докажем, что L(G 1 ) L(G). Пусть и при этом применяется правило A r P 1 \ P.

146 -Правила в cfg Его применение эквивалентно применению правила A C 1 C 2... C r P, из которого оно было получено, и нескольких правил из множества правил P для выводов C i, если i =. Шаги, на которых применяются правила, общие для G и G 1, могут считаться выполняемыми в G. Утверждение I доказано.

147 -Правила в cfg II. Докажем теперь, что L(G) L(G 1 ). Индукцией по числу шагов l в выводе докажем, что если A w и w, то A w для A V N. База. Пусть l = 1. Очевидно, что вывод A w есть также вывод A w, ибо по построению правило A w находится также и P 1.

148 -Правила в cfg Индукционная гипотеза. Предположим, что утверждение выполняется для всех выводов длиной l n (n 1). Индукционный переход. Пусть A w. Более детально этот вывод имеет следующий вид: A C 1 C 2... C r w 1 w 2...w r, причём C i w i, l i n. Если w i, то по индукционному предположению C i w i.

149 -Правила в cfg Кроме того, по построению из правила A C 1 C 2...C r P получается правило A 1 2 … r P 1, где i = C i, если w i, или i =, если w i =. Следовательно, A w. Из рассуждений I и II следует, что L(G 1 ) = L(G). Что и требовалось доказать.

150 Из теоремы 4.11 непосредственно следует тот факт, что единственная разница между КС-грамматикой с правилами вида A и КС-грамматиками без -правил состоит в том, что первая может порождать пустое предложение.4.11 Далее обозначение cfg мы будем исполь- зовать также и для КС-грамматик с -правилами, зная, что эквивалентная грамматика без -правил (за исключением быть может S ) может быть найдена. -Правила в cfg

151 § 4.7. Специальные типы контекстно-свободных языков и грамматик Здесь мы рассмотрим несколько ограниченных классов контекстно-свободных языков и грамматик. Определение 4.6. Говорят, что КС-грам- матика G = (V N, V T, P, S) линейна, если каждое её правило имеет вид A uBv или A u, где A, B V N, u, v. Если v =, то грамматика называется праволинейной, если u =, то она лево- линейна.

152 Язык, который может порождаться линейной грамматикой, называется линейным языком. Не все контекстно-свободные языки являются линейными языками. Заметим, что ни одна цепочка, выводимая в линейной грамматике, не имеет более одного нетерминала. Специальные типы cfg и cfl

153 Пример 4.4. Грамматика G = ({S}, {0, 1}, P, S), где P = {S 0S1, S }, является линейной грамматикой, которая порождает язык L ={0 n 1 n n 0}. Специальные типы cfg и cfl

154 Определение 4.7. Говорят, что грамматика G = (V N, V T, P, S) последовательная, если нетерминалы A 1, A 2,..., A k из словаря V N можно упорядочить так, что если A i P, то не содержит ни одного нетерминала A j с индексом j < i. Язык, порождаемый последовательной грамматикой, называется последователь- ным языком. Специальные типы cfg и cfl

155 Пример 4.5. Грамматика G = ({A 1, A 2 }, {0, 1}, P, A 1 ), где P = {A 1 A 2 A 1, A 1 A 2, A 2 0A 2 1, A 2 }, является последовательной грамматикой, которая порождает язык L = {0 n 1 n n 0} *. Специальные типы cfg и cfl

156 Специальные типы cfg и cfl Определение 4.8. Если КС-язык L над алфавитом V T есть подмножество языка w 1 * w 2 *... w k * для некоторого k, где w i, i = 1, 2,..., k, то говорят, что L ограничен- ный язык. Строго говоря, множество w 1 * w 2 *... w k * следовало бы записывать в виде Но и без скобок не возникает никаких недоразумений.

157 Пример 4.6. Язык {(ab) n c n (dd) * n 1} является ограниченным языком. Здесь k = 3, а w 1 = ab, w 2 = c, w 3 = d. Специальные типы cfg и cfl

158 Определение 4.9. Говорят, что контекстно- свободная грамматика G = (V N, V T, P, S) неоднозначна, если в языке L(G) существует цепочка, выводимая двумя или более раз- личными левосторонними выводами. Или, что то же самое, если существуют два или более различных деревев вывода с одинаковыми результатами. Специальные типы cfg и cfl

159 Пример 4.7. Рассмотрим грамматику G из примера 4.1, которая имеет следующие правила:4.1 P = {S bA,S aB, A a, A aS, A bAA, B b, B bS, B aBB}. Цепочка aabbab имеет следующие два левосторонних вывода: S aB aaBB aabB aabbS aabbaB aabbab, S aB aaBB aabSB aabbAB aabbaB aabbab.

160 Следовательно, грамматика G неодно- значная. Однако язык состоит из цепочек, содержащих равное число букв a и b, и может быть порождён однозначной грам- матикой G 1 = ({S, A, B}, {a, b}, P, S), где P состоит из правил S aBS, S aB, S bAS, S bA, A bAA, A a, B aBB, B b. Специальные типы cfg и cfl

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

162 Существенно неоднозначные контекстно- свободные языки существуют. Классическим примером такого языка является язык L = {a i b j c k i = j или j = k}. Основная причина, по которой язык L существенно неоднозначен, состоит в том, что любая cfg, порождающая язык L, должна порождать те цепочки, для которых i=j, при помощи процесса, который отличается от процесса порождения тех цепочек, для которых j = k. Специальные типы cfg и cfl

163 Невозможно не порождать некоторые из тех цепочек, для которых i = j = k, посред- ством обоих процессов. Строгое доказательство этого факта весьма сложно (см., например, [1]). Известно, что проблема распознавания существенной неоднозначности КС-языков алгоритмически неразрешима. Специальные типы cfg и cfl Next