문맥 자유 언어

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

1. 개요

문맥 자유 언어(Context-free language, CFL)는 문맥 자유 문법(CFG)에 의해 생성되는 형식 언어의 한 종류이다. CFL은 특정 문법의 성질과 무관하게 언어 자체의 고유한 특성을 나타내며, 내리누름 오토마타(pushdown automata)로 인식될 수 있어 구문 분석이 용이하다. CFL은 합집합, 거울상, 문자열 연결, 클레이니 스타, 문자열 준동형사상, 역 준동형사상, 순환 자리 이동 등 다양한 연산에 대해 닫혀 있지만, 교집합, 여집합, 차집합 연산에 대해서는 닫혀 있지 않다. CFL의 소속 문제, 공집합 여부, 유한성 여부 등은 결정 가능하지만, 동치, 서로소, 포함, 전체 집합 여부, 정규성, 모호성 등은 결정 불가능한 문제가 많다. 프로그래밍 언어의 괄호 일치와 같은 수식 표현과 뒤크 언어(Dyck language)가 CFL의 예시이며, L = {a^n b^n : n ≥ 1}과 같은 언어가 전형적인 예시로 사용된다.

문맥 자유 언어

📚 더 읽어볼만한 페이지

형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.

1. 개요
2. 배경
- 2.1. 문맥 자유 문법
- 2.2. 오토마타
3. 예시
4. 성질

2. 배경

문맥 자유 언어는 문맥 자유 문법에 의해 생성되는 언어로, 내리누름 오토마타(푸시다운 오토마타)로 인식할 수 있다. 서로 다른 문맥 자유 문법이 같은 문맥 자유 언어를 생성할 수 있으며, 이를 통해 언어의 고유한 성질을 파악할 수 있다. 문맥 자유 언어는 구문 분석이 용이하며, 주어진 문맥 자유 문법에 대응하는 내리누름 오토마타를 쉽게 구성할 수 있다. 하지만 그 반대 방향(오토마타가 주어졌을 때 문법 생성)은 더 복잡하다.

2.1. 문맥 자유 문법

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

2.2. 오토마타

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

모든 문맥 자유 언어의 집합은 푸시다운 오토마타에 의해 인식되는 언어의 집합과 동일하며, 이로 인해 이러한 언어는 파싱에 적합하다. 또한, 주어진 문맥 자유 문법에 대해 해당 문법(그리고 그에 따른 언어)에 대한 푸시다운 오토마타를 생성하는 직접적인 방법이 있지만, 그 반대 방향(오토마타가 주어졌을 때 문법을 생성하는 것)은 직접적이지 않다.

3. 예시

문맥 자유 언어의 예시로 $L = \{a^nb^n:n\geq1\}$ 가 있으며, 이는 a가 n개, b가 n개로 이루어진 모든 문자열의 집합이다. 이 문자열은 앞 절반이 a로, 뒷 절반이 b로 구성된다. $L$ 은 문법 $S\to aSb ~|~ ab$ 에 의해 생성되며, 정규 언어가 아니다.

무모호 CFL은 모든 CFL의 진부분집합이다. 즉, 본질적으로 모호한 CFL이 존재한다. 본질적으로 모호한 CFL의 예시는 $\{a^n b^m c^m d^n | n, m > 0\}$ 과 $\{a^n b^n c^m d^m | n, m > 0\}$ 의 합집합이다. 이 집합은 문맥 자유 언어의 합집합은 항상 문맥 자유 언어이므로 문맥 자유 언어이다. 그러나 이 두 언어의 교집합(비문맥 자유 부분집합) $\{a^n b^n c^n d^n | n > 0\}$ 의 문자열을 모호하지 않게 구문 분석할 방법은 없다.

프로그래밍 언어 등에서 괄호의 대응은 $S\to SS ~|~ (S) ~|~ \lambda$ 와 같은 규칙으로 나타낼 수 있다.

