[계산이론및오토마타] 5 비정규 언어(Nonregular Languages)

비정규 언어와 DFA의 한계

비정규 언어

정규 언어는 DFA로 표현 가능한 언어이다. 하지만 DFA는 유한한 수의 상태만을 가지기 때문에, 무한히 커질 수 있는 수치를 기억하거나 비교하는 데 한계가 있다. 이때 DFA로 표현 불가능한 언어가 비정규 언어이다

핵심 원리: DFA가 수용할 수 있는 상태의 수는 유한하다는 점을 이용한다

비둘기 집의 원리(Pigeonhole Principle): DFA의 상태 개수가 $m$개일 때, 길이가 $m$ 이상인 문자열을 처리하려면 반드시 어떤 상태를 두 번 이상 방문하게 됩니다. 즉, 그래프상에 사이클(Cycle)이 존재하게 된다

펌핑 렘마(Pumping Lemma)

펌핑 렘마

어떤 언어가 정규 언어라면, 그 언어에 속하는 충분히 긴 모든 문자열은 특정 부분을 ‘펌핑(반복)‘해도 여전히 그 언어에 속해야 한다는 정리이다

조건 (The 3 Conditions) 언어 $L$이 정규 언어라면 펌핑 길이 $m$이 존재하며, $|w|\ge m$인 모든 $w\in L$은 $w=xyz$로 분할 가능하고 다음을 만족한다

• $|xy|\le m$ : 펌핑되는 부분($y$)은 문자열의 앞부분 내에 존재함
• $|y|\ge 1$ : 펌핑되는 부분은 공문자열이 아님
• $w_i=x{y}^{i}z\in L$ ($i\ge 0$) : $y$를 몇 번 반복하더라도(심지어 제거하더라도) 여전히 언어 $L$의 원소여야 함

펌핑 렘마를 이용한 비정규 언어 예시

비정규 언어임을 증명할 때는 귀류법을 사용합니다. “이 언어가 정규 언어라고 가정하면 모순이 발생한다”는 것을 보여주는 방식이다

예시1: $L=\{a^n{b}^n:n\ge 0\}$

• 가정: $L$이 정규 언어라고 가정하고 펌핑 길이를 $m$이라 하자
• 문자열 선택: $w=a^m{b}^m$ 선택 ($|w|=2m\ge m$)
• 분할 분석: $|xy|\le m$이므로, $y$는 오직 $a$로만 이루어져야 함 (예: $y=a^k,k\ge 1$)
• 펌핑: $i=2$일 때, $x{y}^{2}z=a^{m+k}{b}^m$이 됨
• 모순: $a$의 개수가 $b$보다 많아지므로 $x{y}^{2}z\notin L$. 따라서 $L$은 비정규 언어임

예시2: $L=\{w{w}^R:w\in {\Sigma }^{\ast }\}$ (팰린드롬)

• 문자열 선택: $w=a^m{b}^m{b}^m{a}^m$ 선택
• 분할 분석: $|xy|\le m$이므로 $y$는 앞부분 $a^m$의 일부임 ($y=a^k$)
• 펌핑: $i=0$ (삭제)을 적용하면 $x{y}^{0}z=a^{m-k}{b}^m{b}^m{a}^m$이 됨
• 모순: 앞부분의 $a$ 개수와 뒷부분의 $a$ 개수가 달라져 좌우 대칭이 깨지므로 $x{y}^{0}z\notin L$