Синтез распознающего автомата
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
збиваем по входу x1:2={{A, B, C}, {F8,F5,F2,S }, { C, F4, F7, B, A },{ Y, S2, F1, F4},{Z}}
.4 Разбиваем по входу x7:3={A, B, C}, {F8,F5,F2,S }, {C, F4, F7, B, A}, {F1}, {Y, S2},{Z}}
.5 Разбиваем по входу x6:4={{A, B, C}, {F8,F5,F2,S}, { C, F4, F7, B, A }, {S2}, {E}, {F1}, {Y },{Z}}
.6 Разбиваем по входу x4:5={{A, B, C}, {F8,F5,F2,S}, { C, F4, F7, B, A },{S2}, {E}, {S4},{D}, {F1}, {F4}, {Y},{Z}}
.7 Разбиваем по входу x5:6={{A, B, C}, {F8,F5,F2,S}, { C, F4, F7, B, A },{S2}, {E}, {S4},{D}, {F1}, {F3},{F6} {Y},{Z}}
Дальнейшее разбиение невозможно. Перейдем к новым обозначениям:
{S} A
{A, B, C} B
{D, E} C
{S1, S3} D
{S2} E
{S4} F
{F} G
{F1, F4} H
{F2, F5} I
{F3, F6, F8} J
{F7} K
{Z} L
Таблица 6.1
x1x 2x 3x 4x 5x 6x 7AGBRRDRR0BRLRRRCR0CRRRARLR0DEFRRRRR0ERRBRRRR0FRRRRRBR0GHRRRRKH0HRRIRRRR0IJRRRRRRR0JRRRRLRR0KRRRRRRJ0LRRRRRRR1
Граф переходов минимального автомата приведен на рис.3.
Рис. 3 Граф переходов минимального автомата
. ПОСТРОЕНИЕ СЕТИ ПЕТРИ
Для полученной в п.2 праволинейной грамматики построим сеть Петри. Это можно сделать, поставив в соответствие нетерминальным символам грамматики позиции сети Петри, а терминалам - переходы сети Петри. Будем помечать позиции и переходы соответствующими нетерминалами и терминалами. Если в правой части имеет место конкатенация терминалов (т.е. цепочка терминалов), то в сети Петри между переходами, помеченными терминалами, должны появиться дополнительные позиции, которые будут помечены символами левой части правила подстановки с верхними индексами 1,2…
При построении остальных фрагментов соответствующих последующим правилам подстановки, следует использовать ранее обозначенные позиции, но не переходы. Таким образом, позиции могут иметь несколько входящих и исходящих дуг, а переходы могут иметь в точности по одной входящей и не более чем по одной исходящей дуге. Исходящая дуга может отсутствовать, если в правой части правила подстановки отсутствует замыкающий нетерминал. Маркером или фишкой отмечается позиция, соответствующая начальному символу грамматики. Построим сеть Петри (рис.4)
Рис. 4 Сети Петри
Полученная сеть представляет собой автоматную сеть Петри. Позиции можно трактовать как состояния конечного автомата, а переходы - как входные символы. Для полноты соответствия сети Петри распознающему автомату введена заключительная позиция Z, в которую направлены дуги из всех переходов, ранее не имевших исходящих дуг.
Можно заметить, что в этой сети имеются идентичные фрагменты, которые можно склеить. Склеивая фрагменты с позициями S1, S3 по входному переходу X5, устраняем недетерминированность сети. Это позволит произвести еще ряд склеек. Позиции A, B и C склеиваются по выходным переходам X5 и X1, позиции D, E - по входному переходу x5 и по выходному переходу X6. Функционирование сети не изменится, если склеить идентичные фрагменты: F3,F6 и F8; F2 и F5; F1 и F4. Этот этап соответствует минимизации числа состояний автомата. Получим эквивалентную детерминированную сеть следующего вида (см. рис.5):
Рис. 5 Эквивалентная детерминированная сеть Петри
По полученной сети построим граф.
Введем следующие обозначения:
{S} A
{A, B, C} B
{D, E} C
{S1, S3} D
{S2} E
{S4} F
{F} G
{F1, F4} H
{F2, F5} I
{F3, F6, F8} J
{F7} K
{Z} L
Граф приведен на рис.6.
Рис.6 Граф полученной сети
Сравнив два графа (рис.3 и рис.6), можно увидеть, что они в точности совпадают.
8.ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ
.1 Вводная часть
Для проверки правильности построенного конечного распознавателя, написана программа. Программа реализует работу распознающего автомата и производит распознавание вводимых с клавиатуры цепочек. Программа написана на языке TURBO PASCAL. Для проверки работоспособности необходимо откомпилировать файл automat.pas, далее запустить файл automat.exe.
.2 Функциональное назначение
Программа имитирует работу конечного автомата. Программа применяется для распознавания входных цепочек символов право-линейной грамматики.
Для функционирования программы необходима любая ЭВМ, имеющая
транслятор языка Паскаль.
Для работы программы требуются следующие устройства:
- дисплей;
- клавиатура.
- Для работы программы необходимо:
- объем свободной оперативной памяти не менее 10 Kb;
При сбоях в работе устройств, программа прекращает свою работу.
Программа не предусматривает возможности продолжения работы с определенного этапа.
8.3 Описание информации
В качестве входной информации выступают строки, вводимые с клавиатуры, состоящие из символов исходной грамматики и являющиеся строкой для распознавания. Информация о допустимости цепочек выводится на дисплей. Входные данные имеют формат: хАхВхС , где А, В, С - числа от 1 до 7.
Перечень сообщений, используемых в работе программы, представлен в таблице 6.
Таблица 6. Сообщения программы
СообщениеОписаниеВведите цепочку:Приглашение к вводу цепочки. Цепочка не допускаетсяВыводится, если введенная цепочка является недопустимойЦепочка допускаетсяВыводится, если введенная цепочка является допустимой
.4 Описание логики
Логику написанной программы иллюстрирует схема программы, представленная на рис. 7
Рис. 7 Схема программы automat.pas
9. ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА
.1 Назначение
Контрольный пример предназначен для тестирования программы automat.pas, реализующей конечный автомат.
.2 Исходные данные