문맥 자유 언어 문서 원본 보기

{{위키데이터 속성 추적}}
'''문맥 자유 언어'''(文脈自由言語, Context-free language, '''CFL''')는 [[문맥 자유 문법]]이 생성하는 [[형식 언어]]이다. 문맥 자유 언어는 [[프로그래밍 언어]]의 연구에서 중요한 역할을 한다.

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

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

== 예시 ==
문맥 자유 언어의 전형적인 예로 <math>L = \{a^nb^n:n\geq1\}</math>를 들 수 있다. 이 언어는 앞쪽 절반이 <math>a</math>로만 되어 있고 뒤쪽 절반이 <math>b</math>로만 되어 있는 모든 문자열의 집합이다. <math>L</math>을 생성하는 문맥 자유 문법으로 <math>S\to aSb ~|~ ab</math>를 들 수 있다. 이 언어는 [[정규 언어]]가 아니다. <math>L</math>을 받아들이는 내리누름 오토마타는 다음과 같이 정의할 수 있다.
:<math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\}).</math>
단, <math>\delta</math>는 다음과 같다.
:<math>\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}</math>

본질적으로 중의적인(inherently ambiguous) CFL이 존재하기 때문에, 비중의적 CFL의 집합은 CFL의 집합의 진부분집합이다. 본질적으로 중의적인 CFL의 예로는 <math>\{a^n b^m c^m d^n | n, m > 0\}</math>와 <math>\{a^n b^n c^m d^m | n, m > 0\}</math>의 합집합을 들 수 있다. 문맥 자유 언어들의 합집합은 문맥 자유 언어이기 때문에, 이 언어도 문맥 자유 언어이다. 그러나 두 부분의 교집합인 <math>\{a^n b^n c^n d^n | n > 0\}</math>에 속한 문자열을 비중의적으로 구문 분석할 방법은 없다. (또한 이 교집합은 문맥 자유 언어가 아니다.){{sfn|Hopcroft|Ullman|1979|p=100|loc=Theorem 4.7}}

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

