문맥 자유 언어

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

배경

문맥 자유 문법

서로 다른 문맥 자유 문법이 똑같은 문맥 자유 언어를 생성할 수도 있다. 언어를 생성하는 여러 문법을 비교함으로써 언어 고유의 성질을 특정 문법의 성질과 구분할 수 있다.

오토마타

어떤 언어가 문맥 자유 언어라는 것은 어떤 내리누름 오토마타가 그 언어를 받아들인다는 것과 동치이다. 따라서 문맥 자유 언어는 구문 분석이 용이하다. 또한 문맥 자유 문법이 주어지면 그 문법에 대응하는 내리누름 오토마타를 쉽게 구성할 수 있다. 한편 주어진 내리누름 오토마타에 대응하는 문맥 자유 문법을 구성하는 것은 조금 더 복잡하다.

예시

문맥 자유 언어의 전형적인 예로 $L=\{a^{n}b^{n}:n\geq 1\}$ 를 들 수 있다. 이 언어는 앞쪽 절반이 $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{aligned}\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{aligned}}

본질적으로 중의적인(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\}$ 에 속한 문자열을 비중의적으로 구문 분석할 방법은 없다. (또한 이 교집합은 문맥 자유 언어가 아니다.)^[1]

균형 잡힌 괄호 표현의 언어인 뒤크 언어는 $S\to SS~|~(S)~|~\varepsilon$ 로 생성되는 문맥 자유 언어이다.

문맥 자유 언어가 아닌 언어의 예

집합 $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$ 은 문맥 의존 언어이지만 문맥 자유 문법으로 생성할 수 없다.^[2] 따라서 문맥 자유 언어가 아닌 문맥 의존 언어가 존재함을 알 수 있다. 어떤 언어가 문맥 자유 언어가 아님을 보이려면 문맥 자유 언어에 대한 펌핑 보조정리를 쓰거나^[3] 오그덴의 보조정리나 파리크의 정리 따위를 사용할 수 있다.^[4]

성질

문맥 자유 구문 분석

구문 분석이 주변 “문맥”과 무관하다는 특성 때문에, 문맥 자유 언어는 내리누름 오토마타로 쉽게 구문 분석이 가능하다.

주어진 문자열 $w$ 와 문법 $G$ 가 생성하는 언어 $L(G)$ 에 대해, $w\in L(G)$ 인지 결정하는 문제를 소속(membership) 문제 또는 인식(recognition) 문제라고 한다. 촘스키 표준형으로 나타낸 문맥 자유 문법에 대한 인식 문제는 불 대수에서의 행렬 곱셈으로 바꿀 수 있다는 사실이 밝혀졌고, 따라서 복잡도는 최대 O(n^2.3728639)이다.^[5]^{[note 1]} 반대로, O(n^3−ε) 복잡도의 불 행렬 곱셈을 O(n^3−3ε) 복잡도의 CFG 구문 분석으로 바꿀 수 있다는 사실이 알려져 있고, 이는 CFG 구문 분석의 복잡도에 대한 일종의 하계가 된다.^[6]

문맥 자유 언어의 실제 쓰임에서는 인식 문제뿐만 아니라 문법 규칙을 사용해 주어진 문자열을 도출하는 트리를 생성하는 것도 중요하다. 이 트리를 만드는 과정을 구문 분석(파싱)이라 한다. 지금까지 알려진 CFG 구문 분석 알고리즘은 길이 n인 문자열을 분석하는 데 O(n³)만큼의 시간이 걸린다. 그러한 알고리즘의 예로 CYK 알고리즘과 얼리 파서 따위가 있다.

문맥 자유 언어 가운데 결정적 내리누름 오토마타가 받아들이는 언어들을 결정적 문맥 자유 언어라 한다. 이들은 LR 파서로 구문 분석할 수 있다.^[7]

닫힘 성질

문맥 자유 언어의 집합은 여러 연산에 대해 닫혀 있다. L과 P가 문맥 자유 언어이면, 다음 언어도 문맥 자유 언어이다.

