Языки и трансляции. Мартыненко Б.К. - 49 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

48
Существование алгоритма для определения, порождает ли данная КС-грам-
матика пустой язык, является важным фактом. Мы будем использовать его при
упрощении КС-грамматик.
Как увидим в дальнейшем, никакого такого алгоритма для более сложных
грамматик, например, для контекстно-зависимых, не существует.
Теорема 4.2. Для любой контекстно-свободной грамматики G = (V
N
,V
T
,P,S),
порождающей непустой язык, можно найти эквивалентную контекстно-
свободную
грамматику G
1
,
в которой для любого нетерминала A существует
терминальная цепочка x, такая, что A
x.
Доказательство. Для каждого нетерминала A∈V
N
рассмотрим грамма-
тику G
A
=(V
N
, V
T
, P, A). Если язык L(G
A
) пуст, то мы удалим A из алфавита V
N
,
а также все правила, использующие
A в правой или левой части правила.
После удаления из
G всех таких нетерминалов мы получим новую грамматику
G
1
=(V
N
1
, V
T
, P
1
, S), где V
N
1
и P
1
— оставшиеся нетерминалы и правила. Ясно, что
L(G
1
) ⊆ L(G), поскольку вывод в G
1
есть также вывод в G.
Предположим, что существует терминальная цепочка x∈L(G), но x∉L(G
1
).
Тогда вывод S
x должен включать сентенциальную цепочку вида α
1
Aα
2
, где
A∈V
N
\ V
N
1
, т.е. S
α
1
Aα
2
x. Однако тогда должна существовать некоторая
терминальная цепочка x
1
, такая, что A
x
1
, — факт, противоречащий пред-
положению о том, что A∈V
N
\ V
N
1
.
Что и требовалось доказать.
Определение 4.1. Нетерминалы из V
N
1
принято называть продуктивными.
В дополнение к исключению нетерминалов, из которых невозможно
вывести ни одной терминальной цепочки, мы можем также исключать
нетерминалы, которые не участвуют ни в каком выводе.
Теорема 4.3. Для любой данной контекстно-свободной грамматики,
порождающей непустой язык L, можно найти контекстно-свободную
грамматику, порождающую язык L, такую, что для каждого её нетерминала
A существует вывод вида S x
1
Ax
3
x
1
x
2
x
3
, где x
1
,x
2
,x
3
∈V
T
*
.
Доказательство. Пусть G
1
= (V
N
, V
T
, P, S) — произвольная cfg, удовлет-
воряющая условиям теоремы 4.2. Если S
α
1
Aα
2
, где α
1
,α
2
∈V
*
, то существует
вывод S
α
1
Aα
2
x
1
Ax
3
x
1
x
2
x
3
, поскольку терминальные цепочки могут быть
выведены из A и из всех нетерминалов, появляющихся в α
1
и α
2
. Мы можем
эффективно построить множество V
N
’
всех нетерминалов A, таких, что будет
существовать вывод S
α
1
Aα
2
, следующим образом.
Для начала поместим S в искомое множество. Затем последовательно будем
добавлять к этому множеству любой нетерминал, который появляется в правой
части любого правила из P, определяющего нетерминал, уже имеющийся в
этом множестве. Процесс завершается, когда никакие новые элементы не могут
быть добавлены к упомянутому множеству.
Положим G
2
= (V
N
’
,V
T
, P
′
, S), где P
′
— множество правил, оставшихся после
исключения всех правил из P, которые используют символы из V
N
\ V
N
’
слева
или справа. G
2
— требуемая грамматика.
1
*
G
⇒
*
⇒
1
*
G
⇒
1
*
G
⇒
1
*
G
⇒
*
⇒
1
*
G
⇒
1
*
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒

Страницы