[오토마타] 22. CFL의 Closure Property

CFL Clousure Property

CFL은 다음에 연산에 대해 닫혀있다. (다음 연산의 수행 결과 역시 CFL이다.)

 

1. Union

CFL 2개를 합친 언어도 CFL 이다.

 

2. Concatenation

2개 CFL 에 속하는 모든 문장을 이어붙여 만든 언어도 CFL이다.

 

3. Star Clousure

하나의 CFL에 *를 취해도 여전히 CFL이다.

 

하지만 다음에 대해서는 닫혀있지 않다.

1. Intersection

2. Complementation

 

닫혀지 있지 않다는 것은 CFL일 수도 있고, 아닐 수도 있다는 뜻이다.

예를 들어 CFL인 L1 과 L1을 교집합하면 여전히 CFL이다.

 

 

 

RL와 비교해보면 위와 같다.

RL에서는 교집합, 여집합에 대해서도 닫혀있었지만, CFL은 아니다.

 

 

L1 과 L2는 모두 CFL 인데, 이들의 교집합은 펌핑렘마로 CFL이 아님을 증명했던 언어이다.

L1을 보면 a, b의 개수만 따지고 c의 개수를 따지지 않는 경우 스택만으로 디자인할 수 있다.

사실 concatenate 연산에 대해 닫혀있다는 걸 이용하면 aⁿbⁿ 과 cⁿ 의 concatenate 연산 결과가 L1임을 알 수 있다.

모두 같은 변수 n을 썼지만 concatenate하고 나면 모든 조합을 다 만들어야 해서 c는 a,b의 개수와 독립적으로 표현해야 한다.

 

제일 깔끔한 것은 CFL을 보이기 위해 CFG를 정의하면 된다.

 

먼저 aⁿbⁿ 을 만드는 문법 S1과 cᵐ을 만드는 문법 S2를 정의해서 합치면 L1의 문법을 어렵지 않게 정의할 수 있다.

L2도 같은 방법으로 정의하면 된다.

 

그리고 교집합이 닫혀있지 않다는 것을 증명했다면, 교집합은 드모르간 법칙에 의해 각각의 여집합 연산을 취한 결과의 합집합 이후 여집합을 한 것과 같은데,

만약 여집합이 닫혀있다면, 합집합도 닫혀있으므로 L1, L2의 교집합이 닫혀있어야 한다.

따라서 귀류법에 의해 여집합 연산도 닫혀있지 않다고 증명할 수 있다.

 

Closure under regular intersection

그런데 만약 CFL과 RL 사이에서 교집합을 한다면 어떨까? 이 경우에는 그 결과가 CFL이다.

이를 가리켜 closed under regular intersection 이라고도 표현한다.

 

 

자세한 증명은 해주시지 않았지만, L1은 NPDA를 만들고, L2는 DFA를 만든 다음 두 기계를 잘 조합하면 그 기계는 NPDA가 나온다고 한다.

 

 

이 성질을 이용해서 간단한 증명 연습 문제를 풀어보자.

L은 유명한 CFL 언어에 대해서 n = 100 인 경우만 제외했다.

 

먼저 aⁿbⁿ 은 CFL (L1) 이고, a¹⁰⁰b¹⁰⁰ 하나만을 문장으로 갖는 언어는 RL (L2) 이다.

이때 L 은 L1 - L2 = L1 ∩ complement(L2) 이고, 여집합에 대해서 RL은 닫혀있으므로 L2의 여집합도 RL이다.

따라서 L1 과 (L2의 여집합)의 교집합은 위에서 본 대로 CFL과 RL의 교집합과 같아서 CFL이다.

 

 

이 언어는 a, b, c의 개수만 같으면 문장이다.

이 언어가 CFL이 아님을 증명해보자.

사실 펌핑렘마를 활용하면 abc 순으로 나열하고 각각의 개수가 같은 문장을 제시한 다음에 이거에 대해 펌핑렘마 해보라고 하면 절대 성공할 수 없어서 not CFL을 증명할 수 있지만, 다른 방법으로도 증명해보면

 

 

 

귀류법을 사용하여 L이 CFL 이라고 가정하고 RL인 a*b*c* 와 교집합을 취한다.

그러면 CFL에서 순서가 정해진 aⁿbⁿcⁿ 이라는 언어가 등장하는데, 이 언어는 CFL이 아니므로 모순이다.

따라서 L은 CFL이 아니라고도 할 수 있따.

 

즉, L이 CFL이 아님을 증명하는 또 다른 방법으로 RL과의 교집합을 통해 CFL이 아닌 언어를 만들어서 귀류법으로 증명할 수 있다.

 

 

CFL의 특성 판별하기

CFL이 공집합인지 판별하기

CFL을 문법으로 만들었을 때, S가 useless 인지 판별하면 된다.

즉, S에서 유도했을 때, 문장에 닿을 수 없다면 공집합이라는 것과 같다.

 

CFL이 무한집합인지 판별하기

CFL을 문법으로 만들고, 변수와 변수 사이에 dependency graph를 그렸을 때, 사이클이 존재하면 무한집합이고, 사이클이 없으면 유한집합이다.

 

두 CFL 가 같은 지 판별하기

두 문법 G1, G2에 대해 L(G1) 과 L(G2) 가 같은 지 판별할 수 없다.

 

만약 RL였다면 가능했을까?

RL에서는 가능하다.

 

 

이렇게 판단하면 된다.