합집합 $L\cup P$ ^[8]
거울상 L^R^[9]
문자열 연결 $L\cdot P$ ^[8]
클레이니 스타 $L^{*}$ ^[8]
문자열 준동형사상 $\varphi$ 에 대한 상 $\varphi (L)$ ^[10]
문자열 준동형사상 $\varphi$ 에 대한 역상 $\varphi ^{-1}(L)$ ^[11]
순환 자리 이동 $\{vu:uv\in L\}$ ^[12]
접두사 닫힘 (L의 모든 문자열의 접두사들의 집합)^[13]
정규 언어 R에 대한 몫 L/R^[14]

교집합, 여집합, 차집합

문맥 자유 언어의 집합은 교집합 연산에 대해 닫혀 있지 않다. 예컨대 $A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}$ 와 $B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}$ 는 둘 다 문맥 자유 언어이다.^{[note 2]} 두 언어의 교집합은 $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$ 이기 때문이다.^[15]

그러나 L이 문맥 자유 언어이고 D가 정규 언어이면, 교집합 $L\cap D$ 와 차집합 $L\setminus D$ 도 문맥 자유 언어이다.^[16]

결정 가능성

정규 언어에 관한 문제는 대체로 결정 가능하지만, 문맥 자유 언어에 관한 문제는 그렇지 않은 경우가 많다. 문맥 자유 언어가 유한한지는 결정 가능하지만, 문맥 자유 언어가 모든 문자열을 포함하는지, 정규 언어인지, 비중의적인지, 다른 문법으로 생성된 언어와 같은지는 결정 불가능하다.^[17]

일반적인 문맥 자유 문법 A와 B에 대해 다음 문제는 결정 불가능하다.

동치: $L(A)=L(B)$ 인가?^[18]
서로소: $L(A)\cap L(B)=\emptyset$ 인가?^[19] 그러나 문맥 자유 언어와 정규 언어의 교집합은 문맥 자유 언어이므로^[20]^[21] B가 정규 언어라는 조건이 있으면 결정 가능하다. (아래 “공집합” 부분 참조)
포함: $L(A)\subseteq L(B)$ 인가?^[22] 이 문제도 B가 정규 언어라는 조건이 있으면 결정 가능하지만^{[출처 필요]}, A만 정규 언어라는 조건이 있으면 결정 불가능하다.^[23]
전체집합: $L(A)=\Sigma ^{*}$ 인가?^[24]

문맥 자유 문법 A에 대해 다음 문제는 결정 가능하다.

공집합: $L(A)=\emptyset$ 인가?^[25]
유한성: $L(A)$ 는 유한집합인가?^[26]
소속: 주어진 문자열 $w$ 에 대해, $w\in L(A)$ 인가? 소속 문제를 효율적으로 푸는 알고리즘으로 CYK 알고리즘과 얼리 파서 등이 있다.

Hopcroft, Motwani, Ullman (2003)에 따르면^[27] 문맥 자유 언어에 관한 여러 기본적인 닫힘 성질과 결정 가능성은 Bar-Hillel, Perles, Shamir의 1961년 논문에서 처음 증명되었다.^[3]

내용주

↑ 논문이 발표될 당시에 행렬 곱셈 알고리즘의 복잡도는 최대 O(n^2.81)라고 알려져 있었다. 이후 코퍼스미스-위노그라드 알고리즘 등이 발견되면서 상계가 더 낮아졌다.
↑ A는 다음 문맥 자유 문법으로 생성된다. S → Sc | aTb | ε; T → aTb | ε. B의 경우도 비슷하다.

참조주

