Язык Дайка

редактировать

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

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

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

Содержание

1 Формальное определение
- 1.1 Контекстно-свободная грамматика
- 1.2 Альтернативное определение
2 Свойства
3 Примеры
4 Обобщения
5 См. Также
6 Примечания
7 Ссылки

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

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

{u ∈ Σ ∗ | все префиксы u не содержат больше символов], чем [», а количество [в u равно количеству]}. {\ displaystyle \ {u \ in \ Sigma ^ {*} \ vert {\ text {все префиксы}} u {\ text {содержат не более], чем ['s}} {\ text {и количество [в}} u {\ text {равно количеству]}} \}.}

\{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}}\}.

Грамматика без контекста

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

S → ε | "[" S "]" S

То есть S - это либо пустая строка (ε), либо "[", элемент языка Дайка, соответствие "]" и элемент языка Дейка.

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

S → ("[" S "]")

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

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

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

insert ⁡ (u, j) {\ displaystyle \ operatorname {insert} (u, j)}

{\ displaystyle \ operatorname {insert} (u, j)}

- это

u {\ displaystyle u}

u

с "

[] {\ displaystyle}

\text{[math]}

, вставленным в

j {\ displaystyle j}

j

ая позиция

удалить ⁡ (u, j) {\ displaystyle \ operatorname {delete} (u, j)}

{\ displaystyle \ operatorname {delete} (u, j)}

u {\ displaystyle u}

u

с удалением «

[] {\ displaystyle}

\text{[math]}

» из

j {\ displaystyle j}

j

-ой позиции

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

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

Свойства

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

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

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

Примеры

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

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

σ n (u) = ∑ vw = u ((количество [в v) - (количество] в v)) {\ displaystyle \ sigma _ {n} (u) = \ sum _ {vw = u} {\ Big (} ({\ text {count of ['s in}} v) - ({\ text {count of]]' s в }} v) {\ Big)}}

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

В следующей таблице показано, что $σ n {\ displaystyle \ sigma _ {n}}$ $\ sigma_ {n}$ строго монотонный в отношении к правильным свопам.

Строгая монотонность $σ n {\ displaystyle \ sigma _ {n}}$ $\ sigma_ {n}$
частичных сумм $σ n (u) {\ displaystyle \ sigma _ {n} (u)}$ ${ \ displaystyle \ sigma _ {n} (u)}$	$P {\ displaystyle P}$ $P$	$P - 1 {\ displaystyle P-1}$ $P-1$	$P {\ displaystyle P}$ $P$	$Q {\ displaystyle Q}$ $Q$
$u {\ displaystyle u}$ $u$	$… {\ Displaystyle \ ldots}$ $\ ldots$	]	[	$… {\ displaystyle \ ldots}$ $\ ldots$
$u ′ {\ displaystyle u '}$ $u'$	$… {\ displaystyle \ ldots}$ $\ ldots$	[	]	$… {\ displaystyle \ ldots}$ $\ ldots$
частичные суммы $σ N (u ') {\ displaystyle \ sigma _ {n} (u')}$ $\sigma _{n}(u')$	$P {\ displaystyle P}$ $P$	$P + 1 {\ displaystyle P + 1}$ $P + 1$	$P {\ displaystyle P}$ $P$	$Q {\ displaystyle Q}$ $Q$
Разница частичных сумм	0	2	0	0

Следовательно, $σ n (u ') - σ n (u) = 2>0 {\ displaystyle \ sigma _ {n} (u ') - \ sigma _ {n} (u) = 2>0}$ $\sigma_{n}(u') - \sigma_{n}(u) = 2>0$ так что $σ n (u) < σ n ( u ′) {\displaystyle \sigma _{n}(u)<\sigma _{n}(u')}$ $\sigma_{n}(u) < \sigma_{n}(u')$ при наличии правильного свопа, требующего $u {\ displaystyle u}$ $u$ в $u ′ {\ displa ystyle u '}$ $u'$ . Теперь, если мы предположим, что оба $(u, v), (v, u) ∈ S n {\ displaystyle (u, v), (v, u) \ in S_ {n}}$ $(u, v), (v, u) \ in S_ {n}$ и $u ≠ v {\ displaystyle u \ neq v}$ $u \ ne v$ , тогда есть непустые последовательности правильных свопов, такие как $u {\ displaystyle u}$ $u$ . в $v {\ displaystyle v}$ $v$ и наоборот. Но тогда $σ n (u) < σ n ( v) < σ n ( u) {\displaystyle \sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)}$ $\ sigma_ {n } (u) <\ sigma_ {n} (v) <\ sigma_ {n} (u)$ что бессмысленно. Следовательно, если оба $(u, v) {\ displaystyle (u, v)}$ $(u, v)$ и $(v, u) {\ displaystyle (v, u)}$ $(v, u)$ находятся в $S n {\ displaystyle S_ {n}}$ $S_ {n}$ , мы имеем $u = v {\ displaystyle u = v}$ $u = v$ , следовательно, $S n {\ displaystyle S_ {n}}$ $S_ {n}$ антисимметричен.

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

Обобщения

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

См. Также

Примечания

Ссылки