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

UptoLike

ВУЗ: 

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

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

Рубрика: 

67
I-4.4. По cfg в НФХ, построенной в упр. I-4.3, построить эквивалентную cfg
в НФГ.
I-4.5. Построить алгоритм исключения недостижимых нетерминалов из cfg.
Применить его к грамматике G = (V
N
, V
T
, P, S), где V
N
= {S, A, B, C, D};
V
T
= {a, b, d};
P
=
{
(
1
)
S → AB
,
(
2
)
S → B
C
,
(
3
)
A → B
,
(
4
)
A → aA
,
(
5
)
B
→ Ab
,
(
6
)
B
→ b
,
(
7
)
D → d
,
(
8
)
D → dAD
}
.
I-4.6. Построить алгоритм исключения из cfg непродуктивных нетер-
миналов. Применить его к грамматике, полученной в предыдущей задаче:
G = ({S, A, B, C}, {a, b}, P, S), где
P = {(1) S → AB, (2) S → BC, (3) A → B, (4) A → aA, (5) B → Ab, (6) B → b}.
I-4.7. Описать метод построения регулярного выражения, эквивалентного
контекстно-свободной грамматике без самовставлений, аналогичный методу
Гаусса для решения систем линейных алгебраических уравнений. Применить его
к cfg, построенной в упражнении I-2.4.
Пояснение. Множество правил данной cfg, представленных в форме Бэкуса-Наура, считать
аналогом алгебраической системы, в которой роль
неизвестных играют нетерминалы из множества , а в роли коэффициентов
терминальные цепочки над алфавитом
T
.V Символ ‘+’ разделяет альтернативы X
i
-порождений.
Решение такой системы есть множество регулярных выражений, представляющих
регулярные языки, порождаемых соответствующими нетерминалами, в качестве найденных
значений неизвестных.
См. [6, Гл. 2] и [14, Гл. 5].
I-4.8. Дана контекстно-свободная грамматика с m нетерминалами, правые
части правил которой не длиннее l. Найдите верхнюю границу для числа
деревьев вывода, ветви которых не длиннее, чем m + 1.
I-4.9. Рассмотрим грамматику G = ({A, B, C}, {0, 1}, P, A), где
P = { A → 0A1, A → 0AC, A → 1B0, A → 0, B → 1C0, B → AC, C → 1CB, C → AB}.
Найти эквивалентную грамматику G
1
такую, что если D нетерминал
грамматики G
1
, то существует правило вида D → w , где w некоторая терми-
нальная строка.
I-4.10. Если G cfg в нормальной форме Хомского, w∈L(G) и существует
вывод w в p шагов, то какой длины w?
I-4.11. Показать, как привести правила грамматики в нормальной форме
Хомского к форме A → AB, где A ≠ B, а если A → α
1
Bα
2
и
A → γ
1
Bγ
2
правила, то α
1
=
γ
1
и α
2
=
γ
2
.
I-4.12. Рассмотрим грамматику G = ({S}, {p, [, ], ~, ⊃}, P, A), где
P ={ S → p, S → ~S, S → [S ⊃ S] }.
Опишите язык L(G) неформально. Найдите грамматику в нормальной
форме Хомского для этого языка. Перенумеруйте нетерминалы как, чтобы S
011 22
1
{ = + + + ... + }
n
in
ii i n
i
i
Xa aX aX aX
=
1
{}
n
ii
VX
=
=

Страницы