Синтез распознавателей языков компьютерного моделирования объектов с конечным числом состояний

• Автор: Муромцев, Виктор Владимирович
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Белгород
• Количество страниц: 216 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧИ
1.1.Математическое моделирование как метод научных исследований
1.2 . Формальные языки систем моделирования
1.3.Формальные языки автоматических систем диагностирования
1. 4 .Проектирование распознавателей КС-языков
1.5.Задачи исследования
2.РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАСПОЗНАВАТЕЛЕЙ КС-ЯЗЫКОВ И МЕТОДА АВТОМАТИЧЕСКОГО СИНТЕЗА ДАННОЙ МОДЕЛИ
2.1.Задание КС-языков КС-диаграммерами
2.2.Введение понятия С-автомата. Задача синтеза С-автома-та
2.3.Введение правил преобразования диаграмм
2 . 3 .1 .Правила подстановки
2 . 3 .2 .Правила устранения рекурсии
2 . 3 . 3 .Правила устранения неоднозначности
2. 4. Синтез О-автоматов
2 . 5 .Выводы
3.ПРОГРАММНЫЙ КОМПЛЕКС СИНТЕЗА РАСПОЗНАВАТЕЛЕЙ КС-ЯЗЫКОВ
3.1.Алгоритм преобразования БНФ в КС-грамматику
3.2.Алгоритм преобразования КС-грамматики в КС-диаграм-мер
3.3.Алгоритм удаления из КС-диаграммера непродуктивных и недостижимых КС-диаграмм
3.4.Алгоритм удаления из КС-диаграммера избыточных и однотипных КС-диаграмм
3.5.Алгоритм синтеза О-автомата
3.6.Алгоритм преобразования символического описания Б-авто-мата в структуру хранения О-автомата в памяти ЭВМ
3.7. Выводы
4.ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ ПРИ МОДИФИКАЦИИ АВТОМАТИЧЕСКОЙ СИСТЕМЫ ДИАГНОСТИРОВАНИЯ
ЦИФРОВЫХ СХЕМ
4.1.Языки контроля и диагностирования. Язык описания тестовых воздействий
4.2.Синтез распознавателя языка описания тестовых воздействий по традиционной методике
4.3.Синтез распознавателя языка описания тестовых воздействий на основе О-автомата
4.4.Сравнение времени работы распознавателей КС-языков построенных по различным методикам
4.5. Выводы
5. ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ 1.1. ЯЗЫК ЗАДАНИЯ АЛГОРИТМОВ ФУНКЦИОНИРОВАНИЯ

ПРИЛОЖЕНИЕ 1.2. ТРАНСЛЯЦИЯ ЯЗЫКОВ, ИСПОЛЬЗУЕМЫХ В ППП
"31МОЬ-02" В ЯЗЫК УНБЬ
ПРИЛОЖЕНИЕ 2.1. МОДИФИКАЦИИ АЛГОРИТМА СВЕРТКИ КС-ПУТИ
В КС-ДИАГРАММЕ
ПРИЛОЖЕНИЕ 2.2. ПРИМЕРЫ СИНТЕЗА G-ABTOMATOB ДЛЯ ДЕТЕРМИНИРОВАННЫХ КС-ЯЗЫКОВ РАЗЛИЧНЫХ КЛАССОВ..168 ПРИЛОЖЕНИЕ 2.3. ПРОЯВЛЕНИЕ АЛГОРИТМИЧЕСКОЙ НЕРАЗРЕШИМОСТИ ПРОБЛЕМЫ ОПРЕДЕЛЕНИЯ ДЕТЕРМИНИРОВАННОСТИ ЯЗЫКА ЗАДАННОГО КС-ГРАММАТИ-
КОЙ В ПРОИЗВОЛЬНОЙ ФОРМЕ
ПРИЛОЖЕНИЕ 3.1. СИНТЕЗ G-АВТОМАТА ДОПУСКАЮЩЕГО ЯЗЫК БНФ
ПРИЛОЖЕНИЕ 3.2. СИНТЕЗ G'-АВТОМАТ А ДОПУСКАЮЩЕГО ЯЗЫК КС~
ГРАММАТИК
ПРИЛОЖЕНИЕ 3.3. СИНТЕЗ G-ABTOMATA ДОПУСКАЮЩЕГО ЯЗЫК
ДИАГРАММЕРОВ
ПРИЛОЖЕНИЕ 4.1. ТЕКСТ ПРОГРАММЫ НА ЯЗЫКЕ Turbo Pascal
РЕАЛИЗУЮЩЕЙ LL (1)-РАСПОЗНАВАТЕЛЬ ЯЗЫКА ОПИСАНИЯ ТЕСТОВЫХ ВОЗДЕЙСТВИЙ МЕТОДОМ РЕКУРСИВНОГО СПУСКА

