Задачи

6.1. Какие из систем, описанных в задачах представляют системы с конечной памятью?

Представьте в виде -таблицы функции тех систем, которые имеют конечную память.

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

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

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

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

6.6. Покажите, что память минимального -автомата с конечной памятью не может быть больше, чем

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

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

Рис. 36.1.

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

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

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

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

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

6.12. Дано

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

6.13 Дано

где (а) Покажите, что Т (М) характеризует линейный двоичный автомат, только если (б) Покажите, что если то существует автомат такой, что (т. е. если М и соединены в каскад, то вход и выход объединенного автомата одинаковы в любой момент времени). (в) Определите -функцию автомата если М определяется выражением

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

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

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

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

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

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

Начальные условия в момент . Постройте последовательность, которая, будучи приложенной к автомату в момент времени дает постоянный выход, равный 0.

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

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

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

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

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