Составители:
47
Если в полученном дереве имеется путь с двумя узлами, помеченными
одним и тем же нетерминалом, процесс может быть повторен с деревом вывода
S x
3
x
2
x
4
. Фактически процесс может повторяться до тех пор, пока в очередном
дереве имеется путь, в котором находятся два узла, помеченных одинаково.
Рис. 4.1.
Поскольку каждая итерация исключает один узел или более, а дерево
конечно, то процесс в конце концов закончится. Если в грамматике G имеется
m нетерминалов, то в полученном дереве все ветви будут иметь длину
(подразумевается, что длина ветви измеряется числом дуг, её составляющих)
не больше m, ибо в противном случае на длинной ветви неминуемо
встретились бы два узла с идентичными метками.
Итак, если грамматика G порождает какую-нибудь терминальную цепочку
вообще, то существует другой вывод терминальной цепочки, дерево которого
не содержит ни одной ветви длиннее m.
Алгоритм, определяющий, является ли язык L(G) пустым, можно организо-
вать следующим
образом.
Сначала надо построить коллекцию деревьев, представляющих выводы в
грамматике
G:
Шаг 1. Начать коллекцию с единственного дерева, представленного только
корнем — узлом с меткой S.
Шаг 2. Добавить к коллекции любое дерево, которое может быть получено
из дерева, уже имеющегося в коллекции, посредством применения единствен-
ного правила, если образующееся дерево не имеет ни одной ветви длиннее m, и
если такого ещё нет в коллекции. Поскольку число таких деревьев конечно, то
процесс в конце концов закончится.
Шаг 3.
Теперь язык L(G) непуст, если в построенной коллекции есть хотя
бы одно
дерево, представляющее вывод терминальной цепочки. Иначе язык L(G)
пуст.
Требуемый алгоритм построен.
а
б
G = ({S, A, B}, {a, b},
P = {S → Aa, A → aB, B → Aa, B → b}, S)
x
1
= aaba; x
2
= ab.
n
1
n
2
b
a
B
A a
a
B
S
A
a
n
1
b
a
B
S
A
a
n
2
*
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 46
- 47
- 48
- 49
- 50
- …
- следующая ›
- последняя »
