Крючкова Е.Н. Основы математической логики и теории алгоритмов

Подождите немного. Документ загружается.

7.5.2 Преобразование 2 — правила с одинаковыми правыми

частями

При удалении правил вида A → B в множестве правил появляется много пра-

вил с одинаковой правой частью. Рассмотрим построение для произвольной КС–

грамматики эквивалентной КС–грамматики, все правила которой имеют различные

правые части.

Пусть G

= (V

, V

, P

, S) — некоторая КС–грамматика, все нетерминальные

символы которой имеют непустые несовпадающие множества нижних индексов:

V = {A

...i

}, i

< i

при n < m.

Пусть в множестве P

существуют правила с совпадающими правыми частями

...i

→ ϕ ,

...,j

→ ϕ ,

...l

→ ϕ .

(7.1)

Построим грамматику G

n+1

следующим образом:

1) заменим правила (7.1) на A

...n

→ ϕ, где n

< n

при i < j и множество

, n

, ...n

} есть объединение индексов нетерминалов, стоящих в левых частях пра-

вил (7.1);

2) если некоторое A

для i ∈ {n

, n

, ..., n

} есть аксиома S грамматики G

, то

новому множеству правил P

n+1

принадлежит правило S → A

...n

;

3) если множеству P

принадлежат правила вида

B → ξA

...p

η, (7.2)

такие, что {p

, p

, ...p

} ⊂ {n

, n

, ...n

}, то к новому множеству правил добавляются

правила вида B → ξA

...n

η, полученные из (7.2) с помощью подстановки A

...n

вместо некоторых (быть может, никаких) A

...p

в правой части правила (7.2). На-

зовем такое построение G

n+1

по G

операцией частичного склеивания по индексам.

Пример 7.6. Пусть задана грамматика

: S → bA

|baA

→ aaA

|ab|d

→ aaA

|ab|c

Выполним частичное склеивание, удалив правила A

→ ab и A

→ ab :

: S → bA

|baA

|bA

|baA

→ aaA

|d|aaA

→ aaA

|c|aaA

→ ab

201

Выполним опять частичное склеивание, удалив правила A

→ aaA

и A

→ aaA

: S → bA

|baA

|bA

|baA

→ ab|aaA

→ aaA

|d|aaA

→ aaA

|c|aaA

При выполнении частичного склеивания может оказаться, что грамматике G

n+1

од-

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

...i

→ ξ , (7.3)

...n

→ ξ , (7.4)

что {i

, i

, ...i

} ⊂ {n

, n

, ...n

}. Назовем обобщенным склеиванием по индексам такое

построение грамматики G

n+1

по грамматике G

, когда

1) выполнено частичное склеивание G

к G

n+1

;

2) если среди множества полученных правил грамматики G

n+1

окажутся правила

вида (7.3), (7.4), то из множества правил грамматики удаляется правило (7.3) как

более слабое.

В нашем примере грамматике одновременно принадлежат правила A

→ aaA

, A

→ aaA

, первые два из которых можно удалить. Правые части

правил грамматики, полученной в результате такого удаления, различны:

: S → bA

|baA

|bA

|baA

→ aaA

→ ab|aaA

Можно доказать следующую теорему.

Теорема 7.6. В результате последовательного применения к любой КС–грам-

матике операции обобщенного склеивания строится эквивалентная КС–грамматика,

все правила которой имеют различные правые части.

Доказательство. Очевидно, что последовательное применение алгоритма обоб-

щенного склеивания преобразует любую КС-грамматику к такой форме, когда все

правила имеют различные правые части. Осталось показать эквивалентность ис-

ходной грамматики и грамматики, полученной в результате операции обобщенного

склеивания. Сначала заметим, что частичное склеивание является эквивалентным

преобразованием грамматики G

, т.к. замена (7.1) и подстановка (7.2) каждому вы-

воду в G

взаимно однозначно ставят вывод в G

n+1

, полученной из G

операцией

частичного склеивания. Пусть грамматика G