↑ Hopcroft & Ullman 1979, 100쪽, Theorem 4.7.
↑ Hopcroft & Ullman 1979.
↑ ^가 ^나 Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). “On Formal Properties of Simple Phrase-Structure Grammars”. 《Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung》 14 (2): 143–172.
↑ How to prove that a language is not context-free?
↑ Valiant, Leslie G. (April 1975). “General context-free recognition in less than cubic time”. 《Journal of Computer and System Sciences》 10 (2): 308–315. doi:10.1016/s0022-0000(75)80046-8. 2014년 11월 10일에 원본 문서에서 보존된 문서.
↑ Lee, Lillian (January 2002). “Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication” (PDF). 《J ACM》 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242.
↑ Knuth, D. E. (July 1965). “On the translation of languages from left to right” (PDF). 《Information and Control》 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. 2012년 3월 15일에 원본 문서 (PDF)에서 보존된 문서. 2011년 5월 29일에 확인함.
↑ ^가 ^나 ^다 Hopcroft & Ullman 1979, 131쪽, Corollary of Theorem 6.1.
↑ Hopcroft & Ullman 1979, 142쪽, Exercise 6.4d.
↑ Hopcroft & Ullman 1979, 131-132쪽, Corollary of Theorem 6.2.
↑ Hopcroft & Ullman 1979, 132쪽, Theorem 6.3.
↑ Hopcroft & Ullman 1979, 142-144쪽, Exercise 6.4c.
↑ Hopcroft & Ullman 1979, 142쪽, Exercise 6.4b.
↑ Hopcroft & Ullman 1979, 142쪽, Exercise 6.4a.
↑ Stephen Scheinberg (1960). “Note on the Boolean Properties of Context Free Languages” (PDF). 《Information and Control》 3: 372–375. doi:10.1016/s0019-9958(60)90965-7.
↑ Beigel, Richard; Gasarch, William. “A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA’s” (PDF). 《University of Maryland Department of Computer Science》. 2020년 6월 6일에 확인함.
↑ Wolfram, Stephen (2002). 《A New Kind of Science》. Wolfram Media, Inc. 1138쪽. ISBN 1-57955-008-8.
↑ Hopcroft & Ullman 1979, 203쪽, Theorem 8.12(1).
↑ Hopcroft & Ullman 1979, 202쪽, Theorem 8.10.
↑ Salomaa (1973), p. 59, Theorem 6.7
↑ Hopcroft & Ullman 1979, 135쪽, Theorem 6.5.
↑ Hopcroft & Ullman 1979, 203쪽, Theorem 8.12(2).
↑ Hopcroft & Ullman 1979, 203쪽, Theorem 8.12(4).
↑ Hopcroft & Ullman 1979, 203쪽, Theorem 8.11.
↑ Hopcroft & Ullman 1979, 137쪽, Theorem 6.6(a).
↑ Hopcroft & Ullman 1979, 137쪽, Theorem 6.6(b).
↑ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). 《Introduction to Automata Theory, Languages, and Computation》. Addison Wesley. Here: Sect.7.6, p.304, and Sect.9.7, p.411

참고 문헌

Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). 〈Context-Free Languages and Push-Down Automata〉. G. Rozenberg; A. Salomaa. 《Handbook of Formal Languages》 (PDF) 1. Springer-Verlag. 111–174쪽.
Ginsburg, Seymour (1966). 《The Mathematical Theory of Context-Free Languages》. New York, NY, USA: McGraw-Hill.
Hopcroft, John E.; Ullman, Jeffrey D. (1979). 《Introduction to Automata Theory, Languages, and Computation》 1판. Addison-Wesley.
Salomaa, Arto (1973). 《Formal Languages》. ACM Monograph Series.
Sipser, Michael (1997). 〈2: Context-Free Languages〉. 《Introduction to the Theory of Computation》. PWS Publishing. 91–122쪽. ISBN 0-534-94728-X.

[6] 논문이 발표될 당시에 행렬 곱셈 알고리즘의 복잡도는 최대 O(n^2.81)라고 알려져 있었다. 이후 코퍼스미스-위노그라드 알고리즘 등이 발견되면서 상계가 더 낮아졌다.

[16] A는 다음 문맥 자유 문법으로 생성된다. S → Sc | aTb | ε; T → aTb | ε. B의 경우도 비슷하다.

