7. Программная реализация конечного автомата

Программа, моделирующая работу конечного автомата, должна обеспечивать различение допускаемых и не допускаемых цепочек. Цепочки символов должны вводиться с клавиатуры компьютера, программа различения цепочек должна иметь как автоматический, так и пошаговый режим работы и отражать на экране монитора изменение состояний автомата в процессе различения цепочек. При переходе автомата в заключительное состояние (последовательность входных символов образует допустимую цепочку) и появлении признака конца цепочки программа должна формировать сигнал различения цепочки. При наличии цепочек, не принадлежащих языку полученной грамматики, программа должна формировать сигнал ошибки и указывать последнее из состояний автомата, в котором он находился до появления ошибочного символа.

8. Порядок выполнения курсовой работы

ЭТАП 1. Построение праволинейной грамматики. Переход от праволинейной грамматики к автоматной.

ЭТАП 2. Построение недетерминированного распознающего автомата.

ЭТАП 3. Переход от недетерминированного автомата к полностью определенному детерминированному автомату.

Результаты. Таблица переходов и граф переходов детерминированного автомата. Примеры цепочек. Проверка эквивалентности автоматов сравнением множеств цепочек, допускаемых недетерминированным и детерминированным автоматами.

ЭТАП 4. Минимизация автомата. Часть первая: построение таблицы попарной эквивалентности состояний.

Результаты. Треугольная таблица отношений эквивалентности. Множество пар эквивалентных состояний.

ЭТАП 5. Минимизация автомата. Часть вторая: построение разбиения множества состояний на классы эквивалентности. Приведение автомата к минимальному.

Результаты. Таблица переходов и граф переходов минимального автомата. Примеры цепочек. Проверка эквивалентности детерминированного и минимального автоматов сравнением множеств цепочек, допускаемых автоматами.

ЭТАП 6. Разработка программы, моделирующей работу полученного распознающего автомата.

Результаты. Рабочая программа, листинг программы.

9. Требования к оформлению

Результаты, которые получены при выполнении работы в соответствии с разд.8, должны быть полностью отражены в пояснительной записке. Все этапы работы должны содержать пояснения проводимых построений и принятых решений. При проведении этапов 2, 3 и 5 необходимо обязательно привести примеры всех цепочек, допускаемых автоматом. При разработке программы необходимо дать пояснения (комментарии) выбранным решениям.

Пояснительная записка должна быть отпечатана или написана от руки на стандартных листах формата А4. Титульный лист записки должен быть оформлен в соответствии с требованиями к титульным листам пояснительных записок курсовых работ.

Список рекомендуемой литературы

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / Под. ред. В. И. Варшавского. - М.: Наука, 1986. - 400 с.

2. Крючкова Е.Н. Теория формальных языков и автоматов. – Барнаул; 1996

3. Рейуорд – Смит В.Дж. Теория формальных языков. Вводный курс. – М.: Мир, 1988

4. Саломаа А. Жемчужины теории формальных языков. – М.: Мир, 1987.

Теория языков программирования и методы трансляции. Синтез конечного распознающего автомата: методические указания к выполнению курсовой работы для студентов дневной формы обучения специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

АЛЕКСАНДР НИКОЛАЕВИЧ ГОРБУНОВ

Научный редактор В.В. Симкин

Редактор издательства Л.И. Афонина

Компьютерный набор М.В. Березина

Темплан 2004г., п.123

Подписано в печать __.__.04. Формат 60х80 1/16 Бумага офсетная. Офсетная печать. Усл.печ.л. 1,16 . Уч.-изд.л. 1,16 Тираж 50 экз. Заказ Бесплатно.

Брянский государственный технический университет.

241035, Брянск, бульвар 50-летия Октября, 7, БГТУ. 55-90-49.

Лаборатория оперативной полиграфии БГТУ, ул. Институтская, 16.