3.14. Класс минимальных автоматов

Используя определения, введенные в § 2.3, в качестве следствия теоремы 3.1 и определения эквивалентности автоматов получаем:

Лемма 3.12. Явно минимальный (n, p, q) - автомат должен быть минимальным. Явно сократимый (n, p, q) - автомат не может быть минимальным.

Дополнительно теперь докажем следующие леммы.

Лемма 3.13. Мощность семейства перестановок минимального (n, p, q) - автомата равна

Доказательство. Пусть — минимальный (n, p, q) - автомат и пусть — автомат, полученный из М перестановкой обозначений его состояний. Предположим, что перестановка, с помощью которой получен из включает в себя замену обозначения состояния имеют одинаковые таблицы переходов, то реакции на любую входную последовательность должны быть одинаковыми и, следовательно, реакции на любую входную последовательность также должны быть одинаковыми. Это означает, что состояния эквивалентны и, следовательно, не является минимальным автоматом. Из полученного противоречия следует, что различные перестановки должны давать

в результате различные таблицы переходов. Число различных перестановок равно . Лемма доказана.

Лемма 3.14. Мощность класса минимальных (n, p, q) - автоматов, таких, среди которых нет двух изоморфных друг другу автоматов, определяется выражением

Доказательство. Пусть число (n, p, q) - автоматов, не являющихся явно сократимыми, равно , и пусть число минимальных (n, p, q) - автоматов, изоморфных или неизоморфных друг другу, равно . Тогда, согласно лемме 3.12,

Согласно лемме 3.13,

или

Используя уравнение (2.3) для определения получаем доказательство леммы.

Поскольку два минимальных неизоморфных автомата должны быть различимы, то представляет собой также число минимальных (n, p, q) - автоматов, среди которых нет ни одной пары эквивалентных автоматов. Это число должно включать в себя число явно минимальных (n, p, q) - автоматов, среди которых нет ни одной пары изоморфных автоматов. Используя теорему 2.1 для определения , получаем:

Теорема 3.7. Мощность класса минимальных (n, p, q) - автоматов, среди которых нет ни одной пары эквивалентных автоматов, определяется выражением

Например, общее число минимальных (n, p, q) - автоматов, среди которых нет эквивалентных, заключено между 96 и 120.