Курсовая Конечные автоматы. Разбор выражений

Автоматное программирование является одним из стилей программирования

Актуальность работы

В настоящее время многие программисты и ученые в этой сфере обсуждают проблему. Чаще программисты практики, которые сетуют на то, что современная система форма и стиль программирования находится на высоком уровне. Но, несмотря, на то, что система настолько идеализирована ее пользователями, все же большинство проектов заканчиваются неудачно. Именно тут и появляется такое понятие как автоматное программирование. Упрощенная  трактовка  автоматного  программирования  состоит  в  том,  что это стиль  программирования,  при  использовании  которого  поведение программ  предлагается описывать автоматами, которые в дальнейшем преобразуются в код. При этом отметим,  что  автоматы  давно  и  успешно  применяются  в  программировании,  например, при построении компиляторов Автоматы используются также и при решении многих других задач, например, при реализации протоколов.

Цель работы: Рассмотреть и определить основные понятия автоматного программирования, проанализировать принципы построения конечных автоматов.

Исходя из цели, можно установить такие задачи:

• Обосновать теоретическое понятие автоматного программирования
• Рассмотреть основные понятия автоматного программирования
• Проанализировать основные виды конечных автоматов
• Показать пример конечного автомата используемого в жизни.

В работе использованы такие методы:

• Аналитический;
• Теоретический.

Предмет курсовой работы: конечные автоматы.

Объект курсовой работы: применение автоматного программирования в жизненной практике

Работа состоит из двух глав, введения, заключения и списка литературы.

1 ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ КОНЕЧНОГО АВТОМАТА

1.1 Описание конечного автомата

Автоматы удобно описывать с помощью таблиц, а для наглядности использовать  графы.

В практике проектирования автоматов встречаются случаи, когда функции переходов и/или выходов не определены для некоторых значений символов входного алфавита. В этом случае говорят, что автомат недетерминированный или частично определенный. При описании таких автоматов неопределенные позиции таблиц помечаются символом «_*».

Конечный автомат (или попросту FSM - Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

Рисунок 1- Описание состояний автомата

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра - переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

1.2 Виды конечных автоматов

По способу формирования функций выхода выделяют автоматы Мили и Мура.

В автомате Мили функция выходов  определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений  абстрактного автомата, т.е.

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y обнаруживается только при наличии символа во входном канале x. Функциональная схема не отличается от схемы абстрактного автомата.

В автомате Мура функция   определяет значение выходного символа только по одному аргументу - состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:

Особенностью автомата Мура является то, что символ y  в выходном канале существует все время пока автомат находится в состоянии q.

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

Потребность такого автомата возникает при формировании автоматных сетей

Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.

Тогда математическая модель и система рекуррентных соотношений  имеют вид:

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

Пусть Y=. Тогда математическая модель и система рекуррентных соотношений  имеют вид:

1. Leveson N. G., Clark S. T. An Investigation of the Therac-25 Accidents. // IEEE Computer. 26(7):18-41, July 1993.
2. Дейкстра Э. Дисциплина программирования / Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир. 2011.
3. Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ: Model Checking. М.: МЦНМО, 2012. 416 с.
4. Pnueli A. The Temporal Logic of Programs // Proceedings of the 18th IEEE Symposium on Foundation of Computer Science. 2007.
5. Поликарпова Н., Шалыто А. Автоматное программирование. СПб.: Питер, 2009. 176 с.
6. Вельдер С. Э., Шалыто А. А. О верификации автоматных программ на основе метода Model Checking // Информационно-управляющие системы. 2012. № 3, с. 27–38.
7. Васильева К. А., Кузьмин Е. В. Верификация автоматных программ с использованием LTL // Моделирование и анализ информационных систем. Ярославль: ЯрГУ. 2007. Т. 14, № 1, с. 3–14.
8. Abran A., Swebok M. J. Guide to the Software Engineering Body of Knowledge. http://www.swebok.org/
9. Kaner C., Falk J., Nguyen Q. Testing Computer Software. NY: Wiley. 200
10. Бурдонов И. Б., Косачев А. С., Кулямин В. В. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай // Программирование. 2010, № 5.