Некоторые свойства сильносвязных автоматов

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

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

Доказательство. Пусть имеется автомат М, который состоит из изолированных подавтоматов М₁, М₂,..., M _N.

Если начальным состоянием автомата М является состояние σ_i подавтомата M_j, то его конечное состояние σ´_i для любой входной последовательности также должно принадлежать M_j. Поскольку M_j является сильносвязным, всегда возможен переход в σ_i из σ´_i. Последнее означает, что М — обратимый автомат.

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

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

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

Теорема 5.9. Пусть М является сильносвязным автоматом с п состояниями. Тогда он может быть установлен в любое заданное состояние простым условным экспериментом длины l и порядка d, где

Доказательство. Используя выражения (4.23) и (4.24), автомат М всегда можно перевести в известное (но не обязательно заданное) конечное состояние простым условным экспериментом длины n(n— 1)/2 или менее и порядка n— 1 или менее. После того как автомат будет переведен в

известное состояние, может быть приложена дополнительная последовательность, которая переведет его из этого состояния в любое заданное состояние (такая последовательность всегда существует, поскольку М, по предположению, является сильносвязным). Согласно теореме 2.2, длина этой дополнительной последовательности не превышает n—1. Таким образом, общая длина эксперимента будет