n+1

получена из грамматики G

опе-

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

при наличии правил (7.4) не нарушает эквивалентности грамматик. Действительно,

пусть в выводе некоторой цепочки x в грамматике G

применялось правило вида

(7.3):

∗

⇒ z

,...,i

→ z

ξz

∗

⇒ x.

Нетерминал A

,...,i

появился в этом выводе на одном из предшествуюших шагов:

∗

⇒ y

ωA

...i

ηy

= z

...i

→ z

ξz

∗

⇒ x.

202

Но тогда по правилу подстановки при выполнении операции частичного склеивания

в множество правил новой грамматики G

n+1

включается новое првило

B → ωA

...n

и, следовательно, существует эквивалентный вывод в G

n+1

∗

⇒ y

ωA

...n

ηy

= z

...n

→ z

ξz

∗

⇒ x.

Таким образом, L(G

) = L(G

n+1

). 

7.5.3 Преобразование 3 — неукорачивающие грамматики

Определение 7.17. Грамматика, не содержащая правил с пустой правой ча-

стью, называется неукорачивающей грамматикой.

При выводе в неукорачивающей грамматике длина выводимой цепочки не умень-

шается при переходе от k–го шага вывода к (k + 1)–му. В грамматике с правилами

вида A → ε длина выводимой цепочки может уменьшаться:

G : S → aSb|ε

S ⇒ aSb ⇒ aaSbb ⇒ aabb.

В соответствии с определением (7.17) грамматика называется укорачивающей, ес-

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

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

разбором в неукорачивающих грамматиках, так как необходимо найти такой фраг-

мент входной цепочки, где можно вставить пустую цепочку ε:

Основным требованием, предъявляемым к языку программирования, является

возможность определить для каждой данной последовательности символов, являет-

ся ли она программой, написанной на этом языке. Это необходимо в первую оче-

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

формальном уровне это означает, что должна быть разрешима проблема принад-

лежности любой цепочки любому заданному КС–языку. Другими словами, должен

существовать алгоритм, позволяющий определить, принадлежит ли произвольная

заданная цепочка x произвольному заданному КС–языку L. С этой точки зрения

особенный интерес представляют неукорачивающие КС–грамматики в силу следую-

щих теорем.

Теорема 7.7. Пусть G = (V

, V

, P, S) есть неукорачивающая КС–грамматика

и n — число нетерминальных символов в множестве V

. Цепочка x ∈ V

∗

длины k

тогда и только тогда принадлежит языку L(G), когда существует ее вывод

S ⇒ U

⇒ . . . ⇒ U

= x, (7.5)

такой, что p ≤ n

203

Доказательство. Пусть G = (V

, V

, P, S) и x ∈ V

∗

. Согласно определению

языка L(G), если существует вывод (7.5), то x ∈ L(G ). Допустим теперь, что цепочка

x выводима из S в G. Пусть r — наименьшее число, для которого существует вывод

S ⇒ Z

⇒ . . . ⇒ Z

= x. Поскольку G — неукорачивающая КС–грамматика, то

| ≤ |Z

i+1

| для каждого i. Предположим, что r > n

. Тогда в выводе x найдутся

цепочки Z

= Z

при l < m. Отсюда следует, что имеется более короткий вывод S ⇒

⇒ . . . ⇒ Z

⇒ Z

m+1

⇒ . . . ⇒ Z

= x, что противоречит свойству минимальности

рассмотренного нами вывода.

Теорема 7.8. Существует алгоритм, позволяющий узнать, принадлежит ли про-

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

кой.

Доказательство. Пусть x — произвольная цепочка из Σ

∗

и G — некоторая

неукорачивающая КС–грамматика с тем же множеством терминальных символов.

Пусть длина цепочки x равна k. Из теоремы 7.7 следует, что x ∈ L(G) тогда и

только тогда, когда x порождается с помощью некоторого вывода, длина которого не

превышает m = n

|x|

, где n — число нетерминальных символов в G. Тогда достаточно

