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

UptoLike

ВУЗ: 

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

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

Рубрика: 

50
Теорема 4.4. Любой контекстно-свободный язык может быть порожден
контекстно-свободной грамматикой, не содержащей цепных правил, т.е.
правил вида A → B, где A и B — нетерминалы.
Доказательство. Пусть G =(V
N
, V
T
, P, S) — cfg и L = L(G). Мы построим
новое множество правил P
1
, прежде всего включив в него все нецепные правила
из P. Затем мы добавим в P
1
правила вида A →α при условии, что существует
вывод
вида A B, где A и B — нетерминалы, а B →α — нецепное правило из P.
Заметим, что мы легко можем проверить, существует ли вывод A B,
поскольку, если A B
1
B
2
... B
m
= B и некоторый нетерминал появляется
дважды в этом выводе, то мы можем найти более короткую последова-
тельность цепных правил, которая даёт результат A
B. Таким образом,
достаточно рассматривать только те цепные выводы, длина которых меньше,
чем число нетерминалов в V
N
.
Мы теперь имеем модифицированную грамматику G
1
= (V
N
, V
T
, P
1
, S).
I. Покажем, что L(G
1
) ⊆ L(G). Действительно, если A → α∈P
1
, то A
α.
Следовательно, если терминальная цепочка x выводится в G
1
, то она выводима
и в G.
II. Покажем теперь, что L(G) ⊆ L(G
1
).
Пусть
x∈L(G). Рассмотрим левосторонний вывод S = α
0
α
1
... α
n
= x.
Если α
i
α
i +1
для 0≤ i < n посредством нецепного правила, то α
i
α
i +1
.
Предположим, что α
i
α
i +1
посредством цепного правила, но что α
i –1
α
i
с
помощью нецепного правила при условии, конечно, что i ≠ 0.
Предположим также, что α
i +1
α
i +2
... α
j
все
посредством цепных пра-
вил, а α
j
α
j +1
при помощи нецепного правила. Тогда все α
i +1
,
α
i +2
, ... , α
j
одинаковой длины, и поскольку вывод — левосторонний, то нетерминал,
заменяемый в каждой из них, должен быть в одной и той же позиции. Но тогда
α
i
α
j +1
посредством одного из правил из P
1
\ P. Следовательно, x∈L(G
1
).
Из утверждений I и II следует L(G
1
) = L(G). Что и требовалось доказать.
§ 4.2. Нормальная
форма Хомского
Докажем первую из двух теорем о нормальных формах КС-грамматик.
Каждая из них утверждает, что все КС-грамматики эквивалентны грамматикам
с ограничениями на вид правил.
Теорема 4.5 — нормальная форма Хомского.
Любой КС-язык может быть порожден грамматикой, в которой все
правила имеют вид A
→ BC или A → a, где A, B, C — нетерминалы, a —
терминал.
Доказательство.
Пусть G = (V
N
, V
T
, P, S) — КС-грамматика и L = L(G),
причём в соответствии с теоремой 4.4 мы можем считать, что множество её
правил P не содержит ни одного цепного правила. Таким образом, если правая
часть правила состоит из одного символа, то этот символ — терминал, и это
правило уже находится в приемлемой форме.
*
G
⇒
G
⇒
1
G
⇒
G
⇒
1
G
⇒
G
⇒
G
⇒
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒

Страницы