Теория автоматов: Основы вычислений и конечные автоматы
Теория автоматов — это раздел дискретной математики и теоретической информатики, изучающий абстрактные вычислительные машины и задачи, которые они способны решать. Базовой моделью здесь является конечный автомат (Finite State Machine, FSM) — математическая абстракция, представляющая систему, которая может находиться в одном из конечного числа состояний и переходить между ними под воздействием внешних входных сигналов.
Концепция конечного автомата интуитивно понятна на примере турникета в метро. У турникета есть два состояния: «Закрыто» и «Открыто». Подача билета (входной сигнал) переводит его в состояние «Открыто». Проход человека (другой сигнал) возвращает систему в состояние «Закрыто». Любые попытки пройти без билета игнорируются, оставляя турникет закрытым.
Формально детерминированный конечный автомат (ДКА) задается пятеркой элементов:
- Множество состояний (Q).
- Входной алфавит (Σ).
- Функция переходов (δ), определяющая, в какое состояние перейдет автомат из текущего состояния при получении определенного символа.
- Начальное состояние (q0).
- Множество конечных (допускающих) состояний (F).
Основная задача конечного автомата — распознавание регулярных языков. Когда автомату на вход подается строка символов, он читает её символ за символом, меняя свои состояния. Если после прочтения всей строки автомат оказывается в одном из допускающих состояний, говорят, что автомат «допустил» (распознал) эту строку.
На практике теория автоматов является фундаментом для разработки компиляторов и трансляторов. Первый этап компиляции программного кода — лексический анализ — выполняется именно конечными автоматами. Они разбивают сплошной текст программы на осмысленные токены (ключевые слова, идентификаторы, операторы). Регулярные выражения, которые программисты ежедневно используют для поиска и валидации текста (например, проверка корректности email-адреса), «под капотом» преобразуются в недетерминированные конечные автоматы (НКА) для быстрого исполнения.
Венцом теории автоматов является Машина Тьюринга — гипотетическое устройство, имеющее бесконечную ленту памяти. В отличие от простых конечных автоматов, Машина Тьюринга способна вычислить любую функцию, которую в принципе возможно вычислить (тезис Черча-Тьюринга), что делает её абсолютным мерилом алгоритмической разрешимости задач в Computer Science.
