정규언어(Regular Language)

1.정규 문법과 정규 언어 (Regular Grammar & Regular Language)

언어를 만드는 규칙인 '정규 문법'과 그 결과물인 '정규 언어'가 무엇인지 알아보려고 한다.

컴퓨터가 언어와 문법을 이해하는 방법

우리가 일상에서 사용하는 한국어나 영어 같은 자연어처럼, 컴퓨터 과학에서도 언어가 존재한다. 하지만 컴퓨터가 이해하는 언어는 훨씬 더 엄격하고 명확한 규칙을 따라야 한다.

• 언어(Language): 컴퓨터 과학에서 언어는 간단히 문자열(String)의 집합이다. 예를 들어 '0'과 '1'로만 이루어진 모든 문자열의 집합, 혹은 'a'로 시작해서 'b'로 끝나는 모든 문자열의 집합 등이 하나의 언어가 될 수 있다.
• 문법(Grammer): 이 언어에 속하는 문자열들은 어떤 규칙으로 만들어질까? 생성 규칙의 집합을 문법이라고 한다. 문법은 특정 언어에 어떤 문자열이 포함되고, 어떤 문자열은 포함되지 않는지를 정의하는 틀이라고 할 수 있다.

촘스키 계층 (Chomsky Hierarchy)

저명한 언어학자 노암 촘스키는 이 문법들을 규칙의 복잡성과 생성 능력에 따라 4가지 계층으로 분류했다.

• Type 0: 제한 없는 문법 (Recursively Enumerable)
• Type 1: 문맥 의존 문법 (Context-Sensitive)
• Type 2: 문맥 자유 문법 (Context-Free)
• Type 3: 정규 문법 (Regular)

계층의 번호가 높을수록 규칙이 단순하고, 표현할 수 있는 언어의 범위도 작아진다. 이 중에서 가장 단순하고 기본적인 Type3, 정규 문법과 이것이 만들어내는 정규 언어에 대해 알아볼 것이다.

정규 문법 (Regualar Grammar)이란?

정규 문법은 정규 언어를 생성하기 위한 규칙의 집합이다. 이는 4가지 요소로 구성된다.

• VN (비단말 기호, Non-terminal symbols)

  • 문장을 만들어가는 과정에서 사용되는 중간 단계의 기호이다.
  • 보통 대문자로 표현한다. (예: A, B, S)
  • 아직 문장이 완성되지 않았음을 의미한다.

• VT (단말 기호, Terminal symbols)

  • 최종적으로 문자열을 구성하는, 더 이상 바꿀 수 없는 기호이다.
  • 우리가 보는 실제 문자열의 요소들이다.
  • 보통 소문자나 숫자로 표현한다. (예: a, b, 0, 1)

• P (생성 규칙, Production rules)

  • 비단말 기호를 어떻게 단말 기호나 다른 비단말 기호로 바꿔나갈지 정의하는 규칙이다.
  • 예: S → aB

• S (시작 기호, Start symbol)

  • 문장 생성을 시작하는 특별한 비단말 기호이다.
  • $S \in V_N$

정규 문법의 핵심 규칙

정규 문법이 '정규'라고 불리는 이유는 생성 규칙(P)이 매우 단순하고 제한적인 형태를 갖기 때문이다. 그 규칙은 아래 두 가지 형태 중 하나여야 한다.

1. 우선형 (Right-linear) 문법

• 규칙: A → aB 또는 A → a
• 설명: 비단말 기호(A)가 단말 기호(a) 또는 단말 기호와 비단말 기호(aB) 형태로만 확장됩니다. 이때, 비단말 기호(B)가 항상 가장 오른쪽에 위치합니다.

2. 좌선형 (Left-linear) 문법

• 규칙: A → Ba 또는 A → a
• 설명: 비단말 기호가 항상 가장 왼쪽에 위치합니다.

이처럼 규칙이 한쪽 방향으로만 뻗어나가는 선형적인(liner) 형태를 띠기 때문에 이런 이름이 붙었다. 우리는 보통 우선형 문법을 기준으로 많이 사용한다.

정규 언어 (Regular Language)는 뭘가?

정규 언어란, 정규 문법에 의해 생성될 수 있는 모든 문자열의 집합이다.

쉽게 말해, 위에서 설명한 단순한 생성 규칙 (e.g., A → aB)만을 사용해서 만들 수 있는 언어들을 정규 언어라고 부르는 것이다.

간단한 예시

