문맥 자유 언어

**문맥 자유 언어**(文脈自由言語, Context-free language, **CFL**)는 문맥 자유 문법이 생성하는 형식 언어이다. 문맥 자유 언어는 프로그래밍 언어의 연구에서 중요한 역할을 한다.
# 배경

## 문맥 자유 문법
서로 다른 문맥 자유 문법이 똑같은 문맥 자유 언어를 생성할 수도 있다. 언어를 생성하는 여러 문법을 비교함으로써 언어 고유의 성질을 특정 문법의 성질과 구분할 수 있다.
## 오토마타
어떤 언어가 문맥 자유 언어라는 것은 어떤 내리누름 오토마타가 그 언어를 받아들인다는 것과 동치이다. 따라서 문맥 자유 언어는 구문 분석이 용이하다. 또한 문맥 자유 문법이 주어지면 그 문법에 대응하는 내리누름 오토마타를 쉽게 구성할 수 있다. 한편 주어진 내리누름 오토마타에 대응하는 문맥 자유 문법을 구성하는 것은 조금 더 복잡하다.
# 예시
문맥 자유 언어의 전형적인 예로 L = \\{a^nb^n:n\geq1\\}를 들 수 있다. 이 언어는 앞쪽 절반이 a로만 되어 있고 뒤쪽 절반이 b로만 되어 있는 모든 문자열의 집합이다. L을 생성하는 문맥 자유 문법으로 S\to aSb ~|~ ab를 들 수 있다. 이 언어는 정규 언어가 아니다. L을 받아들이는 내리누름 오토마타는 다음과 같이 정의할 수 있다. :M=(\\{q_0,q_1,q_f\\}, \\{a,b\\}, \\{a,z\\}, \delta, q_0, z, \\{q_f\\}). 단, \delta는 다음과 같다. :\begin{align} \delta(q_0, a, z) &= (q_0, az) \\\ \delta(q_0, a, a) &= (q_0, aa) \\\ \delta(q_0, b, a) &= (q_1, \varepsilon) \\\ \delta(q_1, b, a) &= (q_1, \varepsilon) \\\ \delta(q_1, \varepsilon, z) &= (q_f, \varepsilon) \end{align} 본질적으로 중의적인(inherently ambiguous) CFL이 존재하기 때문에, 비중의적 CFL의 집합은 CFL의 집합의 진부분집합이다. 본질적으로 중의적인 CFL의 예로는 \\{a^n b^m c^m d^n | n, m > 0\\}와 \\{a^n b^n c^m d^m | n, m > 0\\}의 합집합을 들 수 있다. 문맥 자유 언어들의 합집합은 문맥 자유 언어이기 때문에, 이 언어도 문맥 자유 언어이다. 그러나 두 부분의 교집합인 \\{a^n b^n c^n d^n | n > 0\\}에 속한 문자열을 비중의적으로 구문 분석할 방법은 없다. (또한 이 교집합은 문맥 자유 언어가 아니다.)loc=Theorem 4.7 균형 잡힌 괄호 표현의 언어인 뒤크 언어는 S\to SS ~|~ (S) ~|~ \varepsilon로 생성되는 문맥 자유 언어이다.
## 문맥 자유 언어가 아닌 언어의 예
집합 \\{a^n b^n c^n d^n | n > 0\\}은 문맥 의존 언어이지만 문맥 자유 문법으로 생성할 수 없다.1979 따라서 문맥 자유 언어가 아닌 문맥 의존 언어가 존재함을 알 수 있다. 어떤 언어가 문맥 자유 언어가 아님을 보이려면 문맥 자유 언어에 대한 펌핑 보조정리를 쓰거나 오그덴의 보조정리나 파리크의 정리 따위를 사용할 수 있다.How to prove that a language is not context-free?
# 성질

