Тематика и разделы самостоятельной работы
Теория автоматов и формальных языков
для студентов специальности
231000.62 «Программная инженерия»
| Разработчик: профессор ____________ И.А. Ходашинский |
Томск – 2012
Содержание
Введение …………………………………………………………….……3
Цели и задачи дисциплины ……...........................................................…4
Содержание разделов дисциплины …………………………………….5
Тематика и разделы самостоятельной работы.........................................6
Темы контрольных работ.……...…..…………………………………….7
Темы индивидуальных заданий …………………….…….……...…..…8
Темы командных заданий……………………………………….………..9
Вопросы на зачет………………………………………..……………….10
Рейтинговая система оценки успеваемости студентов………………..11
Список рекомендуемой литературы…………………………………….12
Введение
В процессе подготовки и выполнения самостоятельных работ формируются следующие компетенции:
1) овладение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения (ОК-1);
2) готовность к кооперации с коллегами, работе в коллективе (ОК-3);
3) понимание основных концепций, принципов, теорий и фактов, связанных с информатикой (ПК-1);
4) способность к формализации в своей предметной области с учетом ограничений используемых методов исследования (ПК-2);
5) навыки моделирования, анализа и использования формальных методов конструирования программного обеспечения (ПК-12).
Формы контроля компетенций — защита отчетов по самостоятельным работам.
Цели и задачи дисциплины
Развитие теоретических представлений и практических навыков применения регулярных и контекстно-свободных языков, конечных автоматов и автоматов с магазинной памятью, конечных преобразователей и преобразователей с магазинной памятью.
Содержание разделов дисциплины
| Наименование разделов | Содержание разделов | Трудоемкость, час | Форми- руемые компе- тенции (ОК, ПК) |
| 1. Вводная часть | Основные понятия теории формальных языков. Алфавит, слово, язык. Способы определения языков. Грамматики. Определение формальной порождающей грамматики Хомского. Иерархия Хомского для формальных грамматик. Распознаватели. Общая структура, конфигурация, такт. Иерархия языков, грамматик, распознавателей. | ОК-1, ПК-1, ПК-2, ПК-12 | |
| 2. Регулярные языки, конечные автоматы | Регулярные языки. Регулярные множества, регулярные выражения. Регулярные грамматики. Конечные автоматы. Общая структура, конфигурация, такт. Недетерминированный и детерминированный конечный автомат. Эквивалентность языков задаваемых регулярной грамматикой и конечным автоматом. Приемы построения грамматик. | ОК-1, ПК-1, ПК-2, ПК-12 | |
| 3 Контекстно-свободные языки | Контекстно-свободные языки. Деревья выводов. Нормальная форма Хомского. Нормальная форма Грейбах. Автомат с магазинной памятью. Общая структура, конфигурация, такт. Детерминированный и недетерминированный автомат с магазинной памятью. Расширенный автомат с магазинной памятью. Эквивалентность языков задаваемых КС-грамматикой и автоматом с магазинной памятью. | ОК-1, ПК-1, ПК-2, ПК-12 | |
| 4. Теория перевода | Понятие перевода. Формализмы, используемые для определения перевода. Схемы синтаксически управляемого перевода. Конечные преобразователи. Преобразователи с магазинной памятью. | ОК-1, ПК-1, ПК-2, ПК-12 |
Тематика и разделы самостоятельной работы
| Раздел дисциплины | Тематика самостоятельной работы | Трудо- емкость час | Компе- тенции ОК, ПК | Контроль выполнения работы |
| 1. Вводная часть | Индивидуальное задание. Основные части компилятора. Лексический анализ. Работа с таблицами. Синтаксический анализ. Генерация промежуточного кода. Оптимизация кода. Анализ и исправление ошибок. | ОК-1, ПК-1 | Защита задания | |
| Проработка лекционного материала. Подготовка к контрольной работе 1 | ОК-1, ПК-1 | Контрольная работа 1 | ||
| 2. Регулярные языки, конечные автоматы | Проработка лекционного материала. Подготовка к контрольной работе 2 | ОК-1, ПК-1 | Контрольная работа 2 | |
| Индивидуальное задание. Автоматы Мили. Автоматы Мура | ОК-1, ПК-1, ПК-2 | Защита задания | ||
| 3. Контекстно-свободные языки | Индивидуальное задание. Индексные грамматики. Вероятностные грамматики. Атрибутивные грамматики. | ОК-1, ПК-1, ПК-2, ПК-12 | Защита задания | |
| Проработка лекционного материала. Подготовка к контрольной работе 3 | ОК-1, ПК-1 | Контрольная работа 3 | ||
| 4. Теория перевода | Командное задание. Грамматики простого предшествования. Грамматики расширенного предшествования. | ОК-1, ОК-3, ПК-1, ПК-12 | Защита командного задания | |
| Командное задание. Грамматики слабого предшествования. Грамматики ограниченного правого контекста. | ОК-1, ОК-3, ПК-1, ПК-2, ПК-12 | Защита командного задания | ||
| Проработка лекционного материала. Подготовка к контрольной работе 4 | ОК-1, ПК-1 | Контрольная работа 4 |
Темы контрольных работ
1. Регулярные выражения, приемы построения регулярных грамматик.
2. Способы задания языков на основе конечного автомата.
3. Способы задания языков на основе КС-грамматики.
4. Способы задания языков на основе автоматас магазинной памятью.