문맥 의존 문법

문맥감응문법(CSG)은 생성규칙의 왼쪽과 오른쪽이 종단 및 비단말기호의 문맥으로 둘러싸이는 형식문법입니다.문맥 의존형 문법은 문맥 의존형 문법보다 일반적입니다.즉, CSG에 의해 기술될 수 있지만 문맥 의존형 문법에 의해 기술되지 않는 언어가 있다는 의미입니다.문맥에 민감한 문법은 제한되지 않은 문법에 비해 일반적이지 않습니다(같은 의미).따라서 CSG는 촘스키 ^[1]계층에서 문맥이 없는 문법과 제한되지 않은 문법 사이에 배치됩니다.

문맥에 민감한 문법, 또는 그에 상응하여 비계약적인 문법 또는 선형 경계 자동화에 의해 기술될 수 있는 형식 언어는 문맥에 민감한 언어라고 불립니다.1959년 ^[6]^[7]노암 촘스키가 CSG를 정의한 방식은 아니지만 일부 교과서는 CSG를 사실상 ^[2]^[3]^[4]^[5]비계약으로 정의하고 있다.이 정의의 선택은 생성된 언어(즉, 두 정의가 약하게 동등함)의 측면에서 차이가 없지만, 구조적으로 문맥에 따라 고려되는 문법의 측면에서 차이가 난다. 후자의 문제는 1963년에 ^[8]^[9]촘스키에 의해 분석되었다.

촘스키는 문맥에 따라 단어가 특정 장소에서 적절할 수도 있고 적절하지 않을 수도 있는 자연어의 구문을 설명하는 방법으로 문맥에 민감한 문법을 도입했다.Walter Savitch는 "문맥 의존적"이라는 용어를 오해의 소지가 있다고 비판하고 CSG와 제한 없는 ^[10]문법의 차이를 더 잘 설명하는 "비 삭제"를 제안했다.

언어의 특정 특징(예: 직렬 간 의존성)이 문맥이 없는 것은 잘 알려져 있지만, 자연 언어에서 발견되는 문맥 감도를 포착하기 위해 CSG의 표현력이 얼마나 필요한지는 미해결 문제이다.이 영역의 후속 연구는 계산적으로 다루기 쉬운 경미한 문맥에 민감한 ^{[citation needed]}언어에 초점을 맞췄다.일부 비주얼 프로그래밍 언어의 구문은 상황에 맞는 그래프 ^[11]문법으로 설명할 수 있습니다.

형식적 정의

형식 문법 G = (N, δ, P, S)는 N개의 비말단 기호 세트, δ의 종단 기호 세트, P의 생산 규칙 세트, 그리고 S의 시작 기호가 있는 경우 문맥에 민감하다.

αAβ → αγβ

A n N,^{[note 1]} α, β ( N(^*NΩ) 및 γ N n N(⁺^{[note 3]}NΩ)이다.

u가 lαAβr로 쓸 수 있고, v가 lαAβr로 쓸 수 있는 경우, 문자열 u δ(^*Nδ)는 직접 생성되거나 직접 유도되며, 일부 제조 규칙(αAβ→αββ) δP 및 일부 컨텍스트 rδ로 쓸 수 있는 경우, 문자열 uδ(^*Nδ)는 직접 생성되거나 직접 유도된다.보다 일반적으로, u는₁ u = u u ... ...일 경우 u ⇒^* v로 표시되는 v를 산출하거나 도출하는 것으로 알려져 있다.일부 nΩ0 및 일부_n-1 문자열₂ u, ..., u(NΩ)^*에 대해 u_n = v.즉, 관계())^*는 관계(⇒)의 반사적 경과적 폐쇄이다.

문법 G의 언어는 시작 기호에서 파생할 수 있는 모든 종단 기호 문자열의 집합입니다. 형식적으로 L(G) = { w ∈ σ^* : S ^*⇒ w }. 종단 기호로 구성된 문자열로 끝나지 않는 파생은 가능하지만 L(G)에는 기여하지 않습니다.

촘스키의 정의와 제한 없는 문법의 정의의 유일한 차이점은 제한되지 않은 경우 ^[10]can가 비워질 수 있다는 것입니다.

문맥에 민감한 문법의 일부 정의는 u → v 형식의 생산 규칙에 대해 u의 길이가 v의 길이보다 작거나 같아야 한다고 요구한다.이 약한 요건은 실제로는 약하게 ^[12]동등합니다.「비계약 문법 #문맥 의존 문법으로 변환」을 참조해 주세요.

또한 양식의 규칙

S → λ