'a'로 시작하고 그 뒤에 'b'가 0번 이상 반복되는 언어 L = {a, ab, abb, abbb, ...} 를 생성하는 정규 문법이다.

• VN (비단말 심볼): {S, B}
• VT (단말 심볼): {a, b}
• S (시작 심볼): S
• P (생성 규칙):
  1. S → aB (문장은 'a'로 시작하고, 나머지 부분은 B가 결정한다.)
  2. B → bB ('b'를 추가하고 B 상태를 유지하여 'b'를 더 생성할 수 있다.)
  3. B → ε ('b' 추가를 멈추고 문자열 생성을 종료한다. ε은 빈 문자열을 의미한다.)

참고: 때로는 B → ε 규칙 대신, S → a 와 S → aB 처럼 종료 규칙을 시작 기호에 직접 명시하기도 합니다. 여기서는 빈 문자열(ε)을 사용해 종료를 표현했습니다.

---

생성 과정 예시: "abb"

문자열 "abb"는 아래와 같은 과정으로 만들어진다.

1. S
   • 시작 기호 S에서 출발한다.
2. → aB
   • S → aB 규칙을 적용한다.
3. → abB
   • B → bB 규칙을 적용한다.
4. → abb
   • B → ε (종료) 규칙을 적용합니다. B가 빈 문자열 ε으로 바뀌면서 사라집니다.

이렇게 생성 규칙을 순서대로 적용하여 "abb" 라는 문자열이 성공적으로 만들어졌다. 이 문법은 L에 속하는 모든 문자열을 생성할 수 있으므로, L은 정규 언어(Regular Language)이다.

---

2.정규 표현: 언어를 패턴으로 압축하기

정규 표현(Regular Expression, Regex)은 언어를 간결한 '패턴'으로 표현하는 표기법이다.

정규 표현이란?

정규 표현은 정규 언어를 나타내는 하나의 문자열이다. L={a,ab,abb,...}라는 언어를 만들기 위해 여러 줄의 생성 규칙을 사용했었는데 정규 표현을 사용하면 이 언어를 ab*라는 아주 짧은 패턴으로 표현할 수 있다.

이처럼 정규 표현은 정규 문법보다 훨씬 직관적이고 간결하다는 장점을 가진다. 복잡한 규칙 대신, 눈에 보이는 패턴으로 언어를 정의한다.

정규 표현의 3가지 기본 연산

모든 정규 언어는 단 세가지 기본 연산의 조합으로 표현할 수 있다.
1. Concatenation (연결)
ab 'a' 바로 뒤에 'b'가 오는 문자열 "ab"를 의미한다.
두 정규 표현을 나란히 쓰는 가장 단순한 형태이다.

2. Union (합집합, OR)

   • a|b 'a' 또는 'b'를 의미한다. (프로그래밍의 || 연산과 비슷하다.)
   • 언어 {a,b}를 표현한다.

3. Kleene Star (클레이니 스타, *)

   • a* 'a'가 0번 이상 반복되는 것을 의미한다. (ε, a, aa, aaa, ...)
   • 가장 강력한 연산자로, 무한한 길이의 문자열을 표현할 수 있게 해준다. '없어도 되고, 몇 개가 있어도 된다'는 의미다.

   이 연결, 합집합, 클리이니 스타 단 세 가지 연산만으로 모든 종류의 정규 언어를 표현할 수 있다.

정규 표현 예시와

기본 예시

• 알파벳 {a,b} 위에서 'b'로 끝나는 모든 문자열

  • (a|b)*b
  • 풀이: (a|b)*는 a 또는 b가 0번 이상 반복되는 모든 문자열을 의미한다. ("", "a", "b", "aa", "ab", ...) 그 뒤에 b를 연결했으니, 'b'로 끝나는 모든 문자열을 나타낼 수 있다.

• 알파벳 {a,b}위에서 'a'가 짝수 개 있는 모든 문자열

  • b(abab)
  • 풀이:
    • b*: 맨 앞이나 중간에 'b'는 몇 개가 와도 상관없다.
    • (ab*ab*)*: ab*ab* 패턴은 'a'를 정확히 두 개 포함된다. 이 덩어리 전체에 *를 붙여 'a' 두 개짜리 묶음이 0번 이상 반복되게 한다. 결과적으로 'a'의 개수는 항상 짝수가 된다.

• X = aX + b의 해는 $a^*b$ 이다

---

3.유한 오토마타 (Finite Automata)

이 파트는 정규 언어를 '인식'하는 추상적 기계 모델을 다룬다. 정규 문법 및 정규 표현과의 관계 파악이 중요하다.

