Категория:Теория формальных языков
Версия от 23:05, 30 сентября 2010; Ivan.pomortsev (обсуждение | вклад)
Лекция 1
- Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов
- Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини
- Регулярные языки: два определения и их эквивалентность
- Детерминированные конечные автоматы
- Недетерминированные конечные автоматы
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
Лекция 2
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков
- Эквивалентность состояний ДКА
- Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
- Замкнутость регулярных языков относительно различных операций
- Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
Лекция 3
Подкатегории
В этой категории отображается 11 подкатегорий из имеющихся 11.
Страницы в категории «Теория формальных языков»
Показано 99 страниц из 99, находящихся в данной категории.
А
- Автоматы в современном мире
- Автоматы Мура и Мили
- Автоматы с eps-переходами. Eps-замыкание
- Автоматы с магазинной памятью
- Алгоритм Бржозовского
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
- Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
- Алгоритм Эрли
- Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
- Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
- Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)
Д
- Двусторонний детерминированный конечный автомат
- Детерминированные автоматы с магазинной памятью
- Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
- Детерминированные конечные автоматы
- ДМП-автоматы и неоднозначность
- ДМП-автоматы и неоднознчность
- Доказательство нерегулярности языков: лемма о разрастании
З
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Замкнутость КС-языков относительно различных операций
- Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
- Замкнутость регулярных языков относительно различных операций
К
Л
М
Н
- Недетерминированные конечные автоматы
- Неотделимые множества
- Неразрешимость задачи вывода типов в языке с зависимыми типами
- Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик
- Неразрешимость игры Braid
- Неразрешимость исчисления предикатов первого порядка
- Неразрешимость проблемы существования решения диофантова уравнения в целых числах
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
- Нормальная форма ДМП-автомата
- Нормальная форма Куроды
- Нормальная форма Хомского
П
- Перечислимые языки
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Правоконтекстные грамматики, эквивалентность автоматам
- Преобразование регулярного выражения в ДКА
- Приведение грамматики к ослабленной нормальной форме Грейбах
- Примеры неразрешимых задач: задача о выводе в полусистеме Туэ
- Примеры неразрешимых задач: задача о замощении
- Примеры неразрешимых задач: однозначность грамматики
- Примеры неразрешимых задач: проблема соответствий Поста
- Примитивно рекурсивные функции
- Простой сопоставитель регулярных выражений
- Прямое произведение ДКА
