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

/<-!«(«-l) + «-l=-i(«+2)(«-l). (5.10)

Общий порядок при этом будет определяться выражением d<ra-1 + 1 = га. (5.11)

5.7. Распознавание сильносвязных (л, р, 9)-автоматов

Частичное знание внутренней структуры заданного автомата во многих случаях позволяет выявить его входной и выходной алфавиты и число его состояний. Например, если автомат представляет собой вычислительный прибор, то эта информация может быть получена из знания входного устройства, выходного устройства и числа элементов памяти прибора. Если число входных символов равно р, число выходных символов - д, а число состояний - п, то эта информация равносильна утверждению, что заданный автомат является (га, р, 9)-автоматом. Если, кроме того, известно, что автомат сильносвязный, то можно утверждать, что заданный автомат является сильносвязным (га, р, 9)-автоматом.

Класс сильносвязных (га, р, 9)-автоматов такой, что никакие два автомата из этого класса не являются эквивалентными, будем обозначать через С„р,. Очевидно, что С„,р является подклассом класса минимальных (га, р, 9)-автоматов таких, что никакие два автомата из этого класса не эквивалентны друг другу. Согласно теореме 3.7, последний класс является конечным и, следовательно, С„ р должен быть также конечным. Используя выражение (3.21), находим, что мощность класса С„ р , обозначаемая С„ р , определяется выражением

{Сп.р.дКЛКдпГ-г]. (5.12)

(п-1)1

(2n-l)(gn)P"

(9" J n(n-l)

2{qn)P J

(5.13)

Таким образом имеем:

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

-(„ 1)!---9 «лР • •1

2(9П)Р J-

Например, сильносвязный (2, 2, 2)-автомат может быть распознан простым безусловным экспериментом, длина которого не будет превышать 725 символов.

6.8. Автоматы без потери информации i)

В главе 4 и предыдущих параграфах настоящей главы мы изучали вопросы распознавания неизвестных состояний и неизвестных автоматов. В этом параграфе мы рассмотрим задачу распознавания другого типа - задачу распознавания неизвестной входной последовательности, приложенной к заданному конечному автомату. В частности, эта задача состоит в следующем: неизвестная конечная входная последовательность прикладывается к автомату М, таблица переходов которого и начальное состояние а,- (т. е. состояние

) Материал этого параграфа частично базируется на работе Хаффмепа (D. А. Н ii f f га а п. Canonical Forms for Information - Lossless Finite -State Logical Machines, IRE Trans., vol. CT -6, special supplement, pp. 41-59, 1959).

Поскольку, согласно теореме 5.6, С„, р представляет собой исключительный класс, любой его член может быть определен простым безусловным экспериментом длины /, где, по следствию 5.1,

i <(2я - 1)(I С„. J я - 1 )<-fi П - г] = •

8г/зг

эяние ( формации.

) Имеется в виду потеря информации. (Прим. ред.)

перед приложением входной последовательности ) известны, а реакция на входную последовательность W может наблюдаться; построить эксперимент, который, будучи проведенным над автоматом Ж, после приложений последовательности распознает эту последовательность. Автоматы, для которых эта задача может быть решена независимо от и а,, называются автоматами без потери информации. Автоматы без потери информации в отличие от всех других конечных автоматов, в которых при известных начальном состоянии и приложенной входной последовательности всегда можно определить выходную последовательность, имеют дополнительное свойство: при заданном начальном состоянии по выходной последовательности можно всегда определить входную последовательность.

Будем говорить, что состояние о, автомата М ведет в состояние о через /<й, если приложение входной последовательности к ЖI а, дает выходную последовательность 0 и переводит автомат Ж в состояние а. Состояние а, будем называть состоянием с потерей), если оно

ведет в некоторое состоя- с ние о; через gj/c и че-

рез з/с, где 1 и - две различные входные последовательности. Послед-, нее определение иллюстри-

Рис. 5.4. Состояние с потерей ин- „уртся пиг 5 4

Теорема 5.11. Для того чтобы автомат Ж был автоматом без потери информации, необходимо и достаточно, чтобы этот автомат не имел состояний с потерей.

Доказательство. Предположим, что автомат Ж содержит состояние с потерей о, такое, как показано на рис. 5.4. Так как выходные последовательности Жо, при g] и при 2 одинаковы и так как обе последовательности переводят Ж в одно и то же конечное состояние, то не существует последующего эксперимента, который бы выявил, вызвана выходная последовательность входной