/p>
Правила виводу мають наступний вигляд:
S -> C1 C2 C3 A; S -> C1 C4 C5 B; S -> C6 C; S -> C7 F; A -> C8 D; A -> ; C9; B -> C8 E; B -> C9; C -> C8 E; C -> C9; D -> C10 S; D -> C11; E -> C10 S; E -> C11; F -> C12 C13 C14 C15; F -> C16 C13 C14 C15; F -> C17 C18 C15.
2. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ. ПОБУДОВА ПРАВОЛІНЕЙНОЙ ГРАМАТИКИ
Індивідуальним завданням є граматика G ', породжувана із заданої формальної граматики G.
Граматика G приводиться до вигляду
G '=
Де V't = {x0, x1, ..., x7} - новий термінальний словник, одержуваний з Vt заміною ci на xi у відповідності з таблицею 1.
Таблиця 1
'- безліч правил виводу, одержуваних з безлічі R, шляхом заміни символів алфавіту Vt символами алфавіту V't, згідно з таблицею 1. Таблиця 1 заповнюється наступним чином: у другий рядок таблиці 1 заносяться ім'я прізвище та по батькові, з обов'язковими пробілами між ними.
Третій рядок таблиці 1 заповнюється відповідно до таблиці 2.
Таблиця 2
В результаті, безліч правил виводу праволінейной граматики G 'має вигляд:
1) S -> x5 x0 x4 A, 2) S -> x5 x5 x4 B; 3) S -> x3 C; 4) S -> x1 F; 5) A -> x7 D; 6) A -> x4; 7) B -> x7 E; 8) B -> x4; 9) C -> x7 E; 10) C -> x4; 11 ) D -> x2 S; 12) D -> x5; 13) E -> x2 S; 14) E -> x5; 15) F -> x6 x2 x4 x6; 16) F -> x7 x2 x4 x6; 17) F -> x3 x0 x6;
Побудуємо граф граматики G '(рис. 1).
Граф граматики G
В
Рис. 1
3. ПОБУДОВА автоматні ГРАМАТИКИ ПО ПРАВОЛІНЕЙНОЙ
Процедура переведення праволінейной граматики в автоматну.
Праволінейная граматика:
1) S -> x5 x0 x4 A, 2) S -> x5 x5 x4 B; 3) S -> x3 C; 4) S -> x1 F; 5) A -> x7 D; 6) A -> x4; 7) B -> x7 E; 8) B -> x4; 9) C -> x7 E; 10) C -> x4; 11 ) D -> x2 S; 12) D -> x5; 13) E -> x2 S; 14) E -> x5; 15) F -> x6 x2 x4 x6; 16) F -> x7 x2 x4 x6; 17) F -> x3 x0 x6;
Для отримання автоматної граматики, необхідно замінити правила, у яких у правій частині перед нетермінальним символом коштує більше ніж один термінальний, декількома правилами.
В результаті заміни правил, були отримані наступні правила
1.1) S -> x5 S1;
.2) S1 -> x0 S2;
1.3) S2 -> x4 A;
.1) S -> x5 S3;
.2)
