1. Цели освоения дисциплины
| 1.1. | Цели освоения дисциплины – дать студенту систематические знания и навыки в области теории автоматов, теории формальных языков и грамматик. Задачами дисциплины является изучение понятийного аппарата дисци-плины, основных теоретических положений и методов, привитие навыков применения теоретических знаний для решения практических задач. |
|---|
2. Место дисциплины в структуре ООП
| Цикл (раздел) ООП: Б1.О.05 |
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
| ОПК-1 | Способен применять естественнонаучные и общеинженерные знания, методы математического анализа и моделирования, теоретического и экспериментального исследования в профессиональной деятельности; |
| ОПК-1.1 | Знать: основы математики, физики, вычислительной техники и программирования |
| ОПК-1.2 | Уметь: решать стандартные профессиональные задачи с применением естественнонаучных и общеинженерных знаний, методов математического анализа и моделирования. |
| ОПК-1.3 | Владеть: навыками теоретического и экспериментального исследования объектов профессиональной деятельности |
| В результате освоения дисциплины обучающийся должен | |
| 3.1. | Знать: |
|---|---|
| 3.1.1. | - основные исторические вехи развития теории автоматов; - основные классы автоматов и их свойства; - способы задания цифровых автоматов, в том числе на языках регуляр-ных выражений алгебры событий и операторных схем алгоритмов; |
| 3.2. | Уметь: |
| 3.2.1. | - выбирать требуемые для решения конкретной задачи классы автоматов с учетом их свойств; - строить и минимизировать конечный автомат по условиям предлагае-мой задачи; - использовать методы синтеза цифровых автоматов для построения распознавателей и преобразователей и систем логического управления; - разрабатывать автоматы для решения прикладных задач. |
| 3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
| 3.3.1. | - навыками по применению различных методов построения автоматов; - навыками по применению различных методов минимизации автоматов; - навыками по синтезу и анализу структурных схем автоматов; - навыками по организации и проведению экспериментов с автоматами. |
4. Структура и содержание дисциплины
| Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
|---|---|---|---|---|---|---|
| Раздел 1. Тема 1. Введение в теорию автоматов. | ||||||
| 1.1. | Становления теории автоматов. Понятие «автомат» и «конечный автомат». Классическими задачами теории конечных автоматов. Определение абстрактного автомата. Функциональная схема абстрактного ав-томата. Примеры задания абстрактного автомата. Классификация автоматов. Автоматы Мили и Мура. Функциональная схема С-автомата. Функциональная схема порождающего автомата. Функциональная схема распознающего авто-мата. | Лекции | 4 | 2 | Л1.1, Л2.2 | |
| 1.2. | Классификация способов задания автоматов. Таблич-ный способ задания автоматов. . Матричный способ задания автоматов. Гра-фический способ задания автоматов. Примеры автоматных моделей: простей-шая ячейка памяти , модель простейшего трехразрядного счетчика, модель ав-томата по продаже напитков. | Лекции | 4 | 2 | Л1.2, Л2.2 | |
| Раздел 2. Основной раздел | ||||||
| 2.1. | Эквивалентность внутренних состояний абстрактного автомата. Минимизация абстрактного автомата. Алгоритмы минимизации ав-томата Мили и автомата Мура. Эквивалентность автоматов Мура и Мили. Пе-реход от автомата Мура к автомату Мили. Переход от автомата Мили к авто-мату Мура. | Лекции | 4 | 2 | Л1.1, Л2.2 | |
| 2.2. | Связность и достижимость автоматов. Понятие ком-позиции автоматов. Последовательное и параллельное соединение автоматов. Формы параллельного соединения автоматов. | Лекции | 4 | 2 | Л1.2, Л2.2 | |
| 2.3. | Понятие алфавитного оператора. Признаки автомат-ности алфавитного оператора. Процедура преобразования алфавитного опера-тора в автоматный. Построение автоматов по автоматному оператору. Пример построение автоматов типа Мили по автоматному оператору. Пример по-строения автомата типа Мура по автоматному оператору. | Лекции | 4 | 0 | Л1.1, Л2.2 | |
| 2.4. | Функции алгебры логики (ФАЛ). Способы задания ФАЛ: табличный, аналитический, числовой. геометрический. Минимизация функций алгебры-логики : карты Карно, метод неопределенных коэффициен-тов, метод Квайна, метод Квайна-Мак-Класки. Функции алгебры логики (ФАЛ). Способы задания ФАЛ: табличный, аналитический, числовой. геометрический. Минимизация функций алгебры-логики : карты Карно, метод неопределенных коэффициен-тов, метод Квайна, метод Квайна-Мак-Класки. | Лекции | 4 | 0 | Л1.2, Л2.2 | |
| 2.5. | Комбинационные логические схемы (КЛС). Характе-ристики КЛС. Построение элементарных автоматов на базе триггеров. | Лекции | 4 | 1 | Л1.1, Л2.2 | |
| 2.6. | Каноническая модель структурного автомата. Кано-ническая модель для автомата Мили. Алгоритм структурного синтеза автомата в рамках канонической модели. Гонки в автоматах. | Лекции | 4 | 1 | Л1.2, Л2.2 | |
| 2.7. | Декомпозиция устройств обработки цифровой ин-формации. Управляющие автоматы. Принцип действия управляющего автома-та с хранимой в памяти логикой и микропрограммное управление. Управляющие автоматы с «жёсткой логикой». Граф - схемы микропрограммных автоматов. Синтез микропрограммных автоматов по граф - схеме алгоритма. Декомпозиция устройств обработки цифровой ин-формации. Управляющие автоматы. Принцип действия управляющего автома-та с хранимой в памяти логикой и микропрограммное управление. Управляющие автоматы с «жёсткой логикой». Граф - схемы микропрограммных автоматов. Синтез микропрограммных автоматов по граф - схеме алгоритма. | Лекции | 4 | 0 | Л1.1, Л2.2 | |
| 2.8. | Определение формального языка. Типа грамматик: порождающие и распознающие. Определение автомата-распознавателя. Авто-матные и неавтоматные языки. Примеры автоматов-распознавателей. | Лекции | 4 | 1 | Л1.2, Л2.2 | |
| 2.9. | Понятие эквивалентности автоматов- распознавателей. Общая структура синхронной композиции двух конечных автоматов. Проверка с помощью синхронной композиции двух конечных ав-томатов распознавателей на их эквивалентность. Алгоритм минимизация автоматов-распознавателей. | Лекции | 4 | 1 | Л1.1, Л2.2 | |
| 2.10. | Определение недетерминированного автомата-распознавателя. Отличия детерминированного автомата-распознавателя от не-детерминированного автомата-распознавателя. Переход от недетерминиро-ванного автомата к детерминированному. Лемма о накачке (лемма о разраста-нии). | Лекции | 4 | 1 | Л2.1, Л1.2 | |
| 2.11. | Регулярные множества. Операции над регулярными множествами: объединение, конкатенация, итерация. Задание регулярных множеств. Понятие регулярного языка. Понятие регулярного выражения. Задание регулярного выражения. Примеры регулярных выражения. Теорема Клини. Построение регулярного выражении, описывающего язык, допускае-мым автоматом-распознавателем. Посторенние автомата-распознавателя, допускающий язык, описываемый заданным регулярным выражением. | Лекции | 4 | 0 | Л1.1, Л2.2 | |
| 2.12. | Назначение лексического анализатора. Понятие лек-семы. Грамматики и распознавателя лексического анализа. Основные методы лексического анализа. Взаимодействие лексического и синтаксического ана-лизаторов. Понятие токена, шаблона и лексемы. Лексические ошибки. Архи-тектура лексического анализатора. | Лекции | 4 | 1 | Л1.2, Л2.2 | |
| 2.13. | Определение формальной грамматики. Задание формального языка. Порождающая и распознающая грамматики. Виды поро-ждающих грамматик. Примеры грамматик. | Лекции | 4 | 1 | Л2.1, Л1.1 | |
| 2.14. | Задание Грамматики Хомского . Классификация грамматик Хомского. Грамматики общего вида – тип 0. Контекстно-зависимые грамматики – тип 1. Контекстно-свободные грамматики – тип 2. Регулярные грамматики – тип 3. Соотношения между типами грамматик. Рас-познающие устройства для грамматик Хомского | Лекции | 4 | 1 | Л1.2, Л2.2 | |
| 2.15. | Организация автомата с магазинной памятью. Опе-рации автомата с магазинной памятью. Связь между грамматиками и автома-тами с магазинной памятью. LL(1) – грамматики. | Лекции | 4 | 1 | Л1.1, Л2.2 | |
| 2.16. | Синтаксический разбор и синтаксический анализа-тор. Классификация методов синтаксического разбора. Последовательность разбора. Нисходящий и восходящий разборы. | Лекции | 4 | 1 | Л1.2, Л2.2 | |
| 2.17. | Способы задания абстрактных конеч-ных автоматов. Составить таблицу переходов и выходов, матрицу переходов и граф автомата для автомата с одним входом и одним выходом. | Практические | 4 | 2 | Л2.1, Л1.1 | |
| 2.18. | Композиция автоматов. Используя данные элементарных автоматов строятся последовательны и параллельные композиции различных форм. | Практические | 4 | 2 | Л1.2, Л2.2 | |
| 2.19. | Функции алгебры логики и способы их задания. | Практические | 4 | 2 | Л2.1, Л1.1 | |
| 2.20. | Канонический метод структурного синтеза конечных автоматов. | Практические | 4 | 2 | Л1.2, Л2.2 | |
| 2.21. | Автоматы-распознаватели. Автомат-ные языки. Примеры автоматов-распознавателей. | Практические | 4 | 2 | Л2.1, Л1.1 | |
| 2.22. | Недетерминированные автоматы-распознаватели | Практические | 4 | 2 | Л1.2, Л2.2 | |
| 2.23. | Лексический анализатор. | Практические | 4 | 4 | Л2.1, Л1.1 | |
| 2.24. | Грамматики Хомского. | Практические | 4 | 4 | Л1.2, Л2.2 | |
| 2.25. | Синтаксический анализатор . | Практические | 4 | 4 | Л2.1, Л1.1 | |
| 2.26. | Подготовка к лекции, под-готовка к практическому занятию | Сам. работа | 4 | 4 | Л1.2, Л2.2 | |
| 2.27. | Подготовка к лекции, под-готовка к практическому занятию | Сам. работа | 4 | 4 | Л2.1, Л1.1 | |
| 2.28. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 4 | Л1.2, Л2.2 | |
| 2.29. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 4 | Л2.1, Л1.1 | |
| 2.30. | Сам. работа | 4 | 8 | Л1.2, Л2.2 | ||
| Раздел 3. Заключительный этап | ||||||
| 3.1. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 4 | Л2.1, Л1.1 | |
| 3.2. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 4 | Л1.2, Л2.2 | |
| Раздел 4. Подготовительный этап | ||||||
| 4.1. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 3 | Л2.1, Л1.1 | |
| 4.2. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 4 | Л1.2, Л2.2 | |
| Раздел 5. Основной раздел | ||||||
5. Фонд оценочных средств
| 5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
| ОЦЕНКА СФОРМИРОВАННОСТИ КОМПЕТЕНЦИИ ОПК-1 Способен организовывать и руководить работой команды, вырабатывая командную стратегию для достижения поставленной цели ПРИМЕРЫ ЗАДАНИЙ ЗАКРЫТОГО ТИПА 1. Вопрос: Что такое детерминированный конечный автомат? a) Это математическая модель, которая описывает процесс работы машины Тьюринга. b) Это математическая модель, описывающая работу компьютера. c) Это математическая модель, в которой каждое состояние имеет только один переход по каждому возможному входу. ___ответ_: с 2. Вопрос: Чем детерминированные конечные автоматы отличаются от недетерминированных? a) В детерминированных конечных автоматах каждое состояние имеет ровно один переход для каждого возможного входа, в то время как в недетерминированных - может быть несколько переходов. b) В детерминированных конечных автоматах все переходы определяются однозначно, а в недетерминированных могут быть варианты. c) Детерминированные конечные автоматы всегда работают точно определенным образом, в то время как недетерминированные могут иметь разные результаты для одинаковых входных данных. ___ответ_:b 3. Вопрос: Как можно использовать детерминированные конечные автоматы? a) Они могут быть использованы для моделирования различных процессов, таких как обработка текста, распознавание речи и т. д. b) Они могут использоваться для создания алгоритмов, которые обрабатывают данные. ___ответ_:a 4. Недетерминированный конечный автомат - это математическая модель, в которой: а) каждое состояние имеет несколько переходов для каждого возможного входного символа; б) все переходы определены однозначно; в) каждое состояние имеет один переход для каждого возможного входного символа. ___ответ_:a 5. Основное отличие недетерминированного конечного автомата от детерминированного заключается в том, что: а) в недетерминированном автомате каждое состояние может иметь несколько переходов для одного и того же входного символа; б) в детерминированном автомате все переходы определены однозначно, а в недетерминированном могут быть варианты; в) недетерминированный автомат всегда работает точно определенным образом. ___ответ_:a 6. Недетерминированные конечные автоматы можно использовать для: а) моделирования различных процессов; б) создания алгоритмов обработки данных; в) разработки компьютерных программ. ___ответ_:a 7. В чём особенность стекового конечного автомата? a) Он имеет несколько состояний и входной алфавит. b) Он имеет один вход и несколько состояний. c) Он имеет одно состояние и стек в качестве памяти. d) Он имеет несколько входов и одно состояние. ___ответ_:b 8. Какая основная задача решается с помощью стековых конечных автоматов? a) Синтез автоматов. b) Анализ автоматов. c) Синтаксический анализ. d) Построение языков программирования. ___ответ_:c 9. Что такое конфигурация стекового конечного автомата? a) Это состояние стекового автомата и содержимое его стека. b) Это состояние автомата и входные символы. c) Это состояние автомата и выходные символы. d) Это состояние автомата и входные и выходные символы. ___ответ_:a 10. Какие функции переходов используются в стековых конечных автоматах? a) Статические и динамические. b) Линейные и нелинейные. c) Детерминированные и недетерминированные. d) Локальные и глобальные. ___ответ_:c 11. Как можно использовать стековые конечные автоматы для решения задач? a) С помощью алгоритмов, основанных на стековых автоматах, можно решать задачи, связанные с обработкой строк и грамматическим разбором. b) С помощью стековых автоматов можно ___ответ_:a 12. Что общего у автоматов Мили и Мура? а) Они оба используют таблицу переходов для определения следующего состояния. б) Они оба имеют выходные сигналы, которые зависят от текущего состояния. в) Они оба используются для моделирования систем. ___ответ_: d 13. В чем разница между автоматами Мили и Мура? а) В автомате Мили выходной сигнал зависит от текущего состояния и входного символа, а в автомате Мура - только от текущего состояния. б) В автомате Мили переход в следующее состояние зависит от входного символа, а в автомате Мура - от текущего состояния. ___ответ_:a 14. Где используются автоматы Мили и Мур? а) Автоматы Мили и Мура используются для моделирования конечных автоматов, управления устройствами и системами распознавания образов. б) Автоматы Мура используются для создания конечных автоматов, а автоматы Мили - для моделирования систем управления. ___ответ_:b 15. Какую роль играют контекстно-свободные грамматики в языке программирования? a) Их можно использовать для создания синтаксических анализаторов. b) Их можно использовать для генерации кода. c) Их можно использовать для описания структуры программы. ___ответ_: b КРИТЕРИИ ОЦЕНИВАНИЯ: Каждое задание оценивается 1 баллом. Оценивание КИМ теоретического характера в целом: • «зачтено» – верно выполнено более 50% заданий; «не зачтено» – верно выполнено 50% и менее 50% заданий; • «отлично» – верно выполнено 85-100% заданий; «хорошо» – верно выполнено 70-84% заданий; «удовлетворительно» – верно выполнено 51-69% заданий; «неудовлетворительно» – верно выполнено 50% или менее 50% заданий. ПРИМЕРЫ ЗАДАНИЙ ОТКРЫТОГО ТИПА 1. Что такое детерминированный конечный автомат (ДКА)? Детерминированный конечный автомат - это математическая модель, которая представляет собой систему с конечным числом состояний, переходов между ними и входным алфавитом. В каждый момент времени система находится в одном из состояний, и на вход подаются символы из алфавита. При этом переходы между состояниями осуществляются только в зависимости от текущего состояния и прочитанного символа, без учета предыдущих входных данных. 2. Как работает ДКА? ДКА работает путем перехода из одного состояния в другое при чтении входных символов. В каждом состоянии автомат может находиться в любом числе, но все состояния должны быть разными. При чтении входного символа автомат переходит в следующее состояние, и если есть несколько возможных переходов, выбирается только один из них. 3. В чем разница между ДКА и недетерминированным конечным автоматом (НКА)? Разница между ДКА и НКА заключается в том, что в НКА при чтении входного символа возможно несколько переходов из текущего состояния, а в ДКА переход осуществляется только в одно конкретное состояние. Это означает, что ДКА всегда имеет единственное решение, в то время как в НКА возможны различные решения. 4. Как можно проверить, является ли данный автомат ДКА или НКА? Для проверки, является ли автомат ДКА, нужно проверить, есть ли в нем состояния, из которых есть несколько переходов по одному и тому же входному символу. Если такие состояния есть, то автомат является НКА. Если же из каждого состояния есть только один переход по каждому входному символу, то автомат - ДКА. 5. Как можно использовать ДКА для решения задач? ДКА можно использовать для решения различных задач, связанных с обработкой строк, например, для проверки правильности скобочных структур, разбора языков программирования, выполнения лексического анализа и других задач. Для этого ДКА преобразуют в регулярное выражение, которое затем используют для проверки входных строк на соответствие заданному языку. 6. Что такое недетерминированный конечный автомат (НКА)? Недетерминированный конечный автомат – это математическая модель, в которой из одного состояния могут выходить несколько дуг с одним и тем же входом. 7. Как работает НКА? НКА работает по принципу перемещения между состояниями при поступлении входных символов. Но в отличие от ДКА, в НКА из одного состояния может выходить несколько дуг для одного и того же входного символа, что делает его работу менее предсказуемой. 8. Чем отличается НКА от ДКА? Основное отличие НКА от ДКА – наличие нескольких возможных переходов из одного и того же состояния, что позволяет ему обрабатывать более сложные задачи, чем ДКА, но делает его работу менее предсказуемой. 9. Можно ли проверить, является ли НКА по-настоящему недетерминированным? Чтобы проверить недетерминированность НКА, нужно проверить наличие состояний, из которых могут выходить несколько дуг с одним и тем же входным символом. Если таких состояний нет, то это значит, что НКА не по-настоящему недетерминирован. 10. Где используются НКА? НКА используются для решения различных задач в области обработки языков, например, проверки правильности скобок, лексического анализа, синтаксического разбора и т.д. 11. Что такое стековый автомат? Стековый автомат - это тип автомата, который использует стек для хранения информации о текущем состоянии. Стек - это структура данных, которая позволяет хранить и извлекать данные в порядке “последним пришел - первым ушел” (LIFO). 12. Как работают стековые автоматы? Стековые автоматы работают путем чтения входных символов и изменения состояния стека. Каждый раз, когда читается входной символ, автомат добавляет символ в стек и изменяет текущее состояние. Когда стек пуст, автомат переходит в начальное состояние. 13. Каковы преимущества использования стековых автоматов? Основным преимуществом стековых автоматов является их простота. Они не требуют большого количества памяти для хранения состояния, как это делают другие типы автоматов, и могут обрабатывать входные данные очень быстро. 14. Что такое контекстно-свободная грамматика? Контекстно-свободная грамматика - это формальная система, которая определяет язык, состоящий из строк символов. Она состоит из набора правил, каждое из которых имеет вид: A → α, где A - нетерминальный символ (начинающий правило), а α - строка символов, которая может содержать как терминальные, так и нетерминальные символы. 15. Как работает контекстно-свободная грамматика? Грамматика работает путем применения правил к строке символов. Сначала выбирается правило, у которого левая часть совпадает с текущим символом в строке. Затем этот символ заменяется на строку символов справа от знака равенства в выбранном правиле. Этот процесс повторяется до тех пор, пока вся строка не будет состоять только из терминальных символов. 16. Для чего используются контекстно-свободные грамматики? Контекстно-свободные грамматики широко используются в теории формальных языков для описания синтаксиса языков программирования. Они также применяются в компиляторах и интерпретаторах для анализа и генерации кода. 17. Каковы преимущества контекстно-свободных грамматик? Одним из главных преимуществ контекстно-свободных грамматик является их простота и понятность. Они легко читаемы и понимаемы, что упрощает их использование и модификацию. Кроме того, контекстно-свободные грамматики позволяют описывать широкий спектр языков, включая языки программирования и естественные языки. 18. Каковы недостатки контекстно-свободных грамматик? Однако контекстно-свободные грамматики имеют и свои недостатки. Один из них - сложность создания грамматик, особенно для сложных языков. Кроме того, они не всегда могут описать контекстно-зависимые языки, такие как языки с фразовой структурой. 19. Чем отличаются автоматы Мура и Мили? Автомат Мура отличается от автомата Мили тем, что в автомате Мура выходной сигнал зависит только от текущего состояния, а в автомате Мили - от текущего состояния и входного сигнала. 20. Как работают автоматы Мура и Мили? В автомате Мура при поступлении входного сигнала происходит переход в новое состояние, а затем вычисляется выходной сигнал. В автомате Мили сначала вычисляется выходной сигнал, а затем происходит переход в следующее состояние. 21. В каких задачах используются автоматы Мура и Мили? Автоматы Мура и Мили используются для моделирования различных систем, например, для разработки конечных автоматов, управляющих устройств, систем распознавания образов и др. 22. В чем преимущества автоматов Мура и Мили перед другими моделями? Преимущество автоматов Мура и Мили заключается в том, что они просты в реализации и анализе, а также позволяют моделировать системы с различными входными и выходными сигналами. 23. Какие недостатки имеют автоматы Мура и Мили? Недостатком автоматов Мура и Мили является то, что они не всегда удобны для моделирования систем с большим числом состояний и сложным поведением. В таких случаях могут потребоваться более сложные модели, например, сети Петри или системы массового обслуживания. КРИТЕРИИ ОЦЕНИВАНИЯ ОТКРЫТЫХ ВОПРОСОВ. «Отлично» (зачтено): Ответ полный, развернутый. Вопрос точно и исчерпывающе передан, терминология сохранена, студент превосходно владеет основной и дополнительной литературой, ошибок нет. «Хорошо» (зачтено): Ответ полный, хотя краток, терминологически правильный, нет существенных недочетов. Студент хорошо владеет пройденным программным материалом; владеет основной литературой, суждения правильны. «Удовлетворительно» (зачтено): Ответ неполный. В терминологии имеются недостатки. Студент владеет программным материалом, но имеются недочеты. Суждения фрагментарны. «Неудовлетворительно» (не зачтено): Не использована специальная терминология. Ответ в сущности неверен. Переданы лишь отдельные фрагменты соответствующего материала вопроса. Ответ не соответствует вопросу или вовсе не дан. |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| не предусморено |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| Промежуточная аттестация заключается в проведении в конце семестра зачета (для обучающихся, не получивших зачет по результатам текущей успеваемости) по всему изученному курсу. Зачет проводится в устной форме по билетам. В билет входит 2 вопроса: 1 вопрос теоретического характера и 1 вопрос практико-ориентированного характера. ВОПРОСЫ ТЕОРЕТИЧЕСКОГО ХАРАКТЕРА 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. Вычислительная мощность МТ. Свойства МТ. Алгоритмически разрешимые пробле-мы. Алгоритмически неразрешимые проблемы. 30. Проблемы разрешимости. 31. Регулярные выражения (РВ) и языки. Операторы РВ. Приоритеты операторов. Связь РВ, ДКА, ε-НКА, НКА. 32. Преобразование ДКА в РВ. 33. Преобразование ДКА в РВ. Метод сокращения состояний. 34. Преобразование РВ в конечный автомат. 35. Применение регулярных выражений. 36. Алгоритмические законы для РВ. 37. Свойства регулярных языков (РЯ). Лемма о накачке для РЯ. 38. Свойства замкнутости РЯ. 39. Временная сложность взаимных преобразований представлений регулярных языков. Вопросы разрешимости РЯ. 40. Контекстно-свободные грамматики (КСГ). Определение КСГ. Терминалы, перемен-ные, продукции. Проверка принадлежности цепочки языку КСГ. Порождения. Выводимые цепочки. 41. Деревья разбора. Определения. Свойства. Примеры. 42. Связь КСГ с конечными автоматами. Нормальная форма Хомского. 43. Принцип микропрограммного управления. Теорема Глушкова. Понятия операционного и управляющих автоматов. 44. Способы описания алгоритмов и микропрограмм. 45. Синтез микропрограммных автоматов по граф-схеме алгоритма. Синтез автомата Ми-ли. 46. Синтез микропрограммных автоматов по граф-схеме алгоритма. Синтез автомата Му-ра. 47. Алгебраическая структурная теория конечных автоматов. Разбиения и частично упо-рядоченные множества. Последовательная декомпозиция КА. 48. Алгебраическая структурная теория конечных автоматов. Разбиения и частично упо-рядоченные множества. Параллельная декомпозиция КА. 49. Структурный синтез КА. Канонический метод структурного синтеза. Элементарные цифровые автоматы с памятью. 50. Кодирование состояний КА. Гонки в автомате. 51. Кодирование состояний КА. Алгоритмы. ВОПРОСЫ ПРАКТИКО-ОРИЕНТИРОВАННОГО ХАРАКТЕРА *** Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}: а) множество всех цепочек, оканчивающихся на 00; Построить автомат Мура, продающий кофе(15 руб) и шоколад(10 руб), автомат принимает монеты 2/5/10 рублей. Предусмотреть варианты отмены заказа и выдачи сдачи. *** Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}: б) множество всех цепочек, содержащих три нуля подряд; Построить автомат Мура, выдающий остаток от деления вводимого десятичного числа на 3. *** Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}: в) множество цепочек, содержащих в качестве подцепочки 011. Постройте машину Тьюринга, которая на вход получает натуральное число N и отнимает от него 1 в двоичной записи. Точнее, изначально на ленте стоит знак $, за которым записано N в двоичном виде. Вначале головка в состоянии q0 обозревает $. Ваша машина должна остановиться с двоичной записью N - 1 на ленте *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: а) множество всех цепочек, в которых всякая подцепочка из пяти последовательных символов содержит хотя бы два 0; Построить КС-грамматики для следующих языков: множество всех цепочек, у которых символов 0 вдвое больше, чем символов 1. *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: б) множество всех цепочек, у которых на десятой позиции справа стоит 1; Построить КС-грамматики для следующих языков: множество {0n1n | n 1} всех цепочек из одного и более символов 0, за которыми следуют символы 1 в таком же количестве; *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: в) множество цепочек, которые начинаются или оканчиваются (или и то, и другое) последовательностью 01; Напишите регулярное выражение для описания телефонных номеров всех видов, которые только можно себе представить. Учтите международные номера, а также тот факт, что в разных странах используется разное количество цифр в кодах областей и в локальных номерах телефонов. *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: г) множество цепочек, в которых число нулей делится на пять, а число единиц — на три. Преобразуйте следующее регулярное выражение в НКА: 00(0 + 1)*. *** Опишите НКА, для языков: б) множество цепочек над алфавитом {0, 1, …, 9}, последняя цифра цепочки которых больше нигде в них не встречается; Преобразуйте следующее регулярное выражение в НКА: (0 + 1)01; *** Опишите НКА, для языков: в) множество цепочек из 0 и 1, в которых содержится два 0, разделенных позициями в количестве, кратном 4. Отметим, что нуль позиций можно также считать кратным 4. Преобразуйте следующее регулярное выражение в НКА: 01*; *** Постройте НКА, распознающие следующие множества цепочек: а) abc, abd и aacd. Входным алфавитом считать {a, b, c, d}; Напишите регулярные выражения для следующих языков: б) множество цепочек из нулей и единиц, в которых десятый от правого края символ равен 1; *** Постройте НКА, распознающие следующие множества цепочек: б) 0101, 101 и 011; Напишите регулярные выражения для следующих языков: а) множество цепочек с алфавитом {a, b, c}, содержащих хотя бы один сим-вол a и хотя бы один символ b; *** Постройте НКА, распознающие следующие множества цепочек: в) ab, bc и ca. Входным алфавитом считать {a, b, c}. Напишите регулярные выражения для следующих языков: в) множество цепочек из нулей и единиц, содержащих не более одной пары последовательных единиц. *** Постройте НКА, распознающие следующие множества цепочек: в) множество цепочек из 0 и 1, в которых хотя бы на одной из последних десяти позиций стоит 1. Напишите регулярные выражения для следующих языков: в) множество цепочек из нулей и единиц, содержащих не более одной пары последовательных единиц. *** Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}: а) множество всех цепочек, оканчивающихся на 00; Напишите регулярное выражение для описания телефонных номеров всех видов, которые только можно себе представить. Учтите международные номера, а также тот факт, что в разных странах используется разное количество цифр в кодах областей и в локальных номерах телефонов. *** Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}: б) множество всех цепочек, содержащих три нуля подряд; Построить КС-грамматики для следующих языков: множество {0n1n | n 1} всех цепочек из одного и более символов 0, за которыми следуют символы 1 в таком же количестве; *** Опишите ДКА, которые допускают следующие языки над алфавитом {0, 1}: в) множество цепочек, содержащих в качестве подцепочки 011. Построить КС-грамматики для следующих языков: множество всех цепочек, у которых символов 0 вдвое больше, чем символов 1. *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: б) множество всех цепочек, у которых на десятой позиции справа стоит 1; Постройте машину Тьюринга, которая на вход получает натуральное число N и отнимает от него 1 в двоичной записи. Точнее, изначально на ленте стоит знак $, за которым записано N в двоичном виде. Вначале головка в состоянии q0 обозревает $. Ваша машина должна остановиться с двоичной записью N - 1 на ленте *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: г) множество цепочек, в которых число нулей делится на пять, а число единиц — на три. Построить автомат Мура, выдающий остаток от деления вводимого десятичного числа на 3. *** Опишите НКА, для языков: в) множество цепочек из 0 и 1, в которых содержится два 0, разделенных позициями в количестве, кратном 4. Отметим, что нуль позиций можно также считать кратным 4. Построить автомат Мура, продающий кофе(15 руб) и шоколад(10 руб), автомат принимает монеты 2/5/10 рублей. Предусмотреть варианты отмены заказа и выдачи сдачи. *** Постройте НКА, распознающие следующие множества цепочек: а) abc, abd и aacd. Входным алфавитом считать {a, b, c, d}; Напишите регулярное выражение для описания телефонных номеров всех видов, которые только можно себе представить. Учтите международные номера, а также тот факт, что в разных странах используется разное количество цифр в кодах областей и в локальных номерах телефонов. *** Постройте НКА, распознающие следующие множества цепочек: б) 0101, 101 и 011; Построить КС-грамматики для следующих языков: множество {0n1n | n 1} всех цепочек из одного и более символов 0, за которыми следуют символы 1 в таком же количестве; *** Постройте НКА, распознающие следующие множества цепочек: в) ab, bc и ca. Входным алфавитом считать {a, b, c}. Построить КС-грамматики для следующих языков: множество всех цепочек, у которых символов 0 вдвое больше, чем символов 1. *** Постройте НКА, распознающие следующие множества цепочек: в) множество цепочек из 0 и 1, в которых хотя бы на одной из последних десяти позиций стоит 1. Постройте машину Тьюринга, которая на вход получает натуральное число N и отнимает от него 1 в двоичной записи. Точнее, изначально на ленте стоит знак $, за которым записано N в двоичном виде. Вначале головка в состоянии q0 обозревает $. Ваша машина должна остановиться с двоичной записью N - 1 на ленте *** Опишите НКА, для языков: б) множество цепочек над алфавитом {0, 1, …, 9}, последняя цифра цепочки которых больше нигде в них не встречается; Построить автомат Мура, выдающий остаток от деления вводимого десятичного числа на 3. *** Опишите ДКА, допускающие такие языки над алфавитом {0, 1}: в) множество цепочек, которые начинаются или оканчиваются (или и то, и другое) последовательностью 01; Построить автомат Мура, продающий кофе(15 руб) и шоколад(10 руб), автомат принимает монеты 2/5/10 рублей. Предусмотреть варианты отмены заказа и выдачи сдачи. |
| Приложения |
6. Учебно-методическое и информационное обеспечение дисциплины
| 6.1. Рекомендуемая литература | ||||
| 6.1.1. Основная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л1.1 | Хопкрофт, Джон | Введение в теорию автоматов, языков и вычислений: | 2-е изд.- М. : [Издат. дом] Вильямс,, 2002 | |
| Л1.2 | Ю. Г. Карпов | Теория автоматов: учеб. для вузов: | СПб. : Питер, 2002 | |
| 6.1.2. Дополнительная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л2.1 | Шевелев Ю.П. | Дискретная математика: учеб. пособие для вузов | СПб.: Лань // ЭБС "Лань", 2008 | e.lanbook.com |
| Л2.2 | Р. Г. Бухараев | Вероятностные автоматы: | Казань : Изд-во Казан. ун-та,, 1977 | |
| 6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет" | ||||
| Название | Эл. адрес | |||
| Э1 | Курс в Мудл по Теории автоматов | portal.edu.asu.ru | ||
| 6.3. Перечень программного обеспечения | ||||
| Open Office – Условия использования по ссылке http://www.openoffice.org/license.html LibreOffice Условия использования: https://ru.libreoffice.org/about-us/license/ 7-zip Условия использования: https://www.7-zip.org/license.txt Acrobat Reader Условия использования: http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf Mozila FireFox Условия использования: https://www.mozilla.org/en-US/about/legal/eula/ Chrome Условия использования: http://www.chromium.org/chromium-os/licenses Microsoft WindowsMicrosoft Office 2010 (Office 2010 Professional, № 4065231 от 08.12.2010), (бессрочно); Microsoft Windows 7 (Windows 7 Professional, № 61834699 от 22.04.2013), (бессрочно); Chrome (http://www.chromium.org/chromium-os/licenses), (бессрочно); 7-Zip (http://www.7-zip.org/license.txt), (бессрочно); AcrobatReader (http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf), (бессрочно); ASTRA LINUX SPECIAL EDITION (https://astralinux.ru/products/astra-linux-special-edition/), (бессрочно); LibreOffice (https://ru.libreoffice.org/), (бессрочно); Веб-браузер Chromium (https://www.chromium.org/Home/), (бессрочно); Антивирус Касперский (https://www.kaspersky.ru/), (до 23 июня 2024); Архиватор Ark (https://apps.kde.org/ark/), (бессрочно); Okular (https://okular.kde.org/ru/download/), (бессрочно); Редактор изображений Gimp (https://www.gimp.org/), (бессрочно) | ||||
| 6.4. Перечень информационных справочных систем | ||||
| 1 Федеральная служба государственной статистики РФ [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.gks.ru/. 2 Федеральный портал по научной и инновационной деятельности [Электронный ресурс]. -Электронные данные. - Режим доступа: http://www.sci-innov.ru/. 3 Научная и учебно-методическая литература [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.intuit.ru. 4 Научный журнал «Вестник Российской академии естественных наук» [Электрон-ный ресурс]. - Электронные данные. - Режим доступа: http://www.ras.ru/publishing/rasherald/rasherald_archive.aspx. 5 Научный журнал «Интеграл» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://www.portalnano.ru/read/databases/publication/journal_integral. 6 Научный журнал «Инновации» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://ojs.innovjoum.ru/index.php/innov 7 Научный журнал «Информатика и системы управления» [Электронный ресурс]. – Электронные данные. - Режим доступа: http://ics.khstu.ru/ 8 Научный журнал «Информационные системы и технологии» [Электронный ре-сурс]. - Электронные данные. - Режим доступа: http://gu-unpk.ru/science/joumal/isit 9 Научный журнал «Информационные технологии» [Электронный ресурс]. - Элек-тронные данные. - Режим доступа: http://novtex.ru/IT/ 10 Научный журнал «Нейрокомпьютеры: разработка, применение» [Электронный ре-сурс]. - Электронные данные. – Режим доступа: http://www.radiotec.ru/catalog.php?cat=jr7 11 Научный журнал «Программные продукты и системы» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://www.swsys.ru/ Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/) | ||||
7. Материально-техническое обеспечение дисциплины
| Аудитория | Назначение | Оборудование |
|---|---|---|
| 202С | библиотека (читальный зал) - помещение для самостоятельной работы | Учебная мебель на 53 посадочных места; компьютеры с подключением к информационно-телекоммуникационной сети «Интернет», доступом к электронной информационно-образовательной среде АлтГУ; ноутбуки (по запросу) |
| Помещение для самостоятельной работы | помещение для самостоятельной работы обучающихся | Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ |
| Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
| 001вК | склад экспериментальной мастерской - помещение для хранения и профилактического обслуживания учебного оборудования | Акустический прибор 01021; виброизмеритель 00032; вольтметр Q1202 Э-500; вольтметр универсальный В7-34А; камера ВФУ -1; компьютер Турбо 86М; масспектрометр МРС -1; осциллограф ЕО -213- 2 ед.; осциллограф С1-91; осциллограф С7-19; программатор С-815; самописец 02060 – 2 ед.; стабилизатор 3218; терц-октавный фильтр 01023; шкаф вытяжной; шумомер 00026; анализатор АС-817; блок 23 Г-51; блок питания "Статрон" – 2 ед.; блок питания Ф 5075; вакуумный агрегат; весы; вольтметр VM -70; вольтметр В7-15; вольтметр В7-16; вольтметр ВУ-15; генератор Г-5-6А; генератор Г4-76А; генератор Г4-79; генератор Г5-48; датчик колебаний КВ -11/01; датчик колебаний КР -45/01; делитель Ф5093; измеритель ИМП -2; измеритель параметров Л2-12; интерферометр ИТ 51-30; источник "Агат" – 3 ед.; источник питания; источник питания 3222; источник питания ЭСВ -4; лабораторная установка для настройки газовых лазеров; лазер ЛГИ -21; М-кальк-р МК-44; М-калькул-р "Электроника"; магазин сопротивления Р4075; магазин сопротивления Р4077; микроскоп МБС -9; модулятор МДЕ; монохроматор СДМС -97; мост переменного тока Р5066; набор цветных стекол; насос вакумный; насос вакуумный ВН-01; осциллограф С1-31; осциллограф С1-67; осциллограф С1-70; осциллограф С1-81; осциллоскоп ЕО -174В – 2 ед.; пентакта L-100; пирометр "Промень"; пистонфон 05001; преобразователь В9-1; прибор УЗДН -2Т; скамья оптическая СО 1м; спектограф ДФС -452; спектограф ИСП -51; стабилизатор 1202; стабилизатор 3217 – 4 ед.; стабилизатор 3218; стабилизатор 3222 – 3 ед.; станок токарный ТВ-4; усилитель мощности ЛВ -103 – 4 ед.; усилитель У5-9; центрифуга ВЛ-15; частотомер Ч3-54А; шкаф металлический; эл.двигатель; электродинамический калибратор 11032 |
8. Методические указания для обучающихся по освоению дисциплины
| Не требуются |