Устранение недостижимых состояний КА

Алгоритм Устранение недостижимых состояний КА

Вход: КА .

Выход: КА .

Шаг 1. Поместить начальное состояние КА в список достижимых состояний , т.е. .

Шаг 2. Для новых элементов списка достижимых состояний пополнить список группой их состояний-приемников, отсутствующих в списке, т.е. .

Шаг 3. Повторить шаг 2, пока список достижимых состояний не перестанет меняться. То есть, если , то i = i +1, иначе .

Шаг 4. Исключить из множества Q состояний КА все состояния, отсутствующие в списке Q_д достижимых состояний, т.е. .

Шаг 5. Исключить недостижимые заключительные состояния и функции переходов, содержащие недостижимые состояния, т.е. , .

Пример Устранить недостижимые состояния КА , где Q = { A, B, C, D, E, F, G }, T = { a, b }, H = { A }, Z = { D, E } и функция переходов задана таблицей 2.4. Граф исходного КА М представлен на рисунке 2.3.

Таблица 2.4 – Функция переходов конечного автомата M

F	A	B	C	D	E	F	G
a	B			C	B	D	F
b	C	D	E	E	D	G	E

Рисунок 2.2 – Граф исходного конечного автомата М

Последовательность устранения недостижимых состояний КА имеет вид:

Q ₀ = { A };

Q ₁ = { A, B, C };

Q ₂ = { A, B, C, D, E };

Q ₃ = { A, B, C, D, E }; т.к. Q ₂ = Q ₃, то Q _д = { A, B, C, D, E }.

Q _н = { F, G }; = { A, B, C, D, E }; = { D, E }.

Функция переходов автомата представлена в таблице 2.6.

Таблица 2.5 - Функция переходов автомата

F	A	B	C	D	E
a	B			C	B
b	C	D	E	E	D

b

Граф КА после устранения недостижимых состояний представлен на рисунке 2.5.

Рисунок 2.3 - Граф КА после устранения недостижимых состояний