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

N"n,P,<,<JlV.qif-rl (2.3)

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

< р., > (дпГ - П [(дпГ - г]. (2.4)

2.4. Изоморфные автоматы

Как указывалось в § 2.2, обозначение состояний не имеет какого-либо особого значения и может выбираться произвольно. Автоматы, у которых характеристические функции одинаковы, за исключением возможных различий в обозначениях состояний, называются изоморфными друг другу. Если задан автомат М, представляющий определенную систему, то любой автомат, изоморфный к М, также может служить представлением этой системы. Следовательно, представление системы автоматом ни в коем случае не единственно.

Пусть М является (я, р, 9)-автоматом, определенным таблицей переходов, такой, как таблица 2.1. Рассмотрим другую таблицу переходов, полученную из таблицы переходов автомата М путем перестановки символов о;, 02.....о„

с последующей записью строк в том порядке, в котором они были выписаны в исходной таблице. В результате получится таблица, представляющая автомат, изоморфный автомату М. Множество всех различных автоматов, получающихся в результате всех возможных л! таких перестановок, называется семейством перестановок автомата М. Ясно, что не обя-

зательно две различные перестановки приводят -к получению двух различных таблиц переходов и, следовательно,- мощность семейства перестановок может быть меньше, чем п1 Следует также заметить, что два автомата, принадлежащие различным семействам перестановок, не могут быть изоморфными друг другу. В качестве примера таблицей 2.3 представлен автомат, изоморфный автомату Л1, представленному таблицей 2.2. Он получен заменой первоначальных обозначений состояний 1, 2, 3, 4 и 5 на 5, 4, 3, 2 и 1 соответственно.

Таблица 2.3 Автомат, изоморфный автомату А1

Лемма 2.1. Мощность семейства перестановок явно минимального (п, р, д)-автомата равна п\.

Доказательство. Строки в таблице явно минимального автомата различны по определению и остаются различными после перестановки обозначений состояний. Поэтому таблицы, получаемые в результате различных перестановок, различны. Так как число различных перестановок равно п I, то лемма доказана.

Теорема 2.1. Мощность Nn!,q класса явно минимальных (п, р, д)-автоматов, не содержащего изоморфных автоматов, определяется формулой

<"!.= 4П(-г). (2.5)

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

Доказательство. множество явно минимальных (л, р, q)-автоматов является объединением семейств перестановок всех автоматов класса, определенного в теореме. поскольку эти семейства перестановок являются непересекающимися 2) и по лемме 2.1 каждое семейство содержит точно п\ различных автоматов, имеем:

«1<р, = <р,,. (2.6)

где Мпрд - мощность класса явно минимальных (п, р, q)-автоматов, определяемая уравнением (2.2). теорему доказывает решение (2.6) относительно Nn!,q.

2.5. граф переходов

граф переходов представляет собой структуру, состоящую из вершин, изображаемых в виде малых кружков, и ориентированных дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. граф переходов, описывающий автомат с п состояниями, содержит п вершин, причем каждая вершина соответствует одному состоянию автомата; состояние, изображаемое вершиной, снабжается обозначением, соответствующим этому состоянию. ориентированные дуги проводятся и обозначаются по следующему правилу. пусть X = [1, .....1] представляет

собой множество значений х, для которых fix, Oi) = Oj,

и пусть аг) = сгд для а = 1, 2.....г. если

Xij не пустое) множество, то дуга проводится из вершины О; в вершину Oj; стрелка указывает направление из О; в и обозначение дуги записывается в виде

) объединение множеств /?21 ..., записываемое в виде ju2u •• N является множеством, которое содержит все элементы, содержащиеся в R, .....R, и никаких других элементов не содержит.

) множества Ry R.....- непересекающиеся, если не

существует двух множеств Ri и Rj(i ф j), содержащих общий элемент.

) множество называется пустым, если оно не содержит ни одного элемента. пустое множество обозначается нулем.