[계산이론](10)[pumping lemma]

nonregular language

finite automata나 regular expression으로 나타내지 못하는 language
이걸 어케 증명하지?
    일일히 DFA를 그리는 시도를 해볼까?
    -> 응안돼

pumping lemma

A가 regular language라면, p라는 숫자가 존재해 (pumping length)
s ∈ A이고 |s| >= p인 모든 s에 대해
다음을 만족하는 s의 어떤 분할 x, y, z가 존재한다.

1. i >= 0일때, $xy^{i}z \in A$
2. |y| > 0
3. |xy| <= p

모든 regular language는 pumping lemma를 만족한다.
-> 즉, nonregular를 대우로 증명할 수 있다!
     regular language => pumping lemma 만족
     대우: pumping lemma 불만족 => regular language 아님

 

regular language -> pumping lemma 증명

r.l에 포함되는 string이고 |s|>= p인 모든 s가 xyz로 분할되고 조건 1, 2, 3을 만족함을 보이자.

|s| < p 인 경우

전제가 거짓이므로, 항상 참 (공허참)

|s| >= p 인 경우

DFA M = ($Q$, $\sum$, $\delta$, $q_0$, $F$)이라 하자.
M의 state 개수 |Q|를 pumping length로 두자 p = |Q|
이때 전제에 의해 |s| = n >= p이다.
s = s1 s2 s3 s4 s5 ... sn 이라 하자. {$s_i\in \sum$ }

• 1번 조건
  이 각각의 symbol을 읽어 진행되는 state의 갯수는 n+1개이다.
  즉, n+1 > n >= p이므로, n+1(진행 state 수) > p(존재하는 state 수)
  따라서 by 비둘기집의 원리,
  적어도 1개의 state는 진행될 때 중복으로 나온다.
  
  이떄 중복되는 상태를 qk라고 한다면
  qk ~ qk 사이에 있는 s를 loop라고 부를 수 있으며,
  이곳을 y로 잡으면 pumping될 수 있다.
      (즉, xz, xyz, xyyz, xyyyz, ... 모두 accept)
  따라서 1번 조건을 만족한다.
  
  
• 2번 조건
  by 비둘기집의 원리, 적어도 반복되는 state가 1개 이상 존재
  따라서 반복 state 사이가 존재하고,
  그 길이는 1 이상이므로, |y| >= 1 > 0
  따라서 |y| > 0
  
  
• 3번 조건
  전제에 의해 |s| >= p이다.
  |p|가 더 길어진다 하더라도, 앞에 p+1개의 state가 있을 것이며,
  무조건 중복 state가 하나 나온다.
  따라서 중복 state 사이를 y로 잡는다면
  항상 |xy| <= p 이다.