여기서 "는 빈 문자열을 나타내며 S는 규칙 오른쪽에 표시되지 않습니다.빈 문자열을 추가하면 문맥에 민감한 언어가 문맥이 없는 언어의 적절한 슈퍼셋이라는 진술을 할 수 있습니다. →문맥이 없는 모든 문맥이 없는 문법도 문맥에 민감한 문법이라는 약한 진술을 할 필요가 없습니다.

문맥 민감이라는 이름은 A의 문맥을 형성하고 A를 β로 치환할 수 있는지 여부를 결정하는 α와 β로 설명된다.이것은, 비단말기의 문맥이 고려되지 않는 문맥이 없는 문법과 다릅니다.실제로 문맥이 없는 문법의 모든 생산은 V → w 형식이다. 여기서 V는 단일 비말단 기호이고 w는 단자 및/또는 비말단의 문자열이다. w는 비워 둘 수 있다.

빈 문자열을 언어에 추가할 수 있는 가능성이 계약되지 않은 문법(빈 문자열을 포함할 수 없음)에 의해 인식되는 문자열에 추가되면 이들 2가지 정의의 언어는 동일합니다.

좌뇌변형 및 우뇌변형 민감 문법은 각각 αA → αγ 및 Aβ → β로 규칙을 제한함으로써 정의된다.이러한 문법에 의해 생성된 언어도 문맥에 민감한 ^[13]언어의 전체 클래스입니다.동등성은 펜토넨 정규형에 ^[14]의해 확립되었다.

예

aⁿbⁿcⁿ

다음 문맥 의존 문법은 시작 기호 S를 사용하여 표준 비문맥 자유 언어 {abcⁿⁿⁿ : n 1 1 }^{[citation needed]}을 생성합니다.

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c

규칙 1과 2는 S를 aBCⁿ(BC)^n-1로 확대하는 것을 허용하고, 규칙 3에서 6은 각 CB를 BC로 순차적으로 교환하는 것을 허용한다(규칙 CB → BC는 체계 αAβ → α412ββ)에 적합하지 않기 때문에 규칙 7-10은 각각 비규칙 B와 C를 대응하는 단말 C로 대체하는 것을 허용하고 있다).aaabbbcc의 생성 체인은 다음과 같습니다.

S

→ ₂aSBC

→₂ aaSBCBC

→₁ AAABCBCBC

→₃ aaaBCZCBC

→₄ aaaBWZCBC

→₅ aaaBWCCBC

→₆ aaaBCCBC

→₃ aaaBCCZC

→₄aaaBBCWZC

→₅aaaBBCWCC

→₆aaaBBCB참조

→₃aaaBBCZ참조

→₄ aaaBBWZ참조

→₅ aaaBBWCCC

→₆AAABBBCCC

→₇ aaabBBCCC

→₈ aaabbBCCC

→₈ aaabbbCCC

→ ₉aaabbc참조

→₁₀ aaabbbccC

→₁₀ aaabbbccc

abcdⁿⁿⁿⁿ 등

