[계산 이론] Non-Context-Free Languages

 

1. The Pumping Lemma for Context-Free-Languages(CFL)

우리는 보조 정리인 Pumping Lemma를 활용하여 CFL이 아님을 보일 것 이다.

 

만약 A가 Context-free-lenaguage라면, pumping length p가 존재하며, A의 어떤 String S라도 최소 p만큼의 길이를 갖는다.

또한 그러한 S는 5조각, 즉 S = uvxyz로 나눌 수 있으며, 다음 조건을 만족한다.

 

조건 2에 의하여 v 또는 y 가 동시에 empty string일수는 없다.

조건 3에 의하여 v,x,y의 길이는 최대 p이다.

 

2. Proof

G를 CFL A의 Context-Free-Grammer(CFG)라 하자.

b를 symbol의 최대 수 라고 하자. 예를 들면 다음 CFG는 b가 3이되는데, 0S1이 가장 긴 symbol의 수 이기 때문이다.

S -> 0S1
S -> #

 

따라서 이러한 CFG를 사용하는 parse tree의 어떤 node도 자식의 수가 b보다 많을 수는 없다.

다시말해서, parse tree의 Level 1은 최대 b개의 자식을 갖을 수 있으며, Level 2는 최대 b^2개, Level 3은 최대 b^3개, ... , Level h는 최대 b^h개의 단말 노드를 갖게된다.

따라서 parse tree의 높이가 최소 h라면, 해당 String의 길이는 최소 b^h만큼의 길이여야 한다.

 

Conversely, 만약 생성된 String의 길이가 최소 (b^h)+1 만큼 길다면, 해당 parse tree의 높이는 최소 h+1 이다.

(생각해보면 당연한게, 높이가 h일때 b^h개를 갖는데, 여기서 1개만 더 늘어난 (b^h)+1 다음 h+1 이여야한다)

 

 

▶ |V|를 G의 variable의 수 라고 하자.

우리는 pumping lenght P를 b^(|V|+1)로 잡을 수 있다.

 

만약 CFL A에 포함된 String S의 길이가 P이상이라면, 해당 CFG의 parse tree는 최소 |V| + 1 만큼의 높이를 갖어야 합니다.

 

왜냐구요?? 이를 위해 P와 h+1 step에서의 단말 노드의 수의 대소 관계를 생각해봅시다. 다음 식을 보시죠!

CFG의 parse tree는 h step 나갔을때 b^|V|만큼의 말단 노드의 수를 갖으며, 말단 노드의 수가 b^|V| + 1은 h+1 step나가기 위한 최소 노드의 수 입니다.

 

(왼) pumping lenght, (오) h+1 step의 node 수

 

하지만 pumping length P는 parse tree가 |V|+1 step 만큼 높이를 갖을때의 최소 노드 수 보다 더 큰 수입니다.

b^|V|에 1을 더한것이 아니라, b만큼 곱하였기 때문이죠.

 

따라서 최소 노의 수 일때도 만족하면, 이보다 조금 더 긴 P의 길이에서도 만족하는 조건을 사용하게 됩니다.

 

우리의 CFG의 variable의 수는 |V|라고 맨 처음 말했었습니다.

하지만 위 parse tree그림을 보면, 시작 S를 중심으로 쭉 아래로 내려오면 최대 (V+1)개의 variable을 사용하게 되는데,

문제는 우리는 |V|개의 variable만 있다는 것 입니다!!

(시작 variable S부터 하여 쭉 중심으로 V+1개만큼 내려오다 마지막 terminal 1개를 만남)

 

여기서 어떤 variable은 최소 2번 사용되었다는 것을 알 수 있습니다 (비둘기집의 원리).

 

h+1 step에서의 최소 노드의 수 에서도 중복이 발생하니, 이보다 더큰 P만큼 에서도 중복은 발생하게 됩니다.

P가 조금은 더 크기 때문이죠!

 

우리는 편의상 R을 가장 아래에서부터 2번 반복되어 나온 variable로 잡을 것 입니다.

 

2-1) Divide S into uvxyz

이제 S를 uvxyz로 나누어 봅시다.

R이 나타내는 큰 subtree는 vxy를 생성하고, 작은 subtree는 x만을 생성합니다. 다음 그림을 보시죠!

 

따라서 동일한 R로부터 나오는 parse tree를 서로 바꿔볼 수 있습니다.

Replacing the smaller by the larger repeatedly gives parse trees for the String uv^ixy^iz at each i > 1.

Replacing the larger by the smaller generates the string uxz

즉 다음 그림과 같이 만들 수 있습니다.

 

2-2) Condition 2 : we must be sure that v and y are not ε 

이거는 귀류법으로 증명 가능하다.

v와 y가 둘다 ε이라 가정하고, 모순됨을 보이면, 원래의 가정이 틀렸다는 것 을 보이면 된다.

 

타오 : 타오는 여러 parse tree들 중 가장 적은 노의 수를 갖는 parse tree를 의미한다.

즉, 이미 가장 적은 노드를 갖는 타오를 선택하였는데, 타오프라임은 더 작은 parse tree가 되어 모순이 발생하는 것 이다.

 

2-3) Condition 3 : we need to be sure that vxy has length at most p

다음 그림과 설명으로 충분하게 이해 가능!

 

3. 결론

Context Free Language들은 모두 pumping length P가 있으며, 다음 조건을 만족해야 한다!