Синтез распознающего автомата
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Введение
Проектирование распознающего автомата и его программная реализация необходимы при построении узлов цифровых вычислительных машин, при создании компиляторов, лингвистических процессоров и лексических анализаторов в трансляторах.
Цель курсовой работы состоит в изучении и использовании различных способов задания языков грамматиками. В курсовой работе необходимо использовать построение распознающего автомата и сети Петри для задания языков. Построить модель конечного автомата, распознающего заданный язык, реализовать полученный автомат программно.
Конечный автомат - это абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
1.Постановка задачи
Построить модель распознающего автомата на основе индивидуального задания.
Для этого необходимо на основе формальной грамматики получить праволинейную грамматику, построить ее граф. По праволинейной грамматики построить автоматную. Затем построить недетерминированный распознающий автомат, задать таблицу переходов для него и изобразить граф переходов. Перейти от недетерминированного к полностью определенному детерминированному автомату. Задать таблицу переходов и изобразить граф переходов для полученного автомата. Минимизировать этот автомат. Задать таблицу переходов и граф переходов для минимального автомата.
Получить граф переходов минимального автомата по праволинейной грамматике используя сети Петри. Сравнить полученную автоматную сеть с графом минимального автомата.
Входными данными для автомата является цепочка из терминальных символов. На выходе автомата появляется состояние, отвергающее или допускающее входную цепочку.
Задана формальная грамматика
G = , где
Vt = {C1, C2,…, C18} - терминальный словарь,
Vn = {S, A, B, C, D, E, F} - нетерминальный словарь,
S - начальный символ грамматики, SVn,
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 ->C17C18C15.
2. Индивидуальное задание. построение праволинейной грамматики
праволинейный грамматика автомат программа
Индивидуальным заданием является грамматика G, порождаемая из заданной формальной грамматики G.
Грамматика Gприводится к виду G=, гдеt={x0, x1, …, x7} - новый терминальный словарь, получаемый из Vt заменой ciна xiв соответствии с таблицей 1.
Таблица 1
cic1c2c3с4c5c6c7c8c9c10c11c12c13c14c15c16c17c18siПРОТОЗАНОВ_ЕВГЕНИЙxix5x0x4x5x4x3x1x7x4x2x5x6x2x4x6x7x3x0
R - множество правил вывода, получаемых из множества R, путем замены символов алфавита Vtсимволами алфавита Vt, в соответствии с таблицей 1. Таблица 1 заполняется следующим образом: во вторую строку таблицы 1 заносятся имя фамилия и отчество, с обязательными пробелами между ними.
Третья строка таблицы 1 заполняется в соответствии с таблицей 2.
Таблица 2
АБВГДЕЖЗИЙКЛМНОПx1х5x2x4x6x6x4x3x3x0x7x0x3x7x4x5PСТУФХЦЧШЩЬЫЭЮЯ_x0х4x5x7x2x5x1x2x2x0x6x1x1x3x7x5
В результате, множество правил вывода праволинейной грамматики G имеет вид:
1) S ->x5x0x4A; 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 ->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;
16.5)F8 ->;
17.1)F ->x3F9;
17.2)F9 ->x0F10;
17.3)F10 ->x6F11.
17.4)F11 ->;
Витогеполучаемследующуюавтоматную грамматику:
1.1)S -> x5 S1;
.2)S1 -> x0 S2;
.3)S2 -> x4 A
.1)S -> x5 S3
.2)S3 -> x5 S4
.3)S4 -> x4 B
) S -> x3 C;
) S -> x1 F;
) A -> x7 D;
.1)A -> x4 A1;
.2)A1 ->;
) B -> x7 E;
.1)B -> x4 B1;
.2)B1 ->;
) C -> x7 E;
.1)C -> x4 C1;
10.2)C1 -> ;
) D ->x2 S;
.1)D ->x2 D1;
.2)D1 -> ;
) E ->x2 S;
.1)E ->x2 E1;
.2)E1 -> ;
.1)F ->x6 F1;
.2)F1 ->x2 F2;
.3)F2 ->x4 F3;
.4) F3 ->x6 F4;
.5)F4 ->;
.1)F -> x7 F5;
.2)F5 -> x2 F5;
.3)F6 -> x4 F6;
.4)F7 -> x6 F8;
.5)F8 -> ;
.1)F -> x3 F9;
17.2)F9 -> x0 F10;
.3)F10 -> x6 F11;
.4)F11 -> ;
4. Построение недетерминированного конечного автомата
Процедуру построения недетерминированного автомата по автоматной грамматике:
1)Входным множеством автомата будет терминальное множество грамматики;
2)Множеством состояний автомата будет нетерминальное множество
грамматики, а в качестве начального состояния будет