## 문맥 자유 구문 분석
구문 분석이 주변 “문맥”과 무관하다는 특성 때문에, 문맥 자유 언어는 내리누름 오토마타로 쉽게 구문 분석이 가능하다. 주어진 문자열 w와 문법 G가 생성하는 언어 L(G)에 대해, w \in L(G)인지 결정하는 문제를 소속(membership) 문제 또는 인식(recognition) 문제라고 한다. 촘스키 표준형으로 나타낸 문맥 자유 문법에 대한 인식 문제는 불 대수에서의 행렬 곱셈으로 바꿀 수 있다는 사실이 밝혀졌고, 따라서 복잡도는 최대 *O*(*n*2.3728639)이다.url-status=dead논문이 발표될 당시에 행렬 곱셈 알고리즘의 복잡도는 최대 *O*(*n*2.81)라고 알려져 있었다. 이후 코퍼스미스-위노그라드 알고리즘 등이 발견되면서 상계가 더 낮아졌다. 반대로, *O*(*n*3−ε) 복잡도의 불 행렬 곱셈을 *O*(*n*3−3ε) 복잡도의 CFG 구문 분석으로 바꿀 수 있다는 사실이 알려져 있고, 이는 CFG 구문 분석의 복잡도에 대한 일종의 하계가 된다.arxiv=cs/0112018 문맥 자유 언어의 실제 쓰임에서는 인식 문제뿐만 아니라 문법 규칙을 사용해 주어진 문자열을 도출하는 트리를 생성하는 것도 중요하다. 이 트리를 만드는 과정을 구문 분석(파싱)이라 한다. 지금까지 알려진 CFG 구문 분석 알고리즘은 길이 *n*인 문자열을 분석하는 데 *O*(*n*3)만큼의 시간이 걸린다. 그러한 알고리즘의 예로 CYK 알고리즘과 얼리 파서 따위가 있다. 문맥 자유 언어 가운데 결정적 내리누름 오토마타가 받아들이는 언어들을 결정적 문맥 자유 언어라 한다. 이들은 LR 파서로 구문 분석할 수 있다.url-status = dead
## 닫힘 성질
문맥 자유 언어의 집합은 여러 연산에 대해 닫혀 있다. *L*과 *P*가 문맥 자유 언어이면, 다음 언어도 문맥 자유 언어이다. * 합집합 L \cup Ploc=Corollary of Theorem 6.1 * 거울상 *L*Rloc=Exercise 6.4d * 문자열 연결 L \cdot Ploc=Corollary of Theorem 6.1 * 클레이니 스타 L^*loc=Corollary of Theorem 6.1 * 문자열 준동형사상 \varphi에 대한 상 \varphi(L)loc=Corollary of Theorem 6.2 * 문자열 준동형사상 \varphi에 대한 역상 \varphi^{-1}(L)loc=Theorem 6.3 * 순환 자리 이동 \\{vu : uv \in L \\}loc=Exercise 6.4c * 접두사 닫힘 (*L*의 모든 문자열의 접두사들의 집합)loc=Exercise 6.4b * 정규 언어 *R*에 대한 몫 *L*/*R*loc=Exercise 6.4a
### 교집합, 여집합, 차집합
문맥 자유 언어의 집합은 교집합 연산에 대해 닫혀 있지 않다. 예컨대 A = \\{a^n b^n c^m \mid m, n \geq 0 \\}와 B = \\{a^m b^n c^n \mid m,n \geq 0\\}는 둘 다 문맥 자유 언어이다.*A*는 다음 문맥 자유 문법으로 생성된다. *S* → *Sc* | *aTb* | *ε*; *T* → *aTb* | *ε*. *B*의 경우도 비슷하다. 두 언어의 교집합은 A \cap B = \\{ a^n b^n c^n \mid n \geq 0\\}인데, 펌핑 보조정리를 사용해 이 언어가 문맥 자유 언어가 아님을 보일 수 있다. 따라서 문맥 자유 언어의 집합은 여집합 연산에 대해서도 닫혀 있지 않은데, 두 언어 *A*와 *B*의 교집합은 합집합과 여집합 연산을 사용해 A \cap B = \overline{\overline{A} \cup \overline{B처럼 나타낼 수 있기 때문이다. 그러므로 문맥 자유 언어의 집합은 차집합 연산에 대해서도 닫혀 있지 않다. \overline{L} = \Sigma^* \setminus L이기 때문이다.doi=10.1016/s0019-9958(60)90965-7 그러나 *L*이 문맥 자유 언어이고 *D*가 정규 언어이면, 교집합 L\cap D와 차집합 L\setminus D도 문맥 자유 언어이다.website=University of Maryland Department of Computer Science
## 결정 가능성
정규 언어에 관한 문제는 대체로 결정 가능하지만, 문맥 자유 언어에 관한 문제는 그렇지 않은 경우가 많다. 문맥 자유 언어가 유한한지는 결정 가능하지만, 문맥 자유 언어가 모든 문자열을 포함하는지, 정규 언어인지, 비중의적인지, 다른 문법으로 생성된 언어와 같은지는 결정 불가능하다.url=https://archive.org/details/newkindofscience00wolf/page/1138 일반적인 문맥 자유 문법 A와 B에 대해 다음 문제는 결정 불가능하다. * 동치: L(A)=L(B)인가?loc=Theorem 8.12(1) * 서로소: L(A) \cap L(B) = \emptyset 인가?loc=Theorem 8.10 그러나 문맥 자유 언어와 정규 언어의 교집합은 문맥 자유 언어이므로1973, p. 59, Theorem 6.7loc=Theorem 6.5 B가 정규 언어라는 조건이 있으면 결정 가능하다. (아래 “공집합” 부분 참조) * 포함: L(A) \subseteq L(B)인가?loc=Theorem 8.12(2) 이 문제도 B가 정규 언어라는 조건이 있으면 결정 가능하지만날짜=2021-04-17, A만 정규 언어라는 조건이 있으면 결정 불가능하다.loc=Theorem 8.12(4) * 전체집합: L(A)=\Sigma^*인가?loc=Theorem 8.11 문맥 자유 문법 A에 대해 다음 문제는 결정 가능하다. * 공집합: L(A) = \emptyset인가?loc=Theorem 6.6(a) * 유한성: L(A)는 유한집합인가?loc=Theorem 6.6(b) * 소속: 주어진 문자열 w에 대해, w \in L(A)인가? 소속 문제를 효율적으로 푸는 알고리즘으로 CYK 알고리즘과 얼리 파서 등이 있다. Hopcroft, Motwani, Ullman (2003)에 따르면publisher=Addison Wesley Here: Sect.7.6, p.304, and Sect.9.7, p.411 문맥 자유 언어에 관한 여러 기본적인 닫힘 성질과 결정 가능성은 Bar-Hillel, Perles, Shamir의 1961년 논문에서 처음 증명되었다.pages=143–172
# 내용주

# 참조주
각주