=== 문맥 자유 언어가 아닌 언어의 예 ===
집합 <math>\{a^n b^n c^n d^n | n > 0\}</math>은 [[문맥 의존 언어]]이지만 문맥 자유 문법으로 생성할 수 없다.{{sfn|Hopcroft|Ullman|1979}} 따라서 문맥 자유 언어가 아닌 문맥 의존 언어가 존재함을 알 수 있다. 어떤 언어가 문맥 자유 언어가 아님을 보이려면 문맥 자유 언어에 대한 [[펌핑 보조정리]]를 쓰거나<ref name="Bar-Hillel.Perles.Shamir.1961"/> [[오그덴의 보조정리]]나 [[파리크의 정리]] 따위를 사용할 수 있다.<ref>[https://cs.stackexchange.com/q/265 How to prove that a language is not context-free?]</ref>

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

주어진 문자열 <math>w</math>와 문법 <math>G</math>가 생성하는 언어 <math>L(G)</math>에 대해, <math>w \in L(G)</math>인지 결정하는 문제를 소속(membership) 문제 또는 인식(recognition) 문제라고 한다. [[촘스키 표준형]]으로 나타낸 문맥 자유 문법에 대한 인식 문제는 불 대수에서의 행렬 곱셈으로 바꿀 수 있다는 사실이 밝혀졌고, 따라서 복잡도는 최대 ''O''(''n''<sup>2.3728639</sup>)이다.<ref>{{저널 인용|first=Leslie G. |last=Valiant |title=General context-free recognition in less than cubic time |journal=Journal of Computer and System Sciences |year=April 1975 |volume=10 |number=2 |pages=308–315 |doi=10.1016/s0022-0000(75)80046-8 |doi-access=free |url=http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&context=compsci |archive-url=https://web.archive.org/web/20141110061739/http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&context=compsci |archive-date=10 November 2014 |url-status=dead }}</ref><ref group="note">논문이 발표될 당시에 행렬 곱셈 알고리즘의 복잡도는 최대 ''O''(''n''<sup>2.81</sup>)라고 알려져 있었다. 이후 [[코퍼스미스-위노그라드 알고리즘]] 등이 발견되면서 상계가 더 낮아졌다.</ref>
반대로, ''O''(''n''<sup>3−ε</sup>) 복잡도의 불 행렬 곱셈을 ''O''(''n''<sup>3−3ε</sup>) 복잡도의 CFG 구문 분석으로 바꿀 수 있다는 사실이 알려져 있고, 이는 CFG 구문 분석의 복잡도에 대한 일종의 하계가 된다.<ref>{{저널 인용|first=Lillian |last=Lee |title=Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication |journal=J ACM |date=January 2002 |volume=49 |number=1 |pages=1–15 |url=http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |doi=10.1145/505241.505242 |arxiv=cs/0112018}}</ref>

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

문맥 자유 언어 가운데 [[결정적 내리누름 오토마타]]가 받아들이는 언어들을 결정적 문맥 자유 언어라 한다. 이들은 [[LR 파서]]로 구문 분석할 수 있다.<ref>{{저널 인용| last1 = Knuth | first1 = D. E. | author-link = 도널드 커누스 | title = On the translation of languages from left to right | doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | url = http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | access-date = 29 May 2011 | archive-url = https://web.archive.org/web/20120315152151/http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | archive-date = 15 March 2012 | url-status = dead }}</ref>

=== 닫힘 성질 ===
문맥 자유 언어의 집합은 여러 연산에 대해 닫혀 있다. ''L''과 ''P''가 문맥 자유 언어이면, 다음 언어도 문맥 자유 언어이다.
* 합집합 <math>L \cup P</math>{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
* 거울상 ''L''<sup>R</sup>{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4d}}
* [[문자열 연결]] <math>L \cdot P</math>{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
* [[클레이니 스타]] <math>L^*</math>{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
* [[문자열 준동형사상]] <math>\varphi</math>에 대한 상 <math>\varphi(L)</math>{{sfn|Hopcroft|Ullman|1979|p=131-132|loc=Corollary of Theorem 6.2}}
* 문자열 준동형사상 <math>\varphi</math>에 대한 역상 <math>\varphi^{-1}(L)</math>{{sfn|Hopcroft|Ullman|1979|p=132|loc=Theorem 6.3}}
* 순환 자리 이동 <math>\{vu : uv \in L \}</math>{{sfn|Hopcroft|Ullman|1979|p=142-144|loc=Exercise 6.4c}}
* 접두사 닫힘 (''L''의 모든 문자열의 [[접두사]]들의 집합){{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4b}}
* 정규 언어 ''R''에 대한 몫 ''L''/''R''{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4a}}

==== 교집합, 여집합, 차집합 ====
문맥 자유 언어의 집합은 교집합 연산에 대해 닫혀 있지 않다. 예컨대 <math>A = \{a^n b^n c^m \mid m, n \geq 0 \}</math>와 <math>B = \{a^m b^n c^n \mid m,n \geq 0\}</math>는 둘 다 문맥 자유 언어이다.<ref group="note">''A''는 다음 문맥 자유 문법으로 생성된다. ''S'' → ''Sc'' | ''aTb'' | ''ε''; ''T'' → ''aTb'' | ''ε''. ''B''의 경우도 비슷하다.</ref> 두 언어의 교집합은 <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>인데, [[펌핑 보조정리]]를 사용해 이 언어가 문맥 자유 언어가 아님을 보일 수 있다. 따라서 문맥 자유 언어의 집합은 여집합 연산에 대해서도 닫혀 있지 않은데, 두 언어 ''A''와 ''B''의 교집합은 합집합과 여집합 연산을 사용해 <math>A \cap B = \overline{\overline{A} \cup \overline{B}}</math>처럼 나타낼 수 있기 때문이다. 그러므로 문맥 자유 언어의 집합은 차집합 연산에 대해서도 닫혀 있지 않다. <math>\overline{L} = \Sigma^* \setminus L</math>이기 때문이다.<ref name="Scheinberg.1960">{{저널 인용| url=https://core.ac.uk/download/pdf/82210847.pdf | author=Stephen Scheinberg | title=Note on the Boolean Properties of Context Free Languages | journal=Information and Control | volume=3 | pages=372&ndash;375 | year=1960 | doi=10.1016/s0019-9958(60)90965-7}}</ref>

그러나 ''L''이 문맥 자유 언어이고 ''D''가 정규 언어이면, 교집합 <math>L\cap D</math>와 차집합 <math>L\setminus D</math>도 문맥 자유 언어이다.<ref>{{웹 인용|last=Beigel|first=Richard|last2=Gasarch|first2=William|title=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|url=http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf|access-date=June 6, 2020|website=University of Maryland Department of Computer Science}}</ref>

=== 결정 가능성 ===
정규 언어에 관한 문제는 대체로 결정 가능하지만, 문맥 자유 언어에 관한 문제는 그렇지 않은 경우가 많다. 문맥 자유 언어가 유한한지는 결정 가능하지만, 문맥 자유 언어가 모든 문자열을 포함하는지, 정규 언어인지, 비중의적인지, 다른 문법으로 생성된 언어와 같은지는 결정 불가능하다.<ref>{{서적 인용|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1138 1138]|isbn=1-57955-008-8|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1138}}</ref>

일반적인 [[문맥 자유 문법]] A와 B에 대해 다음 문제는 결정 불가능하다.
* 동치: <math>L(A)=L(B)</math>인가?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(1)}}
* 서로소: <math>L(A) \cap L(B) = \emptyset </math>인가?{{sfn|Hopcroft|Ullman|1979|p=202|loc=Theorem 8.10}} 그러나 문맥 자유 언어와 정규 언어의 교집합은 문맥 자유 언어이므로<ref>{{harvtxt|Salomaa|1973}}, p. 59, Theorem 6.7</ref>{{sfn|Hopcroft|Ullman|1979|p=135|loc=Theorem 6.5}} B가 정규 언어라는 조건이 있으면 결정 가능하다. (아래 “공집합” 부분 참조)
* 포함: <math>L(A) \subseteq L(B)</math>인가?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(2)}} 이 문제도 B가 정규 언어라는 조건이 있으면 결정 가능하지만{{출처|날짜=2021-04-17}}, A만 정규 언어라는 조건이 있으면 결정 불가능하다.{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(4)}}
* 전체집합: <math>L(A)=\Sigma^*</math>인가?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.11}}

