10.2. Способы представления конечных автоматов

Конечный автомат можно представлять несколькими способами:

- ориентированным графом (графом состояний), в котором

состояния есть вершины графа, а дуги есть переходы между состояниями:

a₃,V₃

q₂ q₄

a₁,V₁

a₅,V₆

q₁

a₃,V₅

a2,V₂ q3 q5 q6

a4,V₄ a6,V8

Рис. 10.1. Граф состояний

a_i - символы входного алфавита, вызывающие переходы; V_i - символы выходного алфавита; q_i - состояния автомата.

- таблицей переходов, в которой по строкам располагаются

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

	a1	a2	a3	a4	a5	a6
q1	q2, V1	q3, V2
q2			q4, V3
q3				q5, V4
q4			q5, V5		q5, V6
q5						q6, V7
q6

- матрица переходов, которая представляет собой квадратную

матрицу, строки и столбцы которой соответствуют внутренним состояниям автомата. Клетки матрицы заполняются входными символами a_k ,при которых автомат переходит из состояния q_i в состояние q_j , а также выходными символами, соответствующими паре (ak , qi ) .

	q1	q2	q3	q4	q5	q6
q1		a1, V1	a2, V2
q2				a3, V3
q3					a4, V4
q4					a3, V5 a5, V6
q5						a6, V7
q6

Определение. Детерминированным конечным автоматом называется такой автомат, каждая клетка таблицы переходов которого не содержит состояний больше одного. В противном случае автомат называется недетерминированным.

Определение. Конечный автомат называется полностью определенным, если его таблица переходов не содержит пустых клеток. Иначе автомат называют частично определенным.