보다 복잡한 $문법$ $C$ $S$ G $(\displaystyle CSG)$ 를 $CSG$ 사용하여 {abcdⁿⁿⁿⁿ: n 1 1 } 및 더 많은 문자를 가진 다른 언어를 해석할 수 있습니다.여기 우리가 더 간단한 방법 규칙적인 생산량의 커널은 문장의 형태를 생성하non-contracting grammars:[표창 필요한]시작 사용한 bcd{\displaystyle(에이비 시디)^{n}abcd n(ABCD)} 다음이 아닌 계약 생산 pD:D→ D를{\displaystyle p_{다}이 포함됩니다.}, p DaD Da\rightarrow을 보여 주B:Db→ bD. $({displaystyle p_{Db$ }: Db\ $right 화살표$ bD $p_{Db}:Db\rightarrow bD$ $Dc$ : $Dc→c\right$ 화살표 $cD$ $p_{Dd}:Dd\rightarrow dd$ $dd,$ $p_{Ca}:Ca\rightarrow aC$ D: Dd\ $right 화살표 p_{Dddd$ $p_{Ca}:Ca\rightarrow aC$ $p_{Dc}:Dc\rightarrow cD$ D: Ddd\rightrow p $C$ : $C$ $:$ C: C: C: $displaystyle$ A.→ $c$ { display $style p$ _ { $Cc$ } : $Cc$ \ $rightarrow$ cc $p_{Cc}:Cc\rightarrow cc$ , $p_{Ba}:Ba\rightarrow aB$ : $p_{Ba}:Ba\rightarrow aB$ a $p_{Ba}:Ba\rightarrow aB$ → $B$ \ $display p_$ {Ba $:$ $Ba\right$ $화살표$ $aB$ , $p_{Bb}:Bb\rightarrow bb$ $p_{Bb}:Bb\rightarrow bb$ : $p_{Bb}:Bb\rightarrow bb$ $p_{Bb}:Bb\rightarrow bb$ { $displaystyle p_{Bb$ , $p_{Aa}:Aa\rightarrow aa$ $p_{Aa}:Aa\rightarrow aa$ : $p_{Aa}:Aa\rightarrow aa$ $p_{Aa}:Aa\rightarrow aa$ { $displaystyle p_{Aa}$ : $Aa\오른쪽 화살표$ aa $p_{Aa}:Aa\rightarrow aa$

a^mbⁿc^mdⁿ

$L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ { $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ m $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ n : m $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ 1, n $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ 1 $L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}$ 1 1 $}$ { $display style$ L_{ Cross } = \ { $a$ ^ { $m$ } $b$ ^ { $c$ ^ { c } { n $geq }$ 에 $CSG$ 하는 $C$ S $G$ { $displaystyle$ CSG $CSG$ } 가 있는 비계약 문법: $R\right$ 화살표 $aRC aC}$ 및 $p_{1}:R\rightarrow aRC|aC$ $p_{3}:T\rightarrow BTd|Bd$ : $p_{3}:T\rightarrow BTd|Bd$ $p_{3}:T\rightarrow BTd|Bd$ $p_{3}:T\rightarrow BTd|Bd$ $p_{3}:T\rightarrow BTd|Bd$ $p_{3}:T\rightarrow BTd|Bd$ B $p_{3}:T\rightarrow BTd|Bd$ \ $display$ style $p_{$ } : $T\right$ 화살표 $BTd$ Bd $p_{3}:T\rightarrow BTd|Bd$ $p_{5}:CB\rightarrow BC$ 5 : $p_{5}:CB\rightarrow BC$ B $p_{5}:CB\rightarrow BC$ $p_{5}:CB\rightarrow BC$ (\ $style p_{5}):$ $CB\rightarrow$ $p_{0}:S\rightarrow RT$ $p_{5}:CB\rightarrow BC$ , $p_{0}:S\rightarrow RT$ : $p_{0}:S\rightarrow RT$ $→$ $p_{0}:S\rightarrow RT$ T { $displaystyle p$ _ { $0$ } : $S\rightarrow$ RT $p_{0}:S\rightarrow RT$ $p_{6}:aB\rightarrow ab$ $p_{6}:aB\rightarrow ab$ B $aB \rightarrow$ ab $p_{6}:aB\rightarrow ab$ $p_{7}:bB\rightarrow bb$ $p_{8}:Cd\rightarrow cd$ $p_{7}:bB\rightarrow bb$ : $B$ \ $displaystyle p_{7$ : B \ $rightarrow$ $p_{8}:Cd\rightarrow cd$ $p_{8}:Cd\rightarrow cd$ : $p_{8}:Cd\rightarrow cd$ $p_{8}:Cd\rightarrow cd$ $p_{8}:Cd\rightarrow cd$ \ displaystyle $p_{9}:Cc\rightarrow cc$ ${8$ : $cdisplaystyle p_rightarrow$ c 9 $p_{9}:Cc\rightarrow cc$ , $p_{9}:Cc\rightarrow cc$ $p_{8}:Cd\rightarrow cd$ : $p_{9}:Cc\rightarrow cc$ $p_{8}:Cd\rightarrow cd$ : c : $p_{9}:Cc\rightarrow cc$ .

이러한 정의에 따라 $a^{3}b^{2}c^{3}d^{2}$ $a^{3}b^{2}c^{3}d^{2}$ 2 $a^{3}b^{2}c^{3}d^{2}$ $a^{3}b^{2}c^{3}d^{2}$ $({$ a $^{3$ } b $^{2}$ c $^{3}d^{2})$ d^{2})의 $a^{3}b^{2}c^{3}d^{2}$ 도출은 $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ 과 $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ p 0 $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ p 1 2 $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ 3 $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ B 2 $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ . 2 . $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ $RT\오른쪽 화살표 _{p_{1}^{2}p_{2}}a^{3$ $}C^{3}T\오른쪽 화살표_{p_{3}p_{4}}a^{3$ $}C^{3}B^{2}d^{2}\오른쪽 화살표_{p_{5}^6$ } $B^{2}C^{3}d^{$ 2}\ $오른쪽 화살표 _{p_{6}p_{7}}a^{3}b^{2$ }C $^{$ 3} $d^{2}\오른쪽$ 화살표 _{ $p_{8}p_{9}{$ 2}^{2}}a $^{3$ }b $^{c}{$ 3} $d$ ^{[citation needed]}2 $}}}}}{d}}}}}}}{}}}.$

a^2개ⁱ

{a^2ⁱ : i 1 1 } 언어에 대한 비계약 문법은 (Hopcroft, Ulman, 1979년)^[15]의 예 9.5 (p.224)에 구성되어 있다.

$S\right 화살표 [ACAB]$
$오른쪽 화살표 aa[Ca] \ displaystyle \ begin { case } \\\[Ca][aB]\오른쪽 화살표 aa[CaB]\\\[ACA]a\오른쪽 화살표[Aa]a[Ca]\\[ACA][aB]\오른쪽 화살표 [Aa]a[CaB]\\\[ACAB]\오른쪽 화살표 [Aa][aCB]\\\ [ CaB ]\ rightarrow a [ aCB ]\end { case }$
${\displaystyle [aCB]\rightarrow [aDB]$
${\displaystyle [aCB]\rightarrow [aE]$
$\[ display style \ begin { case \ a ] \ rightarrow [ Da ]a \ \ \ \ \ \ rightarrow [ DaB ]\\\ [ Aa ] [ Da ] \ rightarrow [ ADA ]a \ \ \ \ \ \ \ \ \ \ rightarrow [ Da ][ aB ] \\\ [ Aa ] [ DaB ] \ rightarrow [ ADA ][ aB ] \ end { case }$
$[ADA]\rightarrow [ACA]$
$\ displaystyle \ begin { case \ a [ Ea ] \ rightarrow [ Ea ]a \ \ \ \ rightarrow [ Ea ] \\\ [ Aa ] [ Ea ] \ rightarrow [ AEA ]a \ end { case }$
$[AEA]\오른쪽 화살표 a$

쿠로다 정형

빈 문자열을 생성하지 않는 문맥 의존 문법은 모두 구로다 정규 형식으로 약등가 문법으로 변환할 수 있다.여기서 "약하게 동등한 것"은 두 문법이 같은 언어를 생성한다는 것을 의미합니다.통상적인 형식은 일반적으로 문맥에 구애받지 않고 계약하지 않는 ^[16]^[17]문법이 됩니다.

구로다 노멀형은 무수축 문법의 실제 노멀 형식입니다.

속성 및 용도

선형 유계 오토마톤에 대한 동등성

형식 언어는 LBA(^[18]Linear Bounded Automaton)에 의해 받아들여지는 경우에만 상황에 맞는 문법으로 기술할 수 있습니다.일부 교과서에서 이 결과는 랜드웨버와 쿠로다에만 기인한다.^[7]다른 사람들은 그것을 마이힐-랜드웨버-쿠로다 ^[19]정리라고 부른다.(Myhill은 1960년에 결정론적 LBA의 개념을 도입했다.Peter S. Landweber는 1963년에 결정론적 LBA에 의해 받아들여진 언어는 문맥에 민감하다고 발표했다.구로다는 1964년에 비결정론적 LBA의 개념과 LBA와 CSG의 동등성을 도입하였다.)^[20]^[21]

2010년 현재^[update], 모든 문맥에 민감한 언어가 결정론적 ^[22]LBA에 의해 받아들여질 수 있을지는 여전히 미해결이다.

닫힘 속성

문맥에 민감한 언어는 보완 하에 폐쇄됩니다.1988년 결과는 이머만-셀렙세니 ^[19]정리라고 알려져 있다.게다가, 그것들은 결합, 교차, 연결, 치환,^{[note 4]} 역동형사상 및 클린 ^[23]플러스에 의해 닫힌다.

각 재귀 열거 가능 언어 L은 문맥에 민감한 언어 L 및 문자열 동형사상 ^[24]h에 대해 h(L)로 쓸 수 있다.

계산상의 문제

특정 문자열이 특정 문맥 의존 문법 G의 언어에 속하는지 여부를 묻는 결정 문제는 PSPACE-complete입니다.게다가 PSPACE-완전 언어인 문맥 의존 문법도 있습니다.즉, 어떤 문자열이 G의 언어에 속하는지 여부를 PSPACE-complete로 판정하는 상황 의존 문법 G가 있다(따라서 G는 고정되고 s만이 ^[25]문제의 입력의 일부이다).

문맥 의존 문법(문맥 의존 문법 G가 주어지면 L(G)=문맥?)의 공허 문제는 결정할 ^[26]^{[note 5]}수 없다.

자연어 모델로서

Savitch는 다음과 같은 이론적 결과를 증명했습니다.그 결과, 자연어의 기초로서 CSG에 대한 비판에 근거하고 있습니다.재귀적으로 열거할 수 있는 집합 R에 대해서, 다음과 같은 방법으로 R의 멤버쉽을 테스트하기 위한 일종의 프록시로 사용할 수 있는 컨텍스트에 민감한 언어/문법 G가 존재합니다. 문자열 s는 exis가 존재하는 경우에만 R에 있습니다.ts sc가 G에 있는 양의ⁿ 정수 n. 여기서 c는 ^[10]R의 일부가 아닌 임의의 기호입니다.

일반적으로 거의 모든 자연어가 문맥에 맞는 문법에 의해 특징지어질 수 있지만, CSG의 전체 클래스는 ^{[citation needed]}자연어보다 훨씬 더 큰 것으로 보인다.더욱이 CSG에 대한 전술한 의사결정 문제가 PSPACE-완전이기 때문에 PSPACE-완전 문제에 대한 다항식 시간 알고리즘은 P=NP를 의미하므로, CSG는 완전히 실용적으로 사용할 수 없게 된다.

일부 자연 언어는 이른바 교차 직렬 종속성과 무한 스크램블링 현상을 식별함으로써 문맥이 없는 언어가 아니라는 것이 입증되었습니다.그러나 이것이 반드시 모든 클래스 CSG가 자연어로 이러한 용어의 구어적 의미에서의 "콘텍스트 감도"를 포착하기 위해 필요한 것은 아니다.예를 들어 CSG보다 완전히 약한(CSG보다 약한) Linear Context-Free Rewriting Systems(LCFRS; 컨텍스트프리 리라이트 시스템)는 크로스 시리얼 의존성의 현상을 설명할 수 있습니다.예를 들어 ^[27]^[28]^[29]{abcdⁿⁿⁿⁿ n 1 1)의 LCFRS 문법을 쓸 수 있습니다.

컴퓨터 언어학에 대한 지속적인 연구는 트리 결합 문법, 조합 범주형 문법, 결합된 문맥 자유 언어 및 선형 문맥 자유 재작성 시스템과 같이 결정 문제가 실현 가능한 "원만한 문맥 민감" 언어의 다른 클래스를 공식화하는 데 초점을 맞추고 있습니다.이러한 형식주의에 의해 생성된 언어는 문맥이 없는 언어와 문맥에 민감한 언어 사이에 적절히 놓여 있습니다.

최근에는 클래스 PTIME이 범위 연결 문법에 의해 식별되었습니다.이 문법은 현재 온화한 컨텍스트에 민감한 언어 클래스 ^[29]중 가장 표현력이 높은 것으로 간주되고 있습니다.

「」를 참조해 주세요.

메모들

^ 즉, A 단일 비단말기
^ 즉, 비단말기 및 단말기의 α 및 β 문자열
^ 즉, is는 비말단 및 단말기의 비어 있지 않은 문자열입니다.
^ 좀 더 형식적으로: L σ^* a σ 、 컨텍스트 의존형 언어 f(a)에 각 a ∈ each each each 、 f(L)는 다시 컨텍스트 의존형 언어입니다.
^ 이것은 또한 (1) 문맥이 없는 언어도 문맥에 민감하고 (2) 문맥에 민감한 언어는 교차로 아래에서 닫히지만 (3) 문맥이 없는 언어의 불협화음을 결정할 수 없기 때문이다.

레퍼런스

^ (홉크로프트, Ulman, 1979년); 9.4장, 227페이지
^ Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. p. 291. ISBN 978-1-4496-1552-9.
^ Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 730. ISBN 978-1-85233-074-3.
^ Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. p. 189. ISBN 978-0-08-050246-5.
^ Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGraw-Hill. p. 277. ISBN 9780073191461.
^ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. p. 26. ISBN 978-90-272-3250-2.
^ ^a ^b Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. pp. 330–331. ISBN 978-0-08-050246-5.
^ Chomsky, N. (1963). "Formal properties of grammar". In Luce, R. D.; Bush, R. R.; Galanter, E. (eds.). Handbook of Mathematical Psychology. New York: Wiley. pp. 360–363.
^ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 125–126. ISBN 978-90-272-3250-2.
^ ^a ^b ^c Carlos Martín Vide, ed. (1999). Issues in Mathematical Linguistics: Workshop on Mathematical Linguistics, State College, Pa., April 1998. John Benjamins Publishing. pp. 186–187. ISBN 90-272-1556-1.
^ 장, 다첸, 강장, 지안농조."시각 언어 지정에 대한 문맥 의존 그래프 문법 형식주의"컴퓨터 저널 44.3 (2001) : 186 ~200.
^ Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 9780201029888.; 페이지 223–224; 연습 9, 페이지 230.2003년판에서는 CSG에 관한 장은 생략되어 있습니다.
^ Hazewinkel, Michiel (1989). Encyclopaedia of Mathematics. Vol. 4. Springer Science & Business Media. p. 297. ISBN 978-1-55608-003-6. https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive에서도 확인하실 수 있습니다.
^ 이토, 마사미, 고바야시, Yūji, 쇼지, Kunitaka(2010년).자동자, 형식 언어와 대수적 시스템:담론 AFLAS는 2008년 일본 교토 20–22 2008년 9월.세계 과학. 우편 183. 아이 에스비엔 978-981-4317-60-3. 이유로 Penttonen,인 마르티(8월 1974년)."공식적인 grammars에 양면One-sided 컨텍스트".정보와 제어이다. 25(4):371–392. doi:10.1016(74)91049-3.
^
그들은 제한되지 않은 문법을 체계적으로 변환하여 문법을 얻었다.
1. $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ B({ $디스플레이$ 스타일 S\ $오른쪽$ 화살표 $ACaB$
2. $Ca\rightarrow aaC$ a $Ca\rightarrow aaC$ $Ca\rightarrow aaC$ \ $display$ Ca \ $rightarrow aaC$
3. $CB\rightarrow DB$ B $CB\rightarrow DB$ $디스플레이$ 스타일 CB\ $오른쪽$ 화살표 $DB}),$
4. $CB\rightarrow E$ B $CB\rightarrow E$ { $style$ CB\ $right 화살표$ E $CB\rightarrow E$
5. $aD\rightarrow Da$ D $aD\rightarrow Da$ $aD\rightarrow Da$ a $\style aD\right 화살표$ Da $aD\rightarrow Da$
6. $AD\rightarrow AC$ D $AD\rightarrow AC$ $AD\rightarrow AC$ C { $displaystyle$ AD $\right 화살표$ AC $AD\rightarrow AC$
7. $aE\rightarrow Ea$ E $aE\rightarrow Ea$ $aE\rightarrow Ea$ a $\display aE\right 화살표$ Ea $aE\rightarrow Ea$
8. $AE\rightarrow \varepsilon$ E $AE\rightarrow \varepsilon$ \ $style$ AE $\right$ 화살표 $\varepsilon$
문맥 의존형 문법에서는 [ $[ACaB]$ $[ACaB]$ a $[ACaB]$ B $]$ \ $displaystyle$ [ $ACAB$ 와 $[ACaB]$ 같이 대괄호로 둘러싸인 문자열은 단일 기호로 간주됩니다(예: <name-part>백커스-나우르 형태로).기호 이름은 제한되지 않은 문법과 유사하도록 선택됩니다.마찬가지로 문맥 의존 문법의 규칙 그룹에는 원래 규칙인 무제한 문법 규칙에 따라 번호가 매겨집니다.
^ Kuroda, Sige-Yuki (June 1964). "Classes of languages and linear-bounded automata". Information and Control. 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.
^ Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto (eds.). Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. pp. 175–252. ISBN 3-540-61486-9., 여기서 : 정리 2.2, 페이지 190
^ (홉크로프트, Ulman, 1979년)정리 9.5, 9.6, 페이지 225–226
^ ^a ^b "Archived copy" (PDF). Archived from the original (PDF) on 2017-02-03. Retrieved 2019-08-29.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
^ Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 755. ISBN 978-1-85233-074-3.
^ Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2.
^ Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGraw-Hill. p. 283. ISBN 9780073191461.
^ (홉크로프트, Ulman, 1979년); 연습 S9.10, 페이지 230–231
^ (Hopcroft, Ulman, 1979년); 연습 S9.14, 페이지 230–232.h는 각 기호를 자체 또는 빈 문자열에 매핑합니다.
^ 그러한 문법, QSAT 문제를 해결하도록 설계된 예 리타, CV(2016-09-01)에 수록되어 있다."그 감지의 문제 Bounded 길이 Polymorphic 바이러스에 복합성에". 2016년 18일 국제 심포지엄에 상징성과 숫자 알고리즘을 과학 컴퓨팅(SYNASC):371–378. doi:10.1109/SYNASC.2016.064.아이 에스비엔 978-1-5090-5707-8.S2CID 18067130.
^ (홉크로프트, Ulman, 1979년); 연습 S9.13, 페이지 230–231
^ Kallmeyer, Laura (2011). "Mildly Context-Sensitive Grammar Formalisms: Natural Languages are not Context-Free" (PDF).
^ Kallmeyer, Laura (2011). "Mildly Context-Sensitive Grammar Formalisms: Linear Context-Free Rewriting Systems" (PDF).
^ ^a ^b Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. pp. 1–5. ISBN 978-3-642-14846-0.

추가 정보

Meduna, Alexander; Švec, Martin (2005). Grammars with Context Conditions and Their Applications. John Wiley & Sons. ISBN 978-0-471-73655-4.

외부 링크

콘텍스트 의존 문법의 얼리 해석

[12] 즉, A 단일 비단말기

[13] 즉, 비단말기 및 단말기의 α 및 β 문자열

[14] 즉, is는 비말단 및 단말기의 비어 있지 않은 문자열입니다.

[26] 좀 더 형식적으로: L σ^* a σ 、 컨텍스트 의존형 언어 f(a)에 각 a ∈ each each each 、 f(L)는 다시 컨텍스트 의존형 언어입니다.

[31] 이것은 또한 (1) 문맥이 없는 언어도 문맥에 민감하고 (2) 문맥에 민감한 언어는 교차로 아래에서 닫히지만 (3) 문맥이 없는 언어의 불협화음을 결정할 수 없기 때문이다.

[1] (홉크로프트, Ulman, 1979년); 9.4장, 227페이지

[Linz2011-2] Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. p. 291. ISBN 978-1-4496-1552-9.

[Meduna2000-3] Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 730. ISBN 978-1-85233-074-3.

[DavisSigal1994-4] Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. p. 189. ISBN 978-0-08-050246-5.

[5] Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGraw-Hill. p. 277. ISBN 9780073191461.

[Levelt2008-6] Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. p. 26. ISBN 978-90-272-3250-2.

[DavisSigal1994b-7] Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. pp. 330–331. ISBN 978-0-08-050246-5.

[8] Chomsky, N. (1963). "Formal properties of grammar". In Luce, R. D.; Bush, R. R.; Galanter, E. (eds.). Handbook of Mathematical Psychology. New York: Wiley. pp. 360–363.

[Levelt2008-126-9] Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 125–126. ISBN 978-90-272-3250-2.

[Vide1999-10] Carlos Martín Vide, ed. (1999). Issues in Mathematical Linguistics: Workshop on Mathematical Linguistics, State College, Pa., April 1998. John Benjamins Publishing. pp. 186–187. ISBN 90-272-1556-1.

[11] 장, 다첸, 강장, 지안농조."시각 언어 지정에 대한 문맥 의존 그래프 문법 형식주의"컴퓨터 저널 44.3 (2001) : 186 ~200.

[15] Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 9780201029888.; 페이지 223–224; 연습 9, 페이지 230.2003년판에서는 CSG에 관한 장은 생략되어 있습니다.

[Hazewinkel1989-16] Hazewinkel, Michiel (1989). Encyclopaedia of Mathematics. Vol. 4. Springer Science & Business Media. p. 297. ISBN 978-1-55608-003-6. https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive에서도 확인하실 수 있습니다.

[ItoKobayashi2010-17] 이토, 마사미, 고바야시, Yūji, 쇼지, Kunitaka(2010년).자동자, 형식 언어와 대수적 시스템:담론 AFLAS는 2008년 일본 교토 20–22 2008년 9월.세계 과학. 우편 183. 아이 에스비엔 978-981-4317-60-3. 이유로 Penttonen,인 마르티(8월 1974년)."공식적인 grammars에 양면One-sided 컨텍스트".정보와 제어이다. 25(4):371–392. doi:10.1016(74)91049-3.

[18] 그들은 제한되지 않은 문법을 체계적으로 변환하여 문법을 얻었다.
$S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ B({ $디스플레이$ 스타일 S\ $오른쪽$ 화살표 $ACaB$

$Ca\rightarrow aaC$ a $Ca\rightarrow aaC$ $Ca\rightarrow aaC$ \ $display$ Ca \ $rightarrow aaC$

$CB\rightarrow DB$ B $CB\rightarrow DB$ $디스플레이$ 스타일 CB\ $오른쪽$ 화살표 $DB}),$

$CB\rightarrow E$ B $CB\rightarrow E$ { $style$ CB\ $right 화살표$ E $CB\rightarrow E$

$aD\rightarrow Da$ D $aD\rightarrow Da$ $aD\rightarrow Da$ a $\style aD\right 화살표$ Da $aD\rightarrow Da$

$AD\rightarrow AC$ D $AD\rightarrow AC$ $AD\rightarrow AC$ C { $displaystyle$ AD $\right 화살표$ AC $AD\rightarrow AC$

$aE\rightarrow Ea$ E $aE\rightarrow Ea$ $aE\rightarrow Ea$ a $\display aE\right 화살표$ Ea $aE\rightarrow Ea$

$AE\rightarrow \varepsilon$ E $AE\rightarrow \varepsilon$ \ $style$ AE $\right$ 화살표 $\varepsilon$
문맥 의존형 문법에서는 [ $[ACaB]$ $[ACaB]$ a $[ACaB]$ B $]$ \ $displaystyle$ [ $ACAB$ 와 $[ACaB]$ 같이 대괄호로 둘러싸인 문자열은 단일 기호로 간주됩니다(예: <name-part>백커스-나우르 형태로).기호 이름은 제한되지 않은 문법과 유사하도록 선택됩니다.마찬가지로 문맥 의존 문법의 규칙 그룹에는 원래 규칙인 무제한 문법 규칙에 따라 번호가 매겨집니다.

[21] $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ B({ $디스플레이$ 스타일 S\ $오른쪽$ 화살표 $ACaB$

[22] $Ca\rightarrow aaC$ a $Ca\rightarrow aaC$ $Ca\rightarrow aaC$ \ $display$ Ca \ $rightarrow aaC$

[23] $CB\rightarrow DB$ B $CB\rightarrow DB$ $디스플레이$ 스타일 CB\ $오른쪽$ 화살표 $DB}),$

[24] $CB\rightarrow E$ B $CB\rightarrow E$ { $style$ CB\ $right 화살표$ E $CB\rightarrow E$

[25] $aD\rightarrow Da$ D $aD\rightarrow Da$ $aD\rightarrow Da$ a $\style aD\right 화살표$ Da $aD\rightarrow Da$

[26] $AD\rightarrow AC$ D $AD\rightarrow AC$ $AD\rightarrow AC$ C { $displaystyle$ AD $\right 화살표$ AC $AD\rightarrow AC$

[27] $aE\rightarrow Ea$ E $aE\rightarrow Ea$ $aE\rightarrow Ea$ a $\display aE\right 화살표$ Ea $aE\rightarrow Ea$

[28] $AE\rightarrow \varepsilon$ E $AE\rightarrow \varepsilon$ \ $style$ AE $\right$ 화살표 $\varepsilon$

[19] Kuroda, Sige-Yuki (June 1964). "Classes of languages and linear-bounded automata". Information and Control. 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.

[20] Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto (eds.). Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. pp. 175–252. ISBN 3-540-61486-9., 여기서 : 정리 2.2, 페이지 190

[21] (홉크로프트, Ulman, 1979년)정리 9.5, 9.6, 페이지 225–226

[flac-22] "Archived copy" (PDF). Archived from the original (PDF) on 2017-02-03. Retrieved 2019-08-29.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)

[23] Meduna, Alexander (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 755. ISBN 978-1-85233-074-3.

[24] Levelt, Willem J. M. (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2.

[25] Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGraw-Hill. p. 283. ISBN 9780073191461.

[27] (홉크로프트, Ulman, 1979년); 연습 S9.10, 페이지 230–231

[28] (Hopcroft, Ulman, 1979년); 연습 S9.14, 페이지 230–232.h는 각 기호를 자체 또는 빈 문자열에 매핑합니다.

[29] 그러한 문법, QSAT 문제를 해결하도록 설계된 예 리타, CV(2016-09-01)에 수록되어 있다."그 감지의 문제 Bounded 길이 Polymorphic 바이러스에 복합성에". 2016년 18일 국제 심포지엄에 상징성과 숫자 알고리즘을 과학 컴퓨팅(SYNASC):371–378. doi:10.1109/SYNASC.2016.064.아이 에스비엔 978-1-5090-5707-8.S2CID 18067130.

[30] (홉크로프트, Ulman, 1979년); 연습 S9.13, 페이지 230–231

[32] Kallmeyer, Laura (2011). "Mildly Context-Sensitive Grammar Formalisms: Natural Languages are not Context-Free" (PDF).

[33] Kallmeyer, Laura (2011). "Mildly Context-Sensitive Grammar Formalisms: Linear Context-Free Rewriting Systems" (PDF).

[Kallmeyer2010-34] Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. pp. 1–5. ISBN 978-3-642-14846-0.

[43] $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ $S\rightarrow ACaB$ B({ $디스플레이$ 스타일 S\ $오른쪽$ 화살표 $ACaB$

[44] $Ca\rightarrow aaC$ a $Ca\rightarrow aaC$ $Ca\rightarrow aaC$ \ $display$ Ca \ $rightarrow aaC$

[45] $CB\rightarrow DB$ B $CB\rightarrow DB$ $디스플레이$ 스타일 CB\ $오른쪽$ 화살표 $DB}),$

[46] $CB\rightarrow E$ B $CB\rightarrow E$ { $style$ CB\ $right 화살표$ E $CB\rightarrow E$

[47] $aD\rightarrow Da$ D $aD\rightarrow Da$ $aD\rightarrow Da$ a $\style aD\right 화살표$ Da $aD\rightarrow Da$

[48] $AD\rightarrow AC$ D $AD\rightarrow AC$ $AD\rightarrow AC$ C { $displaystyle$ AD $\right 화살표$ AC $AD\rightarrow AC$

[49] $aE\rightarrow Ea$ E $aE\rightarrow Ea$ $aE\rightarrow Ea$ a $\display aE\right 화살표$ Ea $aE\rightarrow Ea$

[50] $AE\rightarrow \varepsilon$ E $AE\rightarrow \varepsilon$ \ $style$ AE $\right$ 화살표 $\varepsilon$

[1]

[6]

[7]

[2]

[3]

[4]

[5]

[8]

[9]

[10]

[11]

[note 1]

[note 3]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[note 4]

[23]

[24]

[25]

[26]

[note 5]

[27]

[28]

[29]

Search

문맥 의존 문법

네임스페이스

더

목차

형식적 정의