Назначение и область применения

4.4 Математическое и информационное обеспечение

4.4.1 Теория конечных автоматов

Конечным автоматом называется формальная система M = (Q, Σ, δ, q0, F), где Q – конечное непустое множество состояний; Σ – конечный входной алфавит; δ – отображение типа Q × Σ → Q; q0 ∈ Q – начальное состояние; F ⊆ Q – множество конечных состояний [17].
Конечный автомат состоит из конечного управления и входной ленты, разбитой на ячейки. В каждой ячейке записан один символ из входного алфавита Σ, и все они образуют конечную входную цепочку. Конечное управление первоначально находится в состоянии q₀ и сканирует крайнюю левую ячейку ленты. По мере чтения входной цепочки слева направо автомат переходит в другие состояния из множества Q. Если, прочитав входную цепочку, автомат оказывается в некотором конечном состоянии из множества F, то говорят, что он принял ее. Множество цепочек, принимаемых конечным автоматом, называется языком, распознаваемым данным конечным автоматом.
Конечные автоматы подразделяются на детерминированные и недетерминированные:
Детерминированным конечным автоматом называется такой автомат, в котором нет дуг с меткой ε (неопределённым символом) и из любого состояния по любому символу возможен переход в точности в одно состояние. Все остальные конечные автоматы являются недетерминированными.
Конечные автоматы описывают с помощью двух способов [24]:

1. 
   Таблица переходов
   

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

Символы Состояния