просмотреть все выводы, длины которых не превышают m. Цепочка x принадлежит

L(G) тогда и только тогда, когда ее можно получить с помощью хотя бы одного из

рассмотренных выводов.

Представляет интерес преобразование любой КС–грамматики в эквивалентную

неукорачивающую грамматику. Если G — КС–грамматика и ε ∈ L(G), то хотя бы

одно правило вида A → ε в множестве правил G имеется. Если ε /∈ L(G), то по

грамматике G всегда можно построить КС–грамматику, тоже порождающую язык

L(G), но не содержащую ни одного правила с пустой правой частью. Алгоритм такого

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

Теорема 7.9. Для произвольной КС–грамматики, порождающей язык без пустой

цепочки, можно построить эквивалентную неукорачивающую КС–грамматику.

Доказательство. Построим множество всех нетерминальных символов грамма-

тики G = (V

, V

, P, S), из которых выводится пустая цепочка. С этой целью выделим

следующие множества нетерминалов:

= {A|A → ε ∈ P },

m+1

= W

∪ {B|B → ϕ ∈ P , ϕ ∈ W

∗

Ясно, что A

∗

⇒ ε тогда и только тогда, когда A ∈ W

для некоторого n (n < |V

|).

Рассмотрим множество P

, состоящее из всех правил A → ˜α, полученных из

правил A → α ∈ P при удалении из α некоторых (возможно, никаких) вхождений

символов из множества W

= P \ {A → ε|A → ε ∈ P }

i+1

= {A → ˜α |A → α ∈ P

; α = α

Bα

; B ∈ W

&˜α = α

} .

Грамматика G

= (V

, V

, P

, S) является неукорачивающей. Покажем, что она эк-

вивалентна G. Пусть x ∈ L(G

), тогда существует вывод x в G

. Рассмотрим

первый левый шаг вывода, на котором применялось первое правило, не принадле-

жащее P . По построению множеству P принадлежит такое правило A → α, что

α = x

. . . x

r+1

и A

, A

, . . . A

∈ W n. Это означает, что в G выводимо

∗

⇒ ε, . . . , A

∗

⇒ ε, но тогда рассмотренный шаг вывода в G

можно заменить на

вывод в G :

...x

r+1

⇒ x

...x

r+1

⇒ . . . ⇒ x

...x

r+1

204

Выполняя такие преобразования на каждом шаге вывода в G

, получим вывод x в

G, следовательно, L(G

) ⊆ L(G). Аналогично можно показать, что L(G) ⊆ L(G

). С

этой целью вывод x в G преобразуется в вывод x в G

удалением справа налево всех

правил вида A → ε.

Пример 7.7. Пусть задана КС–грамматика

G : S → AbA|cA|Bbb

A → aAb|ε

B → AA|ca.

Построим множества нетерминалов, из которых выводится ε :

1) W

= {A}, т.к. имеется правило A → ε;

2) W

= {A, B}, т.к. имеется правило B → AA и A ∈ W

;

3) W

= W

Построим неукорачивающую грамматику, эквивалентную исходной:

G : S → AbA|cA|Bbb|Ab|bA|b|c|bb

A → aAb|ab

B → AA|ca|A.

Определение 7.18. КС–грамматики G

и G

эквивалентны с точностью до пу-

стой цепочки, если

L(G

) \ {ε} = L(G

) \ {ε}.

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

вивалентную исходной с точностью до ε.

7.5.4 Преобразование 4 — непродуктивные нетерминалы

Рассмотрим грамматику

G : S → bS|a|aA

A → aAb.

Нетерминальный символ A не участвует в выводе терминальных цепочек и поэто-

му может быть исключен из грамматики вместе со всеми правилами, в которые он

входит.

Определение 7.19. Нетерминальный символ A называется непродуктивным

(непроизводящим), если он не порождает ни одной терминальной цепочки, т.е. не

существует вывода A

∗

⇒ x, где x ∈ V

∗

