문맥 의존 언어

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 계산적 성질
3. 예시
4. 닫힘 성질
참조

1. 개요

문맥 의존 언어는 선형유한 비결정적 튜링 기계와 동등하며, 입력의 길이에 비례하는 테이프 공간을 사용하는 언어이다. 모든 문맥 의존 언어의 집합은 복잡도 종류 NLINSPACE로 나타내며, 결정 문제의 복잡도는 PSPACE-완전 문제이다. 문맥 의존 언어의 예시로는 { a^nb^nc^n : n ≥ 1 } 등이 있으며, 두 문맥 의존 언어의 합집합, 교집합, 문자열 연결, 클레이니 스타, 여집합, 차집합 역시 문맥 의존 언어이다. 문맥 자유 언어는 문맥 의존 언어에 포함된다.

2. 계산적 성질

계산적으로 문맥 의존 언어는 선형유한 오토마타(LBA, Linearly Bounded Automaton)와 동등하다. 선형유한 오토마타는 테이프 길이가 입력 문자열 길이 $n$ 에 비례하여 $kn$ 칸(여기서 $k$ 는 기계마다 정해진 상수)으로 제한된 비결정적 튜링 기계이다.^[11]^[1] 즉, 선형유한 오토마타가 인식할 수 있는 모든 언어는 문맥 의존 언어이며, 모든 문맥 의존 언어는 선형유한 오토마타로 인식될 수 있다.

모든 문맥 의존 언어의 집합은 복잡도 종류 '''NLINSPACE''' (또는 '''NSPACE'''(''O''(''n'')))로 나타내기도 하는데, 이는 비결정적 튜링 기계에서 선형 공간 복잡도로 결정될 수 있음을 의미한다.^[11]^[1] 복잡도 종류 '''LINSPACE''' (또는 '''DSPACE'''(''O''(''n'')))는 비결정적 튜링 기계 대신 결정적 튜링 기계를 사용하여 유사하게 정의된다. '''LINSPACE'''가 '''NLINSPACE'''의 부분집합이라는 것은 분명하지만, '''LINSPACE''' = '''NLINSPACE'''인지 여부는 아직 해결되지 않은 문제이다.^[12]^[2]

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

또한, 문맥 의존 언어는 다음과 같은 연산에 대해 닫혀 있다.

두 문맥 의존 언어의 합집합, 교집합, 연결 연산 결과는 문맥 의존 언어이다.^[9]
문맥 의존 언어의 클레이니 플러스 연산 결과도 문맥 의존 언어이다.^[9]
문맥 의존 언어의 여집합도 문맥 의존 언어이다. 이는 이머만-설레페세니 정리로 알려져 있다.^[10]

3. 예시

문맥 자유 언어가 아닌 문맥 의존 언어의 단순한 예시로 $L = \{ a^nb^nc^n : n \ge 1 \}$ 이 있다. 이는 n개의 "a", 그 뒤에 n개의 "b", 그 뒤에 n개의 "c"가 나오는 모든 문자열(예: abc, aabbcc, aaabbbccc 등)을 모아 놓은 언어이다. 이 언어는 선형 구속 오토마톤을 구성하여 문맥 의존 언어임을 보일 수 있으며, 문맥 자유 언어에 대한 펌핑 보조정리를 사용하여 문맥 자유 언어가 아님을 보일 수 있다. 이 언어를 포함하는 더 큰 언어인 '''바크 언어'''(Bach language)^[13]는 "a", "b", "c"(또는 다른 세 기호)가 똑같은 횟수만큼 나타나는 모든 문자열(예: aabccb, baabcaccb 등)을 모두 모아 놓은 언어인데, 이 역시 문맥 의존 언어이다.^[14]^[15]^[4]^[5]

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

