Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Язык, состоящий из сбалансированных строк скобок.
Language consisting of balanced strings of brackets
В теории формальных языков в информатике, математике и лингвистике, слово Дика — это сбалансированная строка скобок. Множество слов Дика образует язык Дика. Самый простой случай, D1, использует только две пары соответствующих скобок, например, ( и ). Слова и язык Дика названы в честь математика Вальтера фон Дика. Они применяются при разборе выражений, требующих правильно вложенной последовательности скобок, таких как арифметические или алгебраические выражения.
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of brackets. The set of Dyck words forms a Dyck language. The simplest, D1, uses just two matching brackets, e. g. ( and ). Dyck words and language are named after the mathematician Walther von Dyck. They have applications in the parsing of expressions that must have a correctly nested sequence of brackets, such as arithmetic or algebraic expressions.
Свойства
Язык Дайка замкнут относительно операции конкатенации. Рассматривая его как алгебраический моноид относительно конкатенации, мы видим, что моноидная структура переносится на фактор-группу, в результате чего получается синтаксический моноид языка Дайка. Класс будет обозначаться Синтаксический моноид языка Дайка некоммутативен: если и тогда С использованием вышеуказанной нотации, но ни , ни не обратимы в Синтаксический моноид языка Дайка изоморфен бициклической полугруппе благодаря свойствам и , описанным выше. Согласно теореме о представлении Чомского — Шюценбергера, любой контекстно-свободный язык является гомоморфным образом пересечения некоторого регулярного языка с языком Дайка на одном или нескольких типах скобочных пар. Язык Дайка с двумя различными типами скобок может быть распознан в классе сложности Число различных слов Дайка ровно с n парами скобок и k внутренними парами (а именно, подстрока ) — это число Нараяны. Число различных слов Дайка ровно с n парами скобок — это n-е число Каталана. Заметьте, что язык Дайка слов с n парами скобок равен объединению по всем возможным k языков Дайка слов с n парами скобок с k самыми внутренними парами, как определено в предыдущем пункте. Поскольку k может изменяться от 0 до n, мы получаем следующее равенство, которое действительно верно:
The Dyck language is closed under the operation of concatenation. By treating as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient , resulting in the syntactic monoid of the Dyck language. The class will be denoted The syntactic monoid of the Dyck language is not commutative: if and then With the notation above, but neither nor are invertible in The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of and described above. By the Chomsky–Schützenberger representation theorem, any context free language is a homomorphic image of the intersection of some regular language with a Dyck language on one or more kinds of bracket pairs. The Dyck language with two distinct types of brackets can be recognized in the complexity class The number of distinct Dyck words with exactly n pairs of parentheses and k innermost pairs (viz. the substring ) is the Narayana number The number of distinct Dyck words with exactly n pairs of parentheses is the n th Catalan number Notice that the Dyck language of words with n parentheses pairs is equal to the union, over all possible k, of the Dyck languages of words of n parentheses pairs with k innermost pairs, as defined in the previous point. Since k can range from 0 to n, we obtain the following equality, which indeed holds:
Обобщения
Существуют варианты языка Дайка с несколькими разделителями, например, D2 на алфавите "(", ")", "[", и "]". Словами такого языка являются корректно расставленные скобки для всех разделителей, то есть слово можно прочитать слева направо, помещая каждый открывающий разделитель в стек, и при достижении закрывающего разделителя из стека должен быть извлечён соответствующий открывающий разделитель. (Алгоритм подсчёта, описанный выше, не обобщается).
There exist variants of the Dyck language with multiple delimiters, e. g., D2 on the alphabet "(", ")", "[", and "]". The words of such a language are the ones which are well parenthesized for all delimiters, i. e., one can read the word from left to right, push every opening delimiter on the stack, and whenever we reach a closing delimiter then we must be able to pop the matching opening delimiter from the top of the stack. (The counting algorithm above does not generalise).