Теория автоматов: определение, элементы, применение и примеры

Теория автоматов — это область дискретной математики, которая изучает специальные «абстрактные автоматы». Абстрактный автомат — это вычислительная машина, которая представлена в виде специальной математической модели. А для человека он может выглядеть как вычислительное устройство, выполняющее последовательность запрограммированных операций.

Теория автоматов применяется в направлении информатики и вычислительной техники. Она имеет широкую сферу применения в этом направлении. Например:

1. Участвует в проектировании систем с логическим управлением.

2. Помогает обрабатывать тексты и проектировать компиляторы.

3. Обеспечивает спецификацию и верификацию взаимодействующих процессов.

4. Участвует в написании документации к программам, написанным на объектно-ориентированных языках.

5. Участвует в оптимизации логических программ.

Теория автоматов

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

По сути, конечный автомат — это очень сильно упрощенное компьютерное устройство, в котором прописаны определенные состояния и количество этих состояний. В конечных автоматах отсутствуют:

• оперативная память,

• постоянная память,

• средства для ввода или вывода,

• процессорные ядра и др.

Пожертвовав всеми характеристиками компьютера, конечный автомат обладает:

• программной простотой и легкостью,

• упрощенной аппаратной реализацией,

• способностью внедрять удобные логические рассуждения и др.

Конечный автомат характеризуется 4-мя свойствами:

1. Таблица переходов. Это таблица, в которой хранятся вероятные переходы, зависящие от текущего состояния конечного автомата.

2. Текущее состояние. Это набор состояний, в которых может располагаться конечный автомат в конкретный функциональный момент.

3. Стартовое состояние — момент, с которого конечный автомат активирует собственную деятельность.

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

Детерминированный и недетерминированный конечный автомат

Конечный автомат может быть 2-х типов:

1. Детерминированный конечный автомат. Это конечный автомат, который имеет определенное число состояний. Для каждого отдельного состояния определен входной символ. Такой автомат в конкретный момент времени может располагаться в единственном состоянии. Детерминированный конечный автомат обычно представляет собой простейшее устройство.

2. Недетерминированный конечный автомат. Это такой конечный автомат, в котором также определено множество конечных состояний. Однако при определенном входном символе неясно, в какое состояние может перейти автомат, потому что он может перейти в любое состояние. То есть недетерминированные конечные автоматы характеризуются неопределенным состоянием и свободным переходом в текущий момент времени между состояниями.

Пример конечного автомата

Простой пример конечного автомата — электронные часы. Самые обычные электронные часы являются многофункциональным прибором, который может:

• показать время и дату;

• показать секундомер;

• прозвенеть в нужное время;

• дать возможность настроить время, дату, будильник;

• и др.

Люди привыкли пользоваться подобными устройствами и легко «управляют» ими. Однако система управления электронными часами построена по конечно-автоматному способу. Например:

• есть кнопка, нажатие которой регулирует переходы между состояниями: установка минут, установка часов, установка даты, настройка будильника и др.;

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

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

Заключение

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

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