Спецкурс "Теория формальных языков"

М. Р. Пентус
2004/2005

        01.10.2004

1.1.   Формальные языки
1.3.   Порождающие грамматики
1.4.   Классы грамматик

Различие между "конкретным" символом a и метапеременной a.

        08.10.2004

2.1.   Недетерминированные конечные автоматы
2.2.   Конфигурации конечного автомата
2.3.   Конечные автоматы с однобуквенными переходами

Диаграммы конечных автоматов.

Пример конечного автомата, проверяющего сложение натуральных чисел.

Пример конечного автомата, анализирующего формы глаголов эсперанто
(неопределённая форма, спрягаемые формы, деепричастия, причастия).

        15.10.2004

2.4.   Характеризация праволинейных языков
2.6.   Детерминированные конечные автоматы
3.1.   Свойства замкнутости класса автоматных языков

Пример конечного автомата, задающего константы типа double в языке C.

        22.10.2004

3.2.   Пересечение и дополнение автоматных языков
3.3.   Лемма о разрастании для автоматных языков
3.4.   Примеры неавтоматных языков
1.2.   Гомоморфизмы
4.1.   Гомоморфизмы и автоматные языки
4.2.   Длины слов в автоматных языках

Свободная группа, свободный моноид.

        05.11.2004

5.1.   Определение регулярного выражения
5.2.   Свойства регулярных выражений
5.3.   Теорема Клини
6.1.   Множества правых контекстов

        12.11.2004

6.2.   Минимизация детерминированных конечных автоматов
6.3.   Множества двусторонних контекстов

        19.11.2004

7.1.   Деревья вывода
7.2.   Однозначные контекстно-свободные грамматики
7.3.   Однозначные праволинейные грамматики
7.4.   Языки Дика и Лукасевича

        26.11.2004

8.1.   Устранение бесполезных символов
8.2.   Устранение ε-правил
8.3.   Нормальная форма Хомского
8.4.   Нормальная форма Грейбах

        10.12.2004

9.1.   Лемма о разрастании для контекстно-свободных языков
9.2.   Свойства замкнутости класса линейных языков
9.3.   Свойства замкнутости класса контекстно-свободных языков
9.4.   Пересечение и дополнение контекстно-свободных языков

        18.02.2005

9.5.   Пересечение контекстно-свободного языка с автоматным языком
9.6.   Теорема Парика

        25.02.2005

10.1.  Определение автомата с магазинной памятью
10.2.  Характеризация контекстно-свободных языков

        11.03.2005

11.1.  Деление контекстно-свободных языков
11.2.  Гомоморфизмы и контекстно-свободные языки

        18.03.2005

11.3.  Представления контекстно-свободных языков посредством гомоморфизмов

        25.03.2005

12.1.  Детерминированные автоматы с магазинной памятью
12.2.  Свойства класса детерминированных контекстно-свободных языков

        01.04.2005

13.1.  Машины Тьюринга

        08.04.2005

Примеры машин Тьюринга.

13.2.  Массовые задачи
13.3.  Грамматики типа 0
13.4.  Проблема соответствий Поста

        15.04.2005

14.1.  Неукорачивающие грамматики
14.2.  Линейно ограниченные автоматы
14.3.  Проблема выводимости слова
14.4.  Проблема пустоты языка
14.5.  Проблема бесконечности языка
14.6.  Проблема равенства автоматных языков
15.1.  Пересечение контекстно-свободных языков

        06.05.2005

15.3.  Дополнение контекстно-свободного языка
15.4.  Проблема автоматности
15.5.  Проблемы контекстно-свободности


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

Пентус А. Е., Пентус М. Р. Теория формальных языков. --
М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004. -- 80 с.

Имеется список задач к экзамену: pdf (148 кб), PostScript (467 кб), PostScript.zip (119 кб).


Адрес: http://lpcs.math.msu.su/~pentus/specw.htm
Изменения внесены 01.09.2005.
Мати Рейнович Пентус
Телефон/факс: + 7 - 495 - 939 30 31