$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 < m < n \}$ 를 고려할 수 있다. "곱셈" 언어를 변형하여 $L_{MUL1} = \{ a^{mn} : m > 1, n > 1 \}$ 를 만들 수 있고, 이로부터 다시 $L_{m^2} = \{ a^{m^2} : m > 1 \}$ , $L_{m^3} = \{ a^{m^3} : m > 1 \}$ 따위의 문맥 의존 언어를 만들 수 있다.

L_{REP} = \{ 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 \}$ .^[16]^[6]

$L_{PRIMES2} = \{ w : |w| \mbox { is prime } \}$ : 문자열의 길이가 소수인 언어("2"는 알파벳이 2개라는 의미). 유리스 하르트마니스는 펌핑 보조정리를 사용해 이 언어가 문맥 자유 언어가 아님을 보이고, 대응하는 선형 구속 오토마톤을 구성함으로써 이 언어가 문맥 의존 언어임을 보였다.^[17]^[7]

$L_{PRIMES1} = \{ a^p : p \mbox { is prime } \}$ : 'a'의 개수가 소수인 언어("1"은 알파벳이 1개라는 의미). 마티 소이톨라는 선형 구속 오토마톤을 사용해 이 사실을 보였고^[18]^[8] 마르티 펜토넨은 문맥 의존 문법을 사용해 보였다.^[19]

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

4. 닫힘 성질

두 문맥 의존 언어의 합집합, 교집합, 문자열 연결은 문맥 의존 언어이다.^[20]^[9]
문맥 의존 언어의 클레이니 스타도 문맥 의존 언어이다.^[20]^[9]
문맥 의존 언어의 여집합은 문맥 의존 언어이며,^[21]^[10] 이는 이머만-셀레프체니 정리로 알려진 결과이다.^[21]^[10] 따라서 두 문맥 의존 언어의 차집합도 문맥 의존 언어이다.^[21]
문맥 자유 언어는 문맥 의존 언어에 포함된다 (단, 해당 문맥 의존 문법의 정의에 S → ε 규칙이 포함된 경우에만 해당한다).

참조

_[1] 서적 Complexity theory and cryptology Springer-Verlag
_[2] 서적 Classical recursion theory. Vol. II North-Holland Publishing Co.
_[3] 간행물 Context-freeness and the computer processing of human languages http://www.aclweb.or[...]
_[4] 웹사이트 "Discontinuous constituents in generalized categorial grammars" http://people.umass.[...] 2014-01-21
_[5] 문서 "The convergence of mildly context-sensitive grammar formalisms" Cambridge MA: Bradford
_[6] 서적 Introduction to Automata Theory, Languages, and Computation Addison-Wesley
_[7] 저널 On the Recognition of Primes by Automata https://ecommons.cor[...] 1968-07
_[8] 서적 Theory of Automata Pergamon
_[9] 서적 Introduction to Automata Theory, Languages, and Computation https://archive.org/[...] Addison-Wesley
_[10] 저널 Nondeterministic space is closed under complementation http://www.cs.umass.[...] 2004-06-25
_[11] 서적 Complexity theory and cryptology Springer-Verlag
_[12] 서적 Classical recursion theory. Vol. II North-Holland Publishing Co.
_[13] 간행물 Context-freeness and the computer processing of human languages http://www.aclweb.or[...]
_[14] 웹사이트 "Discontinuous constituents in generalized categorial grammars" http://people.umass.[...] 2014-01-21
_[15] 문서 "The convergence of mildly context-sensitive grammar formalisms" Cambridge MA: Bradford
_[16] 서적 Introduction to Automata Theory, Languages, and Computation Addison-Wesley
_[17] 저널 On the Recognition of Primes by Automata https://ecommons.cor[...] 1968-07
_[18] 서적 Theory of Automata Pergamon
_[19] 문서 Formal Languages
_[20] 서적 Introduction to Automata Theory, Languages, and Computation https://archive.org/[...] Addison-Wesley
_[21] 저널 Nondeterministic space is closed under complementation http://www.cs.umass.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com