유한 오토마타란?

유한 오토마타는 상태(State)를 가지며, 입력 문자열을 하나씩 읽어 들이면서 상태를 바꾸는(Transition) 추상 기계이다. 입력 문자열을 모두 읽었을 때, 기계가 특정 최종 상태(Final State)에 도달해 있으면 해당 문자열을 '인수(Accept'하고, 그렇지 않으면 '거부(Reject)'한다.

이는 마치 자판기와 같다. 동전을 넣는 행위(입력)에 따라 '대기' 상태에서 '금액 충족' 상태로 변하고, 버튼을 누르면 '음료 배출' 상태로 전의하는 것과 같은 원리이다.

결정적 유한 오토마타 (DFA: Deterministic Finite Automata)

가장 기본이 되는 유한 오토마타이다.

• 특징: 이름 그대로 동장기 '결정적'이다. 증, 현재 상태와 입력 기호가 주어지면 다음에 이동할 상태가 반드시 유일하게 하나로 정해진다.
• 구성 요소: 5가지 튜플 $(Q, \Sigma, \delta, q_0, F)$로 정의된다.
  • Q: 상태들의 유한 집합이다.
  • Σ: 입력 알파벳의 유한 집합이다.
  • δ: 전이 함수(Q×Σ→Q). 특정 상태에서 특정 입력을 받았을 때 어떤 상태로 갈지 정의한다.
  • $q_0$: 시작 상태. ($q_0$∈Q)
  • F: 최종 상태(인수 상태)들의 집합 (F⊆Q)
• 동작 과정: 문자열 "aba"를 인식하는 과정을 예로 들 수 있다. 기계는 $q_0$에서 시작하여 'a'를 읽고 다음 상태로, 'b'를 읽고 또 다음 상태로 이동한다. 마지막 'a'까지 읽었을 때 머물러 있는 상태가 F에 포함되면 "aba"는 인수된다.