3.1. 전형적인 예시

문맥 자유 언어의 전형적인 예로 $L = \{a^nb^n:n\geq1\}$ 가 있다. 이 언어는 앞쪽 절반이 $a$ 로만 되어 있고 뒤쪽 절반이 $b$ 로만 되어 있는 모든 문자열의 집합이다. $L$ 을 생성하는 문맥 자유 문법은 $S\to aSb ~|~ ab$ 이다. 이 언어는 정규 언어가 아니다.

$L$ 을 받아들이는 푸시다운 오토마타는 다음과 같이 정의할 수 있다.

: $M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\}).$

여기서 $\delta$ 는 다음과 같다.

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

뒤크 언어는 $S\to SS ~|~ (S) ~|~ \varepsilon$ 로 생성되는 문맥 자유 언어이다.

3.2. 뒤크 언어

모든 올바르게 짝지어진 괄호의 언어는 $S\to SS ~|~ (S) ~|~ \varepsilon$ 로 생성되는 문맥 자유 언어이다.

3.3. 프로그래밍 언어

프로그래밍 언어 등에서 괄호의 대응은 $S\to SS ~|~ (S) ~|~ \lambda$ 와 같은 규칙으로 생성된다. 수식 등은 대체로 문맥 자유 언어이다.

3.4. 문맥 자유 언어가 아닌 언어의 예

집합 $\{a^n b^n c^n d^n | n > 0\}$ 은 문맥 의존 언어이지만, 이 언어를 생성하는 문맥 자유 문법은 존재하지 않는다. 따라서 문맥 자유 언어가 아닌 문맥 의존 언어가 존재한다. 어떤 언어가 문맥 자유 언어가 아님을 보이려면 문맥 자유 언어에 대한 펌핑 보조정리를 쓰거나 오그덴의 보조정리나 파리크의 정리 따위를 사용할 수 있다.

4. 성질

L과 P를 문맥 자유 언어, D를 정규 언어라고 할 때, 다음은 모두 문맥 자유 언어이다(닫혀 있다).

* L의 클레이니 폐포
* L의 준동형 사상
* L과 P의 연결
* L과 P의 합집합
* L과 (정규 언어) D의 교집합

하지만, 교집합이나 차집합에 관해서는 닫혀 있지 않다.

문맥 자유 언어에 대해 다음 문제는 결정 불가능하다.

* 등가성: 두 개의 문맥 자유 문법 A와 B가 주어졌을 때, $L(A)=L(B)$ 인가?
* $L(A) \cap L(B) = \emptyset$ 인가?
* $L(A)=\Sigma^*$ 인가?
* $L(A) \subseteq L(B)$ 인가?

문맥 자유 언어에 대한 다음 문제는 결정 가능하다.

* $L(A)=\emptyset$ 인가?
* L(A)는 유한한가?
* 멤버십: 어떤 단어 w가 주어졌을 때 $w \in L(A)$ 인가? (멤버십 문제는 다항 시간으로 결정 가능하다. CYK 알고리즘을 참조)

4.1. 문맥 자유 구문 분석

문맥 자유 언어는 내리누름 오토마타로 쉽게 구문 분석이 가능하다. 주어진 문자열 $w$ 와 문법 $G$ 가 생성하는 언어 $L(G)$ 에 대해, $w \in L(G)$ 인지 결정하는 문제를 소속(membership) 문제 또는 인식(recognition) 문제라고 한다. 촘스키 표준형으로 나타낸 문맥 자유 문법에 대한 인식 문제는 불 대수에서의 행렬 곱셈으로 바꿀 수 있다는 사실이 밝혀졌고, 따라서 복잡도는 최대 O(n^2.3728639)이다. 반대로, O(n^3−ε) 복잡도의 불 행렬 곱셈을 O(n^3−3ε) 복잡도의 CFG 구문 분석으로 바꿀 수 있다는 사실이 알려져 있고, 이는 CFG 구문 분석의 복잡도에 대한 일종의 하계가 된다.

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

