язык Дик

Язык, состоящий из сбалансированных строк скобок

В теории формальных языков информатики , математики и лингвистики слово Дика — это сбалансированная строка скобок. Набор слов Дика образует язык Дика . Самый простой, Дика-1, использует всего две парные скобки, например ( и ) .

Слова и язык Дайка названы в честь математика Вальтера фон Дайка . Они применяются в синтаксическом анализе выражений, которые должны иметь правильно вложенную последовательность скобок, таких как арифметические или алгебраические выражения.

Формальное определение

Пусть будет алфавитом, состоящим из символов [ и ]. Пусть обозначает его замыкание Клини . Язык Дика определяется как: ${\displaystyle \Sigma =\{[,]\}}$ ${\displaystyle \Sigma ^{*}}$

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ all prefixes of }}u{\text{ contain no more ]'s than ['s}}{\text{ and the number of ['s in }}u{\text{ equals the number of ]'s}}\}.}$

Контекстно-свободная грамматика

В некоторых ситуациях может быть полезно определить язык Dyck через контекстно-свободную грамматику . Язык Dyck генерируется контекстно-свободной грамматикой с одним нетерминалом S и продукцией:

С → ε | "[" С "]" С

То есть S — это либо пустая строка ( ε ), либо «[», элемент языка Dyck, соответствующий «]», и элемент языка Dyck.

Альтернативная контекстно-свободная грамматика для языка Дика задается следующей продукцией:

С → ("[" С "]") ^*

То есть S представляет собой ноль или более вхождений комбинации «[», элемента языка Дика, и соответствующего «]», где несколько элементов языка Дика в правой части последовательности могут свободно отличаться друг от друга.

Альтернативное определение

В других контекстах может быть полезно определить язык Дика, разбив его на классы эквивалентности следующим образом. Для любого элемента длины мы определяем частичные функции и с помощью ${\displaystyle \Sigma ^{*}}$ ${\displaystyle u\in \Sigma ^{*}}$ ${\displaystyle |u|}$ ${\displaystyle \operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$ ${\displaystyle \operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$

${\displaystyle \operatorname {insert} (u,j)}$с " " вставленным в th позицию ${\displaystyle u}$ ${\displaystyle []}$ ${\displaystyle j}$

${\displaystyle \operatorname {delete} (u,j)}$с удаленным " " из th позиции ${\displaystyle u}$ ${\displaystyle []}$ ${\displaystyle j}$

с пониманием того, что не определено для и не определено, если . Мы определяем отношение эквивалентности на следующим образом: для элементов мы имеем тогда и только тогда, когда существует последовательность из нуля или более применений функций и , начинающаяся с и заканчивающаяся . То , что последовательность из нуля операций допустима, объясняет рефлексивность . Симметрия следует из наблюдения, что любая конечная последовательность применений к строке может быть отменена с помощью конечной последовательности применений . Транзитивность очевидна из определения. ${\displaystyle \operatorname {insert} (u,j)}$ ${\displaystyle j>|u|}$ ${\displaystyle \operatorname {delete} (u,j)}$ ${\displaystyle j>|u|-2}$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle a,b\in \Sigma ^{*}}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle \operatorname {insert} }$ ${\displaystyle \operatorname {delete} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle \operatorname {insert} }$ ${\displaystyle \operatorname {delete} }$

Отношение эквивалентности разбивает язык на классы эквивалентности. Если взять для обозначения пустой строки, то язык, соответствующий классу эквивалентности, называется языком Дика . ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \epsilon }$ ${\displaystyle \operatorname {Cl} (\epsilon )}$

Обобщения

Типизированный язык Дайка

Существуют варианты языка Dyck с несколькими разделителями, например, Dyck-2 на алфавите "(", ")", "[" и "]". Слова такого языка - это те, которые хорошо заключены в скобки для всех разделителей, т. е. можно прочитать слово слева направо, вставить каждый открывающий разделитель в стек, и всякий раз, когда мы достигаем закрывающего разделителя, мы должны иметь возможность вытолкнуть соответствующий открывающий разделитель с вершины стека. (Приведенный выше алгоритм подсчета не обобщается).

Например, следующее предложение является допустимым в Dyck-3:

( [ [ ] { } ] ( ) { ( ) } ) [ ]

Конечная глубина

Предложение языка Dyck можно представить как спуск и подъем по уровням вложенных скобок. При чтении предложения Dyck каждая открывающаяся скобка увеличивает глубину вложенности на 1, а каждая закрывающаяся скобка уменьшает на 1. Глубина предложения — это максимальная глубина, достигнутая в пределах предложения.

Например, мы можем аннотировать следующее предложение, указывая глубину на каждом шаге:

0 ( 1 [ 2 [ 3 ] 2 { 3 } 2 ] 1 ( 2 ) 1 { 2 ( 3 ) 2 } 1 ) 0 [ 1 ] 0

и все предложение имеет глубину 3.

Мы определяем Dyck-(k, m) как язык с k типами скобок и максимальной глубиной m. Это имеет приложения в формальной теории рекуррентных нейронных сетей . ^[1]

Характеристики