Представляет интерес удаление из грамматики всех непродуктивных нетерми-

нальных символов.

Теорема 7.10. Для произвольной КС–грамматики можно построить эквивалент-

ную КС–грамматику, все нетерминальные символы которой продуктивны.

Доказательство. Пусть G = (V

, V

, P, S) — произвольная КС–грамматика. По-

строим множество всех продуктивных нетерминалов этой грамматики. С этой целью

выделим множество W

нетерминалов, стоящих в левой части терминальных правил:

= {A|A → ϕ ∈ P ; ϕ ∈ V

∗

Затем построим множества W

, W

, . . . , W

(n — число нетерминальных символов в

G):

k+1

= W

∪ {B|B → x ∈ P ; x ∈ (V

∪ W

)

∗

205

Все B ∈ W

продуктивны по построению W

. Пусть продуктивны все B ∈ W

(k ≥

1). Покажем, что продуктивными являются и все B ∈ W

k+1

. Действительно, если

B ∈ W

k+1

, то либо B ∈ W

и является продуктивным, либо B /∈ W

, но тогда

B → x ∈ P и x ∈ (V

∪W

)

∗

. Пусть x = x

. . . x

m+1

, тогда все A

являются

продуктивными, следовательно, B — продуктивный нетерминал. Пусть теперь B —

продуктивный нетерминал, минимальный терминальный вывод из B имеет длину

k + 1 и B ⇒ x

. . . x

m+1

∗

⇒ y ∈ V

∗

, все x ∈ V

∗

, все A

∈ V

∗

. Для каждого

существует вывод A

∗

⇒ y

∗

длины не более k, тогда все A

∈ W

(i ≤ k) и

по построению множества W

k+1

ему принадлежит B. Таким образом, показали, что

B ∈ W

тогда и только тогда, когда он продуктивен. Все символы множества V

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

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

они входят.

Пример 7.8. Пусть задана грамматика:

G : S → SA|BSb|bAb

A → aSa|bb

B → bBb|BaA.

Построим множество продуктивных нетерминалов:

1) W

= {A}, т.к. имеется правило A → bb;

2) W

= {A, S}, т.к. имеется правило S → bAb и A ∈ W

;

3) W

= W

Эквивалентная исходной грамматика, все символы которой продуктивны, имеет

вид:

: S → SA|bAb

A → aAa|bb.

7.5.5 Преобразование 5 — независимые нетерминалы

Существует еще один тип нетерминальных символов, которые можно удалять

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

грамматику

G : S → aS|b

A → aAb|ab.

Нетерминальный символ A не участвует ни в каком выводе в этой грамматике, т.к.

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

Определение 7.20. В КС–грамматике G нетерминальный символ A зависит от

нетерминального символа B, если в G существует вывод A

∗

⇒ xBy.

В рассмотренном выше примере аксиома

не зависит от символа

поэтому

можно удалить из грамматики.

Теорема 7.11. Для произвольной КС–грамматики можно построить эквивалент-

ную КС–грамматику, аксиома которой зависит от всех нетерминальных символов.

Доказательство. Пусть G = (V

, V

, P, S) — произвольная КС–грамматика. По-

строим множество нетерминалов, от которых зависит аксиома. С этой целью выде-

лим множества W

, W

, ...W

= {S},

k+1

= W

∪ {B|A → xBy ∈ P, A ∈ W

Аналогично доказательству теоремы 7.10 можно показать, что B ∈ W

тогда и толь-

ко тогда, когда S зависит от B (доказательство оставляется в качестве упражнения).

206

Все нетерминалы, не содержащиеся в W

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

правилами, в которые они входят. 

Пример 7.9. Пусть задана КС–грамматика

G : S → AS|bb

A → aAb|ab

B → SB|aAb.

Найдем нетерминалы, от которых зависит аксиома:

1) W

= {S};

2) W

= {S, A}, т.к. имеется правило S → AS и S ∈ W

;

3) W

= W

Эквивалентная грамматика, аксиома которой зависит от всех нетерминальных

