Введение. 
Исследование и логическое проектирование конечного автомата

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

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

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров где:

Q — конечное множество состояний автомата;

q0 — начальное состояние автомата ();

F — множество заключительных (или допускающих) состояний, таких что ;

У — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

д — заданное отображение множества во множество подмножеств Q:

(иногда д называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

Конечные автоматы подразделяются на детерминированные и недетерминированные:

• — детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
• — недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:
  • 1) существуют переходы, помеченные пустой цепочкой е;
  • 2) из одного состояния выходит несколько переходов, помеченных одним и тем же символом.

Одна из областей эффективного использования конечного автомата (КА) — разработка игровых программ. Другая предметная область — системы управления и/или функционирования в реальном времени. В этих областях в полной мере присутствуют элементы, которые сложно реализовать при обычных подходах. Это — параллельный характер работы составных частей системы, их синхронизация в реальном времени. В таких областях обычно применяются специализированные системы проектирования. В их основу положена, примененная и в КА-технологии, концепция микроядра, которое реализует параллельные механизмы среды функционирования.

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

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

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

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

Постановка задачи Для выполнения данной курсовой работы необходимо выполнить несколько следующих этапов: