3. Место дисциплины в структуре ООП
Дисциплина «Теория автоматов» входит в цикл дисциплин Б1.В.ДВ. Для
освоения дисциплины необходимы знания, полученные при изучении
следующих дисциплин:
Для освоения дисциплины необходимы знания, полученные при изучении следующих дисциплин:
Для освоения дисциплины необходимы знания, полученные при изучении следующих дисциплин:
Математика; Дискретная математика; Алгебра и геометрия.
Дисциплина "Теория автоматов" изучается в 7семестре, следующие за ней и опирающиеся на нее дисциплины отсутствуют.
6
4. Лабораторный практикум
Лабораторный практикум дисциплины "Теория автоматов" позволяет получить практические навыки синтеза комбинационных схем и конечных автоматов и минимизации конечных автоматов.
4.1 Порядок выполнения лабораторных работ
1)изучить теоретический материал по теме лабораторной работы;
2)Выполнить предложенное преподавателем задание;
3)составить и защитить отчет по лабораторной работе.
4.2 |
Лабораторные работы |
|
||
|
|
Лабораторные работы |
||
|
|
|
|
|
№ |
|
Разделы и темы |
Наименование лабораторных работ |
|
занятия |
дисциплины |
|||
|
||||
|
|
8 семестр |
||
|
|
Раздел 2. Автоматы с памятью, их синтез |
||
1 |
|
Тема 2.1. Комбинационные |
Анализ и синтез комбинационных схем |
|
|
схемы (автоматы без памяти). |
|||
|
|
|
||
|
|
|
|
|
2 |
|
Тема 2.2. Основные понятия |
Задание автоматов таблицами |
|
|
теории конечных автоматов. |
переходов и выходов и графами |
||
|
|
|||
3 |
|
Автоматы Мили и Мура. |
Минимизация автоматов |
|
|
Минимизация автоматов |
|||
|
|
|
||
|
|
Тема 2.3. Элементы памяти |
|
|
4 |
|
цифровых автоматов. |
Триггеры разных типов |
|
|
|
Триггеры |
|
|
5 |
|
Тема 2.4. Синтез автоматов с |
Синтез автоматов Мили и Мура на |
|
|
использованием триггеров |
триггерах |
||
|
|
|||
6 |
|
Тема 2.4. Синтез автоматов с |
Синтез автоматов Мили и Мура на |
|
|
использованием триггеров |
триггерах |
||
|
|
|||
|
|
|
|
|
Лабораторная работа № 1. Анализ и синтез комбинационных схем.
Цель работы: изучение анализа и синтеза комбинационных схем, реализующих данную логическую функцию.
Задание: Выполнить анализ и синтез комбинационных схем в соответствии с заданием, выданным преподавателем.
7
Литература: основная литература [1], дополнительная [1-3]
Лабораторная работа № 2. Задание автоматов таблицами переходов и выходов и графами
Цель работы: научиться строить таблицы переходов и выходов и графы переходов и выходов по описанию работы конечного автомата.
Задание: построить таблицы переходов и выходов и графы переходов и выходов по описанию работы конечного автомата в соответствии с заданием, выданным преподавателем.
Литература: основная литература [1], дополнительная [1-3]
Лабораторная работа № 3. Минимизация автоматов.
Цель работы: освоение алгоритма минимизации конечного автомата. Задание: Минимизировать конечный автомат в соответствии с заданием, предложенным преподавателем.
Литература: основная литература [1], дополнительная [1-3]
Лабораторная работа № 4. Триггеры разных типов.
Цель работы: изучение логики работы триггеров разных типов.
Задание: изучить логику работы (таблицы переходов и выходов, функции возбуждения) RS-триггера, D-триггера, T-триггера, JK-триггера и схемы реализации триггеров на логических элементах и задержке в цепи обратной связи.
Литература: основная литература [1], дополнительная [1-3]
Лабораторная работа № 5. Синтез автоматов Мили на триггерах.
Цель работы: изучение синтеза автоматов Мили на триггерах.
Задание: синтезировать автомат Мили на триггерах данного типа в соответствии з заданием, предложенным преподавателем.
Литература: основная литература [1], дополнительная [1-3]
Лабораторная работа № 6. Синтез автомата Мура на триггерах.
Цель работы: изучение синтеза автомата Мура на триггерах.
Задание: синтезировать автомат Мура на триггерах данного типа в соответствии з заданием, предложенным преподавателем.
Литература: основная литература [1], дополнительная [1-3]
8
5.Контрольные вопросы
1.Алфавит, строка, язык. Конкатенация строк. Замыкание Клини.
2.Регулярные выражения и регулярные языки.
3.Коды. Префиксные, суффиксные, инфиксные коды. Однозначно декодируемые коды.
4.Автоматы-распознаватели, их графы.
5.Алгоритм построения регулярного выражения по графу автоматараспознавателя.
6.Алгоритм построения графа автомата, распознающего регулярный язык, задаваемый регулярным выражением.
7.Алгоритмы построения автоматов, распознающих объединение, пересечение, разность регулярных языков.
8.Алгоритм построения автомата, распознающего конкатенацию регулярных языков.
9.Алгоритм построения автомата, распознающего замыкание Клини регулярного языка.
10.Детерминированные и недетерминированные автоматы. Алгоритм построения графа детерминированного автомата по графу недетерминированного автомата.
11. Формальные грамматики, терминальные и нетерминальные символы, продукции.
12.Деревья грамматического разбора.
13.Контекстно-зависимые и контекстно-свободные грамматики. Регулярные грамматики.
14.Конечный автомат в общем случае. Автоматы Мили и Мура. Задание автоматов таблицами переходов и выходов. Граф конечного автомата.
15.Минимизация конечных автоматов.
16.Понятие о структурном синтезе автоматов.
17.RS-триггер.
18.T-триггер.
19.D-триггер.
20.Синтез автомата на триггерах. Как строятся функции возбуждения триггеров.
6.Критерии оценки выполнения лабораторных работ
5«отлично»: выполнены все задания лабораторной работы, студент четко и без ошибок ответил на все контрольные вопросы.
4 «хорошо»: выполнены все задания лабораторной работы; студент
ответил на все контрольные вопросы с замечаниями.
9
3«удовлетворительно»: выполнены все задания лабораторной работы
сзамечаниями; студент ответил на все контрольные вопросы с замечаниями.
2«неудовлетворительно»: студент не выполнил или выполнил неправильно задания лабораторной работы; студент ответил на контрольные вопросы с ошибками или не ответил на контрольные вопросы.
10