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

UptoLike

ВУЗ: 

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

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

Рубрика: 

26
Далее, те вершины, которые помечены
символами A
i
и для которых
существуют выводы вида A
i
α
m
при l
i
> 0, заменим деревьями вывода T
i
с
корнями, помеченными
A
i
, и результатами α
i
. То, что получится — см. рис. 2.4,
является деревом вывода
A α в грамматике G
A
. Утверждение II доказано.
Из I и II при
A = S следует утверждение теоремы.
Упражнения
I-2.1. Рассмотрим грамматику G = (V
N
, V
T
, P, S), где V
N
= {S, A, B}, V
T
= {0, 1},
P = { S → 0A, S → 1B, S → 0,
A → 0A, A → 0S, A → 1B,
B → 1B, B → 1, B → 0}.
Ясно, что
G — регулярная грамматика. Определить, какой язык порождает
данная грамматика?
I-2.2. Написать регулярную грамматику, порождающую язык
L = {w | w∈ {0, 1}
*
и w не содержит двух последовательных единиц}.
I-2.3. Неформально опишите слова, порождаемые грамматикой G из примера 2.7.
I-2.4. Используя алгоритм теоремы 2.2, определите, принадлежать ли
следующие слова
a)
abaa b) abbb c) baaba
языку, порождаемому грамматикой из примера 2.7.
I-2.5. Если G cfg, можно ли улучшить ограничение на m в теореме 2.2?
Такой же вопрос, если
G регулярная грамматика.
I-2.6. Рассмотрите грамматику G из примера 2.3. Нарисуйте деревья вывода
в
G следующих слов:
a)
ababab b) bbbaabaa c) aabbaabb.
I-2.7. Пусть G = (V
N
, V
T
, P, S), где V
N
= {A, B, S}, V
T
= {0, 1},
P = { S → 0AB, B → 01, 1B → 0, A1→ SB1, B→ SA, A0→ S0B}.
Докажите, что язык
L(G) пуст.
Рис. 2.4.
A
1
A
i
A
m
…
A
α
…
A
l
G
⇒
i
A
l
G
⇒

Страницы