문맥 의존 언어

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

1. 개요

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

문맥 의존 언어

📚 더 읽어볼만한 페이지

언어학에 관한 - 세례명
세례명은 기독교에서 세례를 받을 때 받는 새로운 이름으로, 예수 그리스도 안에서 새롭게 태어남을 의미하며, 성경 속 인물들의 이름 변화에서 유래하여 중세 이후 유럽에서 일반적인 이름 형태로 정착되었고, 수호성인의 이름에서 따와 이름 축일로 기념되기도 한다.
언어학에 관한 - 개명
개명은 개인이나 법인이 이름을 바꾸는 행위로, 결혼, 이혼, 이민, 종교 개종, 성 정체성 확인, 사회적 이미지 개선, 범죄 회피 등 여러 이유로 행해지며, 절차는 국가별로 다르지만 법적 제약과 고려 사항이 따른다.
형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.

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

2. 계산적 성질

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

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

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

또한, 문맥 의존 언어는 다음과 같은 연산에 대해 닫혀 있다.
* 두 문맥 의존 언어의 합집합, 교집합, 연결 연산 결과는 문맥 의존 언어이다.
* 문맥 의존 언어의 클레이니 플러스 연산 결과도 문맥 의존 언어이다.
* 문맥 의존 언어의 여집합도 문맥 의존 언어이다. 이는 이머만-설레페세니 정리로 알려져 있다.

3. 예시

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

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

* $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  \}

.

*

L_{PRIMES2} = \{ w : |w| \mbox { is prime }  \}

: 문자열의 길이가 소수인 언어("2"는 알파벳이 2개라는 의미). 유리스 하르트마니스는 펌핑 보조정리를 사용해 이 언어가 문맥 자유 언어가 아님을 보이고, 대응하는 선형 구속 오토마톤을 구성함으로써 이 언어가 문맥 의존 언어임을 보였다.

*

L_{PRIMES1} = \{ a^p : p \mbox { is prime }  \}

: 'a'의 개수가 소수인 언어("1"은 알파벳이 1개라는 의미). 마티 소이톨라는 선형 구속 오토마톤을 사용해 이 사실을 보였고 마르티 펜토넨은 문맥 의존 문법을 사용해 보였다.

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

4. 닫힘 성질

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