Задачи

3.1. Покажите, что если

3.2. Используя симметричность графа переходов, показанного на рис. 3 3.1, покажите, что

Рис. 3 3.1.

3.3. В подтаблице автомата М все строки одинаковы. Покажите, что М представляет собой тривиальный автомат.

3.4. Покажите, что если строки матрицы одинаковы, то состояния автомата М являются эквивалентными.

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

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

3.7. Автомат М имеет 1-эквивалентные классы содержит состояний. Сосчитайте число строк в таблице пар для М.

3.8. Разбиение автомата с n состояниями имеет r классов. (а) Если каково минимальное число классов в (б) Если каково максимальное число состояний в одном классе P? (в) Каково наименьшее значение k, при котором является заведомо одинаковым с

3.9. Таблица 3 3.1 представляет собой частично заполненную таблицу автомата с шестью состояниями. Определите 2-эквивалентное разбиение этого автомата.

Таблица 3 3.1

Таблица 3 3.2

3.10. Найдите эквивалентное разбиение автомата, определенного таблицей 3 3.2: (а) построением таблиц, (б) методом таблицы пар.

3.11. Определите эквивалентное разбиение автомата, определенного графом на рис. 3 3.2: (а) построением таблиц, (б) методом таблицы пар, (в) катричным разбиением.

3.12. Покажите, что если

3.13. Рис. 3 3.3 представляет собой граф переходов автомата с четырьмя состояниями. Постройте граф переходов автомата с пятью состояниями, эквивалентный заданному на рис. 3 3.3.

3.14. Каждое состояние автомата эквивалентно некоторому состоянию автомата Покажите, что автомат эквивалентен либо изолированному, либо тупиковому подавтомату

3.15. Пусть состояние а; автомата эквивалентно состоянию автомата Известно, что имеется некоторая входная последовательность, которая проводит через все состояния и в то же время проводит через все состояния Покажите, что

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

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

3.18. Покажите, что если представляет собой минимальную форму автомата

Рис. 3.3.2

Рис. 3 3.3.

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

3.20. Дано два автомата (не обязательно минимальных); сформулируйте алгоритм для определения, являются они изоморфными или нет.

Рис. 3.3.4.

3.21. Определите минимальные формы автоматов, заданных в задачах 1.2-1.9 главы 1.

3.22. Постройте таблицу, граф и матрицу переходов минимальной формы автомата, показанного на рис. 3 3.2.

3.23. Сформулируйте правило определения всех явно эквивалентных пар состояний по таблице пар.

3.24. Получите минимальную форму автомата, изображенного на рис. 3 3.2, методом последовательного объединения, описанным в § 3.13.