Шпаргалка по теории автоматов (ТА)

Каждый вопрос размещен на одной отдельной странице (кроме одного - "Алгебраическая и структурная теория КА", который занимает две страницы). Формат шпаргалки: doc.

Далее приведен список вопросов, на которые есть ответы в данной шпаргалке.

Вопросы шпаргалки

1. Предмет теории автоматов
2. Классификация автоматов
3. Приложения теория автоматов
4. Двоичное умножение
5. Умножение в инверсных кодах
6. Деление
7. Деление в инверсных кодах. Особенности
8. Особенности выполнения операций в формате с плавающей запятой
9. Двоично-десятичные коды. Сложение в ДДК
10. Модель дискретного преобразователя Глушкова
11. Микропрограммирование
12. Структуры операционных автоматов
13. Синтез операционного автомата (ОА) процедурного типа
14. Синтез ОА структурного типа
15. Автоматные языки. Формальное задание Автомата
16. Модели автоматов Мили и Мура
17. Эквивалентность конечных автоматов (КА). Теорема Мура
18. Минимизация конечных автоматов
19. Эквивалентность автомата Мили и Мура
20. Виды управляющего автомата (УА)
21. Структурные схемы УА. Мили и Мура
22. Этапы синтеза управляющего автомата с жесткой логикой (УАЖЛ)
23. Примеры синтеза УАЖЛ
24. Гонки и способы борьбы с ними
25. УА с программируемой логикой (УАПЛ)
26. Алгебраическая и структурная теория КА
27. Объединение нескольких УА в один
28. Программная реализация КА. Варианты реализации. Шаблон Состояние
29. Назначение и краткая характеристика VHDL
30. Реализация УА на VHDL
31. Понятие о языке моделирования UML
32. Понятие о языках и формальных грамматиках
33. Классификация языков
34. Лемма о накачке
35. Понятие о НКА. Получение ДКА по НКА
36. Регулярные выражения. Синтаксические диаграммы. Теорема Клини
37. Применение РВ. Различные нотации РВ
38. КС-грамматики и магазинные автоматы
39. Машины Тьюринга
40. Использование МТ для анализа алгоритмов

Далее приведен ответ на первый вопрос в качестве примера.

Пример вопроса из шпаргалки

Предмет теории автоматов

Автомат – объект (идеальный, материальный или более конкретно – устройство), осуществляющий переработку информации.

Изучение способов преобразования информации является предметом теории автоматов  в широком смысле.

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

Теория автоматов использует различные математические модели. Наиболее общие из них изучают абстрактная теория автоматов и алгебраическая ТА.

С точки зрения абстрактной ТА автомат представляет собой совокупность множеств и отображений. Например, автомат может задаваться как шестерка объектов: А = <X, Y, Q, q0, A, B>, где:

• X – множество входных символов автомата
• Y – множество выходных символов автомата
• Q – множество состояний автомата
• q0 – начальные состояния автомата
• A – функция перехода: Q x X -> Q
• B – функция выхода: Q x X -> Y

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

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

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

Можно выделить следующие виды Теорий Автоматов:

• Абстрактные ТА (математические);
• Структурные ТА (технические);
• Общие ТА;
• Прикладные ТА;

ПТЦА - дискретный автомат – устройство, выполняющее преобразование цифровой информации по заданному алгоритму.

ТТ-автомат – устройство, выполняющее преобразование (распознавание) входных слов (текста).