 |
|
Исключение e-правил
Формулировка задания
Преобразовать исходную КС-грамматику G = <T, N, S, R> в эквивалентную НКС-грамматику.
Задание.
2.2.2.3 T = { a, b, c, d }, N = { S, A, B }, R = { S ®Aa, S ®bB, A ®cAdA, A ®a, A ®e, B ®cBdd, B ®e};
Решение:
1. Построим множество укорачивающих нетерминалов.
2. Преобразуем исходную КС-грамматику с e-правилами в эквивалентную НКС-грамматику.
Новая грамматика, эквивалентная исходной имеет следующий вид:
G’ = <T, N’, S’, R’ >
;
Исключение e-правил
Преобразовать исходную КС-грамматику G = < T, N, S, R > в эквивалентную НКС-грамматику:
2.2.2.1. T = { a, b }, N = { A, B, S }, R = { S ® AB, A ® SA, A ® BB, A ® bB, B ® b, B ® aA, B ® e};
Множество укорачивающих нетерминалов:
Nε ={B, A, S}
N0={B} из правила B ® e
N1={B,A} из правила A ® BB
N2={B,A,S} из правила S ® AB
Nε ={B, A, S}
Построение R’ = {
B ® b,
B ® aA,
B ® a, //AÎ Nε, исключаем правило A ® BB,
A ® bB,
A ® b, //BÎ Nε, исключаем правило B ® e
A ® SA,
A ® S, //SÎ Nε, исключаем правило S ® AB
S ® AB,
S ® A,
S ® B,
S’ ® S, //SÎ Nε ,добавляем правило S’ ® e
S’ ® e
}
Т.о.преобразованная грамматика -
G’ = < T, N, S’, R’ >
Исключение e-правил
Преобразовать исходную КС-грамматику G = < T, N, S, R > в эквивалентную НКС-грамматику:
2.2.2.1. T = { a, b }, N = { A, B, S }, R = { S ® AB, A ® SA, A ® BB, A ® bB, B ® b, B ® aA, B ® e};
Множество укорачивающих нетерминалов:
Nε ={B, A, S}
N0={B} из правила B ® e
N1={B,A} из правила A ® BB
N2={B,A,S} из правила S ® AB
Nε ={B, A, S}
Построение R’ = {
B ® b,
B ® aA,
B ® a, //AÎ Nε, исключаем правило A ® BB,
A ® bB,
A ® b, //BÎ Nε, исключаем правило B ® e
A ® SA,
A ® S, //SÎ Nε, исключаем правило S ® AB
S ® AB,
S ® A,
S ® B,
S’ ® S, //SÎ Nε ,добавляем правило S’ ® e
S’ ® e
}
Т.о.преобразованная грамматика -
G’ = < T, N, S’, R’ >
Исключение цепных правил
Определение. Правило вывода вида А à В называется цепным правилом.
Алгоритм 3.7.3. Исключение цепных правил.
Вход.НКС-грамматика G = (N, S, P, S).
Выход.Эквивалентная НКС-грамматика G¢ = (N, S, P¢, S) без цепных правил.