Задачи

4.1. Опишите матричный способ решения диагностической задачи для двух состояний.

4.2. Таблицы 3 4.1 и 3 4.2 соответственно представляют автоматы А и В. Перечислите минимальные диагностические последовательности для всех пар состояний, в которых одно состояние выбирается из А, а второе состояние — из В.

4.3. Рис. 3 4.1 показывает граф переходов автоматов А и В. (а) Известно, что заданный автомат есть А в состоянии 3 или 4. Постройте кратчайший безусловный эксперимент для распознавания начального состояния, (б) Известно, что заданный автомат есть А в состоянии 1 или В в состоянии 1. Постройте кратчайший

Таблица 3 4.1

Таблица 3 4.2

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

4.4. Задайте автомат с шестью состояниями, в котором два состояния могут быть различены с помощью входной последовательности длины 5, но не меньше.

Рис. 3 4.1.

Проверьте, что приведенное выше требование удовлетворяется.

4.5. Задайте автомат с шестью состояниями и автомат с девятью состояниями, в которых два состояния (по одному в каждом автомате) могут быть различены с помощью входной последовательности длины 14, но не меньше. Убедитесь, что указанное требование удовлетворяется.

4.6. Рис. 3 4.2 показывает уровни от 0 до 3 частично снабженного обозначениями дерева преемников, где суть А-группы. Покажите, что три пути, проходящих через уровня 3, не могут представлять минимальных диагностических последовательностей для М и А (М).

4.7. Покажите, что минимальная диагностическая последовательность для автомата с q выходными символами и множеством

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

4.8. Определите минимальную диагностическую последовательность для автомата, представленного таблицей 3 4.3 и множеством допустимых начальных состояний

Рис. 34.2.

4.9. Известно, что заданный автомат есть автомат, определенный либо таблицей 3 4.4, либо таблицей 3 4.5. Постройте кратчайший безусловный эксперимент для распознавания автомата и его начального состояния.

Таблица 3 4.3

4.10. Для автомата, определенного таблицей 3 4.6. (а) Постройте безусловные диагностические эксперименты, если множества допустимых начальных состояний таковы: (I) (б) Для случаев (II) и (III) опишите условный диагностический эксперимент, если истинное начальное состояние есть 1 (что сначала не известно).

4.11. Заданный автомат представлен графом переходов на рис. 3 4.3. (а) Постройте кратчайший безусловный эксперимент для распознавания начального состояния автомата, (б) Постройте кратчайший безусловный эксперимент для распознавания конечного состояния автомата.

Таблица 3 4.4

Таблица 3 4.5

Таблица 3 4.6

4.12. Для автомата, заданного таблицей 3 4.6, и множества допустимых начальных состояний (а) Постройте кратчайший безусловный установочный эксперимент, (б) Постройте регулярный безусловный установочный эксперимент, (в) Опишите регулярный условный установочный эксперимент, если истинное начальное состояние есть 5 (что заранее не известно).

4.13. Для автомата, показанного на рис. 3 4.4. (а) Постройте регулярный безусловный установочный эксперимент, если истинное начальное состояние есть 7 (что сначала не известно).

4.14. Неизвестное начальное состояние автомата на рис. 3 4.4 есть 1. Опишите условный эксперимент, который будет переводить автомат в состояние 7.

4.15. Известно, что заданный автомат есть либо А, либо В из задачи 4.2. Постройте безусловный эксперимент для распознавания автомата и определите его конечное состояние.

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

превышает

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

Рис. 3 4.3.

Рис. 34.4.

(а) Найдите и (как функцию m), которое минимизирует верхнюю границу l. (б) Оцените наименьшую верхнюю границу l для m = 2, 4, 8, 1024.

4.18. Таблица пар автомата состояниями содержит только различные пары. Покажите, что начальное состояние М всегда может быть определено простым безусловным экспериментом, длина которого не превышает

4.19. Не строя каких-либо диагностических экспериментов, покажите, что диагностическая задача для восьми состояний для автомата, представленного в таблице 34.3, может быть решена с помощью простого эксперимента и что диагностическая задача для пяти состояний для автомата, представленного таблицей 34.6, не может быть решена с помощью простого эксперимента.

4.20. (а) Постройте минимальный (3, 2, 2)-автомат с входным алфавитом в котором имеется пара -совместимых состояний

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

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

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