[FOOTNOTEHopcroftUllman1979100Theorem_4.7-1] Hopcroft & Ullman 1979, 100쪽, Theorem 4.7.

[FOOTNOTEHopcroftUllman1979-2] Hopcroft & Ullman 1979.

[Bar-Hillel.Perles.Shamir.1961-3] 가 ^나 Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). “On Formal Properties of Simple Phrase-Structure Grammars”. 《Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung》 14 (2): 143–172.

[4] How to prove that a language is not context-free?

[5] Valiant, Leslie G. (April 1975). “General context-free recognition in less than cubic time”. 《Journal of Computer and System Sciences》 10 (2): 308–315. doi:10.1016/s0022-0000(75)80046-8. 2014년 11월 10일에 원본 문서에서 보존된 문서.

[7] Lee, Lillian (January 2002). “Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication” (PDF). 《J ACM》 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242.

[8] Knuth, D. E. (July 1965). “On the translation of languages from left to right” (PDF). 《Information and Control》 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. 2012년 3월 15일에 원본 문서 (PDF)에서 보존된 문서. 2011년 5월 29일에 확인함.

[FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1-9] 가 ^나 ^다 Hopcroft & Ullman 1979, 131쪽, Corollary of Theorem 6.1.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4d-10] Hopcroft & Ullman 1979, 142쪽, Exercise 6.4d.

[FOOTNOTEHopcroftUllman1979131-132Corollary_of_Theorem_6.2-11] Hopcroft & Ullman 1979, 131-132쪽, Corollary of Theorem 6.2.

[FOOTNOTEHopcroftUllman1979132Theorem_6.3-12] Hopcroft & Ullman 1979, 132쪽, Theorem 6.3.

[FOOTNOTEHopcroftUllman1979142-144Exercise_6.4c-13] Hopcroft & Ullman 1979, 142-144쪽, Exercise 6.4c.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4b-14] Hopcroft & Ullman 1979, 142쪽, Exercise 6.4b.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4a-15] Hopcroft & Ullman 1979, 142쪽, Exercise 6.4a.

[Scheinberg.1960-17] Stephen Scheinberg (1960). “Note on the Boolean Properties of Context Free Languages” (PDF). 《Information and Control》 3: 372–375. doi:10.1016/s0019-9958(60)90965-7.

[18] Beigel, Richard; Gasarch, William. “A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA’s” (PDF). 《University of Maryland Department of Computer Science》. 2020년 6월 6일에 확인함.

[19] Wolfram, Stephen (2002). 《A New Kind of Science》. Wolfram Media, Inc. 1138쪽. ISBN 1-57955-008-8.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(1)-20] Hopcroft & Ullman 1979, 203쪽, Theorem 8.12(1).

[FOOTNOTEHopcroftUllman1979202Theorem_8.10-21] Hopcroft & Ullman 1979, 202쪽, Theorem 8.10.

[22] Salomaa (1973), p. 59, Theorem 6.7

[FOOTNOTEHopcroftUllman1979135Theorem_6.5-23] Hopcroft & Ullman 1979, 135쪽, Theorem 6.5.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(2)-24] Hopcroft & Ullman 1979, 203쪽, Theorem 8.12(2).

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(4)-25] Hopcroft & Ullman 1979, 203쪽, Theorem 8.12(4).

[FOOTNOTEHopcroftUllman1979203Theorem_8.11-26] Hopcroft & Ullman 1979, 203쪽, Theorem 8.11.

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(a)-27] Hopcroft & Ullman 1979, 137쪽, Theorem 6.6(a).

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(b)-28] Hopcroft & Ullman 1979, 137쪽, Theorem 6.6(b).

[29] John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). 《Introduction to Automata Theory, Languages, and Computation》. Addison Wesley. Here: Sect.7.6, p.304, and Sect.9.7, p.411

[1]

[2]

[3]

[4]

[5]

[note 1]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[note 2]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]