Выхованец В.С. Сборник задач по теории автоматов Учебное пособие для вузов.
Оглавление
ПРЕДИСЛОВИЕ…………………………………………………………………………………………………………………………………………………….. 2
Раздел 1. Формальные языки и грамматики…………………………………………………………………………………. 3
СКАЧАТЬ!
Занятие 1.1. Формальные языки……………………………………………………………………………………………………………………. 3
Занятие 1.2. Формальные системы……………………………………………………………………………………………………………… 5
Занятие 1.3. Формальные грамматики………………………………………………………………………………………………………. 6
Занятие 1.4. Контекстно-свободные грамматики………………………………………………………………………………….. 8
Занятие 1.5. Разрешимость языков…………………………………………………………………………………………………………… 13
Раздел 2. Основы общей теории автоматов………………………………………………………………………………. 19
Занятие 2.1. Машина Тьюринга (МТ)………………………………………………………………………………………………………… 19
Занятие 2.2. Сети Петри……………………………………………………………………………………………………………………………….. 21
Занятие 2.3. Магазинный автомат (МА)…………………………………………………………………………………………………. 25
Занятие 2.4. Конечный автомат (КА)……………………………………………………………………………………………………….. 29
Раздел 3. Конечные автоматы……………………………………………………………………………………………………………. 32
Занятие 3.1. Минимизация автоматов……………………………………………………………………………………………………. 32
Занятие 3.2 Автомат Мура………………………………………………………………………………………………………………………….. 35
Занятие 3.3. Детерминация источников………………………………………………………………………………………………….. 36
Раздел 4. структурный синтез автоматов………………………………………………………………………………….. 39
Занятие 4.1. Синтез комбинационных автоматов………………………………………………………………………………… 39
Занятие 4.2 Синтез асинхронных автоматов……………………………………………………………………………………….. 42
Занятие 4.3 Синтез синхронных автоматов………………………………………………………………………………………….. 44
СПИСОК ЛИТЕРАТУРЫ…………………………………………………………………………………………………………………………………… 47
В последнее время инженеры, занимающиеся прикладными исследованиями, все больше используют аппарат теории автоматов. Это объясняется необходимостью создания и эксплуатации современной вычислительной техники, средств передачи и обработки информации, автоматизированных систем управления и проектирования. Наконец, в современной математической науке исследования в областях, традиционно относящихся к дискретной математике (формальные языки и грамматики, общая теория алгоритмов, теория конечных автоматов, трудоемкость вычислений и т.д.), занимают все более заметное место.
Цель создания учебного пособия — научить студентов решать задачи из теории автоматов, где под автоматом понимается любой преобразователь дискретной информации, имеющий входной и выходной каналы данных и находящийся в каждый дискретный момент времени в одном из допустимых состояний. В связи с общностью и универсальностью моделей, рассматриваемых в теории автоматов, представляется целесообразным создание учебного пособия для студентов, где основы перечисленных разделов дискретной математики излагались бы с единых позиций и в доступной форме, но достаточно полно и строго.
Данное учебное пособие включает методы решения ряда практических задач. Рассмотрен практический аспект проектирования дискретных устройств. Материал, приведенный в учебном пособии, разбит на введение и четыре раздела. Во введении рассматриваются предмет и метод теории автоматов, на неформальном уровне вводятся основные понятия, обсуждается концепция порождения и распознавания. В первом разделе рассматриваются задачи из области формальных языков и грамматик. Второй раздел посвящен основам общей теории алгоритмов. В третьм разделе изучаются конечные автоматы, а в четвертом — теоретические основы проектирования дискретных устройств.
При написании учебного пособия в значительной мере использовался опыт чтения автором курса по теории автоматов на инженерно-техническом факультете Приднестровского государственного университета им. Т. Г. Шевченко.