• Язык Dyck закрыт относительно операции конкатенации .
• Рассматривая как алгебраический моноид при конкатенации, мы видим, что структура моноида переносится на фактор , в результате чего получается синтаксический моноид языка Дика . Класс будет обозначаться . ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma ^{*}/R}$ ${\displaystyle \operatorname {Cl} (\epsilon )}$ ${\displaystyle 1}$
• Синтаксический моноид языка Дика не является коммутативным : если и то . ${\displaystyle u=\operatorname {Cl} ([)}$ ${\displaystyle v=\operatorname {Cl} (])}$ ${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$
• С обозначениями выше, но ни один из них не обратим в . ${\displaystyle uv=1}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \Sigma ^{*}/R}$
• Синтаксический моноид языка Дика изоморфен бициклической полугруппе в силу свойств и описанных выше. ${\displaystyle \operatorname {Cl} ([)}$ ${\displaystyle \operatorname {Cl} (])}$
• По теореме Хомского–Шютценбергера о представлении любой контекстно-свободный язык является гомоморфным образом пересечения некоторого регулярного языка с языком Дика по одному или нескольким видам пар скобок. ^[2]
• Язык Дика с двумя различными типами скобок можно распознать в классе сложности . ^[3] ${\displaystyle TC^{0}}$
• Число различных слов Дика с ровно n парами скобок и k самыми внутренними парами (т.е. подстрокой ) называется числом Нараяны . ${\displaystyle [\ ]}$ ${\displaystyle \operatorname {N} (n,k)}$
• Число различных слов Дика с ровно n парами скобок является n -м каталонским числом . Обратите внимание, что язык Дика слов с n парами скобок равен объединению по всем возможным k языков Дика слов из n пар скобок с k самыми внутренними парами , как определено в предыдущем пункте. Поскольку k может принимать значения от 0 до n , мы получаем следующее равенство, которое действительно выполняется: ${\displaystyle C_{n}}$

${\displaystyle C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)}$

Примеры

Решетка из 14 слов Дика длиной 8 - [ и ] интерпретируются как вверх и вниз

Мы можем определить отношение эквивалентности на языке Дика . Для нас имеет место тогда и только тогда, когда , т.е. и имеют одинаковую длину. Это отношение разбивает язык Дика: . Мы имеем , где . Обратите внимание, что пусто для нечетного . ${\displaystyle L}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle u,v\in {\mathcal {D}}}$ ${\displaystyle (u,v)\in L}$ ${\displaystyle |u|=|v|}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle {\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots \}}$ ${\displaystyle {\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}}$ ${\displaystyle {\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle n}$

Введя слова Дика длины , мы можем ввести отношение на них. Для каждого мы определяем отношение на ; для нас есть тогда и только тогда, когда можно достичь из с помощью серии правильных замен . Правильная замена в слове меняет вхождение '][' на '[]'. Для каждого отношение превращается в частично упорядоченный набор . Отношение рефлексивно , потому что пустая последовательность правильных замен занимает до . Транзитивность следует, потому что мы можем расширить последовательность правильных замен, которая занимает до , объединив ее с последовательностью правильных замен, которая занимает до , образовав последовательность, которая занимает до . Чтобы увидеть, что это также антисимметрично , мы вводим вспомогательную функцию, определенную как сумма по всем префиксам : ${\displaystyle n}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle u,v\in {\mathcal {D}}_{n}}$ ${\displaystyle (u,v)\in S_{n}}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u\in {\mathcal {D}}_{n}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle S_{n}}$ ${\displaystyle \sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N} }$ ${\displaystyle v}$ ${\displaystyle u}$

${\displaystyle \sigma _{n}(u)=\sum _{vw=u}{\Big (}({\text{count of ['s in }}v)-({\text{count of ]'s in }}v){\Big )}}$

Следующая таблица иллюстрирует, что она строго монотонна относительно правильных обменов. ${\displaystyle \sigma _{n}}$

Следовательно , когда есть правильный обмен, который принимает в . Теперь, если мы предположим, что и и , то есть непустые последовательности правильных обменов, такие принимаются в и наоборот. Но тогда , что бессмысленно. Поэтому, когда оба и находятся в , мы имеем , следовательно, является антисимметричным. ${\displaystyle \sigma _{n}(u')-\sigma _{n}(u)=2>0}$ ${\displaystyle \sigma _{n}(u)<\sigma _{n}(u')}$ ${\displaystyle u}$ ${\displaystyle u'}$ ${\displaystyle (u,v),(v,u)\in S_{n}}$ ${\displaystyle u\neq v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)}$ ${\displaystyle (u,v)}$ ${\displaystyle (v,u)}$ ${\displaystyle S_{n}}$ ${\displaystyle u=v}$ ${\displaystyle S_{n}}$

Частично упорядоченный набор показан на иллюстрации, сопровождающей введение, если мы интерпретируем [ как движение вверх, а ] как движение вниз. ${\displaystyle D_{8}}$

Смотрите также

• конгруэнтность Дайка
• Слово-решетка

Примечания

1. Хьюитт, Джон; Хан, Майкл; Гангули, Сурья; Лян, Перси; Мэннинг, Кристофер Д. (15.10.2020). «RNN могут генерировать ограниченные иерархические языки с оптимальной памятью». arXiv : 2010.07515 [cs.CL].
2. Камбитс, Сообщения в алгебре Том 37 Выпуск 1 (2009) 193-208
3. Баррингтон и Корбетт, Information Processing Letters 32 (1989) 251-256

Ссылки

• Язык Дика на PlanetMath .
• Доказательство теоремы Хомского-Шютценбергера
• Запись в блоге AMS о словах Дика