비결정적 유한 오토마타 ((NFA: Non-deterministic Finite Automata)

DFA보다 유연한 구조를 가진 오토마타이다.

• 특징: 동작이 '비결정적'이다. 현재 상태에서 같은 입력 기호에 대해 여러 개의 다음 상태로 이동할 수 있다. 심지어 입력 없이도(ϵ-move) 다른 상태로 전이가 가능하다.
• DFA와의 차이점: NFA는 왜 필요한가? 특정 언어에 대해 DFA보다 훨씬 더 단순하고 직관적인 형태로 기계를 설계할 수 있게 해준다. 예를 들어, 'ab'또는 'ac'로 끝나는 언어를 표현할 때, NFA는 마지막 분기점을 간단하게 표현할 수 있다.
• 핵심: NFA와 DFA의 언어 인식 능력은 동일하다. 즉, 모든 NFA는 그와 동일한 언어를 인식하는 DFA로 변환될 수 있다. 표현의 간결함을 위해 NFA를 사용하지만, 그 능력의 본질은 DFA와 다르지 않다.

세 가지 개념의 동치 관계

이것이 정규 언어 이론의 핵심이다. 지금까지 세 가지 개념은 표현 방식만 다를 뿐, 본질적으로 완전히 동일한 능력을 가진다

정규 문법 ↔ 정규 표현 ↔ 유한 오토마타

• 정규 문법은 언어를 '생성'하는 규칙이다.
• 정규 표현은 언어를 '표현'하는 패턴이다.
• 유한 오토마타는 언어를 '인식'하는 기계이다.

이 셋은 모두 정규 언어라는 동일한 클래스를 각자의 방식으로 정의하고 다룰 뿐이다. 어떤 언어가 정규 문법으로 생성될 수 있다면, 그 언어를 표현하는 정규 표현과 인식하는 유한 오토마타는 반드시 존재한다.

---

4. 정규 언어의 속성과 한계 (Pumping Lemma)

정규 언어는 정규 문법, 정규 표현, 유한 오토마타라는 동치 관계의 세 개념으로 정의된다. 이 장에서는 정규 언어의 수학적 속성과 그 한계를 다룬다.

---

닫힘 속성 (Closure Properties)

어떤 집합이 특정 연산에 대해 '닫혀 있다(closed)'는 것은, 집합의 원소에 해당 연산을 적용한 결과가 다시 그 집합의 원소가 됨을 의미한다.

정규 언어의 집합은 여러 주요 연산에 대해 닫혀 있다. 이는 정규 언어들을 조합한 결과 역시 항상 정규 언어임을 보장한다. $L_1$과 $L_2$가 정규 언어일 때, 다음 연산의 결과 또한 정규 언어이다.

1. 합집합 (Union): $L_1 \cup L_2$

   • 두 언어의 모든 문자열을 포함하는 언어이다.

2. 연결 (Concatenation): $L_1 \cdot L_2$

   • $L_1$의 문자열과 $L_2$의 문자열을 순서대로 이어 붙인 문자열의 집합이다.

3. 클레이니 스타 (Kleene Star): $L_1^*$

   • $L_1$의 문자열을 0번 이상 연결하여 만들 수 있는 모든 문자열의 집합이다.

4. 교집합 (Intersection), 여집합 (Complement), 차집합 (Difference)

   • 이 연산들에 대해서도 닫혀 있음이 증명된다. 특히 여집합은 $L$을 인식하는 DFA에서 최종 상태와 비-최종 상태를 서로 교체하여 간단히 증명할 수 있다.

---

정규 언어의 한계와 펌핑 렘마 (Pumping Lemma)

정규 언어는 모든 언어를 표현할 수 없다. 유한 오토마타는 상태 개수가 유한하므로, 무한한 수를 기억하거나 개수를 세는 작업은 처리하지 못한다. 어떤 언어가 정규 언어가 아님을 증명하는 데에는 펌핑 렘마(Pumping Lemma)가 사용된다.

펌핑 렘마의 정의

• 목적: 특정 언어 $L$이 정규 언어가 아님을 증명하는 귀류법 도구이다. (어떤 언어가 정규 언어임을 증명하는 데는 사용할 수 없다.)

• 핵심 아이디어: 만약 어떤 언어가 정규 언어라면, 그 언어 내의 충분히 긴 문자열은 반드시 특정 중간 부분을 반복(펌핑)시켜도 여전히 해당 언어에 속해야 한다. 이는 긴 문자열을 처리하는 유한 오토마타가 반드시 특정 상태를 반복 방문(cycle)해야 하기 때문이며, 이 순환 구간이 펌핑 가능한 부분이 된다.

비정규 언어 예시: $L = \{a^n b^n \mid n \ge 0\}$

$L$은 'a'의 개수와 'b'의 개수가 동일한 문자열의 집합이다. 유한 오토마타는 'a'의 개수를 무한히 기억할 수 없으므로 이 언어는 정규 언어가 아니다.

[증명 과정 (귀류법)]

1. 가정: $L = \{a^n b^n\}$이 정규 언어라고 가정한다.

2. 펌핑 길이: 펌핑 렘마에 의해, 특정 펌핑 길이 $p$가 반드시 존재한다.

3. 문자열 선택: $p$보다 긴 문자열 $s \in L$를 선택한다. $s = a^p b^p$로 정한다.

4. 분할: $s$는 $s=xyz$라는 세 부분으로 나눌 수 있으며, 다음 조건을 만족해야 한다.

   • $|y| > 0$
   • $|xy| \le p$

5. 모순 증명:

   • 문자열 $s = a^p b^p$에서 $|xy| \le p$ 조건에 의해, $x$와 $y$는 반드시 문자열의 접두사인 $a...a$ 부분에만 존재해야 한다.
   • 따라서 $y$는 하나 이상의 'a'로만 구성된 문자열이다 ($y=a^k$, $k \ge 1$).
   • 펌핑 렘마에 따라 $xy^iz$는 모든 $i \ge 0$에 대해 $L$에 속해야 한다.
   • $i=2$일 때 문자열은 $xy^2z = a^{p+k} b^p$가 된다.
   • 이 문자열은 'a'의 개수($p+k$)와 'b'의 개수($p$)가 다르므로 $L$에 속하지 않는다. 이는 모순이다.

6. 결론: 최초의 가정, 즉 "$L$은 정규 언어이다"는 거짓이다.

결론

• 정규 언어는 정규 문법으로 생성되고, 정규 표현으로 표현되며, 유한 오토마타로 인식된다.
• 정규 언어는 합집합, 연결 등 여러 연산에 대해 닫혀 있는 속성을 가진다.
• 메모리의 한계로 인해 명확한 한계를 가지며, 이는 펌핑 렘마를 통해 증명된다.

이 개념들은 컴파일러, 텍스트 처리 등 컴퓨터 과학의 여러 분야에서 기초 원리로 활용된다. 정규 언어보다 표현력이 더 큰 상위 언어로는 문맥 자유 언어(Context-Free Language)가 있다.