Вопросы по конечным автоматам (Бабаш)

2010

1. Множество. Операции над подмножествами.

2. Бинарная операция на М (множестве).

3. Бинарное отношение на множестве М.

4. Бинарное отношение эквивалентности.

5. Разбиение множества.

6. Связь разбиений множества с бинарными отношениями эквивалентности.

7. Определение автомата Милли.

8. Определение автомата Мура.

9. Автономный автомат.

10. Граф переходов автомата.

11. Шифрующий автомат.

12. Периоды последовательности состояний при заданной периодической последовательности.

    Основные понятия теории автоматов:

13. Основные определения, примеры.

14. Подавтоматы, гомоморфизмы и конгруэнции.

15. Операции с автоматами.

16. Способы задания автоматов.

    Привести примеры.

    Автоматные базисы и проблемы полноты, декомпозиция автоматов:

17. Декомпозиция автоматов.

    Привести примеры.

    Эквивалентность в автоматах:

18. Эквивалентность состояний автоматов.

19. Эквивалентность автоматов.

20. Обобщение понятий эквивалентности и гомоморфизма автоматов.

    Привести примеры.

    Свойства автоматных отображений.

21. Восстановление автомата по автоматным отображениям.

22. Представимость автоматных отображений и событий в автоматах.

23. Обратимость автоматов и автоматы без потери информации.

24. Память автоматов.

    Привести примеры.