Модели вычислений — различия между версиями
Материал из Кафедра математической кибернетики
(→Литература) |
(→Формальные грамматики и языки) |
||
| Строка 28: | Строка 28: | ||
=== Формальные грамматики и языки === | === Формальные грамматики и языки === | ||
<ol start="16"> | <ol start="16"> | ||
| − | <li> | + | <li> Формальные грамматики: основные понятия. Классификация Хомского формальных грамматик (иерархия Хомского). |
| − | <li> | + | <li> Праволинейные грамматики и языки. Совпадением класса праволинейных языков и класса автоматных языков. Разрешимость проблем принадлежности и эквивалентности для класса праволинейных языков. |
| − | <li> | + | <li> Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся автоматными. |
| − | <li> | + | <li> Контекстно-свободные грамматики и языки. Примеры контекстно-свободных языков. Замкнутость класса контекстно-свободных языков относительно операции объединения. Разрешимость проблемы принадлежности для контекстно-свободных языков. |
| − | <li> | + | <li> Нормальная форма Хомского для контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского. |
| − | <li> | + | <li> Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся контекстно-свободными. |
| − | <li> | + | <li> Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью. |
| − | <li> | + | <li> Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения. |
| − | <li> | + | <li> Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков. |
| − | <li> | + | <li> Грамматики типа 0 и рекурсивно-перечислимые языки. |
| − | + | ||
| − | + | ||
</ol> | </ol> | ||
Версия 18:12, 28 декабря 2014
Лектор - профессор Захаров Владимир Анатольевич.
Содержание
Программа курса
Конечные автоматы и регулярные выражения
- Конечные автоматы: определения основных понятий. Языки, распознаваемые конечными автоматами. Замкнутость класса автоматных языков относительно операций объединения, пересечения и дополнения.
- Детерминированные конечные автоматы. Метод детерминизации конечных автоматов.
- Алгоритм проверки эквивалентности детерминированных конечных автоматов.
- Минимальные детерминированные конечные автоматы. Алгоритм минимизации детерминированных конечных автоматов.
- Алгебра регулярных выражений. Примеры тождеств в алгебре регулярных выражений. Регулярные языки.
- Алгоритм построения регулярного выражения, определяющего язык, распознаваемый заданным конечным автоматом.
- Алгоритм построения конечного автомата, распознающего язык, определяемый заданным регулярным выражением. Теорема Клини о совпадении класса автоматных языков и класса регулярных языков.
Вычислимые функции и рекурсивные множества
Формальные грамматики и языки
- Формальные грамматики: основные понятия. Классификация Хомского формальных грамматик (иерархия Хомского).
- Праволинейные грамматики и языки. Совпадением класса праволинейных языков и класса автоматных языков. Разрешимость проблем принадлежности и эквивалентности для класса праволинейных языков.
- Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся автоматными.
- Контекстно-свободные грамматики и языки. Примеры контекстно-свободных языков. Замкнутость класса контекстно-свободных языков относительно операции объединения. Разрешимость проблемы принадлежности для контекстно-свободных языков.
- Нормальная форма Хомского для контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
- Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся контекстно-свободными.
- Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
- Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
- Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.
- Грамматики типа 0 и рекурсивно-перечислимые языки.
Алгоритмически неразрешимые математические задачи
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. - М.: Мир, 1978. - 612 с.
- Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Вильямс, 2001. - 768 с.
- Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. - М.: МЦНМО, 1999. - 176 с.
- Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983.
- Льюис Ф., Розенкранц Д, Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.. - 656 с.
- Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. - М.: Бином, 2008. - 200 с.
- Пунтус А.Е., Пентус М.Р. Математическая теория формальных языков. Серия "Основы информатики и математики" - М: Бином, 2006. - 247 с.
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.
- Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. - М.: Вильямс, 2002. - 528 с.
