문맥 의존 언어 문서 원본 보기

{{위키데이터 속성 추적}}
'''문맥 의존 언어'''(context-sensitive language)는 [[문맥 의존 문법]]이 생성하는 [[형식 언어]]이다. 이와 동치인 정의로, [[비축약 문법]]이 생성하는 형식 언어라고 할 수도 있다. 문맥 의존 언어는 [[촘스키 위계]]에 속한 네 가지 유형의 형식 언어 중 하나이다.

== 계산적 성질 ==
계산적으로 문맥 의존 언어는 선형유한 [[비결정적 튜링 기계]], 즉 [[선형유한 오토마타]]와 동등하다. 이것은 입력의 길이가 <math>n</math>일 때 테이프의 길이가 <math>kn</math>칸으로 제한된 비결정적 튜링 기계이다. 이때 <math>k</math>는 기계에 따라 정해진 상수이다. 다시 말해, 이러한 기계가 인식하는 모든 언어는 문맥 의존 언어이고, 거꾸로 모든 문맥 의존 언어는 이러한 기계로 인식할 수 있다.

모든 문맥 의존 언어의 집합은 [[복잡도 종류]] '''NLINSPACE''' 또는 '''NSPACE'''(''O''(''n''))으로 나타내기도 하는데, 비결정적 튜링 기계에서 선형 공간복잡도로 결정할 수 있기 때문이다.<ref>{{인용
 | last = Rothe | first = Jörg
 | isbn = 978-3-540-22147-0
 | location = Berlin
 | mr = 2164257
 | page = 77
 | publisher = Springer-Verlag
 | series = Texts in Theoretical Computer Science. An EATCS Series
 | title = Complexity theory and cryptology
 | year = 2005}}.</ref>  복잡도 종류 '''LINSPACE''' (또는 '''DSPACE'''(''O''(''n'')))도 비슷하게 정의하지만 비결정적 튜링 기계 대신 결정적 튜링 기계를 사용하는 점이 다르다. '''LINSPACE'''이 '''NLINSPACE'''의 부분집합인 것은 당연하지만, '''LINSPACE''' = '''NLINSPACE'''인지는 아직 밝혀지지 않았다.<ref>{{인용
 | last = Odifreddi | first = P. G.
 | isbn = 978-0-444-50205-6
 | location = Amsterdam
 | mr = 1718169
 | page = 236
 | publisher = North-Holland Publishing Co.
 | series = Studies in Logic and the Foundations of Mathematics
 | title = Classical recursion theory. Vol. II
 | volume = 143
 | year = 1999}}.</ref>

어느 문자열이 주어진 문맥 의존 언어 또는 결정적 문맥 의존 언어에 속하는지 결정하는 문제는 [[PSPACE-완전]] 문제이다.

