규칙적인 다시 쓰기

규제된 재작성은 파생 단계에서 적용되는 생산에 대해 일종의 통제권을 가질 수 있는 문법 시스템을 연구하는 공식 언어의 특정 영역입니다.이러한 이유로, 규제된 재작성 이론에서 연구된 문법 체계는 "제어된 파생 문법"이라고도 불립니다.이러한 문법 중에서 주목할 수 있는 것은 다음과 같습니다.

매트릭스 문법

기본 개념

정의.
행렬 문법, $({displaystyle$MG$\})$는 $4차원{\displaystyle }$ G $=$ (${\displaystyle N,T}$, ${\displaystyle M,}$ $)$ {\$displaystyle$ G=($N, T$, $M, S)}$이며, 다음과 같은 값을 갖습니다.
1.- $({displaystyle$N})은$$ 비종단 기호의 알파벳입니다.
2.- $({displaystyle$T})는$$ N$({displaystyle$N})과 분리된 터미널 기호의 알파벳입니다.
3.- $M{\displaystyle }$${\displaystyle {}_{}}$ ${\displaystyle {m1\mathrm{}}_{}}$ ${\displaystyle {m2\mathrm{}}_{},}$ ${\displaystyle .,}$ ${$n}, m{$displaystyle$ M={$m_{1}, m_{2},$ ..., $m_{n}}$은 행렬의 유한 집합으로, ${\displaystyle {}_{}}$ 있지 않은 시퀀스 $mi$ [$pi$1$,$ ${\displaystyle {{.,}_{}}_{}}$ ${\displaystyle {{\mathrm{pi}}_{}}_{}}$ ${\displaystyle {{(}_{}}_{}}$i${\displaystyle {{}_{}}_{}}$ {$i (i)},$ $p_{i$(i$)$ kge (i),$\},$ $1(i$ (${\displaystyle i}$), ▁11, style), $1$, (), ▁,), ▁(), ≥), ▁k1$,$ ▁1),$그리고{\displaystyle \mathrm{}}$ 1${\displaystyle }$≤ ${\displaystyle i}$ \ \ \ \ \ j ${\displaystyle \le k}$$$(${\displaystyle i}$ ${\displaystyle )}$ \ $displaystyle p_{i_{j}1\leq$ j$\leq$ $k$$(i)$}, 여기서 각 ${\displaystyle {{pij}_{}}_{}}$ 1$$${\displaystyle \le }$ j ≤ k (i) \ $displaystyle p_{i_{j$}}$=$는${\displaystyle }$L (${\displaystyle N{}^{}}$ N${\displaystyle {}^{}(N{}^{}}$${\displaystyle R}$ ${\displaystyle {\in }^{}}$ ( ${\displaystyle N}$ ${\displaystyle {}^{}}$ ${\displaystyle T}$ ) $∗$ {\$displaystyle L\in$(N$\cup T)^{*}N(N\cup$ T$)^{*}}$ 이러한$$ 쌍을 "생산${\displaystyle "}$이라고 하며, ${\displaystyle {이러한}_{}}$ 조건에서 L ${\displaystyle {{}_{}}_{}}$$$${\displaystyle {}_{}}$\${\displaystyle {{displaystyle\mathrm{}}_{}}_{}}$ L${\displaystyle {{}_{}}_{}}$$rightarrow$ R$\}$로 $나타낼{\displaystyle {}_{}}$ 수 있습니다${\displaystyle .}$$→$
4.- S는 시작 기호입니다.

