Учебная программа Дисциплины б6 «Теория автоматов и формальных я

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

Радиофизический факультет

Кафедра математики

УТВЕРЖДАЮ

Декан радиофизического факультета

____________________Якимов А.В.

«18» мая 2011 г.

Учебная программа

Дисциплины Б2.Б6 «Теория автоматов и формальных языков»

по направлению 010300 «Фундаментальная информатика и информационные технологии»

Нижний Новгород

2011 г.

1. Цели и задачи дисциплины

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

2. Место дисциплины в структуре программы бакалавра

Дисциплина «Теория автоматов и формальных языков» относится к дисциплинам базовой части математического и естественнонаучного цикла основной образовательной программы по направлению 010300 «Фундаментальная информатика и информационные технологии», преподается в 4 семестре.

Знания, полученные при изучении курса «Теория автоматов и формальных языков», необходимы для изучения дисциплин «Программная инженерия», «Алгоритмы и анализ сложности», «Архитектура вычислительных систем», «Операционные системы», а также курсов «Компьютерная графика», «Интеллектуальные системы» и отдельных разделов дисциплин по выбору и дисциплин профилей.

Преподавание курса строится с учетом того, что студенты получили необходимые знания из курсов дисциплин «Дискретная математика» и «Основы программирования».

3. Требования к уровню освоения содержания дисциплины

В результате освоения дисциплины «Теория автоматов и формальных языков» формируются следующие компетенции:

владеть основными методами, способами и средствами получения, переработки информации, иметь навыки работы с компьютером как средством управления информацией (ОК–12);

способность применять в профессиональной деятельности современные языки программирования, способность исследовать и разрабатывать модели, алгоритмы, методы и программные решения по тематике проводимых научно-исследовательских проектов (ПК–1);

способность профессионально решать задачи производственной и технологической деятельности, включая: разработку алгоритмических, программных решений в области системного и прикладного программирования, разработку математических, информационных и имитационных моделей (ПК–2);

способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат, фундаментальные концепции и системные методологии, способность использовать современные инструментальные и вычислительные средства (ПК–4);

способность профессионально владеть базовыми математическими знаниями и информационными технологиями, эффективно применять их для решения научно-технических задач и прикладных задач, связанных с развитием и использованием информационных технологий (ПК–8);

понимание концепций и абстракций математическая логики и теории алгоритмов, теорию автоматов и формальных языков, способность использовать их в практической деятельности (ПК–15).

В результате изучения дисциплины студенты должны:

знать классификацию грамматик в соответствии с иерархией Хомского;

уметь задавать язык с помощью грамматики и регулярного выражения, а также строить конечные автоматы требуемого вида (детерминированные, полные, минимальные) для распознавания различных языков;

научиться определять, являются ли автоматными данные словарные функции и языки;

освоить алгоритмы построения конечного автомата по праволинейной грамматике и наоборот, автомата с магазинной памятью по контекстно-свободной грамматике и наоборот;

знать основные алгоритмически разрешимые и неразрешимые проблемы теории автоматов и формальных языков.

4. Объём дисциплины и виды учебной работы:

Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.

Виды учебной работы

Всего часов

Семестры

Общая трудоемкость дисциплины

108

4

Аудиторные занятия

51

51

Лекции

34

34

Практические занятия (ПЗ)

17

17

Семинары (С)

Лабораторные работы (ЛР)

Другие виды аудиторных занятий

Самостоятельная работа

57

57

Курсовой проект (работа)

Расчетно-графическая работа

Реферат

Другие виды самостоятельной работы

Вид итогового контроля (зачет, экзамен)

зачет

зачет

5. Содержание дисциплины

5.1. Разделы дисциплины и виды занятий

№ п/п

Раздел дисциплины

Лекции

ПЗ (или С)

ЛР

0

Введение

3

3

1

Конечные автоматы.

8

3

2

Свойства автоматных языков.

4

3

3

Регулярные выражения.

3

2

4

Минимизация детерминированных конечных автоматов.

3

2

5

Контекстно-свободные (КС) грамматики и языки.

4

1

6

Свойства КС-языков.

3

1

7

Автоматы с магазинной памятью.

3

2

8

Связь теории автоматов и формальных языков с теорией алгоритмов.

3

5.2. Содержание разделов дисциплины

Раздел 0. Введение.

Начальные понятия теории формальных языков. Понятие грамматики. Классы грамматик. Иерархия Хомского.

Раздел 1. Конечные автоматы.

1.1. Автоматы-преобразователи.