문맥 자유 문법 A에 대해 다음 문제는 결정 가능하다.
* 공집합: <math>L(A) = \emptyset</math>인가?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(a)}}
* 유한성: <math>L(A)</math>는 유한집합인가?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(b)}}
* 소속: 주어진 문자열 <math>w</math>에 대해, <math>w \in L(A)</math>인가? 소속 문제를 효율적으로 푸는 알고리즘으로 [[CYK 알고리즘]]과 [[얼리 파서]] 등이 있다.

Hopcroft, Motwani, Ullman (2003)에 따르면<ref>{{서적 인용|author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=2003| publisher=Addison Wesley}} Here: Sect.7.6, p.304, and Sect.9.7, p.411</ref> 문맥 자유 언어에 관한 여러 기본적인 닫힘 성질과 결정 가능성은 Bar-Hillel, Perles, Shamir의 1961년 논문에서 처음 증명되었다.<ref name="Bar-Hillel.Perles.Shamir.1961">{{저널 인용|author1=Yehoshua Bar-Hillel |author2=Micha Asher Perles |author3=Eli Shamir | title=On Formal Properties of Simple Phrase-Structure Grammars| journal=Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung| year=1961| volume=14| number=2| pages=143–172}}</ref>

== 내용주 ==
<references group="note"/>

== 참조주 ==
{{각주}}

== 참고 문헌 ==
* {{서적 인용|first=Jean-Michel |last=Autebert |first2=Jean |last2=Berstel |first3=Luc |last3=Boasson |url=http://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf |chapter=Context-Free Languages and Push-Down Automata |editor1=G. Rozenberg |editor2=A. Salomaa |title=Handbook of Formal Languages |volume=1 |publisher=Springer-Verlag |date=1997 |pp=111–174}}
* {{서적 인용|first=Seymour |last=Ginsburg | title = The Mathematical Theory of Context-Free Languages |url=https://archive.org/details/mathematicaltheo0000gins | year = 1966 | publisher = McGraw-Hill | location = New York, NY, USA}}
*{{서적 인용| last1 = Hopcroft| first1 = John E. | last2 = Ullman | first2 = Jeffrey D. | title = Introduction to Automata Theory, Languages, and Computation | url = https://archive.org/details/introductiontoau00hopc | url-access = registration | publisher = Addison-Wesley | edition = 1st | year = 1979}}
* {{서적 인용|first=Arto |last=Salomaa |title = Formal Languages |publisher = ACM Monograph Series |year= 1973}}
* {{서적 인용|first=Michael |last=Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips |pp=91–122 |chapter=2: Context-Free Languages}}

{{형식 언어 및 형식 문법}}

{{전거 통제}}

[[분류:형식 언어]]