символов:

: S → AS|Sb

A → aAb|ab

Определение 7.21. КС–грамматика G = (V

, V

, P, S) называется приведенной,

если S зависит от всех нетерминалов из V

и в V

нет непродуктивных символов.

Из теорем 7.10 и 7.11 следует, что для любой КС–грамматики можно построить

приведенную эквивалентную КС–грамматику.

7.5.6 Преобразование 6 — терминальные правила

Рассмотрим в КС–грамматике G = ( V

, V

, P, S) удаление правила с терминаль-

ной правой частью A → β, где β ∈ V

∗

. Любой вывод с использованием этого правила

имеет вид

S ⇒

∗

⇒ x

βx

Но нетерминал A в сентенциальной форме x

появился на некотором преды-

дущем шаге вывода B → uAv, тогда

∗

⇒ z

∗

⇒ z

uAvz

= x

⇒ x

βx

Если в правило грамматики B → uAv вместо A подставить β, получим правило

B → uβv и длина вывода сократится на один шаг при неизменности выводимой

цепочки. Следовательно, для того, чтобы удалить терминальное правило грамматики

A → β, необходимо рассмотреть следующие варианты :

а) для A больше нет правил, тогда во всех правых частях A заменяется на β;

б) для A есть другие правила, тогда добавляются новые правила, в которых A

заменяется на β.

Пример 7.10. Рассмотрим грамматику, порождающую идентификаторы (см.

7.2), обозначив для наглядности символами b — букву, c — цифру:

G : S → bA

A → AZ|ε

Z → b|c.

Удалим правила для Z, получим эквивалентную грамматику

: S → bA

A → Ab|Ac|ε.

207

7.5.7 Преобразования 7 и 8 — леворекурсивные и праворекур-

сивные правила

Некоторые специальные методы грамматического разбора неприменимы к лево-

рекурсивным или праворекурсивным грамматикам, поэтому рассмотрим устранение

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

грамматикой с конечным числом правил только благодаря рекурсии, следовательно,

вообще избавиться от рекурсии в правилах невозможно. Можно лишь преобразовать

один вид рекурсии в другой.

Теорема 7.12. Для любой леворекурсивной КС–грамматики существует эквива-

лентная праворекурсивная.

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

имеют вид

A → Ax

|Ax

|. . . |Ax

|. . . |w

, (7.6)

где x

и w

— цепочки над V

∪ V

. Введем дополнительные нетерминалы B и D и

заменим (7.6) на эквивалентные правила

A → AB|D

B → x

|. . . |x

D → w

|. . . |w

Вывод из A имеет вид A ⇒ AB ⇒ ABB ⇒ ... ⇒ AB

∗

⇒ DB

∗

и, следовательно, для

A можно определить эквивалентные правила

A → DK

K → BK|ε.

Выполняя подстановку B и D в эти правила, получим праворекурсивные правила

A → w

K|w

K|...|w

K → x

K|x

K|...|x

K|ε .



Пример 7.11. Для грамматики

G : S → SaA|ab

A → Aab|aAb|c

можно построить эквивалентную нелеворекурсивную

: S → abT

T → aAT |ε

A → aAbR|cR

R → abR|ε.

Аналогично можно построить алгоритм устранения правой рекурсии и доказать

эквивалентность соответствующего преобразования.

Теорема 7.13. Для любой праворекурсивной КС–грамматики существует экви-

валентная леворекурсивная.

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

имеют вид

A → x

A|x

A|. . . |x

A|w

|. . . |w

, (7.7)

208

где x

и w

— цепочки над V

∪ V

. Введем дополнительные нетерминалы B и D и

заменим (7.7) на эквивалентные правила

A → BA|D

B → x

|. . . |x

D → w

|. . . |w

Вывод из A имеет вид A ⇒ BA ⇒ BBA ⇒ ... ⇒ B

∗

A ⇒ B

∗

D и, следовательно, для

A можно определить эквивалентные правила

A → KD

K → KB|ε.

