범위연결문법

레인지 결합 문법(Range Concatenation Grammer, RCG)은 중국어 번호와 독일어 단어 순서 뒤엉키기 등 자연 언어의 여러 현상을 특징짓기 위해 1998년 피에르 불리에가 개발한 문법 형식주의다.^[2]

이론적인 관점에서, 다항식 시간에 구문 분석할 수 있는 모든 언어는 양성 범위 결합 그래머라고 불리는 RCG의 하위 집합에 속하며, 호혜적으로 사용된다.^[4]

그로닝크의 문자 그대로의 움직임 문법 그래머(LMGs)에 변형된 것으로 의도되었지만, RCG는 문법적 과정을 제작이라기보다는 증거로 취급한다.LMG는 시작 술어에서 단자 문자열을 생성하는 반면, RCG는 시작 술어(단자 문자열의 술어)를 빈 문자열로 감소시키는 것을 목표로 하고 있으며, 이는 언어에서 단자 문자열 멤버쉽의 증거를 구성한다.

설명

형식 정의

포지티브 범위 연결 문법(PRCG)은 튜플 $G{\displaystyle }$= ${\displaystyle (N,}$ ${\displaystyle \text{T},}$ ${\displaystyle \text{V},}$ ${\displaystyle \text{S},}$ P${\displaystyle }$) ${\displaystyle G=(N,$ ~$T,$ ~$V,$ ~$S,$ ~$P)}$이며$,$ 여기서:

• ${\displaystyle }$$N{\displaystyle }$ ${\displaystyle N$ T ${\displaystyle T}$ 및$$ $V{\displaystyle }$ ${\displaystyle V}$은(의존적으로) 술어 이름, 터미널 기호 및 변수 이름의 분리된 유한 집합이다.각 술어 이름에는 ${\displaystyle 딤함수\mathbb{}}$N${\displaystyle }$→ N ${\displaystyle \setminus }${ ${\displaystyle 0\}}$ ${\displaystyle \dim$:$N\rightarrow \mathb$ {N$} \setminus \{0\}}}}$이(가) 부여된 연관성이 있다$.$
• ${\displaystyle S}$ ${\displaystyle \in }$ ${\displaystyle N}$ ${\displaystyle S\in N}$은(는) 시작 술어 이름이며 ${\displaystyle \dim (S)}$= ${\displaystyle 1}$ ${\displaystyle \dim(S)=1$}을$($를) 확인하십시오$.$
• ${\displaystyle P}$ is a finite set of clauses of the form ${\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}}$, where the ${\displaystyle \psi _{i}}$ are predicates of the form ${\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha$${\displaystyle {\_}_{}}${\$dim(A_{i}}})$ ${\displaystyle 및}$$\alpha {\displaystyle {}_{}}$ ${\displaystyle i_{}\in (\mathrm{T<img\; alt="\{\backslash displaystyle\; A\_\{i\}\backslash in\; N\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/36506f0a369c1873ca575cf3584e7d21a303b191"\; style="vertical-align:\; -0.671ex;\; width:7.447ex;\; height:2.509ex;"\; papago-attr-id="41">}}$ $∪$ V${\displaystyle {}^{}}$ ${\displaystyle {\star }^{}}$ ${\$ V$)^{\star$ $\}$이(가) 있는 $_{\$dim(A_${$$i$}}}}}}}}}}.

A Negative Range Concatenation Grammar (NRCG) is defined like a PRCG, but with the addition that some predicates occurring in the right-hand side of a clause can have the form ${\displaystyle {\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}}$. Such predicates are called n자아의 술어

범위 연계 문법은 긍정적이거나 부정적이다.PRCG는 기술적으로 NRCG이지만 음성 술어의 부재(PRCG) 또는 존재(NRCG)를 강조하기 위해 이 용어를 사용한다.

