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