문맥 자유 언어 가운데 결정적 내리누름 오토마타가 받아들이는 언어들을 결정적 문맥 자유 언어라 한다. 이들은 LR 파서로 구문 분석할 수 있다.

4.2. 결정적 문맥 자유 언어

결정적 문맥 자유 언어는 결정적 푸시다운 오토마톤에 의해 허용되는 언어의 집합으로 정의되며 LR(k) 파서로 파싱할 수 있다.

4.3. 닫힘 성질

L과 P가 문맥 자유 언어이면, 다음 언어도 문맥 자유 언어이다.

* L과 P의 합집합 $L \cup P$
* L의 거울상
* L과 P의 문자열 연결 $L \cdot P$
* L의 클레이니 스타 $L^*$
* 문자열 준동형사상 $\varphi$ 에 대한 상 $\varphi(L)$
* 역 준동형사상 $\varphi^{-1}$ 에 대한 역상 $\varphi^{-1}(L)$
* L의 순환 자리 이동 $\{vu : uv \in L \}$
* L의 접두사 닫힘 (L의 모든 문자열의 접두사들의 집합)
* 정규 언어 R에 대한 L의 몫 L/R

하지만, 교집합, 여집합, 차집합에 관해서는 닫혀 있지 않다.

4.3.1. 교집합, 여집합, 차집합

문맥 자유 언어의 집합은 교집합, 여집합, 차집합 연산에 대해 닫혀 있지 않다. 예를 들어 $A = \{a^n b^n c^m \mid m, n \geq 0 \}$ 와 $B = \{a^m b^n c^n \mid m,n \geq 0\}$ 는 둘 다 문맥 자유 언어이지만, 두 언어의 교집합은 $A \cap B = \{ a^n b^n c^n \mid n \geq 0\}$ 인데, 펌핑 보조정리를 사용해 이 언어가 문맥 자유 언어가 아님을 보일 수 있다.

문맥 자유 언어는 여집합에 대해서도 닫혀 있지 않은데, 두 언어 A와 B의 교집합은 합집합과 여집합으로 표현될 수 있기 때문이다( $A \cap B = \overline{\overline{A} \cup \overline{B}}$ ). 따라서 문맥 자유 언어는 차집합에 대해서도 닫혀 있지 않다( $\overline{L} = \Sigma^* \setminus L$ ).

그러나 L이 문맥 자유 언어이고 D가 정규 언어이면, 교집합 $L\cap D$ 와 차집합 $L\setminus D$ 는 모두 문맥 자유 언어이다.

4.4. 결정 가능성

일반적인 문맥 자유 문법 A와 B에 대해 다음 문제는 결정 불가능하다.

* 동치: $L(A)=L(B)$ 인가?
* 서로소: $L(A) \cap L(B) = \emptyset$ 인가? 그러나 B가 정규 언어라는 조건이 있으면 결정 가능하다.
* 포함: $L(A) \subseteq L(B)$ 인가? B가 정규 언어라는 조건이 있으면 결정 가능하지만, A만 정규 언어라는 조건이 있으면 결정 불가능하다.
* 전체집합: $L(A)=\Sigma^*$ 인가?

문맥 자유 문법 A에 대해 다음 문제는 결정 가능하다.

* 공집합: $L(A) = \emptyset$ 인가?
* 유한성: $L(A)$ 는 유한집합인가?
* 소속: 주어진 문자열 $w$ 에 대해, $w \in L(A)$ 인가? 소속 문제를 효율적으로 푸는 알고리즘으로 CYK 알고리즘과 얼리 파서 등이 있다.

Hopcroft, Motwani, Ullman (2003)에 따르면, 문맥 자유 언어에 관한 여러 기본적인 닫힘 성질과 결정 가능성은 Bar-Hillel, Perles, Shamir의 1961년 논문에서 처음 증명되었다.