Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

151

Рисунок 9.7 – Пример формы для автомата-распознавателя

Рисунок 9.8 – Пример формы для автомата Мили

Для конечного автомата с магазинной памятью доступ-

ны:

 вкладка для ввода и редактирования грамматики;

 таблица-магазин;

 поля для вывода выходного алфавита автомата;

 поле для выбора способа разбора автомата.

Для задания входной цепочки внизу

формы есть лента.

Красная стрелка указывает на ячейку под головкой автомата.

Для того, чтобы задать символ в ячейке необходимо нажать

на ячейку (она выделится красным цветом) или перейти на

неё с помощью клавиш-стрелок, после этого нажать на кла-

вишу соответствующую символу, который необходимо запи-

152

сать в ячейку ленты. Также на ленте внизу формы есть кноп-

ки для сдвига ленты вправо (кнопка «>») и влево (кнопка

«<»). Ими можно пользоваться и при пошаговой интерпрета-

ции автомата.

9.3 Детерминизация и минимизация автоматов-

распознавателей

При работе с автоматами-распознавателями необходи-

мо задать его командами, таблицей или матрицей переходов

(рисунки 9.9, 9.10).

Рисунок 9.9 – Таблица переходов распознавателя

153

Рисунок 9.10 – Матрица переходов распознавателя

При минимизации распознавателя состояния группи-

руются по классам эквивалентности и состояния, входящие в

один класс, выделяются одинаковым цветом. Используется

при минимизации (рисунок 9.11).

Рисунок 9.11 – Пошаговая минимизация распознавателя

При детерминизации автомата-распознавателя работа

154

осуществляется с таблицей переходов. Пример работы про-

граммы при пошаговой детерминизации автомата-

распознавателя приведен на рисунке 9.12.

9.4 Синтез и интерпретация МП-автоматов

При создании МП-автомата отображаются следующие

элементы:

− кнопка на панели инструментов «Построить»;

− кнопка на панели инструментов «Интерпретировать с

получением результата сразу»;

− кнопка на панели инструментов «Интерпретировать

пошагово»;

− входная лента автомата;

− вкладка «Грамматика» (она по умолчанию является ак-

тивной);

Рисунок 9.12 – Пошаговая детерминизация распознавателя

− вкладка «Команды» (недоступна для редактирования);

− список состояний автомата (первоначально пустой);

155

− магазин МП-автомата (первоначально пустой);

− выпадающий список для выбора типа анализа МП-

автомата;

− поле для просмотра наименования начального состоя-

ния;

− поле для просмотра символов алфавита ленты МП-

автомата;

− поле для просмотра символов алфавита магазина;

− таблица для вывода синтаксических ошибок, допущен-

ных пользователем при вводе правил

грамматики.

Внешний вид формы представлен на рисунке 9.13.

Чтобы создать МП-автомат, распознающий какой-

либо язык, необходимо задать правила грамматики, порож-

дающей этот язык. Для этого эти правила нужно ввести в по-

ле на вкладе «Грамматика». При нажатии на кнопку «По-

строить» на панели инструментов происходит следующее.

Анализируется тип автомата, анализируются

правила, стро-

ятся команды, алфавиты, список состояний МП-автомата.

Если при анализе были обнаружены ошибки, они выводятся

в список ошибок.

156

Рисунок 9.13 – Форма для создания описания автомата с

магазинной памятью

Если при анализе правил не было обнаружено синтак-

сических ошибок, активной становится вкладка «Команды».

Внешний вид формы, представляющей описание построен-

ного автомата, приведен на рисунке 9.14.

Для того, чтобы осуществить интерпретацию МП-

автомата, необходимо создать его описание или открыть его

помощью команды главного меню «Файл» – «Открыть» –

«Автомат с магазинной памятью». Для запуска процесса ин-

терпретации на панели инструментов на форме имеются

кнопки «Интерпретировать с получением результата сразу» и

«Интерпретировать пошагово». Пошаговая интерпретация

позволяет более наглядно проследить работу автомата.

157

Рисунок 9.14 – Форма с описанием построенного МП-

автомата

При пошаговой интерпретации выполняемая команда

выделяется цветом, отображаются изменение положения го-

ловки ленты на данном шаге, а также изменения содержимо-

го магазина (рисунок 9.15). При интерпретации в обычном

режиме отображается только окончательные состояния ленты

и магазина.

Если ни одна из возможных последовательностей вы-

полнения команд не приведет к распознаванию заданной це-

почки, то об этом выводится сообщение (рисунок 9.16).

158

Рисунок 9.15 – Пошаговая интерпретация МП-автомата

Рисунок 9.16 – Сообщение о неудовлетворительном резуль-

тате разбора при пошаговой интерпретации МП-автомата

9.5 Структурный синтез автоматов

Дл

необхо

синтез»

пуска.

Ст

На пер

ровани

ний ав

синтеза

Рисун

турног

Для тог

гов нео

ку «<<

выполне

имо выбра

или нажа

уктурный

ом шаге с

входных,

омата. Пр

приведен

к 9.17 –

Пр

Для того

синтеза н

о чтобы ве

ходимо со

азад».

а втором

ия структ

ь пункт м

ь на кнопк

синтез авт

руктурног

ыходных

мер форм

а рисунке 9

имер форм

син

чтобы вып

обходимо

нуться на

тветствую

аге структ

рного син

ню «Опера

на

мата вып

синтеза ос

игналов и

первого

.17.

первого

еза

лнить сле

ажать на

акой-либо

ее число

рного син

еза автома

ии \\ Стру

анели быс

лняется п

уществляе

внутренни

шага стру

ага струк

ующий ш

нопку «Да

из предыд

аз нажать

еза осущес

а Мили

ктурный

рого за-

шагам.

ся коди-

состоя-

турного

урного

г струк-

ее >>».

щих ша-

а кноп-

твляется

160

получение кодированных матриц переходов и выходов, вы-

водится кодированная матрица выходов. Пример формы по-

лучения кодированной матрицы выходов представлен на ри-

сунке 9.18.

Рисунок 9.18 –Получение кодированной матрицы выходов

На этом же шаге на экран выводится кодированная

матрица переходов (рисунок 9.19).

На третьем шаге структурного синтеза формируется

матрица возбуждения и выводится на

экран. Пример формы

представлен на рисунке 9.20.