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

1. 비정규 언어와 DFA의 한계

비정규 언어 (Nonregular Languages)

정규 언어는 유한 상태 기계인 DFA로 표현(인식) 가능한 언어이다. 하지만 DFA는 **유한한 수의 상태(Memory)**만을 가지기 때문에, 무한히 커질 수 있는 수치를 기억하거나 두 수치를 비교하는 데에는 근본적인 한계가 있습니다. 이러한 한계로 인해 DFA로 표현할 수 없는 언어를 비정규 언어라고 부른다

• 핵심 원리: DFA가 기억할 수 있는 상태의 수는 ‘유한’하다는 점을 역이용한다
• 비둘기 집의 원리 (Pigeonhole Principle): DFA의 상태 개수가 $m$개일 때, 길이가 $m$ 이상인 문자열을 처리하려면 입력 과정에서 반드시 어떤 상태를 두 번 이상 방문하게 된다. 즉, 전이 그래프 상에 필연적으로 사이클(Cycle, 반복 루프)이 존재하게 된다는 것을 의미한다

---

2. 펌핑 렘마 (Pumping Lemma)

펌핑 렘마의 정의

어떤 언어가 정규 언어라면, 그 언어에 속하는 충분히 긴 모든 문자열은 특정 부분(루프)을 ‘펌핑(반복하거나 삭제)‘해도 여전히 그 언어에 속해야 한다는 수학적 정리이다. 주로 어떤 언어가 비정규 언어임을 증명할 때 사용된다

펌핑 렘마의 3가지 조건 어떤 언어 $L$이 정규 언어라면, 펌핑 길이(상태의 개수) $m$이 존재하며, 길이가 $m$ 이상인($|w|\ge m$) 모든 문자열 $w\in L$은 $w=xyz$ 세 부분으로 분할 가능하고 다음 세 가지 조건을 모두 만족해야 한다

1. $|xy|\le m$ : 펌핑되는 부분($y$)은 반드시 문자열의 시작점으로부터 $m$번째 기호 이내에 존재해야 한다 (이유: 첫 번째 루프는 $m$번의 전이 내에 무조건 발생하기 때문이다)
2. $|y|\ge 1$ : 펌핑되는 부분 $y$는 공스트링($\lambda$)이 될 수 없다 (이유: 최소 1글자 이상이어야 실제로 사이클이 형성된다)
3. $x{y}^{i}z\in L(i\ge 0)$ : $y$부분을 $i$번 반복하더라도 (심지어 $i=0$으로 아예 제거하더라도) 새롭게 만들어진 문자열은 여전히 언어 $L$에 속해야 한다

---

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

비정규 언어임을 증명할 때는 귀류법(Proof by Contradiction)을 사용한다. “이 언어가 정규 언어라고 가정했을 때, 펌핑 렘마의 조건을 적용하면 모순이 발생한다”는 것을 보여주는 논리 전개 방식이다

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

(설명: $a$와 $b$의 개수가 정확히 똑같은 문자열의 집합)

1. 가정: $L$이 정규 언어라고 가정하고 펌핑 길이를 $m$이라고 하자
2. 문자열 선택: 펌핑 렘마를 적용하기 위해 $L$에 속하면서 길이가 $m$ 이상인 문자열 $w=a^m{b}^m$ 을 선택한다($|w|=2m\ge m$)
3. 분할 분석: $w=xyz$ 로 나눌 때, 조건 1($|xy|\le m$)에 의해 $x$와 $y$는 무조건 앞부분인 $a$ 구역에만 존재해야 한다 (예: $y=a^k$, 단 $k\ge 1$)
4. 펌핑 적용 ($i=2$): $y$를 두 번 반복(Pump up)해 본다. 새롭게 만들어진 문자열은 $x{y}^{2}z=a^{m+k}{b}^m$ 이 된다
5. 모순 도출: 펌핑 결과 $a$의 개수($m+k$)가 $b$의 개수($m$)보다 많아져서 서로 개수가 같아야 한다는 $L$의 규칙이 깨진다. 즉, $x{y}^{2}z\notin L$ 이다. 이는 펌핑 렘마 조건 3에 위배되므로, $L$은 정규 언어가 아님이 증명된다.

📌 예시 2: $L=\{w{w}^R:w\in {\Sigma }^{\ast }\}$

(설명: 완벽하게 대칭을 이루는 짝수 길이의 팰린드롬 집합)

1. 문자열 선택: $L$에 속하면서 길이가 $m$ 이상인 교묘한 문자열 $w=a^m{b}^m{b}^m{a}^m$ 을 선택한다
2. 분할 분석: 조건 1($|xy|\le m$)에 의해 $y$는 무조건 가장 앞부분인 $a^m$ 구역 안의 일부여야만 한다 ($y=a^k$, 단 $k\ge 1$)
3. 펌핑 적용 ($i=0$): 이번에는 $y$를 삭제(Pump down)해 본다. 새롭게 만들어진 문자열은 $x{y}^{0}z=a^{m-k}{b}^m{b}^m{a}^m$ 이 된다
4. 모순 도출: 앞부분의 $a$ 개수($m-k$)와 뒷부분의 $a$ 개수($m$)가 달라져 완벽한 좌우 대칭이 깨진다. 즉, $x{y}^{0}z\notin L$ 입니다. 따라서 모순이 발생하므로 이 집합 역시 정규 언어가 아니다.