Тема 4. Мощность множества конечных автоматов.

ЭЛЕМЕНТЫ Теории автоматов

(теоретическая часть раздела)

В.В. Гуренко

Модуль 2.

План. Мощность множества КА. Классы КА. Эквивалентные состояния автомата и их свойства. Минимальная форма автомата. Алгоритм получения минимального КА.

Тема 4. Мощность множества конечных автоматов.

Лемма. Мощность множества конечных автоматов с n состояниями, p входными сигналами и q выходными сигналами равна

Доказательство. Рассмотрим структуру таблицы переходов/выходов КА в общем виде (достаточно, например, только для автомата Мили в силу функциональной эквивалентности моделей Мили и Мура, рис. 4.1):

y(t)	s(t+1)
x(t) s(t)	x1	x2	…	xp	x1	x2	…	xp
s1
s2			yi				sj
…
sn

L_y y_iÎ Y = {y₁, y₂, … y_q} s_jÎ S = {s₁, s₂, … s_n} L_s

Рис. 4.1. Структура таблицы переходов/выходов КА

Всего способов заполнения одной подстроки подтаблицы выходов (L_y), очевидно,

Всего способов заполнения одной подстроки подтаблицы переходов (L_s) –

Так как строк в таблице n, то:

всего возможных подтаблиц выходов

всего возможных подтаблиц переходов

Тогда число всех возможных таблиц переходов/выходов конечных автоматов, что и составляет мощность множества конечных автоматов, есть произведение этих двух величин:

▄