Понятие автомата. Автоматы и словарные функции. Критерий автоматности словарной функции. Построение диаграммы Мура для ограниченно-детерминированных функций. Автоматы с несколькими входами и выходами. Реализация сложения с помощью конечного автомата и невозможность реализовать умножение.

1.2. Автоматы-распознаватели.

Недетерминированные и детерминированные автоматы-распознаватели. Автоматы и автоматные языки.

Раздел 2. Свойства автоматных языков.

Свойства замкнутости класса автоматных языков (достаточные условия автоматных языков). Лемма о разрастании для автоматных языков (необходимое условие автоматных языков). Гомоморфизмы и автоматные языки.

Раздел 3. Регулярные выражения.

Определение регулярного выражения. Свойства регулярных выражений. Критерий регулярности языка.

Раздел 4. Минимизация детерминированных конечных автоматов.

Критерий автоматности языка в терминах правых контекстов. Построение минимальных детерминированных конечных автоматов.

Раздел 5. Контекстно-свободные (КС) грамматики и языки.

Деревья вывода. Однозначность контекстно-свободных грамматик. Устранение бесполезных символов и эпсилон-правил в КС-грамматиках. Нормальная форма Хомского.

Раздел 6. Свойства контекстно-свободных языков.

Лемма о разрастании для КС-языков. Свойства замкнутости класса контекстно-свободных языков.

Раздел 7. Автоматы с магазинной памятью.

Определение автомата с магазинной памятью (МП-автомата). Характеризация КС-языков. Детерминированные МП-автоматы. Применение МП-автоматов.

Раздел 8. Связь теории автоматов и формальных языков с теорией алгоритмов.

Машина Тьюринга как разновидность МП-автомата. Алгоритмически разрешимые и неразрешимые проблемы теории автоматов и формальных языков.

5.3. Темы практических занятий

Начальные понятия теории формальных языков.

Эквивалентность и виды грамматик.

Конечные автоматы-преобразователи. Построение диаграмм Мура для ограниченно-детерминированных функций.

Автоматы-распознаватели и автоматные языки. Детерминированные автоматы. Свойства автоматных языков.

Контрольная работа по темам четырех предыдущих занятий.

Регулярные выражения.

Минимизация детерминированных конечных автоматов. Контекстно-свободные грамматики и языки.

Автоматы с магазинной памятью.

6. Лабораторный практикум

Не предусмотрен.

7. Учебно-методическое обеспечение дисциплины

7.1. Рекомендуемая литература

а) основная литература:

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1: Синтаксический анализ. М.: Мир, 1978. – 612 с.

Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002. – 528 с.

Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: Учебное пособие. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. – 247 с.

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд., переработанное и дополненное.

Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. — М.: Радио и связь, 1988. – 128 c.

б) дополнительная литература:

Гладкий А.В. Формальные грамматики и языки.– М.: Наука, 1973.– 368c.

Минский М. Вычисления и автоматы. — М.: Мир, 1971.

8. Вопросы для контроля

1. Начальные понятия теории формальных языков.

2. Понятие грамматики. Классы грамматик. Иерархия Хомского.

3. Конечный автомат-преобразователь: определение и способы задания.

4. Автоматы и словарные функции. Детерминированные и ограниченно-детерминированные функции. Критерий автоматности словарной функции.

5. Построение диаграмм Мура для ограниченно-детерминированных функций.

6. Автоматы с несколькими входами и выходами. Реализация сложения и нереализуемость умножения с помощью конечного автомата.

7. Недетерминированные автоматы-распознаватели.

8. Автоматы и автоматные языки.

9. Детерминированные и полные автоматы-распознаватели.

10. Свойства замкнутости класса автоматных языков.

11. Лемма о разрастании для автоматных языков.

12. Гомоморфизмы и автоматные языки.

13. Регулярные выражения: определение и свойства.

14. Критерий регулярности языка.

15. Критерий автоматности языка в терминах правых контекстов.

16. Построение минимальных детерминированных конечных автоматов.

17. Контекстно-свободные (КС) грамматики и деревья вывода.

18. Однозначные, неоднозначные и существенно неоднозначные контекстно-свободные грамматики.

19. Устранение бесполезных символов в КС-грамматиках.

20. Устранение эпсилон-правил в КС-грамматиках.

21. Нормальная форма Хомского в КС-грамматиках.

22. Лемма о разрастании для КС-языков.

23. Свойства замкнутости класса КС-языков.

24. Определение автомата с магазинной памятью (МП-автомата).



Страницы: 1 | 2 | Весь текст