Математическая теория формальных языков
Математическая теория формальных языков
ПредисловиеСлова, языки и грамматики
Формальные языки
Операции над языками
Гомоморфизмы
Порождающие грамматики
Классы грамматик
Математическая теория формальных языков
Конечные автоматыНедетерминированные конечные автоматы
Конфигурация конечного автомата
Конечные автоматы с однобуквенными переходами
Характеризация праволинейных языков
Нормальная форма праволинейных грамматик
Детерминированные конечные автоматы
Преобразование конечного автомата к детерминированному виду
Основные свойства автоматных языков
Свойства замкнутости класса автоматных языков
Пересечение и дополнение автоматных языков
Лемма о разрастании для автоматных языков
Примеры неавтономных языков
Математическая теория формальных языков
Дополнительные свойства автоматных языковГомоморфизмы и автоматные языки
Локальные языки
Длины слов в автоматных языках
Регулярные выражения
Определение регулярного выражения
Свойства регулярных выражений
Теорема Клини
Звездная высота
Синтаксические моноиды
Множества правых контекстов
Минимизация детерминированных конечных автоматов
Множества двусторонних контекстов
Классы эквивалентности слов
Математическая теория формальных языков
Неоднозначность в контекстно-свободных грамматикахДеревья вывода
Однозначные контекстно-свободные грамматики
Однозначные праволинейные грамматики
Языки Дика и Лукасевича
Нормальные формы контекстно-свободных грамматик
Устранение бесполезных символов
Устранение эпсилон-правил
Нормальная форма Хомского
Нормальная форма Грейбах
Математическая теория формальных языков
Основные свойства контекстно-свободных языковЛемма о разрастании для контекстно-свободных языков
Лемма о разрастании для линейных языков
Свойства замкнутости класса линейных языков
Свойства замкнутости класса контекстно-свободных языков
Пересечение и дополнение контекстно-свободных языков
Пересечение контекстно-свободного языка с автоматным языком
Теорема Парика
Автоматы с магазинной памятью
Определение автомата с магазинной памятью
Характеризация контекстно-свободных языков
Автоматы с магазинной памятью с однобуквенными переходами
Дополнительные свойства контекстно-свободных языков
Деление контекстно-свободных языков
Гомоморфизмы и контекстно-свободные языки
Представления контекстно-свободных языков посредством гомоморфизмов
Математическая теория формальных языков
Детерминированные контекстно-свободные языкиДетерминированные автоматы с магазинной памятью
Свойства класса детерминированных языков
Синтаксический разбор
Нисходящий разбор
Восходящий разбор
Алгоритмические проблемы
Машины Тьюринга
Разрешимые и перечислимые множества
Массовые задачи
Грамматики типа 0
Проблема соответствий Поста
Алгоритмически разрешимые проблемы
Неукорачивающие грамматики
Линейно ограниченные автоматы
Проблема выводимости слова
Проблема пустоты языка
Проблема бесконечности языка
Проблема эквивалентности конечных автоматов
Проблема эквивалентности детерминированных МП-автоматов
Классы P и NP
Проблема неравенства регулярных выражений без итерации
Алгоритмически неразрешимые проблемы
Пересечение контекстно-свободных языков
Проблема однозначности
Дополнение контекстно-свободного языка
Проблема автоматности
Проблемы контекстной свободности
Содержание раздела
