[오토마타] 13. Context-Free Language

Context-Free Language

L = { aⁿbⁿ : n ≥ 0 }

 

위 언어는 펌핑 레마를 통해 RL이 아님을 증명한 적이 있다.

그런데 이 언어는 프로그래밍 언어에서 등장하는 언어로 표현할 수 있다.

homomorphism을 이용하여 h(a) = '(', h(b) = ')' 로 표현하면 위 언어는 언제나 올바른 괄호 문자열이 된다.

(강의록에서는 nested programming language 라고 표현하였다.)

 

그런데 우리는 분명 이런 언어도 표현하기를 원할 때가 있다.

따라서 RL 보다 더 넓은 범위를 커버할 수 있는 언어를 새로 정의해보려고 한다.

 

그리고 그 시작으로 Context-Free Language를 먼저 정의해보자.

 

Def. 만약 G = (V, T, S, P) 를 구성하는 모든 production 들이 A → x , (A는 변수 하나, x는 터미널 또는 변수들의 무작위 나열) 이라면, 이 문법은 Context-Free 하다.

 

말로 쉽게 풀었으나, production 의 정의를 수학적으로는 다음과 같이 표현한다.

 

 

x는 V와 T의 합집합에 대한 star-closure 이므로, 아무것도 나열하지 않거나( = λ), 임의의 변수와 터미널을 자유롭게 섞어써서 표현한 형태로 나타낸 것을 말한다.

사실상 context-free grammar는 모든 production 들에 대해 화살표 왼쪽이 1개의 변수로만 구성되어있으면 Context-Free 한 것이나 마찬가지다.

그리고 어떤 언어를 Context-Free Grammar(CFG)로 표현할 수 있다면 L(G)를 Context-Free Language 라고 한다.

 

 

위와 같이 모든 변수가 오른쪽에 몰려있는 문법을 Right-Linear Grammar 라고 한적이 있다.

이 문법은 CFG보다 더 제약조건이 붙은 문법이므로, CFG가 더 포괄적이라는 것을 알 수 있다.

다르게 말하면 Right-Linear Grammar는 CFG이기도 하다.

 

 

 

결론적으로는 위와 같이 모든 RL은 CFL에 속한다고 표현할 수 있다.

 

Example

 

위 문법은 CFG 일까?

CFG는 문법의 production 들에서 화살표 왼쪽이 하나의 변수로 구성되어있는지만 보면 된다.

화살표의 오른쪽은 어떻게 표현해도 상관이 없기 때문이다.

모든 production 의 화살표 왼쪽이 하나의 변수로만 구성되어 있으므로 이 문법은 CFG이고, 따라서 L(G)=CFL 이다.

 

이 문법이 만드는 문장은 abba, aaaaaa, aabbaa 와 와 같은 문장을 만든다.

이를 집합 기호로 표현하면 L = { wwᴿ : { a, b }* ∋ w } 로 표현할 수 있다.

그리고 이 언어는 RL가 아님을 펌핑 레마를 통해 증명했었다.

 

 

이 productions 로 구성된 문법은 CFG일까?

역시 화살표 왼쪽이 한 개의 변수로 구성되었는지만 보면 되니, CFG임을 어렵지 않게 알 수 있다.

이 문법이 만들어내는 문장을 보면 abbba, aabbab 와 같은 문장을 만든다.

 

이때 유도 과정을 적어보면 S => abB => abbbAa => abbbaaBba => .. 가 반복되다가 마지막에 A가 람다가 되는 순간 끝난다.

이를 계속 유도해보면 abB 이후에 B를 기준으로 왼쪽에 bbaa 가 붙고, 오른쪽에 ba가 반복해서 붙는 것을 알 수 있다.

 

S =>* ab(bbaa)ⁿB(ba)ⁿ => ab(bbaa)ⁿbba(ba)ⁿ 으로 표현할 수 있다.

 

 

 

따라서 위 문법이 나타내는 언어는 위와 같으며, 이 문장은 RL가 아니다. bbaa 의 개수와 ba의 개수를 추적해서 같다는 것을 유지해야 하기 때문이다.

 

 

그리고 이 예제까지 보면, CFG, Linear Grammar, RG는 위와 같은 포함 관계를 갖는 것을 알 수 있다.

Linear Grammar는 화살표 오른쪽에 있는 변수의 개수가 1개 이하인 production으로만 구성된 문법을 말한다.

위 예시 5.1, 5.2 가 나타내는 문법이 모두 해당하며 이를 통해 Linear Grammar는 RG는 아닐 수 있음을 알 수 있다.

반면 RG는 모두 Linear Grammar로 표현된다.

 

 

주어진 언어가 CFL 임을 증명하는 문제이다.

정의를 이용해 CFG로 이 언어를 만들면 증명에 성공할 것이다.

 

문법은 다음과 같이 구성할 수 있다.

 

S → AT | TB

A → aA | a

B → bB | b

T → aTb | λ

 

그리고 이 문법을 구성하는 productions 이 모두 화살표 오른쪽에 한 개의 변수를 가지므로, CFG이다.

따라서 이 언어는 CFG로 표현할 수 있기 때문에 CFL이다.

 

 

마지막으로 5.4 를 살펴보자.

모든 production 의 화살표 왼쪽이 하나의 변수로 구성되어 있으므로, 이 문법은 CFG 이다.

이 문법이 만드는 문장을 살펴보면 ab, abab, aaabbbaabb 와 같은 문장을 만들 수 있다.

 

이 문장은 linear 하지는 않다. 왜냐하면 S → SS 때문에 화살표 오른쪽에서 변수가 1개 이하여야 한다는 규칙에 위배되기 때문이다.

또한 이 문법도 나름대로 유명한 형태이다. 이 문법이 만드는 문장에 대해 a = (, b = ) 로 표현하면, 이 문장은 언제나 올바른 괄호 문자열을 만든다.

 

이 문법이 만드는 언어를 집합 기호로 표현하면 아래와 같다.

 

 

모든 a, b 로 구성된 문장 중에서 a, b의 개수가 같고, 이 문장의 모든 prefix에 대해서 a의 개수 ≥ b의 개수이면 된다.

 

 

L1 은 a, b의 개수가 같은 정렬된 문자열, L2는 a, b 의 개수와 상관없이 정렬된 문자열을 문장으로 갖는다.

L1 은 CFL이고, L2는 RL 이자 CFL 임을 어렵지 않게 받아들일 수 있다.

 

 

L1이 CFL임은 CFG를 만들어서 보일 수 있다.

(이때, 이 문법이 regular가 아니라고 해서, 이 언어가 regular 가 아니라는 것은 보장할 수 없다. RL의 문법은 다양하게 존재할 수 있기 때문이다. not regular는 펌핑 레마로 증명하자.)

 

 

L2가 RL 임은 DFA 또는 NFA를 그려서 보일 수 있고, CFL 임은 CFG를 만들어서 보일 수 있다.

(아래 그림에서는 RG로 표현하였다. RG는 화살표 왼쪽이 1개의 변수를 갖고, 오른쪽에는 모든 프로덕션이 모두 right-linear 하거나 모두 left-linear하면 된다.)