Pumping Lemma for Regular Languages

 

 

 

 

 

1. Pumping Lemma

 Pumping Lemma는 Regular Language의 일반적인 성질을 기술한 이론입니다. 따라서 어떤 language가 regular language를 판단할 때 사용됩니다.

참고로 한가지 써놓자면, pumping lemma는 언어가 non-finite일때를 한정해서 non-regular 증명용으로 사용합니다.

이에 대한 설명을 몇가지 덧붙이자면,1. 만약 어떤 language가 finite(유한)하다면 무조건 regular합니다. 그에 해당하는 FSM이 무조건 존재하기 때문이죠.2. 그러나 language의 길이가 non-finite(무한)한 경우, 이건 해당하는 FSM이 존재하지 않을지도 모릅니다. 따라서 이 경우에는 regular language가 아니라는 것을 증명하기 위해 pumping lemma를 사용합니다.

 

 

기본적으로 pumping lemma는 비둘기 집의 원리를 이용하며, state의 개수보다 긴 string을 accept 하기 위해서는 어디선가 loop을 무조건 돌아야 한다는 개념을 가지고 증명을 진행합니다.

 

해당 theorem은 다음과 같습니다.

Theorem  Let A is a regular language. Then there exists an integer p≥1, called the pumping length, such that the following holds :   Every string s in A, with |s| ≥ p, can be written as s = xyz     satisfying the following.    ① |y| ≥ 1    ② |xy| ≤ p    ③ xyⁿz ∈ A  for all n ≥ 0  즉, 길이가 p 이상이라면 1, 2, 3 의 조건을 모두 만족함.

 

따라서 기본적인 흐름은 다음과 같습니다. (귀류법 이용)

 

1. language A는 regular, 그리고 정수 p가 p≥1임을 가정

2. s∈A인 string을 임의로 선택

3. |xy|≤p, |y|>1을 만족하도록 A를 x*y*z*의 꼴로 맞춤 (조건 끼워맞추기)

4. Pumping Lemma 조건에 모순이 생기는 부분을 찾기 >> thus proved.

 

 

이렇게만 보면 이해하기 힘드니 예시를 하나 같이 봅시다.

 

 

2. 예시

 

1) Prove that L = {0ⁿ1ⁿ : n≥0} is NOT regular.

 

풀이는 타이핑으로 하기 어려워 필기본으로 대체합니다.

처음 공부할 때는 2번가정을 할 때 y가 0으로 이루어진 string인게 이해가 안됐는데, 어차피 모순법을 이용해 증명하는 과정이라 하나의 케이스라도 부합하지 않음을 보이면 증명이 되는거라 이렇게 한 것 같습니다. 이 문제 말고도 다른 문제들도 이런 가정을 기반으로 푸는 문제들이 많더라구요.

 

 

2) Prove that L = {0^n! : n≥0} is NOT regular.

 

 

 

뭐 이런늒김이라는거,,

끝!