다이크어

이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "Dyck Language" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2015년 4월)

컴퓨터 과학, 수학, 언어학의 형식 언어 이론에서 Dyck 단어는 대괄호 [와 ]의 균형 잡힌 문자열이다.Dyck 단어 집합은 Dyck 언어를 형성한다.

Dyck 단어와 언어는 수학자 Walther von Dyck의 이름을 따서 명명되었다.그들은 산술적 또는 대수적 표현식과 같이 대괄호 서열이 정확하게 중첩되어야 하는 표현식의 파싱에 응용이 있다.

형식 정의

$\sigma {\displaystyle \mathrm{}}$=${\displaystyle }${${\displaystyle }$[ ,${\displaystyle ]}$} ${\displaystyle \Sigma =\{[,]\}}$을(를) 기호 [ 및 ]로 구성되도록 한다$$.${\$는 클라인 폐쇄를 나타낸다$$.Dyck 언어는 다음과 같이 정의된다.

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{{}}의 모든 접두사에는 [}{\text{}보다 큰 ]이 포함되지 않으며 [}의 수는 }{\text{}}}}}의 수와 같다.$

문맥 없는 문법

어떤 상황에서는 문맥이 없는 문법을 통해 Dyck 언어를 정의하는 것이 도움이 될 수 있다.Dyck 언어는 단일 비단어 S로 문맥이 없는 문법에 의해 생성되며, 생산은 다음과 같다.

S → ε "[" S "]" S

즉, S는 빈 문자열(ε)이거나 "[], Dyck 언어의 요소, 일치하는 "], 그리고 Dyck 언어의 요소 중 하나이다.

Dyck 언어에 대한 대체 문맥 없는 문법은 제작에 의해 제공된다.

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

즉, S는 Dyck 언어의 요소인 "[]와 일치하는 "]의 조합으로 0 이상 발생하며, 여기서 생산 우측에 있는 Dyck 언어의 복수 요소들은 서로 자유롭게 차이가 난다.

대체 정의

