문맥 의존 언어

**문맥 의존 언어**(context-sensitive language)는 문맥 의존 문법이 생성하는 형식 언어이다. 이와 동치인 정의로, 비축약 문법이 생성하는 형식 언어라고 할 수도 있다. 문맥 의존 언어는 촘스키 위계에 속한 네 가지 유형의 형식 언어 중 하나이다.
# 계산적 성질
계산적으로 문맥 의존 언어는 선형유한 비결정적 튜링 기계, 즉 선형유한 오토마타와 동등하다. 이것은 입력의 길이가 n일 때 테이프의 길이가 kn칸으로 제한된 비결정적 튜링 기계이다. 이때 k는 기계에 따라 정해진 상수이다. 다시 말해, 이러한 기계가 인식하는 모든 언어는 문맥 의존 언어이고, 거꾸로 모든 문맥 의존 언어는 이러한 기계로 인식할 수 있다. 모든 문맥 의존 언어의 집합은 복잡도 종류 **NLINSPACE** 또는 **NSPACE**(*O*(*n*))으로 나타내기도 하는데, 비결정적 튜링 기계에서 선형 공간복잡도로 결정할 수 있기 때문이다.. 복잡도 종류 **LINSPACE** (또는 **DSPACE**(*O*(*n*)))도 비슷하게 정의하지만 비결정적 튜링 기계 대신 결정적 튜링 기계를 사용하는 점이 다르다. **LINSPACE**이 **NLINSPACE**의 부분집합인 것은 당연하지만, **LINSPACE** = **NLINSPACE**인지는 아직 밝혀지지 않았다.. 어느 문자열이 주어진 문맥 의존 언어 또는 결정적 문맥 의존 언어에 속하는지 결정하는 문제는 PSPACE-완전 문제이다.
# 예시
문맥 자유 언어가 아닌 문맥 의존 언어의 단순한 예시로 L = \\{ a^nb^nc^n : n \ge 1 \\}이 있다. 즉 n개의 "a", 그 뒤에 n개의 "b", 그 뒤에 n개의 "c"가 나오는 모든 문자열, 예컨대 abc, aabbcc, aaabbbccc 등을 모아 놓은 언어이다. 이 언어를 포함하는 더 큰 언어인 **바크 언어**(Bach language)url=http://www.aclweb.org/anthology/P83-1001는 "a", "b", "c"(또는 다른 아무런 세 기호)가 똑같은 횟수만큼 나타나는 모든 문자열, 예컨대 aabccb, baabcaccb 등을 모두 모아 놓은 언어인데, 이 역시 문맥 의존 언어이다.Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars" date=2014-01-21. *NELS*, vol. 11, pp. 1-12.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. 언어 L을 인식하는 선형유한 오토마타를 만듦으로써 L이 문맥 의존 언어임을 보일 수 있다. L이 문맥 자유 언어가 아님을 보이려면 문맥 자유 언어에 대한 펌핑 보조정리를 사용할 수 있다. 문맥 자유 언어가 아닌 문맥 의존 언어의 다른 예시로는 다음과 같은 것이 있다. L_{Cross} = \\{ a^mb^nc^{m}d^{n} : m \ge 1, n \ge 1 \\}: 이 언어를 생성하는 문맥 의존 문법은 a^mC^m 과 B^nd^n 꼴의 문장 형식을 생성하는 문맥 자유 문법으로 시작해서 CB\rightarrow BC 와 같은 자리바꿈 규칙을 추가하고, 새로운 시작 기호와 표준적인 문법적 장치를 더해서 만들 수 있다. L_{MUL3} = \\{ a^mb^nc^{mn} : m \ge 1, n \ge 1 \\}: (이름의 "3"은 알파벳이 3개 글자로 되어 있다는 뜻이다.) 즉 "곱셈" 연산은 문맥 의존 언어를 낳는다. (반면에 "덧셈" 연산은 문맥 자유 언어로 충분한데, 규칙 S\rightarrow aSc|R와 R\rightarrow bRc|bc로 구성된 문법을 보면 알 수 있다.) 곱셈의 교환법칙 때문에, 이 언어를 생성하는 가장 직관적인 문법은 중의적이다. 중의성을 해결하려면 더 제한된 부분집합, 예컨대 L_{ORDMUL3} = \\{ a^mb^nc^{mn} : 1 1, n > 1 \\}를 만들 수 있고, 이로부터 다시 L_{m^2} = \\{ a^{m^2} : m > 1 \\}, L_{m^3} = \\{ a^{m^3} : m > 1 \\} 따위의 문맥 의존 언어를 만들 수 있다. L_{REP} = \\{ w^{|w|} : w \in \Sigma^* \\}: 이 언어를 생성하는 문맥 의존 문법은 L_{Square} = \\{ w^2 : w \in \Sigma^* \\}, L_{Cube} = \\{ w^3 : w \in \Sigma^* \\} 따위를 생성하는 문맥 의존 문법을 일반화해서 얻을 수 있다. L_{EXP} = \\{ a^{2^n} : n \ge 1 \\}.Example 9.5 (p. 224) of Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley L_{PRIMES2} = \\{ w : |w| \mbox { is prime } \\}: (이름의 "2"는 알파벳이 2개 글자로 되어 있다는 뜻이다.) 유리스 하르트마니스는 펌핑 보조정리를 사용해 이 언어가 문맥 자유 언어가 아님을 보이고, 대응하는 선형유한 오토마타를 구성함으로써 이 언어가 문맥 의존 언어임을 보였다.date=Jul 1968 L_{PRIMES1} = \\{ a^p : p \mbox { is prime } \\}: (이름의 "2"는 알파벳이 1개 글자로 되어 있다는 뜻이다.) 마티 소이톨라는 선형유한 오토마타를 사용해 이 사실을 보였고Salomaa, Arto (1969), *Theory of Automata*, , Pergamon, 276 pages. 10.1016/C2013-0-02221-9 (pages 213-214, exercise 6.8) 마르티 펜토넨은 문맥 의존 문법을 사용해 보였다.Formal Languages by A. Salomaa, page 14, Example 2.5. 문맥 의존 언어가 아닌 재귀 언어의 예로는 결정 문제의 복잡도가 EXPSPACE-난해한 임의의 언어가 있다. 예를 들어 서로 동등한 두 정규 표현식의 짝들의 집합이 그러한 언어이다.
# 닫힘 성질
* 두 문맥 의존 언어의 합집합, 교집합, 문자열 연결은 문맥 의존 언어이다. 문맥 의존 언어의 클레이니 스타도 문맥 의존 언어이다.year=1979; Exercise 9.10, p.230. 2000년판에는 문맥 의존 언어에 관한 장이 빠졌다. * 문맥 의존 언어의 여집합은 문맥 의존 언어이다.citeseerx = 10.1.1.54.5941 이 결과를 이머만-셀레프체니 정리라고 한다. 따라서 두 문맥 의존 언어의 차집합도 문맥 의존 언어이다.