Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
Задачи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 частично снабженного обозначениями дерева преемников, где 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) 4.11. Заданный автомат представлен графом переходов на рис. 3 4.3. (а) Постройте кратчайший безусловный эксперимент для распознавания начального состояния автомата, (б) Постройте кратчайший безусловный эксперимент для распознавания конечного состояния автомата. Таблица 3 4.4
Таблица 3 4.5
Таблица 3 4.6
4.12. Для автомата, заданного таблицей 3 4.6, и множества допустимых начальных состояний 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. Постройте диагностическое дерево и установочное дерево для этого автомата.
|
1 |
Оглавление
|