== 예시 ==
[[문맥 자유 언어]]가 아닌 문맥 의존 언어의 단순한 예시로 <math>L = \{ a^nb^nc^n : n \ge 1 \}</math>이 있다. 즉 {{mvar|n}}개의 "a", 그 뒤에 {{mvar|n}}개의 "b", 그 뒤에 {{mvar|n}}개의 "c"가 나오는 모든 문자열, 예컨대 abc, aabbcc, aaabbbccc 등을 모아 놓은 언어이다. 이 언어를 포함하는 더 큰 언어인 '''바크 언어'''(Bach language)<ref>{{콘퍼런스 인용|last=Pullum |first=Geoffrey K. |year=1983 |title=Context-freeness and the computer processing of human languages |conference=Proc. 21st Annual Meeting of the [[Association for Computational Linguistics|ACL]] |url=http://www.aclweb.org/anthology/P83-1001}}</ref>는 "a", "b", "c"(또는 다른 아무런 세 기호)가 똑같은 횟수만큼 나타나는 모든 문자열, 예컨대 aabccb, baabcaccb 등을 모두 모아 놓은 언어인데, 이 역시 문맥 의존 언어이다.<ref>Bach, E. (1981). [http://people.umass.edu/ebach/papers/nels11.htm "Discontinuous constituents in generalized categorial grammars"] {{Webarchive|url=https://web.archive.org/web/20140121022931/http://people.umass.edu/ebach/papers/nels11.htm |date=2014-01-21 }}. ''NELS'', vol. 11, pp.&nbsp;1&ndash;12.</ref><ref>Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors). ''Foundational Issues in Natural Language Processing''. Cambridge MA: Bradford.</ref>

언어 {{mvar|L}}을 인식하는 선형유한 오토마타를 만듦으로써 {{mvar|L}}이 문맥 의존 언어임을 보일 수 있다. {{mvar|L}}이 [[문맥 자유 언어]]가 아님을 보이려면 문맥 자유 언어에 대한 [[펌핑 보조정리]]를 사용할 수 있다.

문맥 자유 언어가 아닌 문맥 의존 언어의 다른 예시로는 다음과 같은 것이 있다.

<math>L_{Cross} = \{ a^mb^nc^{m}d^{n} : m \ge 1, n \ge 1 \}</math>: 이 언어를 생성하는 문맥 의존 문법은
<math>a^mC^m</math>
과
<math>B^nd^n</math>
꼴의 문장 형식을 생성하는 문맥 자유 문법으로 시작해서
<math>CB\rightarrow BC</math>
와 같은 자리바꿈 규칙을 추가하고, 새로운 시작 기호와 표준적인 문법적 장치를 더해서 만들 수 있다.

<math>L_{MUL3} = \{ a^mb^nc^{mn} : m \ge 1, n \ge 1 \}</math>: (이름의 "3"은 알파벳이 3개 글자로 되어 있다는 뜻이다.) 즉 "곱셈" 연산은 문맥 의존 언어를 낳는다. (반면에 "덧셈" 연산은 문맥 자유 언어로 충분한데, 규칙 <math>S\rightarrow aSc|R</math>와 <math>R\rightarrow bRc|bc</math>로 구성된 문법을 보면 알 수 있다.) 곱셈의 교환법칙 때문에, 이 언어를 생성하는 가장 직관적인 문법은 중의적이다. 중의성을 해결하려면 더 제한된 부분집합, 예컨대 <math>L_{ORDMUL3} = \{ a^mb^nc^{mn} : 1 < m < n \}</math>를 고려하면 된다. "곱셈" 언어를 변형해서
<math>L_{MUL1} = \{ a^{mn} : m > 1,  n > 1 \}</math>를 만들 수 있고, 이로부터 다시 <math>L_{m^2} = \{ a^{m^2} : m > 1 \}</math>, <math>L_{m^3} = \{ a^{m^3} : m > 1 \}</math> 따위의 문맥 의존 언어를 만들 수 있다.

<math>L_{REP} = \{ w^{|w|} : w \in \Sigma^* \}</math>: 이 언어를 생성하는 문맥 의존 문법은 <math>L_{Square} = \{ w^2 : w \in \Sigma^* \}</math>, <math>L_{Cube} = \{ w^3 : w \in \Sigma^* \}</math> 따위를 생성하는 문맥 의존 문법을 일반화해서 얻을 수 있다.

<math>L_{EXP} = \{ a^{2^n} : n \ge 1  \}</math>.<ref>Example 9.5 (p. 224) of Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley</ref>

<math>L_{PRIMES2} = \{ w : |w| \mbox { is prime }  \}</math>: (이름의 "2"는 알파벳이 2개 글자로 되어 있다는 뜻이다.) [[유리스 하르트마니스]]는 펌핑 보조정리를 사용해 이 언어가 문맥 자유 언어가 아님을 보이고, 대응하는 선형유한 오토마타를 구성함으로써 이 언어가 문맥 의존 언어임을 보였다.<ref>{{저널 인용| doi=10.1145/321466.321470 | url=https://ecommons.cornell.edu/bitstream/1813/5864/1/68-1.pdf | author=J. Hartmanis and H. Shank | title=On the Recognition of Primes by Automata | journal=Journal of the ACM | volume=15 | number=3 | pages=382–389 | date=Jul 1968 }}</ref>

<math>L_{PRIMES1} = \{ a^p : p \mbox { is prime }  \}</math>: (이름의 "2"는 알파벳이 1개 글자로 되어 있다는 뜻이다.) 마티 소이톨라는 선형유한 오토마타를 사용해 이 사실을 보였고<ref>Salomaa, Arto (1969), ''Theory of Automata'', {{ISBN|978-0-08-013376-8}}, Pergamon, 276 pages. {{doi|10.1016/C2013-0-02221-9}} (pages 213-214, exercise 6.8)</ref> 마르티 펜토넨은 문맥 의존 문법을 사용해 보였다.<ref>Formal Languages by A. Salomaa, page 14, Example 2.5.</ref>

문맥 의존 언어가 아닌 [[재귀 언어]]의 예로는 결정 문제의 복잡도가 [[EXPSPACE]]-난해한 임의의 언어가 있다. 예를 들어 서로 동등한 두 [[정규 표현식]]의 짝들의 집합이 그러한 언어이다.

== 닫힘 성질 ==
* 두 문맥 의존 언어의 합집합, 교집합, [[문자열 연결]]은 문맥 의존 언어이다. 문맥 의존 언어의 [[클레이니 스타]]도 문맥 의존 언어이다.<ref>{{서적 인용|author=John E. Hopcroft|author2=Jeffrey D. Ullman|title=Introduction to Automata Theory, Languages, and Computation|url=https://archive.org/details/introductiontoau00hopc|url-access=registration|publisher=Addison-Wesley|year=1979}}; Exercise 9.10, p.230. 2000년판에는 문맥 의존 언어에 관한 장이 빠졌다.</ref>
* 문맥 의존 언어의 여집합은 문맥 의존 언어이다.<ref>{{저널 인용| last = Immerman | first = Neil | year = 1988 | title =Nondeterministic space is closed under complementation | journal = SIAM J. Comput. | issue = 5 | pages = 935–938 | doi = 10.1137/0217058 | volume = 17 | url=http://www.cs.umass.edu/~immerman/pub/space.pdf| citeseerx = 10.1.1.54.5941 }}</ref> 이 결과를 [[이머만-셀레프체니 정리]]라고 한다. 따라서 두 문맥 의존 언어의 차집합도 문맥 의존 언어이다.

== 각주 ==
{{각주}}
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co.

== 같이 보기 ==
* [[선형유한 오토마타]]
* [[촘스키 위계]]

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

[[분류:형식 언어]]