2.3. Перечисление автоматов

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

Класс - автоматов, - автомат — это автомат, имеющий множество состояний входной алфавит, определяемый множеством и выходной алфавит, определяемый множеством или некоторым подмножеством Z. Любая таблица переходов, имеющая в основном столбце символы заглавия столбцов значения из можества Z или из подмножества Z и значения из множества S, характеризует , - автомат. Мощность этого класса автоматов определяется формулой

Класс явно минимальных - автоматов. Назовем -автомат явно минимальным, если для каждого I и каждого имеется по крайней мере одно k такое, что Любая таблица переходов, в которой все строки в подтаблице различны, характеризует явно минимальный автомат. Мощность этого класса равна

где отрицательные значения считаются равными нулю.

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

Из (2.1) и (2.3) следует, что нижняя граница числа явно сократимых - автоматов определяется формулой