Оглавление
Язык Дейка
-
Определение и свойства языка Дейка
- Язык Дейка состоит из слов, которые можно прочитать слева направо, соблюдая порядок скобок.
- Слова языка Дейка могут содержать любое количество скобок, но количество скобок в каждой строке ограничено.
- Язык Дейка является контекстно-свободным и имеет синтаксический моноид, изоморфный бициклической полугруппе.
-
Примеры и классификация сложности
- Язык Дейка с двумя типами скобок принадлежит классу сложности T C 0.
- Количество слов Дейка с заданным числом пар скобок равно числу Нараяны или каталонскому числу.
-
Эквивалентность и разбиение на части
- Язык Дейка можно разделить на части по длине слов.
- Для каждого n ∈ N существует отношение S n, которое упорядочивает слова с n парами скобок.
-
Антисимметричность и монотонность
- Отношение S n является антисимметричным, что следует из монотонности функции σ n.
- Если два слова находятся в S n, то они равны.
-
Обобщения и дополнительные сведения
- Существуют варианты языка Дейка с несколькими разделителями.
- Алгоритм подсчета слов Дейка не обобщается на другие варианты.
-
Ссылки и рекомендации
- Ссылки на PlanetMath и блог AMS для дополнительной информации.
Полный текст статьи: