정규 표현식

정규 언어를 표현하는 방법은 크게 세 가지(Grammar, Automata, RE)가 있으며, 그중 RE는 가장 선언적(Declarative)이고 직관적인 방법으로, 복잡한 언어의 패턴을 간결하게 묘사할 수 있다

정규 표현식의 재귀적 정의 알파벳 $Σ$ 에 대해 다음 규칙을 만족하는 문자열을 정규 표현식이라 한다

기본 정규 표현 (Primitive RE):
- $\emptyset$ : 공집합
- $λ$ : 공 문자열
- $a \in Σ$ : 각 알파벳 심볼
재귀적 규칙 (Recursive Rules):
- 합집합 (Union): $r_{1} + r_{2}$
- 결합 (Concatenation): $r_{1} \cdot r_{2}$ (또는 $r_{1} r_{2}$ )
- 클레이니 스타 (Kleene Star): $r_{1}^{*}$
- 괄호 (Parentheses): $(r_{1})$
특정 문자열이 RE가 되려면 반드시 위 기본 표현에서 시작해 유한 번의 규칙 적용을 거쳐 유도되어야 한다

RE의 성질 및 연산 우선 순위

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

연산 우선순위

주요 성질 및 항등원

정규 표현식은 박스(Box) 형태의 NFA 조각들을 조립하여 시각화할 수 있다

기본 변환 규칙

합집합 ( $r_{1} + r_{2}$ ): 새로운 시작 상태에서 두 박스( $M (r_{1}), M (r_{2})$ )로 $λ$ 전이를 갈라지게 하여 병렬로 연결한다

결합 ( $r_{1} \cdot r_{2}$ ): $M (r_{1})$ 박스의 출구를 $M (r_{2})$ 박스의 입구와 $λ$ 전이로 직렬 연결한다

클레이니 스타 ( $r^{*}$ ): * 박스의 끝에서 입구로 돌아가는 $λ$ 전이 추가 (반복)
- 시작에서 끝으로 바로 가는 $λ$ 전이 추가 (0회 반복 허용)

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

특징: 일반적인 NFA는 전이 레이블로 심볼( $a, b$ )이나 $λ$ 를 사용하지만, GTG는 전이 레이블로 정규 표현식(RE) 자체를 가질 수 있다

상태 간 전이: 만약 두 상태 사이에 직접적인 길이 없다면 $\emptyset$ 을 추가하여 모든 상태가 연결된 것으로 간주한다

의의: 모든 NFA는 GTG로 변환 가능하며, 이를 통해 최종적으로 RE를 추출할 수 있습니다. 이는 NFA, DFA, RE의 표현 능력이 동일함을 증명하는 근거가 된다

복잡한 오토마타를 단순화하여 정규 표현식을 찾아내는 핵심 알고리즘이다

기본 원리 (2-State GTG 공식) 상태가 두 개( $q_{i}, q_{j}$ )만 남았을 때, 시작 상태에서 최종 상태로 가는 전체 정규 표현식 $r$ 은 다음과 같이 정의된다

$r = r_{1}^{*} r_{2} (r_{4} + r_{3} r_{1}^{*} r_{2})^{*}$

단계별 제거 과정(3개 이상의 상태)

중간 상태 선택: 시작 상태( $q_{s}$ )와 최종 상태( $q_{f}$ )가 아닌 중간 상태 $q_{k}$ 를 선택한다
경로 업데이트: $q_{k}$ 를 거쳐가는 모든 경로를 RE 결합 연산으로 대체하여 남은 상태들 사이의 전이를 업데이트한다
- 예를 들어, $q_{i} \to q_{k} \to q_{j}$ 경로가 있다면 새로운 전이는 $r_{ik} \cdot (r_{kk})^{*} \cdot r_{kj}$ 가 된다
반복: 상태가 2개 남을 때까지 위 과정을 반복한다

유용한 공식

예제: $a$ 는 짝수, $b$ 는 홀수