[계산이론및오토마타] 3 정규 표현식(Regular Expressions, RE)

1. 정규 표현식 (Regular Expressions, RE)

정규 표현식 (RE)

정규 언어를 표현하는 방법은 크게 세 가지(문법, 오토마타, 정규 표현식)가 있다. 그중 RE는 가장 선언적(Declarative)이고 직관적인 방법으로, 복잡한 언어의 패턴을 수학적 수식처럼 간결하게 묘사할 수 있다

1.1 정규 표현식의 재귀적 정의

어떤 알파벳 $\Sigma$에 대해 다음 규칙을 만족하는 문자열만을 정규 표현식이라고 부른다. 특정 문자열이 RE가 되려면 반드시 아래의 기본 표현에서 시작해 유한 번의 규칙 적용을 거쳐 유도되어야 한다

• 기본 정규 표현 (Primitive RE):
  • $\varnothing$: 공집합 (아무 문자열도 포함하지 않음)
  • $\lambda$: 공스트링 (빈 문자열)
  • $a\in \Sigma$: 알파벳 집합에 속한 각각의 기호
• 재귀적 규칙 (Recursive Rules):
  • 합집합 (Union): $r_1+r_2$ (또는 $r_1\cup r_2$)
  • 결합 (Concatenation): $r_1\cdot r_2$ (또는 점을 생략하여 $r_1{r}_2$)
  • 클레이니 스타 (Kleene Star): $r_1^{\ast }$ (0번 이상 반복)
  • 괄호 (Parentheses): $(r_1)$ (연산 우선순위 지정)

1.2 RE의 성질 및 연산 우선순위

수학의 사칙연산처럼 RE에도 연산 순서와 대수적 성질이 존재한다

연산 우선순위

1. 클레이니 스타 ($\ast$): 가장 높음
2. 결합 ($\cdot$): 중간
3. 합집합 ($+$): 가장 낮음 (예시: $(a+b\cdot c{)}^{\ast }$ 식에서는 $b\cdot c$가 제일 먼저 묶이고, 그 다음 $a$와 더해진 후, 마지막에 스타 연산이 적용된다)

주요 성질 및 항등원 정규 표현식은 집합 연산을 기반으로 하므로 다음과 같은 성질을 가진다

• 항등원 (Identity): * $r+\varnothing =r$ (공집합을 더해도 그대로)
  • $r\cdot \lambda =r$ (빈 문자열을 결합해도 그대로)
• 공집합과의 결합 (Annihilator): * $r\cdot \varnothing =\varnothing$ (어떤 문자열과도 결합할 수 없게 되므로 결과는 공집합)
• 분배 법칙 (Distributive Law): * $r_1(r_2+r_3)=r_1{r}_2+r_1{r}_3$

---

2. RE에서 NFA로의 변환

톰슨의 구성법 (Thompson's Construction)

정규 표현식은 입력과 출력을 가진 박스(Box) 형태의 NFA 조각들을 재귀적으로 조립하여 시각화할 수 있다.

• 1. 합집합 ($r_1+r_2$): 병렬 연결 새로운 시작 상태에서 두 박스($M(r_1)$와 $M(r_2)$)로 향하는 $\lambda$-전이를 갈라지게 하여 병렬로 연결한다

• 2. 결합 ($r_1\cdot r_2$): 직렬 연결 $M(r_1)$ 박스의 출구를 $M(r_2)$ 박스의 입구와 $\lambda$-전이로 직렬 연결한다

• 3. 클레이니 스타 ($r^{\ast }$): 반복 루프 생성
  • 박스의 끝(출구)에서 다시 입구로 돌아가는 $\lambda$-전이 추가(1회 이상 반복 처리)
  • 박스의 시작에서 끝으로 아예 건너뛰는 $\lambda$-전이 추가(0회 반복 허용 처리)

---

3. NFA를 정규 표현식으로 변환

NFA, DFA, RE는 모두 표현 능력이 동일하다. 이를 증명하기 위해 오토마타를 다시 수식(RE)으로 되돌리는 방법이 존재한다

3.1 GTG (Generalized Transition Graph)

NFA에서 정규 표현식을 유도하기 위해 사용하는 확장된 형태의 그래프 모델이다

• 특징: 일반적인 NFA는 전이 레이블로 단일 심볼($a,b$)이나 $\lambda$만을 사용하지만, GTG는 전이 레이블 자체에 정규 표현식(RE) 전체를 적을 수 있다
• 상태 간 전이: 만약 두 상태 사이에 직접적인 연결 경로가 없다면 레이블을 $\varnothing$으로 두어, 논리적으로는 모든 상태가 서로 연결된 것으로 간주한다

3.2 상태 제거법 (State Elimination Method)

복잡한 GTG에서 상태를 하나씩 지워나가며(우회 경로를 수식으로 병합하며) 최종적으로 정규 표현식을 찾아내는 핵심 알고리즘이다

단계별 제거 과정

1. 중간 상태 선택: 시작 상태($q_s$)와 최종 수락 상태($q_f$)가 아닌 중간 상태 $q_k$를 하나 선택하여 제거한다
2. 경로 업데이트 (핵심): $q_k$를 거쳐 가는 우회 경로를 RE 연산으로 묶어 기존 경로에 더해준다
   • 만약 상태 $q_i$에서 $q_j$로 가는 기존 경로 레이블이 $r_{old}$ 였다면, $q_k$를 지우면서 다음과 같이 업데이트된다
   • $r_{new}=r_{old}+r_{ik}\cdot (r_{kk}{)}^{\ast }\cdot r_{kj}$
   • (해석: 기존에 바로 가던 길 + $q_k$로 들어가서 자기 루프를 돌고 다시 $q_j$로 나오는 길)
3. 반복: 상태가 오직 시작 상태와 최종 상태 단 2개만 남을 때까지 위 과정을 반복한다 ㄹ 2-State GTG 공식 (최종 산출) 상태가 단 두 개(시작 상태와 수락 상태)만 남았을 때, 최종 정규 표현식 $r$은 다음과 같이 정리된다

$r=r_1^{\ast }{r}_2(r_4+r_3{r}_1^{\ast }{r}_2{)}^{\ast }$

• $r_1$: 시작 상태에서의 자기 루프 (Self-loop)
• $r_2$: 시작 상태 $\to$ 최종 상태 전이
• $r_3$: 최종 상태 $\to$ 시작 상태로 돌아오는 전이
• $r_4$: 최종 상태에서의 자기 루프

변환 시 유용한 축약 공식

경로를 합치다 보면 수식이 지저분해질 수 있습니다. 다음 공식을 활용해 간소화하라

• $r+\varnothing =r$ (없는 경로는 더해도 무시)
• $r\cdot \varnothing =\varnothing$ (끊긴 경로와 결합하면 그 길도 끊어짐)
• ${\varnothing }^{\ast }=\lambda$ (아무것도 없는 것을 0번 이상 반복하면 빈 문자열만 나옴)

변환 예제

조건: $a$는 짝수 개, $b$는 홀수 개 포함하는 문자열을 인식하는 NFA