Выполняя подстановку B и D в эти правила, получим леворекурсивные правила

A → Kw

|Kw

|...|Kw

K → Kx

|Kx

|...|Kx

|ε.



7.6 Теорема о языке a

В 7.2 мы сформулировали, но не доказали теорему о языке a

. Рассмотрим

теперь ее доказательство. Сразу отметим, что при доказательстве этой теоремы мы

будем использовать только понятие выводимости и определение дерева граммати-

ческого разбора, не пытаясь применить полученные из теоремы 7.2 выводы о неза-

мкнутости семейства КС–языков относительно операций пересечения, дополнения и

разности.

Лемма 7.1. Для любой КС – грамматики, порождающей бесконечный язык,

существуют такие натуральные числа p и q, что каждая цепочка w ∈ L(G), |w| > p,

может быть представлена в виде w = xuyvz , где |uv| > q и для любого n > 0 цепочка

z ∈ L(G).

Доказательство. Рассмотрим всевозможные выводы S

∗

⇒ t терминальных це-

почек t ∈ V

∗

из аксиомы S, удовлетворяющие тем условиям, что в дереве разбора

цепочки t на пути из корня в любой лист один и тот же нетерминал не встречается

два раза. Возьмем в качестве числа p максимальную длину таких цепочек t. Возь-

мем произвольную цепочку w такую, что |w| > p и S

∗

⇒ w. По построению числа p в

дереве вывода цепочки w на каком–то пути из S в лист существует повторяющийся

нетерминал A

(см. рис. 7.6).

Мы знаем, что любая грамматика может быть преобразована так, что она яв-

ляется неукорачивающей и не содержит правил вида нетерминал–нетерминал, сле-

довательно, |uv| > 0. Возьмем в качестве числа q = |uv|. Тогда существует вывод

∗

⇒ u

для любого n. Следовательно, в G существует вывод

∗

⇒ xA

∗

⇒ xu

z ⇒ xu



Теорема 7.2. Язык a

, n ≥ 0 — не КС–язык.

Доказательство. Пусть a

— КС–язык, т.е. существует КС–грамматика G,

его порождающая. По доказанной лемме существует такая цепочка xvyuz ∈ L(G),

что xv

z ∈ L(G). Рассмотрим все варианты определения подцепочки v в слове

209

Рис. 7.6: Повторяющийся нетерминал A

в дереве вывода.

: a

, a

, b

, c

, a

. Покажем, что ни один из этих вариантов опреде-

ления v не может иметь места.

Пусть v = a

, тогда a

)

z ∈ L(G), что невозможно из–за нарушения соотно-

шения между равным числом символов a и b или a и c.

Пусть v = a

, тогда a

)

zL(G), чего быть не может, т.к. при k > 1 в

полученной цепочке после символа b встречается символ a.

Аналогично можно показать невозможность оставшихся вариантов определения

v. Следовательно, язык a

не может порождаться КС–грамматикой. Пример

грамматики типа 0, порождающей этот язык, приведен в примере 7.2. 

7.7 Контрольные вопросы к разделу

1. Поясните понятие терминальных символов грамматики.

2. Чем терминальные символы отличаются от нетерминальных?

3. Чем отличаются КС–грамматики от грамматик непосредственно составляю-

щих?

4. Какой класс грамматик является более широким: грамматики типа 0 или грам-

матики типа 2?

5. Как построить грамматику для итерации языка, заданного КС–грамматикой?

6. Как построить грамматику для объединения языков, заданных КС–граммати-

ками?

7. Замкнуто ли множество КС–языков относительно операции пересечения?

8. Можно ли для произвольной КС–грамматики построить эквивалентную неуко-

рачивающую? Если можно, то как это сделать?

9. Как в заданной КС–грамматике избавиться от правил с одинаковыми правыми

частями?

10. Чем характеризуется восходящая стратегия разбора?

11. Приведите пример КС–грамматики, для которой возникают затруднения при

нисходящем грамматическом разборе.

210