) Если не определено иначе, то будем считать, что «класс» автоматов состоит из сравнимых минимальных автоматов таких, среди которых никакие два автомата не являются эквивалентными.

знание его входного алфавита и граничного значения числа состояний его минимальной формы. Предварительное знание выходного алфавита, как мы увидим в дальнейшем, для распознавания автомата не является обязательным.

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

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

[Ml, М2..... 14}• котором ни одно состояние любого

автомата Mi не эквивалентно никакому состоянию автомата Mj и Ф О-

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

Tt=[Mi, 2..... лЬ Необходимое и достаточное

условие распознавания автомата М состоит в том, чтобы Ш был исключительным классом.

Доказательство. Если Ш. не является исключительным классом, то имеется, по крайней мере, одна пара эквивалентных состояний, скажем а в Mi и а-" в Mj. Тогда, если автомат М является либо автоматом Aija, либо Mj\a\ то никаким экспериментом нельзя установить, каким именно автоматом он является. Следовательно, чтобы автомат М всегда был распознаваем, класс Ш должен быть исключительным. Чтобы доказать достаточность условия теоремы, рассмотрим автомат (Му М, Ждг), в который каждый член множества Ш включен как изолированный подавтомат. Поскольку Ж является исключительным, то

Д(Ж1, М.....Ждг) является минимальным и, следовательно,

всегда существует установочный эксперимент, который определяет его конечное состояние. Зная конечное состояние

автомата A(Mi, М..... Ждг), можно найти подавтомат,

имеющий начальное состояние, принадлежащее автомату

(rai + raj-1)

LVra /

или менее.

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

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

причем га1<га. Тогда автомат М может быть

A(Mi, м.2, .... Ждг), И, следовательно, найти автомат Жд, с которым может быть отождествлен автомат М. Таким образом, если 2% - исключительный класс, то Ж распознаваем.

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

Пусть га,- обозначает число состояний автомата Ж и пусть автоматы в исключительном классе Ш=\М\, М, Ждг) перенумерованы так, что ra+i га. Тогда Д (Ж;, М.....Ждг)

содержит 2 "I состояний. Согласно теореме 4.1, любые два

состояния в автомате М являются(га - 1)-различимыми. По следствию 4.1, любые два состояния - одно из Ж;, а другое из Mj (J Ф i) - являются (га + га - 1)-различи-мыми. Так как га + га <! га; + газ, то любые два состояния

в A(Mi, Жз..... Ждг) (независимо от того, являются они

состояниями одного и того же автомата или двух разных автоматов) должны быть (га; + газ - 1)-.различимыми. Исполь-

зуя следствие 4.2. при L=:rai + ra2-1 и m==2/ можно

заключить, что установочная задача для A(Mi, Жз.....Ждг)

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

/<(«1 + «2- 1)

(5.1)

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

Следствие 5.1. О заданном автомате М известно, что он принадлежит исключительному классу автоматов

[Ml, М2......лЬ где каждый автомат имеет не более га

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

/<(2га-1)(Л/га-1). (5.2)

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

Алгоритм 5.1. Известно, что автомат М принадлежит

к исключительному классу автоматов [М .....лЬ

Чтобы распознать М при помощи простого условного эксперимента: (1) Полагаем /г=1. (2) Проводим над М регулярный условный установочный эксперимент, построенный для с множеством допустимых начальных состояний,

содержащим все состояния автомата УИ. (3) (а) Если /г < Л/, то увеличиваем k на единицу и возвращаемся к (2). (б) Если

k=N, то принимаем, что а, г= 1, 2.....N, обозначает

настоящее состояние М, считая, что М,- это Ж,, и переходим к операции (4). (4) Проводим над М регулярный условный установочный эксперимент, построенный для

b.{Mi, М2.....Ждг) с множеством допустимых начальных

состояний {а, а\ а}. Если конечное состояние

автомата A(Mi, М2.....Мд) принадлежит подавтомату Ж,

то М является автоматом Жд.

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

у га, (га, - 1) входных символов, где га, - число состоя-

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

I N