[Automata][WIP] 정규 언어의 성질, 비정규언어 판별하기

chapter 4의 내용이다!

정규 언어의 Closure

정규 언어에 대한 주요한 질문들

비정규 언어 판별하기

- pigeonhole principle(비둘기집 원리)

 

예시로 살펴보자! L = {a^n b^n: n>=0} 이면 L은 정규언어일까? (예제 4.6)

 

여기에 해당하는 언어는 L = { ƛ, ab, aabb, ... } 등이 있을 것이다.

 

이 문제를 귀류법으로 접근하면, 

L이 regular language라면 DFA M = {Q, {a,b}, 𝛿, q_0, F}가 존재할 것이다. 

 

i=1,2,3..일 때 𝛿*(q_0, a^i)를 생각하면 i는 무한대로 많을 것인데 M에는 state개수가 유한하다.

그렇다면, 

 

𝛿*(q_0, a^n) = q

𝛿*(q_0, a^m) = q인

서로 다른 n, m이 존재하게 될 것이다. 

 

하지만 M은 a^n b^n을 accept하므로, 𝛿*(q, b^n) = q_f ⊆ F 인 q_f가 필요하다. 

𝛿*(q_0, a^m b^n) = 𝛿*(𝛿*(q_0, a^m), b^n)

= 𝛿*(q, b^n)

= q_f

 

인데 이 가정은, 원래 가정이었던 a^m b^n은 m==n일때만 accept한다는 가정이 깨지게 된다. 

그러므로 L은 정규언어가 아니다. 

 

 

- pumping lemma(펌핑 보조정리)

 

펌핑 보조정리는 비둘기집 원리를 다른 형태로 바꿔서 쓰는 정리이다.

이 정리는 n개의 vertex가 있고 n개 이상의 path가 있으면 무조건 cycle이 생긴다는 이론을 기반으로 한다. 

 

예제 4.8

 

예제 4.9

 

예제 4.10

..

 

예제 4.13