Лекция: Теория Автоматов

Понятие автомата

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

В курсе рассматривается абстрактная теория автоматов.

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

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

Будем иметь в виду две ключевые абстракции:

1. Автомат функционирует в абстрактном времени.

2. Все переходы происходят мгновенно.

Автомат есть система шести объектов:

a = <X, Y, Q, f, j, q0>

X = {x1,...,xn} — конечный входной алфавит (множество входных сигналов).

Y = {y1,...,ym} — конечный выходной алфавит (множество выходных сигналов).

Q = {q0, q1,...,qk} – множество состояния автомата.

Если множество конечно автомат называется конечным.

f (q, x) — функция переходов.

j (q, x) — функция выходов.

q0Î Q — начальное состояние.