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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
Другими словами,
T
m
содержит сентенциальные формы, выводимые не
более, чем за
m шагов, и не длиннее, чем n символов. Очевидно, что T
0
={S} и
T
m
= T
m–1
∪ {α | β⇒α, β∈ T
m–1
, |α|≤n}, т. е. T
m
есть результат пополнения
множества
T
m–1
цепочками, выводимыми из его цепочек за один шаг, длина
которых не превосходит
n.
Если
S α и |α|≤n, то α∈ T
m
при некотором m.
Если вывод
S α не существует или | α | > n, то α∉T
m
ни при каком m.
Также очевидно, что T
m–1
⊆ T
m
для всех m ≥ 1. Поскольку T
m
зависит только
от
T
m–1
, то T
m
= T
m +1
= T
m +2
= ... , если окажется на некотором шаге вычислений
членов этой последовательности T
m
= T
m–1
.
Наш алгоритм будет вычислять
T
1
, T
2
, T
3
, ... до тех пор, пока для некото-
рого
m не окажется T
m
= T
m–1
. Если цепочки x нет во множестве T
m
, то её нет и в
L(G), потому что T
j
= T
m
для j > m. Конечно, если x ∈T
m
, то S x.
Осталось доказать, что для некоторого
m непременно будет T
m
= T
m–1
.
Вспомним, что
T
i
⊇T
i–1
для каждого i ≥ 1. При T
i
≠ T
i–1
число элементов во
множестве
T
i
, по крайней мере, на 1 больше, чем во множестве T
i–1
.
Если алфавит
V имеет k символов, то число строк длины n или меньше во
множестве
V
+
равно k + k
2
+ k
3
+ ... + k
n
≤ (k + 1)
n
. И это единственно возмож-
ные строки, которые могут быть в любом множестве
T
i
. Таким образом, при
некотором
m ≤ (k +1)
n
непременно случится T
m
= T
m –1
. Следовательно, процесс
вычисления множеств
T
i
(i >0) гарантированно закончится за конечное число
шагов, и он тем самым является алгоритмом.
Замечание 2.4. Нет нужды доказывать, что алгоритм, описанный в теореме 2.2,
применим также к контекстно-свободным и регулярным грамматикам.
Пример 2.6. Рассмотрим грамматику G из примера 2.2. С помощью
только что описанного алгоритма проверим:
abac ∈ L(G)?
T
0
= {S}, T
1
= {S, aSBC, aBC}, T
2
= {S, aSBC, aBC, abC},
T
3
= {S, aSBC, aBC, abC, abc}, T
4
= T
3
.
Поскольку
abac∉T
3
, то abac∉L(G).
§ 2.6. Деревья вывода
в контекстно-свободных грамматиках
Рассмотрим теперь наглядный метод описания любого вывода в контек-
стно-свободной грамматике. Фактически мы его уже могли наблюдать в §2.1.
Определение 2.10. Пусть G =(V
N
, V
T
, P, S) — контекстно-свободная грам-
матика. Дерево есть
дерево вывода для G, если оно удовлетворяет следующим
четырем условиям:
1) каждый узел имеет метку — символ из алфавита V;
2) метка корня —
S;
3) если узел имеет по крайней мере одного потомка, то его метка должна
быть нетерминалом;
4) если узлы
n
1
, n
2
, ... , n
k
— прямые потомки узла n, перечисленные слева
направо, с метками
A
1
, A
2
, ... , A
k
соответственно, а метка узла n есть A, то
A → A
1
A
2
... A
k
∈P.
Пример 2.7. Рассмотрим КС-грамматику G = ({S, A}, {a, b}, P, S), где
P = {S → aAS, S → a, A → SbA, A → ba, A → SS}.
*
⇒
*
⇒
*
⇒

Страницы