5.5. Сильносвязные автоматы

В этом параграфе рассмотрим важный класс автоматов, называемых «сильносвйзными автоматами».

Определение 5.1. Автомат М с множеством состояний называется сильносвязным, если существует входная последовательность, которая переводит автомат М из любого заданного состояния в любое заданное состояние (где I может равняться ).

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

изолированный подавтомат, не может быть сильногвязным автоматом. Таким образом, сильносвязным является такой автомат, в котором можно перейти в каждое состояние независимо от предыстории автомата.

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

Лемма 5.1. Если автоматы являются сильносвязными и различимыми, то ни одно состояние в не эквивалентно какому-либо состоянию в

Доказательство. Пусть множеством состояний автомата будет множество а множеством состояний автомата Предположим, что в автомате имеется состояние которое эквивалентно некоторому состоянию в . Пусть будет входной последовательностью, которая переводит автомат из состояния — входной последовательностью, переводящей автомат из состояния в состояние для (все такие последовательности существуют, поскольку автомат сильносвязный). Приложим последовательность После приложения последовательности окажется в состоянии — в некотором состоянии Так как то их преемники по отношению к любой входной последовательности должны быть эквивалентными, следовательно, Таким образом, для каждого состояния в существует эквивалентное состояние в Теперь пусть будет входной последовательностью, которая переводит автомат из состояния — входной последовательностью, которая переводит из состояния (все такие последовательности существуют, так как — сильносвязный автомат). Приложим последовательность

и к . После приложения окажется в состоянии в некотором состоянии Поскольку , то мы должны получить, как и прежде, для , то есть для каждого состояния в существует эквивалентное состояние в Таким образом показано, что если . Это противоречит условию теоремы и, следовательно, ни одно состояние в не может быть эквивалентным какому-либо состоянию в

Теорема 5.6. Если является конечным классом сильносвязных автоматов таких, что среди них никакие два автомата не являются эквивалентными, то класс является исключительным.

Доказательство. Предположим, что не является исключительным классом. Тогда в некотором автомате должно существовать состояние, эквивалентное некоторому состоянию в другом автомате Однако, согласно лемме 5.1, это невозможно, поскольку и различимы и сильносвязны. Полученное противоречие доказывает, что класс должен быть исключительным.

Объединяя теоремы 5.3 и 5.6, получим

Следствие 5.3. Если известно, что автомат принадлежит к определенному конечному классу сильносвязных автоматов, то он всегда может быть распознан. Процедура распознавания сильносвязного автомата и оценка длины распознающего эксперимента идентичны процедуре и оценке, представленным в предшествующих параграфах.