) 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 -> x3x0x6;
Побудуємо граф грамматікі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 -> x0S2;
1.3) S2 -> x4A;
.1) S -> x5S3;
.2) S3 -> x5S4;
.3) S4 -> x4B;
.1) A -> x4 A1;
.2) A1 ->;
.1) B -> x4 B1;
.2) B1 ->;
.1) C -> x4C1;
.2) C1 ->;
12.1) D -> x2D1;
.2) D1 ->;
.1) E -> x2E1;
14.2) E1 ->;
15.1) F -> x6 F1;
15.2) F1 -> x2F2;
15.3) F2 -> x4 F3;
15.4) F3 -> x6 F4;
15.5) F4 -> ? ;
16.1) F -> x7 F5;
16.2) F5 -> x2F5;
16.3) F6 -> x4 F6;
16.4) F7 -> x6F8;
