06

Определение 2.1.1. Конечный автомат (finite automaton, finite-state machine) - это пятерка $M = \langle Q , \Sigma , \Delta , I , F \rangle$ , где $\Sigma$ - конечный входной алфавит (или просто алфавит) данного конечного автомата, Q и $\Delta$ - конечные множества,

$\Delta \subseteq Q \times \Sigma ^* \times Q ,$

$I \subseteq Q$ , $F \subseteq Q$ . Элементы Q называются состояниями (state), элементы I - начальными (initial) состояниями, элементы F - заключительными или допускающими (final, accepting) состояниями. Если $\langle p , x , q \rangle \in \Delta$ , то $\langle p , x , q \rangle$ называется переходом (transition) из p в q, а слово x - меткой (label) этого перехода.

На содержательном уровне функционирования КА можно представить следующим образом

Имеется бесконечная лента, разбитая на ячейки в каждой из которых может находиться только один символ из $\Sigma$ . На ленте записана цепочка αэ $\Sigma$ *.

Иметься конечное устройсво управления с головкой чтения, которое может последовательно считывать символы с ленты, передвигаясь вдоль ленты слева направа. При этом устройство управления моджет находиться в каком либо одном состоянии и начинает свою работу устройство с I, а заканчивает в одном из состоянии F . Каждый раз переходя к новой ячейки на ленте УУ переходит в новое состояние в состояние с функцией $\Delta$ .

Функцию перехода КА можно представить разными способами. Основные из них

- совокупность команд

-диаграммы состояния

-матрицы переходов

Пример:

1) Коианда КА (qi,aj)—qx

Данная команда означает что КА находиться в состоянии qi, УУ стоит на ячейки символов aj и переходит в состоянии qx.

2)диаграмма состояния

Графически команда представляеться сл виде. Дуги графа идущая из вершины qi, дуга помечена символом ai

Графич представление называю диаграммой состояния КА.

Замечание 2.1.3. Конечные автоматы можно изображать в виде диаграмм состояний (state diagram) (иногда их называют диаграммами переходов (transition diagram)). На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Стрелка из p в q, помеченная словом x, показывает, что $\langle p , x , q \rangle$ является переходом данного конечного автомата. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое допускающее состояние отмечается на диаграмме двойным кружком.

Пример 2.1.4. На диаграмме изображен конечный автомат из примера 2.1.2.

$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aaa} \ar `ur_r{+/u7mm/}`r_dr{[0,2]}^{ab} "1,3" \ar "1,3" ^{b} & & *=[o][F=]{2} \ar `dl_l{+/d7mm/}`l_ul{[0,-2]}^{\varepsilon} "1,1" }$

Замечание 2.1.5. Если в конечном автомате имеются несколько переходов с общим началом и общим концом, то такие переходы называются параллельными. Иногда на диаграмме состояний конечного автомата параллельные переходы изображают одной стрелкой. При этом метки переходов перечисляют через запятую.

Для диаграмм справедливы следующие утверждения:

1)из одной вершины не может выходить 2х ребер с одинаковым входным символом.

2) если при работе автомата реализована входная комбинация qi, aj то обязательно существует ребро идущее от вершины qi к qx, помеченное символом aj/

3) Количество вершин и ребер диаграммы являеться конечным.

3) матрицы переходов

Строяться след образом: строки матрицы составл символом входного алфавита, стролбцы- символом алфавита состояния. Элементы матрицы соответствуют состояниям в которое переходит КА для данной комбинации входного символа и состояния.

	q0	q1	q2	qn
a1			qz
a2		qx
am				qy

Если КА оказываеться в ситуации (qi,aj) и не являеться левой частью какой-либо формулы, то он останавливаеться. Если же устройство управления считает все символы цепочки, которые законченные на ленте и при этом перейдет в конечное состояние то говорят что цепочка α допустима КА.