Разработка компиляторов
Конечные автоматы
Конечный автомат - это один из самых простых механизмов, используемых при работе с языками. У этого распознавателя есть только фиксированный набор ячеек памяти, а управляющее устройство может только сдвигаться вправо по входной ленте и изменять состояния памяти. Основная часть конечного автомата - это функция перехода, определяющая возможные переходы для любого текущего состояния и любого входного символа. Подразумевается, что допускается возможность перехода сразу в несколько различных состояний автомата, т.е. управляющее устройство распознавателя может быть и недетерминированным. Недетерминированность надо понимать следующим образом: если возможно сразу несколько переходов из данного состояния, то создается несколько копий нашего автомата, по одному на каждое новое состояние. Цепочка считается принадлежащей языку, если хотя бы одна из последовательностей шагов завершается в заключительном состоянии.
После такого краткого объяснения основных идей мы можем дать формальное определение конечного автомата.
Определение. Конечный автомат - это пятерка
, где
- Q - конечное множество состояний
- - конечное множество допустимых входных символов
- - отображение множества в множество P(Q) , определяющее поведение управляющего устройства (эту функцию часто называют функцией переходов)
- - начальное состояние управляющего устройства
- - множество заключительных состояний
В принципе, для определения последующих действий конечного автомата достаточно знать текущее состояние управляющего устройства плюс последовательность все еще необработанных символов на входной ленте. Этот набор данных называется конфигурацией автомата.
