- •Глава 4. Автоматы
- •§ 4.1. Автоматы: определение, примеры, способы задания
- •4.1.1 Определение и примеры автоматов
- •4.1.2. Диаграмма Мура и таблица автоматов
- •§ 4.2. Отличимость состояний автомата
- •4.2.1 Продолжение функций и
- •4.2.2. Приведённый автомат
- •4.2.3. Периодичность выходной последовательности конечного автомата
- •4.2.4. Теоремы Мура
- •4.3. Ограниченно детерминированные функции. Информационное дерево
- •Задачи для самостоятельного решения
- •§ 4.4. Синтез автоматов
- •Задачи для самостоятельного решения
- •§ 4.5. Алгебраический подход к теории автоматов
- •Упражнения для самостоятельного решения
Упражнения для самостоятельного решения
Полигон над полугруппой называется циклическим, если существует такое что Доказать, что если циклический полигон над группой с единицей и для всех то для некоторой подгруппы группы
Указание.
Пусть – полигон над полугруппой являющейся коммутативной полугруппой идемпотентов (т.е. и для всех Доказать, что будет являться частично упорядоченным множеством, если положить
Что из себя представляет полугруппа переходов автомата, диаграмма Мура которого изображена на рисунке 4.43?
Ответ: группа из 2 элементов.
Назовём полугруппу полугруппой правых нулей, если для всех Пусть – полигон над полугруппой правых нулей. Для пусть
а) Доказать, что – отношение эквивалентности.
б) Доказать, что при любых
в) Доказать, что для любого множество пересекается с каждым -классом ровно по одному элементу.
г) Доказать, что – конгруэнция полигона