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

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

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

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

Рис. 5.4. Состояние с потерей информации.

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

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

последовательностью или . Таким образом, необходимость условия теоремы очевидна. Предположим теперь, что М не содержит состояний с потерей и что М наблюдается при приложении неизвестной входной последовательности к автомату М в известном начальном состоянии По таблице переходов определим все различные входные последовательности, скажем которым точно соответствует одной из этих последовательностей должна быть . Обозначим состояния, в которые ведет через соответственно. Поскольку, согласно допущению, не является состоянием с потерей, должны быть различными и, следовательно, должно существовать взаимно однозначное соответствие между состояниями и входными последовательностями Теперь приложим установочную последовательность, скажем построенную для М с множеством допустимых начальных состояний Обозначим конечное состояние, в которое перейдет автомат после приложения через , а выходную последовательность, которая получится при этом, через . Пара последовательностей вход - выход может относиться только к одному из состояний по следующим соображениям: допустим, что относится к двум состояниям, скажем тогда Однако, так как — различные последовательности, это означало бы, что является состоянием с потерей, что противоречит предположению, по которому автомат М не содержит состояний с потерей. Следовательно, однозначно определяет состояние, в которое автомат переходит из при приложении и, значит, однозначно определяет . Это положение иллюстрируется рис. 5.5, где предполагается, что является действительной входной последовательностью

Пусть обозначает множество состояний, в которое переходит автомат М из состояния с выходным символом . Если М является автоматом без потери информации, имеющим p входных и q выходных символов, то множества должны содержать полное число элементов p. Теперь пусть «множество обозначает

некоторое множество состояний, скажем достижимых из состояния с выдачей одной и той же выходной последовательности длины k. Тогда множество является множеством . Если М—автомат без потери информации, то число элементов множества должно равняться числу всех элементов в множествах для любого j. Таким образом, составляя рекурсивно все множества для всех k и можно определить, является автомат М автоматом без потери информации или нет.

Рис. 5.5. Пояснение доказательства теоремы 5.11.

Указанный критерий может быть легко применен при построении так называемой таблицы, проверки потерь. В этой таблице каждому столбцу соответствует свой, отличный от других, выходной символ Таблица делится на следующие друг за другом подтаблицы, первая из которых содержит в основном столбце состояния автомата М, а содержимым клетки, находящейся на пересечении строки и столбца имеет множество . Клетки основного столбца подтаблицы заполняются содержимым клеток подтаблицы, притом таким, которое не встречалось в основных столбцах предшествующих подтаблиц. В клетке на пересечении строки и столбца подтаблиие записывается множество которое может быть составлено по данным первой подтаблицы. Построение таблицы заканчивается при выполнении одного из следующих условий: (1) число элементов некоторого множества (в первой подтаблице) меньше мощности входного алфавита: (2) число элементов некоторого множества подтаблице, где меньше общего числа элементов множеств (3) нельзя добавить ни одной новой строки

в основном столбце. Если условия (1) и (2) не имеют места, то М является автоматом без потери информации. Очевидно, что общее число строк в таблице проверки потерь не может превышать

Поэтому проверка потерь информации является конечным процессом.

В качестве примера в таблице 5.9 приведена таблица проверки потерь для автомата заданного графом переходов рис. 5.6 и таблицей 5.8. Первая подтаблица строится на основании таблицы 5.8.

Рис. 5.6. Автомат .

В основной столбец второй подтаблицы переписываются из первой таблицы множества не содержащиеся в основном столбце последней. В клетке второй подтаблицы на пересечении строки и столбца 1, например, проставляется набор состояний, стоящих в клетках первой подтаблицы на пересечении строк 1 и 5 и столбца 1, а именно . Остальные клетки таблицы заполняются аналогично. Так как из рассмотрения таблицы 5.9 следует, что условия (1) и (2) не имеют места, автомат является автоматом без потери информации.

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

Таблица 5.8. Автомат

Таблица 5.9. Таблица проверки потерь для автомата

последовательность 111. Из графа переходов, изображенного на рис. 5.6, можно заключить, что последовательность 111 может соответствовать входным последовательностям которые переводят автомат из состояния 1 в состояния 2, 3 и 4 соответственно. Последовательность является установочной последовательностью для автомата с множеством допустимых состояний При приложении последовательности в состояниях 2, 3 и 4 выходные последовательности будут соответственно и 10. Следовательно, истинной входной последовательностью будет или в зависимости от того, какая будет реакция автомата на последовательность (приложенную после неизвестной входной последовательности) - 11, 01 или 10 соответственно.

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

передачи каждого сообщения. Если получатель не может контролировать передающий конец (как это часто имеет место), то второе требование может быть удовлетворено, если отправитель «согласится» заканчивать каждое сообщение последовательностью , т. е. заранее определенной установочной последовательностью для автомата М и для множества допустимых начальных состояний содержащего все состояния автомата. Например, для автомата и для множества допустимых состояний установочной последовательностью будет Если отправитель систематически заканчивает каждое сообщение передачей последовательности (или передает в течение определенных, заранее оговоренных интервалов времени), то все переданные сообщения могут быть расшифрованы на приемном конце без необходимости доступа к входным зажимам автомата. Можно также показать, что если отправитель согласен передавать последовательность перед каждым сообщением, то принимающему не нужно знать начальное состояние М (т. е. состояние М, в котором к М был приложен первый символ сообщения), так как это начальное состояние может быть определено по реакции автомата на . Таким образом, если до и после каждого сообщения передается последовательность , то это сообщение может быть расшифровано с помощью только таблицы переходов М. В нашем случае это означает, что передача каждого сообщения должна начинаться и заканчиваться передачей входной последовательности

Рис. 3 5.1.