Конечные автоматы – распознаватели

Определение. Детерминированным конечным автоматом – распознавателем называется устройство или алгоритм А = (Q, S, d, q₀, F), где Q – непустое конечное множество состояний, S – конечный входной алфавит, q₀ Î Q – начальное состояние, d - функция переходов, F Î Q – множество заключительных состояний.

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

Определение. Автомат распознает (допускает) цепочку, если по окончании цепочки перейдет в одно из заключительных состояний. Распознаваемым языком называется множество всех цепочек, распознаваемых этим автоматом.