ПРИЛОЖЕНИЕ 4.2. ТЕКСТ ПРОГРАММЫ НА ЯЗЫКЕ Turbo Pascal 6.0 РЕАЛИЗУЮЩЕЙ РАСПОЗНАВАТЕЛЬ ЯЗЫКА ОПИСАНИЯ ТЕСТОВЫХ ВОЗДЕЙСТВИЙ ПОСТРОЕННЫЙ НА ОСНОВЕ
МОДЕЛИРОВАНИЯ в-АВТОМАТА
ПРИЛОЖЕНИЕ 4.3. 6-АВТОМАТ, ДОПУСКАЮЩИЙ ЯЗЫК ОПИСАНИЯ
СТРУКТУРНЫХ МОДЕЛЕЙ ЦИФРОВЫХ СХЕМ
ПРИЛОЖЕНИЕ 4.4. ИСПОЛЬЗОВАНИЕ ЯЗЫКА ОПИСАНИЯ ТЕСТОВЫХ ВОЗДЕЙСТВИЙ ПРИ ПОИСКЕ ТЕСТОВ ПУТЕМ
МОДЕЛИРОВАНИЯ НЕИСПРАВНОСТЕЙ
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ
УКАЗАТЕЛЬ СОКРАЩЕНИЙ И ОПРЕДЕЛЕНИЙ
УКАЗАТЕЛЬ УТВЕРЖДЕНИЙ И ТЕОРЕМ

2.РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАСПОЗНАВАТЕЛЕЙ КС-ЯЗЫКОВ И МЕТОДА АВТОМАТИЧЕСКОГО СИНТЕЗА ДАННОЙ МОДЕЛИ
В данной главе рассматриваются математические модели задания (разд.2.1) и распознавания (разд.2.2) КС-языков. В качестве математической модели задания КС-языков предложено использовать КС-диаграммер. С одной стороны, КС-диаграммер является графовым представлением КС-грамматики, с другой, он может рассматриваться как МП-автомат, управляющее устройство которого задается конечным множеством КС-диаграмм. В качестве математической модели распознавания КС-языков предложена новая математическая модель - 6-автомат. Данный автомат относится к классу односторонних недетерминированных распознавателей с магазинной памятью. Отличие такта работы 6-автомата от такта классического МП-автомата и от тактов его разновидностей состоит в том, что в 6-автомате переход не зависит от верхнего магазинного символа. Для задания КС-диаграммеров и 6-автоматов определен язык диаграммеров. Разработаны правила преобразования диаграмм (разд.2.3) и процедура автоматизированного синтеза 6-автоматов (разд.2.4). Процесс синтеза 6-автоматов рассматривается как вывод в формальной системе, множество разрешимых слов которой составляет язык диаграммеров. Правилами вывода являются правила преобразования диаграмм.
2.1. Задание КС-языков КС-диаграммерами
Пусть КС-язык задан КС-грамматикой 6=(Ы,Т,В,Б). КС-правила будем изображать КС-диаграммами [1] . КС-диаграммой А, соответствующей множеству КС-правил
А—>ХцХ12 . Х1Ш I Х23.Х22" Х2Н2 | ... | ХМ1Хм2 . Хцда назовем помеченный ориентированный граф:
&— (Ан, Ац;Хц) , (Ац, Ах2;Х12) , . (Ацщ-и , Ак;Хцц)
(Ан, А21;Х21) , (А2х, А22,'Х22) , - , (А2 (N2-1), Ак; Х2мг)
(АН,АМ1;ХМ1) , (А}ц, Амг; Хц2) / - , (Амда-и , Ак," Хмцм)
Здесь и далее графы задаются списком дуг. При символи-
ческой записи списка дуг используются следующие соглашения: