문맥 의존 문법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

문맥 의존 문법(Context-sensitive grammar, CSG)은 형식 문법의 한 종류로, 생성 규칙 적용 시 기호의 앞뒤 문맥을 고려하여 생성되는 언어를 정의한다. 촘스키에 의해 도입되었으며, 문맥 자유 문법보다 더 복잡한 언어를 표현할 수 있다. 문맥 의존 문법은 선형 구속 오토마타와 동등하며, 자연어의 문법을 기술하는 데 사용되지만, 계산 복잡성으로 인해 실용적인 사용에는 한계가 있다.

문맥 의존 문법

기본 정보

이름	문맥 의존 문법
영어 이름	Context-sensitive grammar
일본어 이름	文脈依存文法 (분먀쿠 이존 분포)
유형	형식 문법
생성 규칙 형태	αAβ → αγβ (여기서 A는 비단말 기호이고, α와 β는 단말 기호와 비단말 기호의 문자열이며, γ는 비어 있지 않은 단말 기호와 비단말 기호의 문자열임)

특징

생성 능력	문맥 자유 문법보다 강력함
인식 능력	선형 제한 오토마타에 의해 인식됨
언어 종류	문맥 의존 언어

속성

촘스키 계층 구조	유형-1
결정 가능성	멤버십 문제는 결정 가능함; 비어 있음 문제는 결정 불가능함

📚 더 읽어볼만한 페이지

형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
언어학에 관한 - 세례명
세례명은 기독교에서 세례를 받을 때 받는 새로운 이름으로, 예수 그리스도 안에서 새롭게 태어남을 의미하며, 성경 속 인물들의 이름 변화에서 유래하여 중세 이후 유럽에서 일반적인 이름 형태로 정착되었고, 수호성인의 이름에서 따와 이름 축일로 기념되기도 한다.
언어학에 관한 - 개명
개명은 개인이나 법인이 이름을 바꾸는 행위로, 결혼, 이혼, 이민, 종교 개종, 성 정체성 확인, 사회적 이미지 개선, 범죄 회피 등 여러 이유로 행해지며, 절차는 국가별로 다르지만 법적 제약과 고려 사항이 따른다.

1. 개요
2. 정의
3. 예
4. 표준형
- 4.1. 구로다 표준형 (Kuroda Normal Form)
5. 속성 및 응용
6. 한국어 특성과 문맥 의존 문법

2. 정의

형식 문법 G = (N, Σ, P, S)에서 P의 모든 생성 규칙이 αAβ → αγβ 형태일 때 문맥 의존 문법이라고 한다. 여기서 A는 비단말, α, β는 비단말 및 단말 기호의 문자열, γ는 비단말 및 단말 기호로 된 길이가 0이 아닌 문자열이다.

"문맥 의존"이라는 이름은 A를 γ로 대체할 수 있는지 여부가 A의 주변 문맥(α와 β)에 의해 결정된다는 것을 의미한다. 이는 문맥 자유 문법과 대조적인데, 문맥 자유 문법에서는 비단말 기호 주변의 문맥이 고려되지 않는다.

문맥 의존 문법은 1950년대 노엄 촘스키가 자연 언어의 문법을 기술하기 위해 고안했다. 자연 언어에서는 특정 단어가 문맥에 따라 적절한지 여부가 결정되기 때문이다.

문맥 의존 문법은 각 생성 규칙이 α -> β 형식을 따르며, | α | ≤ | β | 라는 제한을 추가하여 정의할 수도 있다. 여기서 | α |는 α의 길이이다. 이러한 문법은 생성 규칙을 적용할 때 문자열의 길이가 줄어들지 않으므로, "단조 문법"(monotonic grammar^영어) 또는 "비축소 문법"(noncontracting grammar^영어) 등으로 불린다.

2.1. 형식 문법

형식 문법 $G = (N, \Sigma, P, S)$ 는 비단말 기호 집합 $N$ , 단말 기호 집합 $\Sigma$ , 생성 규칙 집합 $P$ , 시작 기호 $S \in N$ 의 튜플로 정의된다.

문자열 $u \in (N \cup \Sigma)^*$ 가 문자열 $v \in (N \cup \Sigma)^*$ 를 직접 생성한다(또는 직접 파생한다)는 것은 $u \Rightarrow v$ 로 표기하며, v가 u에 P의 생성 규칙을 적용하여 얻어짐을 의미한다. 즉, $u = \gamma L \delta$ 이고 $v = \gamma R \delta$ 일 때, $(L \to R) \in P$ 는 생성 규칙이고, $\gamma, \delta \in (N \cup \Sigma)^*$ 는 각각 문자열의 영향을 받지 않는 왼쪽 및 오른쪽 부분이다.

u가 $u \Rightarrow^* v$ 로 표기되는 v를 생성한다(또는 파생한다)는 것은 생성 규칙을 반복 적용하여 u에서 v를 얻을 수 있음을 의미한다. 즉, $u = u_0 \Rightarrow ... \Rightarrow u_n = v$ (n ≥ 0, $u_1, ..., u_{n-1} \in (N \cup \Sigma)^*$ ). 이는 관계 $\Rightarrow^*$ 가 관계 $\Rightarrow$ 의 반사적 추이적 폐포임을 뜻한다.

문법 G의 언어는 시작 기호에서 파생될 수 있는 모든 단말 기호 문자열의 집합이며, $L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}$ 로 정의된다. 단말 기호로만 구성된 문자열로 끝나지 않는 파생은 가능하지만, L(G)에는 포함되지 않는다.

2.2. 문맥 의존 문법

형식 문법 G = (N, Σ, P, S)에서 P의 모든 규칙이 αAβ → αγβ 형태일 때 문맥 의존 문법이라고 한다. 여기서 A는 비단말 기호, α, β는 비단말 및 단말 기호의 문자열, γ는 비단말 및 단말 기호로 된 길이가 0이 아닌 문자열이다. α, β ∈ (N ∪ Σ ∖ {S})^*, γ ∈ (N ∪ Σ ∖ {S})⁺. S → ε (ε는 빈 문자열) 형태의 규칙도 허용될 수 있다.

"문맥 의존"이라는 이름은 A를 γ로 대체할 수 있는지 여부가 A의 주변 문맥(α와 β)에 의해 결정된다는 데서 유래한다. 이는 문맥 자유 문법과 대조적인데, 문맥 자유 문법에서는 비단말 기호 주변의 문맥이 고려되지 않는다.

문맥 의존 문법은 1950년대 노엄 촘스키가 자연 언어의 문법을 기술하기 위해 고안했다. 자연 언어에서는 특정 단어가 문맥에 따라 적절한지 여부가 결정되기 때문이다. 문맥 의존 문법으로 기술되는 형식 언어는 문맥 의존 언어라고 불린다.

2.3. 약한 동치 정의

모든 문맥 의존 문법은 비축약 문법이며 모든 비축약 문법은 동등한 문맥 의존 문법으로 변환될 수 있다. 이 두 부류는 약하게 동치이다. 비축약 문법과 문맥 의존 문법은 거의 약한 등가(같은 언어 클래스를 정의할 수 있다)이지만, 차이점은 비축약 문법에서는 빈 문자열 ε을 포함하는 언어를 생성할 수 없다는 점이다. 문맥 의존 문법으로 기술된 언어 L에 대해, 비축소 문법은 L - {ε}을 기술할 수 있으며, 그 역도 성립한다.

3. 예

문맥 의존 문법의 예시는 다음과 같다.

👆

좌우로 밀어서 보기

생성 규칙
S → aSBC>aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

여기서 "|" 기호는 같은 비종단 기호로부터 생성되는 규칙들을 한 줄로 표기하기 위해 사용된다. 이 문법은

\{ a^n b^n c^n : n \ge 1 \}

언어를 생성하며, 이 언어는 문맥 자유 언어가 아니다. 문맥 의존 문법은 생성 규칙을 적용할 때 여러 문자(문자열)에 대해 패턴 매칭을 하며, 매치해야 할 문자 수에는 제한이 없다. 반면 문맥 자유 문법은 항상 하나의 문자(비종단 기호)에 대해서만 패턴 매칭을 한다.

"aaabbbccc"를 생성하는 과정은 다음과 같다.

:S
:→ aSBC
:→ aaSBCBC
:→ aaaBCBCBC
:→ aaaBBCCBC
:→ aaaBBBCCC
:→ aaabBBCCC
:→ aaabbBCCC
:→ aaabbbCCC
:→ aaabbbcCC
:→ aaabbbccC
:→ aaabbbccc

위의 예시를 단조 문법으로 표현하면 다음과 같다.

:S → abc | aSBc
:cB → Bc
:bB → bb

3.1. ''anbncn''

{ aⁿbⁿcⁿ | n ≥ 1 }은 문맥 자유 언어가 아니지만, 문맥 의존 문법으로 생성 가능하다.

문맥 의존 문법은 생성 규칙을 적용할 때 여러 문자(문자열)에 대해 패턴 매칭을 하며, 매치해야 할 문자 수에는 제한이 없다. 반면 문맥 자유 문법에서는 항상 하나의 문자(비종단 기호)에 대해서만 패턴 매칭을 한다.

다음은 { aⁿbⁿcⁿ | n ≥ 1 }을 생성하는 문맥 의존 문법의 예시이다.

👆

좌우로 밀어서 보기

번호	생성 규칙
1	S → aBC
2	S → aSBC
3	CB → CZ
4	CZ → WZ
5	WZ → WC
6	WC → BC
7	aB → ab
8	bB → bb
9	bC → bc
10	cC → cc

* 규칙 1과 2는 S를 aⁿBC(BC)^n-1 형태로 확장한다.
* 규칙 3부터 6까지는 각 CB를 BC로 순차적으로 교환한다. (Revesz의 트릭에 의해 4개의 규칙이 필요하다. CB → BC 규칙은 αAβ → αγβ 형태에 맞지 않기 때문이다.)
* 규칙 7–10은 비단말 기호 B 또는 C를 해당 단말 기호 b 또는 c로 각각 대체한다.

`aaabbbccc` 문자열 생성 과정은 다음과 같다.

: S
: →₂ aSBC
: →₂ aaSBCBC
: →₁ aaaBCBCBC
: →₃ aaaBCZCBC
: →₄ aaaBWZCBC
: →₅ aaaBWCBC
: →₆ aaaBBCBC
: →₃ aaaBBCZC
: →₄ aaaBBCWZC
: →₅ aaaBBCWCC
: →₆ aaaBBBCCC
: →₇ aaabBBCCC
: →₈ aaabbBCCC
: →₈ aaabbbCCC
: →₉ aaabbbcCC
: →₁₀ aaabbbccC
: →₁₀ aaabbbccc''

3.2. ''anbncndn''

aⁿbⁿcⁿdⁿ^영어 (n ≥ 1)과 같이 더 복잡한 언어도 문맥 의존 문법(또는 비축약 문법)으로 생성 가능하다.

$(ABCD)^{n}abcd$ 형태를 생성하는 정규 생성 규칙과 비축약 생성 규칙은 다음과 같다.

👆

좌우로 밀어서 보기

p_{Da} : Da\rightarrow aD

p_{Db} : Db\rightarrow bD

p_{Dc} : Dc\rightarrow cD

p_{Dd} : Dd\rightarrow dd

p_{Ca} : Ca\rightarrow aC

p_{Cb} : Cb\rightarrow bC

p_{Cc} : Cc\rightarrow cc

p_{Ba} : Ba\rightarrow aB

p_{Bb} : Bb\rightarrow bb

p_{Aa} : Aa\rightarrow aa

3.3. ''ambncmdn''

L^영어 = a^mbⁿc^mdⁿ^영어 (m ≥ 1, n ≥ 1)와 같은 교차 종속성을 갖는 언어도 문맥 의존 문법으로 생성 가능하다.

언어 L^영어 = a^mbⁿc^mdⁿ^영어 (m ≥ 1, n ≥ 1)에 대한 비축약 문법(이에 해당하는 CSG가 존재함)은 다음과 같이 정의된다.

* p₀ : S → RT
* p₁ : R→ aRC | aC
* p₃ : T→ BTd | Bd
* p₅ : CB→ BC
* p₆ : aB→ ab
* p₇ : bB→ bb
* p₈ : Cd→ cd
* p₉ : Cc→ cc

이 정의들을 사용하여, a³b²c³d²에 대한 파생은 다음과 같다.

: S
: →_p₀ RT
: →_p²₁p₂ a³C³T
: →_p₃p₄ a³C³B²d²
: →_p⁶₅ a³B²C³d²
: →_p₆p₇ a³b²C³d²
: →_p₈p²₉ a³b²c³d²

3.4. ''a''2''i''

a^영어^{2^{i^영어}} ( $a^{2^i}$ ) 형태(i ≥ 1)로 지수적으로 증가하는 문자열도 문맥 의존 문법으로 생성할 수 있다. 이 문법은 다음과 같은 생성 규칙을 따른다.

👆

좌우로 밀어서 보기

번호		좌변			우변
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

4. 표준형

문맥 의존 문법을 더 간결하게 표현하기 위한 표준형으로 다음과 같은 단조 문법을 들 수 있다.

:S → abc | aSBc
:cB → Bc
:bB → bb

4.1. 구로다 표준형 (Kuroda Normal Form)

빈 문자열을 생성하지 않는 모든 문맥 의존 문법은 약하게 동치인 구로다 표준형으로 변환 가능하다. 여기서 "약하게 동치"란 두 문법이 동일한 언어를 생성한다는 의미이다. 구로다 표준형은 일반적으로 문맥 의존적이지 않지만, 비축약 문법이 된다.

구로다 표준형은 비축약 문법의 실제 정규형이다.

5. 속성 및 응용

문맥 의존 문법(Context-sensitive grammar^영어)은 다양한 분야에 응용된다.

문맥 의존 언어는 여집합에 대해 닫혀 있으며, 이는 1988년에 발표된 Immerman–Szelepcsényi 정리로 알려져 있다. 또한 합집합, 교집합, 결합, 대입, 역 준동형, 클레이니 플러스 연산에 대해서도 닫혀 있다.

주어진 문자열 s가 주어진 문맥 의존 문법 G의 언어에 속하는지를 묻는 결정 문제는 PSPACE-완전이다. 더욱이, 언어가 PSPACE-완전인 문맥 의존 문법도 존재한다. 다시 말해, 주어진 문자열 s가 G의 언어에 속하는지 결정하는 것이 PSPACE-완전이 되도록 하는 문맥 의존 문법 G가 존재한다(따라서 G는 고정되어 있고 s만 문제의 입력의 일부이다). 문맥 의존 문법에 대한 공집합 문제(주어진 문맥 의존 문법 G에 대해, L(G)=∅인가?)는 결정 불가능 언어이다.

계산 언어학의 지속적인 연구는 약하게 문맥 의존적 언어처럼 결정 문제가 실현 가능한 다른 클래스의 언어를 공식화하는 데 초점을 맞추고 있다. 트리 부착 문법, 조합 범주 문법 등이 이러한 예시에 해당한다. 이러한 형식주의를 통해 생성된 언어는 문맥 자유 언어와 문맥 의존 언어 사이에 위치한다. 최근에는 PTIME 클래스가 범위 연결 문법과 동일하게 식별되었으며, 이는 현재 약하게 문맥 의존적인 언어 클래스 중 가장 표현력이 풍부한 것으로 평가된다.

5.1. 선형 유계 오토마타와의 동치성

문맥 의존 언어는 선형 구속 오토마타(Linear Bounded Automaton, LBA)에 의해 인식될 수 있다. 이는 마이힐–랜드웨버–구로다 정리에 의해 확립되었다. 마이힐은 1960년에 결정적 LBA의 개념을 제시하였고, 피터 S. 랜드웨버는 1963년에 결정적 LBA에 의해 허용되는 언어가 문맥 의존적이라고 발표했다. 구로다는 1964년에 비결정적 LBA 개념과 LBA와 CSG 간의 동등성을 제시했다. 모든 문맥 의존 언어가 *결정적* LBA에 의해 인식될 수 있는지 여부는 여전히 미해결 문제이다.

5.2. 닫힘 속성 (Closure Properties)

문맥 의존 언어는 여집합에 대해 닫혀 있으며, 이 결과는 1988년에 발표된 Immerman–Szelepcsényi 정리로 알려져 있다. 또한 합집합, 교집합, 결합, 대입, 역 준동형, 클레이니 플러스 연산에 대해서도 닫혀 있다.

5.3. 계산 문제

주어진 문자열 s가 주어진 문맥 의존 문법 G의 언어에 속하는지를 묻는 결정 문제는 PSPACE-완전이다. 더욱이, 언어가 PSPACE-완전인 문맥 의존 문법도 존재한다. 다시 말해, 주어진 문자열 s가 G의 언어에 속하는지 결정하는 것이 PSPACE-완전이 되도록 하는 문맥 의존 문법 G가 존재한다(따라서 G는 고정되어 있고 s만 문제의 입력의 일부이다).

문맥 의존 문법에 대한 공집합 문제 (주어진 문맥 의존 문법 G에 대해, L(G)=∅인가?)는 결정 불가능 언어이다.

5.4. 자연어 모델링

계산 언어학의 지속적인 연구는 약하게 문맥 의존적 언어처럼 결정 문제가 실현 가능한 다른 클래스의 언어를 공식화하는 데 초점을 맞추고 있다. 트리 부착 문법, 조합 범주 문법 등이 이러한 예시에 해당한다. 이러한 형식주의를 통해 생성된 언어는 문맥 자유 언어와 문맥 의존 언어 사이에 위치한다.

최근에는 PTIME 클래스가 범위 연결 문법과 동일하게 식별되었으며, 이는 현재 약하게 문맥 의존적인 언어 클래스 중 가장 표현력이 풍부한 것으로 평가된다.

6. 한국어 특성과 문맥 의존 문법

한국어는 교착어로서, 조사가 문법적 기능을 담당하고 어순이 비교적 자유로운 특징을 갖는다. 이러한 특징은 문맥 의존 문법으로 분석될 수 있다. 한국어의 복잡한 문장 구조와 중의성은 문맥 의존 문법 연구에 있어 중요한 과제이다.

문맥 의존 문법

1. 개요

2. 정의

2.1. 형식 문법

2.2. 문맥 의존 문법

2.3. 약한 동치 정의

3. 예

3.1. ''a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>''

3.2. ''a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>d<sup>n</sup>''

3.3. ''a<sup>m</sup>b<sup>n</sup>c<sup>m</sup>d<sup>n</sup>''

3.4. ''a''<sup>2<sup>''i''</sup></sup>

4. 표준형

4.1. 구로다 표준형 (Kuroda Normal Form)

5. 속성 및 응용

5.1. 선형 유계 오토마타와의 동치성

5.2. 닫힘 속성 (Closure Properties)

5.3. 계산 문제

5.4. 자연어 모델링

6. 한국어 특성과 문맥 의존 문법

번호		좌변			우변
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		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		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