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

UptoLike

ВУЗ: 

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

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

Рубрика: 

63
Из построения грамматики G
2
очевидно, что она моделирует все
левосторонние выводы в грамматике G
1
, так что L(G
2
)=L(G
1
).
Действительно, индукцией по длине вывода легко показать, что S xα
посредством левостороннего вывода тогда и только тогда, когда [S]
x[α].
Здесь x∈V
T
+
— закрытая, а α∈V
N
1
*
— открытая часть данной сентенциальной
формы.
I. Докажем сначала, что если S
xα, то [S]
x[α].
База. Пусть l = 1. Имеем S
xα, S → xα∈P
1
, x∈V
T
, α∈V
N
1
*
. Следователь-
но, существует правило [S] → x[α] ∈P
2
и потому [S]
x[α].
Индукционная гипотеза. Предположим, что аналогичное утверждение
имеет место при всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем утверждение при l ≤ n +1.
Пусть S
x
’ Aβ
x’bα’β = xα, т. е. x = x’b, α = α’β. По индукционной гипо-
тезе из существования вывода S
x
’Aβ следует, что [S]
x’[Aβ], а поскольку
на последнем шаге вывода использовано правило A → bα
’∈P
1
, то существует
правило [Aβ] → b[α
’β] ∈P
2
, с помощью которого можно завершить имеющийся
вывод [S]
x
’ [Aβ]
x’b[α’β] = x[α].
II. Докажем теперь, что если [S]
x[α], то S
xα.
База. Пусть l =1. Имеем [S]
x[α]. Существует правило [S] → x[α] ∈P
2
,
x∈V
T
, α∈V
N
1
*
, которое обусловлено существованием правила S → xα∈P
1
, и
потому S
xα.
Индукционная гипотеза. Предположим, что аналогичное утверждение
имеет место при всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем утверждение при l ≤ n + 1.
Пусть [S]
x
’[Aβ] x’b[α] = x[α], где x =x’b, α∈V
N
2
*
. По индукционной
гипотезе из существования вывода [S]
x
’[Aβ] следует, что S
x’Aβ. На
последнем шаге вывода в G
2
использовано правило [Aβ] → b[α] ∈P
2
,
существование которого обусловлено существованием правила A → bα
’∈P
1
при α
’∈V
N
1
*
, где α = α’β, которое можно использовать для завершения
имеющегося вывода: S
x
’Aβ
x’bα’β = xα.
Из рассуждений I и II при α = ε получаем L(G
1
) = L(G
2
). Таким образом,
язык L(G) — регулярен.
Что и требовалось доказать.
§ 4.6. ε-Правила
в контекстно-свободных грамматиках
Ранее мы показали, что на правила можно накладывать некоторые
ограничения, не сужая класс языков, которые могут порождаться. Теперь мы
рассмотрим расширения КС-грамматик, которые разрешают использовать
правила вида A →ε для любого нетерминала. Такое правило называется ε-
правилом или ε-порождением. Многие описания синтаксиса языков
программирования допускают такие порождения. Мы покажем, что язык,
порождаемый КС-грамматикой с ε-правилами, всегда КС-язык.
2
*
G
⇒
1
*
G
⇒
1
G
l
⇒
2
*
G
⇒
1
G
⇒
2
G
⇒
1
G
⇒
1
G
n
⇒
1
G
n
⇒
2
*
G
⇒
2
*
G
⇒
2
G
⇒
2
G
l
⇒
1
*
G
⇒
2
G
⇒
1
G
⇒
2
G
n
⇒
2
G
⇒
2
G
n
⇒
1
*
G
⇒
1
*
G
⇒
1
G
⇒

Страницы