computation theory (7) - pumping lemma for CFL

    CFL을 위한 pumping lemma는 RL을 위한 pumping lemma와 유사하지만 약간 다른 점이 있다.

Language A가 context-free lanugage라면 pumping length p가 있으면 p보다 긴 string s를 s=uvwxyz로 다음을 만족하도록 나눌 수 있다. 1. for each i >= 0, u(v^i)x(y^i)z 는 language A에 포함된다. 2. |uv| > 0 3. |uxy| <= p //사지방 컴퓨터가 flash 안되는 컴퓨터여서 나중에 추가

증명은 비둘기집의 원리(pigeonhole principle)로 증명한다.

CFL A를 recognize하는 CFG G의 rules중에 오른쪽 심볼의 개수가 가장 많은 rule의 오른쪽 심볼의 개수를 b라고 하면 parse tree의 깊이가 h일때 최대 children의 수는 b^h이다. variable의 개수를 |V|라 할때 pumping length를 b^(|V| + 1) = p로 설정하면 p보다 긴 string의 parse tree는 반드시 |V| + 1이상의 height를 가진다.  가장 작은 parse tree는 |V| + 1의 height를 가질 때이므로 |V| + 2개의 node가 필요하고 그 중 한개가 terminal이면 |V| + 1개의 variable이 필요하다. 비둘기집의 원리로 어떤 variable은 두번 이상 나타난다. 이제 string s를 uvxyz로 나눠야하는데 parse tree를 생각해보면 두번 이상 나타나는 variable을 기준으로 자르면 Figure 1처럼 condition 1이 성립함을 알 수 있다.  Figure 1. parse tree (출처 : https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages -위키피디아) Node N은 비둘기집의 원리로 같은 자리에 있지 않으므로 |uv| > 0이 성립하며 |V| + 1의 높이를 가진 parse tree의 최대 children의 수는 b^(|V| + 1) = p이므로 |uxy| < p가 성립한다. //사지방 컴퓨터가 flash 안되는 컴퓨터여서 나중에 추가

모든 CFG는 pumping lemma를 만족한다.