Задачи

5.1. Постройте автомат, от которого никаким экспериментом длины 4 нельзя отличить автомат, изображенный на рис. 3 5.1, но который не эквивалентен этому автомату.

5.2. Известно, что минимальный автомат М имеет два состояния, входной алфавит и выходной алфавит . Известно также, что ни одно из состояний автомата М на графе переходов не имеет петель. Опишите эксперимент, распознающий этот автомат, если его истинное представление такое, как показано

в таблице 3 5.1, и если его действительное начальное состояние 1 (которое сначала не известно).

5.3. Известно, что автомат, определенный таблицей 35.2, неисправен и что в результате неисправности, по крайней мере, вместо одной из «1» вырабатывается . Опишите эксперимент, распознающий повреждение, состоящее в том, что в состоянии 1 вместо «1» на выходе вырабатывается и если, начальным состоянием автомата является состояние 3 (что сначала не известно).

Таблица 3 5.1

Таблица 3 5.2

5.4. На рис. 3 5.2 показан неполный граф переходов автомата с двумя состояниями. Опишите эксперимент над автоматом, с помощью которого можно закончить построение графа переходов. Предположите, что искомая дуга обозначается и ведет в состояние 1 и что начальным состоянием автомата является состояние 1 (которое сначала не известно).

Рис. 35.2.

5.5. Покажите, что автомат М с множеством состояний является сильиосвязным тогда и только тогда, когда [Определение дано в § 2.6.]

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

5.7. Автоматы являются сильносвязными и состояние автомата эквивалентно состоянию автомата . Покажите, что

5.8. Постройте автомат с состояниями, который является сильиосвязным, не содержит одного полного контура.

5.9. Автомат М имеет множество состояний Покажите, что: (а) М является обратимым, если в каждом изолированном подавтомате автомата М имеется состояние такое, что

является сильиосвязным, если имеет состояние такое, что [Определение дано в § 2.6; определение дано в задаче 2.10.]

5.10. Покажите, что если автомат М является сильиосвязным, то М также является сильиосвязным, что и обратное утверждение не обязательно справедливо.

5.11. Докажите следующее неравенство, использованное в выражении (5.13):

5.12. Известно, что автомат М является сильиосвязным -автоматом. Покажите, что М всегда может быть распознан простым безусловным экспериментом длины l, где

Вычислите верхнее значение I при

Рис. 3 5.3.

5.13. Известно, что автомат М является , -автоматом и содержит полный контур. Найдите, верхнее значение длины распознающего М эксперимента (можно предположить, что п. 1).

5.14. Определите, является ли автомат изображенный на рис. 3 5.3, автоматом без потери информации.

5.15. Покажите, что автомат, представленный на рис. 3 5.3, является автоматом без потери информации, и опишите распознавание входной последовательности приложенной к этому автомату в состоянии 2.

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