- •Синтез распознающего автомата
- •1.Индивидуальное задание.
- •2.Переход от праволинейной грамматики к автоматной.
- •3.Построение недетерминированного конечного автомата.
- •4.Переход от недетерминированного автомата к детерминированному
- •6.Использование сетей Петри при переходе от грамматики к минимальному Автомату.
Синтез распознающего автомата
Цель работы:
Изучение способов задания языков грамматиками, распознающими автоматами, сетями Петри и построение конечного автомата, распознающего заданный язык.
1.Индивидуальное задание.
Исходными данными являются Таблицы 1,2 (1-ая строка) и правила вывода P исходной грамматики.
Таблица №1
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
И |
Й |
К |
Л |
М |
Н |
О |
П |
х1 |
х5 |
х2 |
х4 |
х6 |
х6 |
х4 |
х3 |
х3 |
х0 |
х7 |
х0 |
х3 |
х7 |
х4 |
х5 |
Р |
С |
Т |
У |
Ф |
Х |
Ц |
Ч |
Ш |
Щ |
Ь |
Ы |
Э |
Ю |
Я |
_ |
х0 |
х4 |
х5 |
х7 |
х2 |
х5 |
х1 |
х2 |
х2 |
х0 |
х6 |
х1 |
х1 |
х3 |
х7 |
х5 |
Во 2-ую строку Таблицы 2 надо вписать свои фамилию, имя, отчество, а затем заполнить 3-ю строку, вписав в нее коды русских букв по Таблице 1.
Таблица №2
ci |
c1 |
c2 |
c3 |
c4 |
c5 |
c6 |
c7 |
c8 |
c9 |
c10 |
c11 |
c12 |
c13 |
c14 |
c15 |
c16 |
c17 |
c18 |
si |
Ш |
А |
Л |
А |
К |
И |
Н |
_ |
Н |
И |
К |
О |
Л |
А |
Й |
_ |
Н |
И |
xi |
х2 |
х1 |
х0 |
х1 |
х7 |
х3 |
х7 |
х5 |
х7 |
х3 |
х7 |
х4 |
х0 |
х1 |
х0 |
х5 |
х7 |
х3 |
R: S→ c1 c2 c3 A │c1 c4 c5 B │c6 C │c7 F;
A→ c8 D │c9;
B→ c8 E │c9;
C→ c8 E │c9;
D→ c10 S │c11;
E→ c10 S │c11;
F→ c12 c13 c14 c15 │c16 c13c14 c15│c17 c18 c15;
Продукции Р имеют вид универсальных соотношений, но после использования таблицы №2 грамматика становится индивидуальной. Запишем продукции Р в соответствии с таблицей №2 данного примера:
R: S→ x2 x1 x0 A │x2 x1 x7 B │x3 C │x7 F;
A→ x5 D │x7;
B→ x5 E │x7;
C→ x5 E │x7;
D→ x3 S │x7;
E→ x3 S │x7;
F→ x4 x0 x1 x0 │x5 x0x1 x0 │x7 x3 x0;
2.Переход от праволинейной грамматики к автоматной.
Переход от праволинейной грамматики к автоматной осуществляется за счет расширения нетерминального словаря. Запишем исходную грамматику в автоматном виде:
S→ х2 S1, S1→х1S2 , S2→х0 A;
S→ х2 S3, S3→х1S4 , S4→х7 B;
S→ х3 C; S→х7F;
A→ х5 D, A→х7;
B→ х5 E, B→х7;
C→ х5 E, C→х7;
D→ х3 S, D→х7 ;
E→ х3 S, E→х7 ;
F→ х4F1, F1→х0F2 , F2→х1F3, F3 → х0;
F→ х5F4 , F4→х0F5 , F5→х1F6, F6 → х0;
F→ х7F7 , F7→х3F8, F8 → х0;