pJv ф pJv-l ® ... @

где 1и > iu-\ > > i\ и у, > >...>;,. (а) Покажите, что Т(М) характеризует линейный двоичный автомат, только если ]\ < i- (б) Покажите, что если г, = у, = О, то существует автомат такой, что 7(Л1) 7(Af-)= / (т. е. если М и ЛГ" соединены в каскад, то вход и выход объединенного автомата одинаковы в любой момент времени)). (в) Определите л:-г-функцию автомата если М определяется выражением

6.14. Покажите, что период свободной выходной последовательности линейного двоичного автомата, имеющего 4 состояния, не может превышать 63.

6.15. На линейный двоичный автомат М с памятью х подается входная последовательность периода ро. Покажите, что выходная реакция станет периодической после конечного числа символов и что ее период не будет превышать Po(2 - 1).

6.16. Импульсная характеристика линейного двоичного автомата, из состояния покоя, есть 1011001001001 ... Найдите выходную реакцию автомата, из состояния покоя, на входные последовательности: (а) 110101000000000 (б) 101101101101101 ... Разбейте результирующую выходную реакцию на переходную и периодическую составляющие.

6.17. Импульсная характеристика линейного двоичного автомата, находящегося в состоянии покоя, есть

101010011101001110100111010011 ...

Определите х-г-функцию этого автомата.

6.18. Линейный двоичный автомат определяется выражением

= ATv ® Х„-1 ® Jfv-2 ® 2v-2 ® 2v-3-

Начальные условия в момент ty,: Xy, i = Ху, 2 - v-3=2v-i = .2 2 = = v 3=l. Постройте последовательность, которая, будучи приложенной к автомату в момент времени t, дает постоянный выход, равный 0.

6.19. Известно, что не зависящий от выхода автомат имеет память 5 и входной алфавит {0. 1). Постройте самый короткий безусловный эксперимент для распознавания автомата.

6.20. Известно, что заданный автомат М является не зависящим от выхода {п, р, 9)-автоматом. Покажите, что М может быть

1) Как автомат М, так и автомат М являются автоматами без потери информации (см. § 5.8).

6.13. Дано

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

6.21. Постройте автомат с двумя состояниями, отвечающий следующим требованиям: (а) чтобы он не был автоматом с конечной памятью, (б) чтобы он был автоматом с конечной памятью, но не зависящим от выхода, (в) чтобы он был не зависящим от выхода автоматом.

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

2у = (Ху, Sy),

ГЛАВА 7

АВТОМАТЫ С ОГРАНИЧЕНИЯМИ 41А ВХОДЕ

7.1. Введение

При изучении конечных автоматов мы обращали внимание на свойства самих автоматов и не касались свойств источников входных последовательностей, возбуждающих эти автоматы. Мы логично предполагали, что рассматриваемые автоматы могут подвергаться воздействиям со стороны любых источников сигналов, лишь бы генерируемые входные символы принадлежали входному алфавиту автомата. В этой главе мы откажемся от этого предположения и рассмотрим более общий класс автоматов, в котором на источники могут быть наложены определенные ограничения. Особо мы будем исследовать класс автоматов, известных как автоматы с ограничениями на входе, в которых не каждый входной символ может быть подан на автомат, находящийся в определенном состоянии. Такое ограничение неизменно возникает, поскольку существует некоторая взаимосвязь между внутренней структурой автомата и источником входных символов. Для иллюстрации рассмотрим пример 2 из § 1.7, где английский текст, состоящий из 26 букв алфавита и промежутков, просматривается с целью подсчета числа слов, начинающихся с «мя» и оканчивающихся на Когда автомат находится, например, в состоянии «появление и-п-й», входной символ «р» не может быть подан, так как не существует английских слов, содержащих последовательность букв шпйр» (или вероятность появления такой последовательности чрезвычайно мала).

Поэтому для всех практических целей символ «р» (так же как и многие другие символы) может быть исключен из множества входных символов, когда автомат, который описывает систему, просматривающую текст, находится в состоянии «появление u-n-d».