- 1, ТО увеличиваем /г на 1 и возвращаемся к (2). (б) Если k=pA-\-1,тоД, является компактной (/7, i)-

•1 •2 А

последовательностью.

В качестве примера (6.86) показывает построение компактной (3,3)-последовательности для не зависящего от выхода автомата с памятью 3 и входным алфавитом (а, р, у). Последовательные строки показывают подпоследовательности длины 3 (имеется 27 таких подпоследовательностей). Последняя строка показывает суммарную последовательность, длина которой 33 -f 3 - 1 = 29. у у у у у а у а а ааа

ара р а а

а а Y ау а

V а Р а р р р р а р а р

а р Y (6.86)

р Y а Y а Y а Y Р у р а р а у ауу Y Y Э V Р Р Р Р Р PPY PYP Y Р Y Р Y Y

YYY<"<P<°YoPP«PYOYPaYYPPPYPYY

Последовательности, полученные по алгоритму 6.3, обладают следующим свойством. Если первые p символов

Таблица 3 6.1

разместить по окружности, то каждая последовательность, построенная считыванием p -{-[i - 1 последовательных символов, образует компактную (р, р)-последовательность (независимо от начального символа и независимо от того, счи-тываются символы по часовой стрелке или против). Поскольку последовательности, построенные путем выбора различных начальных символов на окружности (но продолжающиеся в одном и том же направлении), обязательно различны, то каждое применение алгоритма 6.3 может дать рц различных компактных (р, р)-последовательностей. Число Up различных компактных {р, р)-последовательностей дается выражением

Wp = {p\f-\ (6.87)

В заключение приведем следующую теорему.

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

l<p + V - \. (6.88)

Задачи

6.1. Какие из систем, описанных в задачах 1.2-1.9, представляют системы с конечной памятью? Представьте в виде лг-г-таблицы функции тех систем, которые имеют конечную память.

6.2. Покажите, что автомат с нулевой памятью является тривиальным автоматом.

6.3. Постройте таблицу переходов (в минимальной форме) для автомата с конечной памятью, входной и выходной алфавит которого {0,1! и который характеризуется равенством ~ дг-г X 2„ i.

6.4. Автомат, определенный таблицей 3 6.1, имеет память ц. (а) Найдите верхнюю границу х. (б) Определите ц.

6.5. Для автомата, показанного на рис. 3 6.1: (а) определите память; (б) постройте минимальную дг-г-таблицу.

) Этот результат получен ван Аарденном-Эренфестом и де Брюином (Т. van Aardenne-Ehrenfest and N. О. de BrulJ п, Circuits and Trees in Oriented Linear Graphs, Simon Stevin, vol 28, pp. 203-217, 1950-1951.)

Рис. 36.1.

6.9. Линейный двоичный автомат А определяется соотношением

(а) Составьте диаграмму переходов минимального автомата А и определите основное состояние, (б) Найдите передаточное отношение автомата А и упростите его сокращением общего делителя полиномов числителя и знаменателя, (в) Покажите, что автомат А, находящийся в начальный момент времени в состоянии покоя, можно описать соотношением 2 = XyiZy i. (г) Составьте диаграмму переходов представленного в пункте (в) автомата А, находящегося в начальный момент времени в состоянии покоя. Удостоверьтесь, что этот автомат составляет множество состояний автомата А, которые достижимы из основного состояния, (д) Найдите выходную реакцию автомата А, находящегося в начальный момент времени в состоянии покоя, на входную последовательность 101100011100.

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

= Jfv ® -v-i ® • •• Ф Ху ® ® z-y 2 ® ... ®

Покажите, что автомат, начинающий работу из своего основного состояния, является тривиальным автоматом.

6.11. (а) Покажите, что D ® I является делителем ® I для любого г > 1. (б) Покажите, что любой полином от D по модулю 2 с четным числом членов имеет делитель D ® I. (в) Покажите, что

D> ® D ® ... ® Doio ® @ ... ® dkf.

6.12. Дано

Р° ® Р8 ® Р» ® ® D t КЩ- от ® D* ® О-® D® I

Найдите дг-г-функцию для автомата М, находящегося в начальный момент времени в состоянии покоя.

6.6. Покажите, что память минимального {п, р, 9)-автомата с конечной памятью не может быть больше, чем (log n)l(\og pq).

6.7. Известно, что автомат М имеет р входных символов, п состояний и память ц. Найдите нижнюю границу мощности выходного алфавита.

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