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