5.7. Распознавание сильносвязных (n, p, q)-автоматов
Частичное знание внутренней структуры заданного автомата во многих случаях позволяет выявить его входной и выходной алфавиты и число его состояний. Например, если автомат представляет собой вычислительный прибор, то эта информация может быть получена из знания входного устройства, выходного устройства и числа элементов памяти прибора. Если число входных символов равно p, число выходных символов q, а число состояний — n, то эта информация равносильна утверждению, что заданный автомат является 
-автоматом. Если, кроме того, известно, что автомат сильносвязный, то можно утверждать, что заданный автомат является сильносвязным 
-автоматом.
Класс сильносвязных 
-автоматов такой, что никакие два автомата из этого класса не являются эквивалентными, будем обозначать через 
Очевидно, что 
является подклассом класса минимальных 
-автоматов таких, что никакие два автомата из этого класса не эквивалентны друг другу. Согласно теореме 3.7, последний класс является конечным и, следовательно, 
, должен быть также конечным. Используя выражение (3.21), находим, что мощность класса 
обозначаемая 
определяется выражением
Поскольку, согласно теореме 5.6 
представляет собой исключительный класс, любой его член может быть определен простым безусловным экспериментом длины l, где, по следствию 5.1,
Таким образом имеем:
Теорема 5.10. Если известно, что автомат М является сильносвязным 
-автоматом, то М всегда может быть распознан простым безусловным экспериментом длины l, где
Например, сильносвязный (2, 2, 2)-автомат может быть распознан простым безусловным экспериментом, длина которого не будет превышать 725 символов.
