[Automata] CFG와 Pumping Lemma

Chapter 8의 내용이다!

 

CFG의 특성에 대해서는 이미 정의할 때 한번 다뤘는데 왜 또 얘기하지? 싶었는데

Pumping Lemma를 다루기 위한 것이였던 것 같다!

 

Theorem 8.3, 8.4

CFL은 union, concatenation, star-closure에 닫혀 있다.

intersection과 complementation에는 닫혀 있지가 않다. 

 

Theorem 8.5

L1이 context free language이고 L2이 regular language라면

L1 교집합 L2는 context free이다. 

 

Theorem 8.6

Context-free grammar G=(V, T, S, P)에 대하여, L(G)가 비어있는지 아닌지를 결정하는 알고리즘이 있다. 

 

Theorem 8.7

Context-free grammar G=(V, T, S, P)에 대하여, L(G)가 무한한지 아닌지를 결정하는 알고리즘이 있다. 

 

 

CFG를 위한 pumping lemma 정리를 사용해서, language가 context-free가 아님을 보일 수 있다. ㅇ

Theorem 8.1

L이 infinite한 CFL이라고 가정하자. 그렇다면 어떤 양의 정수 m이 존재하는데, L에 속하는 길이가 m보다 큰 임의의 문자열 w에 대해서, 

 

w = uvxyz 라고 하면

|vxy| <= m 이고, 

|vy| >= 1이고, 

uv^i x y^i z가 L에 속할 때 i=0,1,2...에 대해서 성립한다.