 |
|
Исключение левой рекурсии
Формулировка задания
Исключить левую рекурсию из КС-грамматики G = <T, N, S, R>.
Задание.
2.2.4.6 
Решение:
1. I=1;
Заменим выражения стоящие слева от фигурной скобки на выражения, написанные справа от фигурной скобки
2. i=2
Повторим предыдущий шаг для i=2;
T 
T 
3. i=3;
Преобразования не требуются.
Новая грамматика, эквивалентная исходной:
,где
Исключение левой рекурсии
Исключить левую рекурсию из КС-грамматики G = < T, N, S, R >.
2.2.4.1. T = { a, b, с }, N = { S, A }, R = { S ® SaA, S ® AA, S ® b, A ® ASa, A ® Ab, A ® c };
1. i=1
S ® SaA; S ® AA, S ® b
после замены S ® AA, S ® b, S ® AAS’, S ® bS’, S’ ® aA, S’ ® aA S’
2. i=2, j=1
правил вида A2®A1a нет.
j=i-1
3. j=1, i=2
A ® ASa, A ® Ab, A ® c
После замены A ® c, A ® cА’, A’ ® Sa, A’ ® b,
A’ ® SaA’, A’ ® bA’
R’={ S ® AA, S ® b, S ® AAS’, S ® bS’, S’ ® aA, S’ ® aA S’, A ® c, A ® cА’, A’ ® Sa, A’ ® b,
A’ ® SaA’, A’ ® bA },
N’={S,A,S’A’}
Грамматика без левой рекурсии -
G’={T,N’,S,R’}
Исключение левой рекурсии
Исключить левую рекурсию из КС-грамматики G = < T, N, S, R >.
2.2.4.1. T = { a, b, с }, N = { S, A }, R = { S ® SaA, S ® AA, S ® b, A ® ASa, A ® Ab, A ® c };
i=1
S ® SaA; S ® AA, S ® b
после замены S ® AA, S ® b, S ® AAS’, S ® bS’, S’ ® aA, S’ ® aA S’
i=2, j=1
правил вида A2®A1a нет.
j=i-1
j=1, i=2
A ® ASa, A ® Ab, A ® c
После замены A ® c, A ® cА’, A’ ® Sa, A’ ® b,
A’ ® SaA’, A’ ® bA’
R’={ S ® AA, S ® b, S ® AAS’, S ® bS’, S’ ® aA, S’ ® aA S’, A ® c, A ® cА’, A’ ® Sa, A’ ® b,
A’ ® SaA’, A’ ® bA },
N’={S,A,S’A’}
Грамматика без левой рекурсии -
G’={T,N’,S,R’}
Построение детерминированного конечного автомата по автоматной грамматике
Формулировка задания
Построить детерминированный конечный автомат по автоматной грамматике G = < T, N, S, R >. Определить язык, допускаемый конечным автоматом.
Задание.
3.2.1.3. 
Решение:
Исключим e - правила из грамматики.
Запишем грамматику недетерминированного конечного автомата:
K = ({S, A, B, C, D, E}, {0, 1}, 
, S, {E}), где функции переходов:
Преобразуем недетерминированный конечный автомат в детерминированный:
| d | ||
| P0 {S} | 
| P1 {A} |
| P1 {A} | P0 {S} | P2 {B} |
| P2 {B} | P3 {C, E} |
|
| P3 {C, E} | P3 {C, E} | P4 {D, E} |
| P4 {D, E} | P4 {D, E} |
|
K’ = ({P0, P1, P2, P3, P4}, {1,0}, 
’, P0, {P3, P4})
Граф переходов полученного детерминированного автомата
| P1 |
| P2 |
| P3 |
| P0 |
| P4 |
Функции переходов
(P0, 1) = P1
(P1, 0) = P0
(P1, 1) = P2
(P2, 0) = P3
(P3, 0) = P3
(P3, 1) = P4
(P4, 0) = P4