5.3. Распознавание автоматов известного класса

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

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

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

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

Теорема 5.3 показывает, что два «различимых» (согласно определению § 3.9) автомата не обязательно различимы по их внешнему поведению, поскольку такие автоматы не обязательно исключительные. Например, автоматы и ЛЮ, изображенные на рис. 3.6 и 3.7, различимы, но не являются исключительными (состояния 1 и 2 автомата эквивалентны состояниям 1 и 2 автомата соответственно), поэтому не всегда можно определить, является автомат М автоматом (можно определить только в том случае, когда М является автоматом ЛЮ в состоянии 3), и, следовательно, автомат М нераспознаваем.

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

Так как решение установочной задачи является также решением задачи распознавания автомата М, мы имеем следующую теорему.

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

распознан простым безусловным экспериментом длины l, где

Важным частным случаем теоремы 5.4 является случай, когда или верхние граничные значения одинаковы для всех

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

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

Алгоритм 5.1. Известно, что автомат М принадлежит к исключительному классу автоматов Чтобы распознать М при помощи простого условного эксперимента: (1) Полагаем Проводим над М регулярный условный установочный эксперимент, построенный для с множеством допустимых начальных состояний, содержащим все состояния автомата (а) Если , то увеличиваем k на единицу и возвращаемся к (2). (б) Если k = N, то принимаем, что обозначает настоящее состояние М, считая, что — это и переходим к операции (4). (4) Проводим над М регулярный условный установочный эксперимент, построенный для с множеством допустимых начальных состояний Если конечное состояние автомата принадлежит подавтомату , то М является автоматом .

Из выражения (4.23) следует, что выполнение операции (2) алгоритма требует при не более входных символов, где — число состояний

в . Если то, по следствию выполнение операции (4) требует не более операций. Из теоремы 4.13 следует, что порядок эксперимента, описанного алгоритмом, не превышает

Таким образом получаем:

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

Следует заметить, что при проведении установочного эксперимента для любого частного автомата согласно требованию операции (2) алгоритма 5.1, наблюдаемые реакции могут быть использованы для исключения одного или нескольких автоматов (возможно, самого ) из дальнейшего рассмотрения в качестве автомата М. Когда выполнение операции (2) сопровождается таким исключением, то как длина, так и порядок эксперимента значительно сокращаются.

Когда или верхняя граница одинаковы для всех I, то из теоремы 5.5 вытекает

Следствие 5.2. Если заданный автомат М принадлежит исключительному классу автоматов , в котором каждый автомат имеет, по крайней мере, n состояний, то автомат М может быть распознан простым условным экспериментом длины и порядка d, где