정의.
${\displaystyle \mathrm{MG}}$ $=$ (${\displaystyle N,}$ ${\displaystyle T,}$ ${\displaystyle M,S}$) {\$displaystyle$ MG=($N, T$, $M, S)}$를 행렬 문법으로 $하고{\displaystyle }$$,$ P {\$displaystyle$ P$$$\}$를 $MG$의 행렬에 대한 모든 생성물의 $모음$으로 합니다. $우리$는$MG$ {\$displaystyle$MG$$}가 ${\displaystyle \mathrm{i}=,1,}$ 2, $3,$0, 2,$$$2$, $i2$, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,$3$ 또는 "길이 증가" 또는 "$선형{\displaystyle }$" 또는 $"{\displaystyle$\displaystyle \$displays}-$productions$$ 없이"는 문법 G $=$($N$ ${\displaystyle T,}$ S) {\$displaystyle$ G=($N,$T,$P$, $S)$가 해당 속성을 갖는 경우에만 해당됩니다.

전형적인 예

참고: Abraham 1965에서 가져온 것으로, 터미널이 아닌 이름을 변경했습니다.

상황에 민감한 언어 L${\displaystyle (G)}$ ${\displaystyle =}$ { ${\displaystyle \mathrm{an}}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle \mathrm{cn}{}^{}}$: n ${\displaystyle \ge }$ 1$}$ {\$displaystyle$ L$(G$) ${\displaystyle =}$ $\{a^{n}b^{n}c^{n}:n\geq$1\}은 $CFMG$${\displaystyle }$$$$=$ ($N,$ $S$$)$ {\$displaystyle$ G $=$ {$S}$에 의해 생성됩니다.${\displaystyle T}$ ${\displaystyle =}$ {${\displaystyle a,}$ $}{\displaystyle$ T$=\{a, b,$ c\}가$$ 단자 집합이고 행렬 $집합$은${\displaystyle }$M$:{\displaystyle$ M$:\}$${\displaystyle }$ [${\displaystyle S}$${\displaystyle \to }$ ${\displaystyle a}$c$$] {$displaystyle \left[S$ \$rightarrow$abc\$right$ [${\displaystyle S}$$$${\displaystyle \to }$ A ${\displaystyle \mathrm{BC}}$${\displaystyle C}$] $디스플레이$스타일 \$left[S$ \$rightarrow Abc\],$${\displaystyle B}$${\displaystyle \to <img\; alt="\backslash left[S\backslash right\; 화살표\; a\; AbBcC\backslash right]"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/3627dbfc269dcd0c3a7e5a7aef3722098d1ca27e"\; style="vertical-align:\; -0.838ex;\; width:14.915ex;\; height:2.843ex;">}$ B }, ${\displaystyle B}$$$→ ${\displaystyle B}$ right$displaystyle \left[$$A\right$ arrow $aA,B\right$arrow bB,C\$right$ arrow $cC\right$$]\},$ [${\displaystyle A\to a}$,${\displaystyle B}$$$${\displaystyle \to b}$,${\displaystyle C}$ →${\displaystyle c}$] \$displaystyle \left[$$A\rightarrow$ a$,B\rightarrow$ b$,C\rightarrow$ c$\right$

시간 변형 문법

기본 개념
정의.
시간 변형 문법은 ($)$ \$displaystyle ($G, v) \displaystyle (G,$v)$쌍입니다$$. 여기서 G${\displaystyle }$${\displaystyle =}$ (${\displaystyle N,}$ ${\displaystyle T,P}$, $)$ {\$displaystyle$ G=($N$$,$ $T, P,$S)}는 문법이고${\displaystyle ,}$ ${\displaystyle v\mathbb{}}$ → $({$v:\$mathbb${N$} \rightarrow$ 2$^{P})}$는 자연수 집합의 집합에서 부분 집합의 집합까지의 함수입니다.

프로그래밍된 문법

기본 개념

정의.

프로그래밍된 문법은 ${\displaystyle 한}{\displaystyle }$쌍${\displaystyle (G}$,${\displaystyle }$s$$) {$displaystyle (G, s)}$이며, 여기서 G ${\displaystyle =}$ (${\displaystyle N,}$ ${\displaystyle T,}$P, $)$ {$displaystyle$ G=($N, T, P$, $S)}$은 $문법$이고${\displaystyle ,}$ s,${\displaystyle f}$ : ${\displaystyle {\mathrm{}}^{}}$ → ${\displaystyle {2P}^{}}$ ${$$P\rightarrow 2^{P}}$는 생산 집합에서 생산 집합의 하위 집합 클래스까지의 성공 및 실패 함수입니다.

정규 제어 언어가 있는 문법

기본 개념

정의.
정규$$ 언어를 사용하는 문법, GWRCL({$displaystyle$${\displaystyle \mathrm{GWRL}}$})은 쌍${\displaystyle (G},{\displaystyle }$ e$){displaystyle(G,$e)}입니다. 여기서 G$=(N$ $T$ $P,$ $)$는 $문법$이고$$e${$$displaystyle}$는 일련의 제품 알파벳 위에 있는 정규 표현입니다.

순진한 예

$CFG{\displaystyle }$ G ${\displaystyle =}$ (${\displaystyle N,}$ ${\displaystyle T,}$ ${\displaystyle P,S}$) {\$displaystyle$ G=($N, T$, $P, S)}$를 생각해 보십시오. $여기$서 N ${\displaystyle =}$ {$,$, $}$는 비종단 집합이고, T ${\displaystyle =}$ {${\displaystyle a,}$ ${\displaystyle B,}$ $}$는 p${\displaystyle ={}_{}}${${\displaystyle {}_{}}$$, B,$ C\}, ${\displaystyle p_{}}$는 p는 2${\displaystyle {}_{}}$ ${\displaystyle p_{}}$는 p는 2${\displaystyle {}_{}}$ p는 2로 ${\displaystyle {}_{}}$됩니다.$p$ 6 $}$ ${\displaystyle$ P$$${\displaystyle {}_{}}$ $\{p_{0},p_{1},p_{2},p_{3},p_{4},$p_$${5},p_{6}\},${\displaystyle p}$ ${\displaystyle C}$ ${\displaystyle {}_{}}$ A$$\$rightarrow$ $ABC$$}$ ${\displaystyle p_{}}$ 1 ${\displaystyle =}$ ${\displaystyle A}$$→$ A \\$displaystyle P_{1$$}$ ${\displaystyle {B\mathrm{}}_{}}$ B $right$ A$,Bright$ $B_2$$=$ $B_styleight$ }${\displaystyle {p\mathrm{}}_{}}$ 3 ${\displaystyle =}$ $→$ ${\displaystyle C}$ \ $displaystyle p_{3}$$=$$C$ \ $rightarrow$ ${\displaystyle c_{}}$$$${\displaystyle =}$ ${\displaystyle A}$ ${\displaystyle {}_{}}$ ${\displaystyle a}$\ $displaystyle$ $p_$${4}= A$ \ $rightarrow$ a$,$ $p{\displaystyle {}_{}}$ ${\displaystyle {5\mathrm{}}_{}}$ ${\displaystyle {}_{}}$$$ ${\displaystyle \to }$ ${\displaystyle b}$ \ $displaystyle p_$${5}$$=$$B$ \ $rightarrow$ b$,$ ${\displaystyle {및\mathrm{}}_{}}$ p ${\displaystyle 6}$ $→$ ${\displaystyle C}$ =$$C \ $displaystylearrow$ C \ $rightarrow$$C$는 명확합니다.${\displaystyle L}$(${\displaystyle G)}$ $=$ {${\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle {\ast }^{}}$ ${\displaystyle {}^{}{}^{}}$ $}${{$displaystyle$ L$(G$)=\{$a^{*}b^{*}c$ 이제, 곱집합 P$(displaystyle$ P$)$를 알파벳으로 고려하면,P$${\$displaystyle$ P$\}$에 대한 정규식 정의: $=$ ${\displaystyle {}_{}}$ (${\displaystyle {p\mathrm{}}_{}}$ 1 ${\displaystyle {}_{}{}_{}}$ 2 ${\displaystyle {p\mathrm{}}_{}{}^{}}$3 )${\displaystyle {}^{}}$∗ (${\displaystyle {}_{}{}_{}}$ 4 ${\displaystyle {}_{}{}_{}}$ 5 ${\displaystyle {p\mathrm{}}_{}}$ 6$$) {\$displaystyle$ e$=p_${0$}(p_{1}p_{2}p_{3})^{*}(p_{4}p_{5}p_{6$

CFG $문법{\displaystyle }$ G${displaystyle$ G$}$와 정규 $표현{\displaystyle }$ e{$displaystyle$ e$\}$를 결합하여 CFGWRL (${\displaystyle G,}$ $=$ (${\displaystyle G}$, ${\displaystyle {}_{}{0\mathrm{}}_{}}$ (${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$ p ${\displaystyle {}_{}{}_{}}$ p ${\displaystyle {3\mathrm{}}_{}{}^{}}$)$$ ( ${\displaystyle {p\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {p\mathrm{}}_{}}$ 5 ${\displaystyle {p\mathrm{}}_{}}$ 6${\displaystyle }$) \"$displaystyle (G,$e) = ($G,$$p_{0}(p_{1}p_{2}p_{3})^{*}(p_{4}p_{5}p_{6})}$ $언어$를 생성하며, 이 언어는${\displaystyle L(G}$)$=$ {${\displaystyle \mathrm{an}}$ ${\displaystyle n^{}\ge }$ 1$}{{a^{n}b{n}c^{n}$c^{$n}}}\geq$ 1$\}}$입니다$.$

규제된 재작성이 있는 다른 문법들 외에도, 위에 인용된 네 가지는 튜링 기계의 강력한 문법 장치를 얻기 위해 어떤 종류의 제어 메커니즘으로 문맥 없는 문법을 확장하는 방법의 좋은 예입니다.

레퍼런스

• 살로마아, 아르토 (1973) 형식 언어.아카데믹 프레스, ACM 모노그래프 시리즈

• Rozenberg, G.; Saloma, A. (ed.) 1997, 공식 언어 핸드북.베를린; 뉴욕: 스프링거 ISBN3-540-61486-9 (세트) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491 : v. 3)

• Dassow, Jürgen; Paun, G. 1990, 형식 언어 이론에서의 Regulated Rewriting ISBN 03875147.Springer-Verlag New York, Inc.Secaucus, 뉴저지, 미국, 페이지: 308. 매체:하드커버.

• Dassow, Jürgen, Regulated Rewriting이 있는 문법.스페인 Tarragona, 2006 제5회 박사과정 "형식적 언어와 응용" 강의

• 아브라함, S. 1965언어 이론의 몇 가지 질문들, 컴퓨터 언어학에 관한 1965년 국제 회의의 진행, 1-11페이지, 독일 본,