A range in a word ${\displaystyle w\in T^{\star }}$ is a couple ${\displaystyle \langle l,r\rangle _{w}}$, with ${\displaystyle 0\leq l\leq r\leq n}$, where ${\displaystyle n}$ is the length of ${\displaystyle w}$. Two ranges ${\displaystyle$$\langle l_{1},r_{1}\rangle _{w}}$ and ${\displaystyle \langle l_{2},r_{2}\rangle _{w}}$ can be concatenated iff ${\displaystyle r_{1}=l_{2}}$, and we then have: ${\displaystyle \langle l_{1},r_{1}\$$랑글 _{w}\cdot \langle l_{2},r_{2},\angle _{w}=\langle l_{1},r_{2}\angle _{w$

For a word ${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$, with ${\displaystyle w_{i}\in T}$, the dotted notation for ranges is: ${\displaystyle \langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{$$r-1}\properties w_${r$}\ldots$ w_${n$

문자열 인식

LMGs와 마찬가지로 RCG 절에는 일반 $스키마{\displaystyle }$ A${\displaystyle ({x1\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$. . ,${\displaystyle x_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$→ ${\displaystyle \alpha }$ ${\displaystyle A(x_{1$}, $...,x_{n})\to \alpha}$가 있는데$,$ 여기서 RCG에서는 $\alpha {\displaystyle }$ ${\displaystyle \alpha}$이 빈 문자열 또는 술어의 문자열이다$$.인수 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 LMG와 같이 실제 인수 값과 일치하는 패턴으로 구성된 터미널 기호 및/또는 변수 기호의 문자열로 구성되며$$, 인접한 변수는 파티션에 대한 일치를 구성하므로 인수 x ${\displaystyle y}$ ${\displaystyle xy$는 두 변수를 사용하여 리터럴 문자열과 일치한다.${\displaystyle }$$b$의$세$ 가지 다른$$ ${\displaystyle \mathrm{방법}}$: x =${\displaystyle \text{a},}$ ${\displaystyle \text{y}}$= a ; x${\displaystyle }$= a${\displaystyle ,}$ ${\displaystyle y}$= ${\displaystyle a,}$ y${\displaystyle }$= ${\displaystyle a,}$ ${\displaystyle \text{y}}$= $,$ ϵ, ϵ, ϵ, \$displaystyle$ x$=\epsilon,\y=a,\ y=b;\x=ab,\y$=y=y=y$=$y=\$epsilon$ $\}.$

술어 용어는 양수(성공할 때 빈 문자열을 생성함)와 음수(실패할 때 빈 문자열을 생성함/양수 용어가 빈 문자열을 생성하지 않는 경우)의 두 가지 형태로 나타난다.음의 용어는 $A{\displaystyle \stackrel{}{({x\mathrm{}}_{}}}$ 1,${\displaystyle \stackrel{}{}}$.${\displaystyle \stackrel{}{}}$. .${\displaystyle \stackrel{}{}}$, ${\displaystyle \stackrel{}{{}_{}{n}_{}}}$)의$${\$displaystyle {\overline$ {A$(x_{1$}, $...,$x_${n}}}}$에서와 같이 양의 용어와 같은 것으로 표시된다$.$

The rewrite semantics for RCGs is rather simple, identical to the corresponding semantics of LMGs. Given a predicate string ${\displaystyle A(\alpha _{1},...,\alpha _{n})}$, where the symbols ${\displaystyle \alpha _{i}}$ are terminal strings, if there is a rule ${\displaystyle A(x_1,...,x_n)}$${\displaystyle \to }$ ${\displaystyle \beta }$ ${\displaystyle A(x_{1},...,x_{n}})\$ to $\beta }$의 술어 문자열과$$ 일치하는 각 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 변수 대신$$$\beta {\displaystyle }$ ${\displaystystyle \beta }$로 대체$.$

For example, given the rule ${\displaystyle A(x,ayb)\to B(axb,y)}$, where ${\displaystyle x}$ and ${\displaystyle y}$ are variable symbols and ${\displaystyle a}$ and ${\displaystyle b}$ are terminal symbols, the predicate string ${\displaystyle A(a,abb)}$can be rewritten as ${\displaystyle B(aab,b)}$, because ${\displaystyle A(a,abb)}$ matches ${\displaystyle A(x,ayb)}$ when ${\displaystyle x=a,\ y=b}$. Similarly, if there were a rule ${\displaystyle A(x,ayb)\to$$A$$(x,x)\ A(y$$,$$y)},$A${\displaystyle (a,}$ ${\displaystyle b}$ )${\$$displaystyle$ $A(a,abb)}$은(는$)$ $(,$ ${\displaystyle a,}$ $b)로$다시 쓸 수 있다$$$.$

문자열 $\alpha {\displaystyle }$ ${\displaystyle \alpha}$의 증명/인식은 $S{\displaystyle (\alpha )}$ ${\displaystyle S(\alpha )}$이(가) 빈 문자열을 생성한다는$$ 것을 보여줌으로써 이루어진다$$.개별 재작성 단계의 경우, 복수의 대체 변수 일치가 가능한 경우, 전체 증거를 성공으로 이끌 수 있는 모든 재작성을 고려한다.따라서 초기 문자열 $S{\displaystyle (\alpha }$ )${\displaystyle$ S$(\alpha )}$에서 빈 문자열을 생산하는 방법이 적어도 하나 이상 있다면$,$ 그 증거는 실패하는 다른 방법이 얼마나 많은지에 관계없이 성공으로 간주된다.

예

RCG는 다음과 같이$$ 비선형 인덱스 언어${\displaystyle }${${\displaystyle w}$ ${\displaystyle w}$ : ${\displaystyle w}$ w w : ${\displaystyle w}$ w${\displaystyle \in }${ a ,${\displaystyle b}$ ${\displaystyle {\}}^{}}$} ${\displaystyle \{www:w\\in$\{$a,b\}^{*}\}}}}}}}}$을(를) 인식할 수 있다.

x, y 및 z를 변수 기호로 지정:

$(\displaystyle S(xyz)\to A(x,y,z)}$

$(\displaystyle A(ax,ay,az)\to A(x,y,z)}$

${\displaystyle A(bx, by,bz)\to A(x,y,z)}$

$\\displaystyle A(\epsilon ,\epsilon ,\epsilon )\to \epsilon }$

압밥에 대한 증거는 그때 있다.

$(\displaystyle S(abbabbabb)\오른쪽 화살표 A(abb,abb,abb)\오른쪽 화살표 A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

또는 범위에 대해 보다 정확한 점 표기법 사용:

${\displaystyle S(\bullet {}abbabbabb\bullet {})\Rightarrow A(\bullet {}abb\bullet {}abbabb,abb\bullet {}abb\bullet {}abb,abbabb\bullet {}abb\bullet {})\Rightarrow A(a\bullet {}bb\bullet {}abbabb,abba\bullet {}bb\bullet {}abb,abbabba\bullet {}bb\bullet {})}$ ${\displaystyle \Rightarrow \bb\bullet {}abbabb,abbabbab\bullet {}bb\bullet {}B\balllet {}\Rightarrow A(\epsilon ,\epsilon )\Rightarrow \epsilon }$

참조