다른 맥락에서 ${\$을(를) 다음과 같이 동등성 등급으로$$ 분할하여 Dyck 언어를 정의하는 것이 도움이 될 수 있다.For any element ${\displaystyle u\in \Sigma ^{*}}$ of length ${\displaystyle u }$, we define partial functions ${\displaystyle \operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$ and ${\displaystyle \operatorn$$ame {delete} :\Sigma ^{*}\time \mathb$ {$N} \rightarrow$ \$Sigma ^{*}$ by$$:

${\displaystyle (u}$, ${\displaystyle j}$) ${\displaystyle \insertname$ {$insert}(u,$j)}은(는) $]$ {\$displaystyle []"$이$($$가{\displaystyle }$) j ${\displaystyle j}$ 위치에$$ 삽입된$$ ${\displaysty$ j} $u$}입니다.

${\displaystyle \mathrm{delete}(u}$, ${\displaystyle j}$) ${\displaystyle \designname {delete}(u,j)}$은(는) "[$$] {\$displaystyle$${\displaystyle }$이($)$ j {\displaystyle $j}$ 위치에서$$ 삭제된 {\$displaystyle$ j} $u}$입니다.

만약 j>;− 2{\displaystyle j&gt입니다;-2}. 우리는 동치 관계를 정의하는}⁡(u, j){\displaystyle \operatorname{삽입}(u,j)을 이해로 j을에;{\displaystyle j>,마}과 ⁡(u, j){\displaystyle \operatorname{삭제}(u,j)삭제}확실하지 않은 것 정의되지 않습니다. R{\di$splaystyle R}$ on ${\displaystyle \Sigma ^{*}}$ as follows: for elements ${\displaystyle a,b\in \Sigma ^{*}}$ we have ${\displaystyle (a,b)\in R}$ if and only if there exists a sequence of zero or more applications of the ${\displaystyle \operatorname {insert} }$ and ${\displaystyle \mathrm{delete}}$${\displaystyle \detname {delete}$ 함수는$$ ${\displaystyle a}$에서 $시작$하여 b ${\displaystyle b}$로 끝나는 함수$.$제로 연산 순서가 허용된다는 $것$은 R ${\displaystyle$R}의 반사율을 설명한다는 것이다.$$대칭성은 문자열에 대한$$ ${\displaystyle \mathrm{삽입}}$ ${\$$displaystyle \operatorname$${insert}}$의 응용 순서는 ${\displaystyle \mathrm{삭제}}$된 응용 순서의 유한 순서에 따라 취소할 수 있다는 관측에서 비롯된다$.$$토르네임 {delete}$}$$. transitability는 정의에서 분명히 알 수 있다.

동등성 관계는 언어 ${\$을 동등성 클래스로$$ 분할한다.빈 문자열을 나타내기 위해$$ $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$을(를) 선택하면 동등성 클래스 ${\displaystyle \mathrm{Cl}}$ ⁡${\displaystyle }$(${\displaystyle ϵ}$ )${\displaystyle \operatorname {Cl} (\epsilon )}$에 해당하는 언어를 Dyck 언어라고 한다$$.

특성.

• Dyck 언어는 concertation의 작동으로 폐쇄된다.
• $\sigma {\displaystyle {\mathrm{}}^{}}$ $∗{\$을(를) 연결 상태에서 대수적 단조로이드로 처리함으로써 우리는 모노이드 구조가 $\sigma {\displaystyle {\mathrm{}}^{}{\ast }^{}}$ / ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}/$R$\}$의 지수로 전달되어 Dyck 언어의 구문 단조로 된 것을 알 수 있다.${\displaystyle \mathrm{Cl}}$ ${\displaystyle }$ (${\displaystyle ϵ}$ ) ${\displaystyle \operatorname {Cl} (\epsilon )}$ 클래스는 $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$로 표시된다$.$
• The syntactic monoid of the Dyck language is not commutative: if ${\displaystyle u=\operatorname {Cl} ([)}$ and ${\displaystyle v=\operatorname {Cl} (])}$ then ${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$.
• 위의 표기법으로 $u{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle v}$= ${\displaystyle 1}$ ${\displaystyle u=1$} 그러나$$${\displaystyle {}^{}}$$u{\displaystyle }$ ${\displaystyle u}$과 v ${\displaystyle$ v$}$은(는) ${\displaystyle {\ast }^{}}$ / R ${\displaystyle \Sigma ^{*}/R}$에서 변환할$$수 없다.
• Dyck 언어의 통사적 모노이드는 위에서 설명한$$ ${\displaystyle \mathrm{Cl}}$ ${\displaystyle }$(${\displaystyle }$[${\displaystyle }$) ${\displaystyle \operatorname$ {$Cl} ([)}$ 및$$ ${\displaystyle \mathrm{Cl}}$ ${\displaystyle }$ (${\displaystyle }$]) ${\displaysty \operatorname {Cl} (])$의 속성으로 인해 자전거 세미그룹에 이형이다.
• 촘스키-슈첸베르거 표현 정리에 의해, 어떤 문맥 없는 언어는 하나 이상의 괄호 쌍에 Dyck 언어와 어떤 정규 언어의 교차점에 대한 동형상이다.^[1]
• 두 가지 뚜렷한 유형의 괄호를 가진 Dyck 언어는 복잡도 등급 $T{\displaystyle }$ ${\displaystyle {}^{}}$ ${\$에서 인식할 수 있다$.$^[2]
• 괄호 쌍과 k 가장 안쪽 쌍(viz. 하위 문자열${\displaystyle }$[$$ {\$displaystyle [\$ $]\})$이 정확히 n쌍인 Dyck 단어의 수는 Narayana 번호 $N{\displaystyle \mathrm{}(n}$, ${\displaystyle k}$) ${\displaysty \operatorname {N}(n,k)}$이다$.$
• 괄호 쌍이 정확히 n개인 고유 Dyck 단어의 수는 n번째 카탈로니아 $수{\displaystyle {}_{}}$ ${\displaystyle C_{}}$ n ${\$이다$.$ n 괄호 쌍이 있는 단어의 Dyck 언어는 앞의 p에서 정의한 바와 같이, 가능한 모든 k에 걸쳐 k개의 가장 안쪽 쌍과 n 괄호 쌍이 있는 단어의 Dyck 언어의 조합과 같다.연고. k는 0에서 n까지 범위가 가능하기 때문에, 우리는 다음과 같은 평등을 얻는데, 이것은 정말로 중요하다.

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

예

We can define an equivalence relation ${\displaystyle L}$ on the Dyck language ${\displaystyle {\mathcal {D}}}$. For ${\displaystyle u,v\in {\mathcal {D}}}$ we have ${\displaystyle (u,v)\in L}$ if and only if ${\displaystyle u = v }$, i.e. ${\displaystyl$$e u}$과($)$ v {\$displaystyle v}$의 길이는$$ 같다.This relation partitions the Dyck language: ${\displaystyle {\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots ,\}}$. We have ${\displaystyle {\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}$$}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}}$ where ${\displaystyle {\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid u =n\}}$. Note that ${\displaystyle {\mathcal {D}}_{n}}$ is empty for odd ${\displaystyle n}$.

길이 $n$의 Dyck $단어들$을 소개한 후에$,$ 우리는 그것들에 대한 관계를 소개할 수 있다.For every ${\displaystyle n\in \mathbb {N} }$ we define a relation ${\displaystyle S_{n}}$ on ${\displaystyle {\mathcal {D}}_{n}}$; for ${\displaystyle u,v\in {\mathcal {D}}_{n}}$ we have ${\displaystyle (u,v)\in S_{n}}$ if and only if ${\displ$$aystyle v}$은(는) 일련의 적절한 스왑을 통해$$ $u{\displaystyle }$ ${\displaystyle u}$에서 연결할 수 있다$$.$u{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {Dn}_{}}$ ${\$ 단어의 적절한 스왑은 '[]'과 ']의 발생을 스왑한다$$.각 $n{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle N\mathbb{}}$ ${\$에 대해 관계 ${\displaystyle S_{}}$ ${\$$displaystyle S_{n}}$는 ${\displaystyle {Dn}_{}}$ {\$displaystyle{\mathcal{D}_{n}}}$를 부분적으로 정렬된 세트로 만든다$$$$.관계 ${\displaystyle {Sn}_{}}$ {\$displaystyle S_{n}$는 적절한 스왑의 빈 시퀀스가 $u{\displaystyle }$ ${\displaystyle u}$에 걸리기 때문에 반사적이다.$$$u{\displaystyle }$ {\$displaystyle u}$을(를$)$ 시퀀스 $o$와 연결함으로써$$v {\$displaystyle v}$에 이르는 적절한 스왑 시퀀스를 확장할 수 있기 때문에 transitivity가 따른다$.$$v{\displaystyle }$ ${\displaystyle v$$}$에서 $w{\displaystyle }$ ${\$$displaystyle w$$}까지의 시퀀스$를 $구성$하는 적절한$$ 스왑$.$ ${\displaystyle {Sn}_{}}$ ${\$도 대칭성이라는 것을$$ 확인하기 위해 보조 함수 $function{\displaystyle {}_{}}$ : ${\displaystyle D_{}{}_{}}$n → ${\displaystyle N\mathbb{}}$ ${\$를 도입한다.$hcal {D}_{n}\오른쪽$ 화살표 $\mathb {N}}$$u{\displaystyle }$ ${\displaystyle u}$의 모든 접두사 $v{\displaystyle }$ ${\displaystyle v}$에 대한 합으로 정의됨$:$

${\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 {monn}_{}}$ ${\$의 엄격한 단조함

일부 합계 ${\displaystyle {\sigma n}_{}}$(${\displaystyle u}$) ${\displaystyle \sigma _{n}(u)}$	$P}$	$P-1(표시 스타일 P-displaystyle P-1})$	$P}$	$(\displaystyle Q}$
$(\displaystyle u}$	$\displaystyle \ldots }$	]	[	$\displaystyle \ldots }$
$(\displaystyle u'}$	$\displaystyle \ldots }$	[	]	$\displaystyle \ldots }$
일부 합계 ${\displaystyle {\sigma n}_{}}$(${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$) ${\displaystyle \sigma _{n}(u')}$	$P}$	${\displaystyle P+1}$	$P}$	$(\displaystyle Q}$
부분합계차이	0	2	0	0

가 끝난 뒤 너 ′{\displaystyle 너의}에 너{\displaystyle u}을 고려한 적정 스왑은 이제 만약 우리들이 둘 다(으로 가정하는 따라서σ n=2을(u);0{\displaystyle \sigma_{n}(너의)-\sigma _ᆱ(u)=2>. 0}일 경우 그렇게σ n(u)<>σ n(u′){\displaystyle \sigma_{n}(u)<, \sigma _ᆳ(너의)}.σ n−(u′). u, v=,(${\displaystyle v}$ ,${\displaystyle u}$ )${\displaystyle }$S ${\displaystyle n_{}}$ ${\$ ${\displaystyle u}$ ${\displaystyle \ne }$ v ${\displaystyle u\neq v$ 그러면 v ${\displaystyle u}$과 같은 적절한 스왑의 빈 시퀀스가 $v$ ${\displaystyty v}$에 포함되며 그 반대의 경우도 있다.그러나 그 다음 )< ) ${\displaystyle \sigma _{n}(u)<\n(v)><\sigma _{n}(u)}}$은(는) 터무니없는 말이다.${\displaystyle {따라서}_{}}$${\displaystyle }$(${\displaystyle u}$, ${\displaystyle v}$) ${\displaystyle (u,v)}$과 $({\displaystyle v}$, ${\displaystyle u}$) ${\$$$($v,u)}$이(가$)$ 모두${\displaystyle \mathrm{Sn}}$ {\$displaystyle$ S_{n}에 있을$$ 때마다$$${\displaystyle u_{}}$ = v ${\$u=$v$이$(가)$가 대칭적이다.

부분 순서 집합 $D{\displaystyle {}_{}}$ ${\$를 [위로, ]을(를) 아래로 해석하면 소개에 수반되는 그림에 표시된다$$.

일반화

알파벳 "(), "), "," ", "," 그리고 "]와 같은 다중 구분 기호를 가진 Dyck 언어의 변형들이 존재한다.이러한 언어의 단어는 모든 구분 기호에 대해 잘 키워드화된 단어들이다. 즉, 단어를 왼쪽에서 오른쪽으로 읽을 수 있고, 모든 구분 기호를 스택에 밀어 넣을 수 있으며, 닫는 구분 기호에 도달할 때마다 스택의 맨 위에서 일치하는 구분 기호를 터뜨릴 수 있어야 한다.

참고 항목

• Dyck 응집법
• 격자어

메모들

참조

• 플래닛매트릭스의 Dyck 언어.
• 촘스키슈첸베르거 정리의 증거
• Dyck 단어에 대한 AMS 블로그 항목