정규 문법 (Regular Grammars)

정규 문법

정규 문법은 정규 언어를 생성하는 생성 규칙( $P ro d u c t i o n R u l e$ )의 집합이다. 크게 두 가지 형태가 존재한다

문법의 종류

우선형 문법 (Right-linear Grammar): 모든 규칙이 $A \to x B$ 또는 $A \to x$ 형태이다( $x \in Σ^{*}$ , 즉 단말 기호의 문자열)
좌선형 문법 (Left-linear Grammar): 모든 규칙이 $A \to B x$ 또는 $A \to x$ 형태이다

정규 표현식 유도 예시

문법이 주어졌을 때, 반복적인 대입을 통해 해당 문법이 생성하는 언어를 RE로 표현할 수 있다

우선형 예시: $S \to ab S ∣ a$

$S \Rightarrow ab S \Rightarrow abab S \Rightarrow \dots \Rightarrow (ab)^{*} a$

좌선형 예시: $S \to S_{1} ab, S_{1} \to S_{1} ab ∣ S_{2}, S_{2} \to a$

$S \Rightarrow S_{1} ab \Rightarrow (S_{1} ab) ab \Rightarrow \dots \Rightarrow aab (ab)^{*}$

문법과 오토마타의 상호 변환

오토마타의 상태(State)는 문법의 변수(Non-terminal)와 대응된다

우선형 문법→ DFA 문법의 전이 규칙을 오토마타의 상태 전이로 바꾼다

규칙: $V_{i} \to a V_{j}$ 는 상태 $V_{i}$ 에서 $a$ 를 입력받아 $V_{j}$ 로 가는 화살표가 된다
예시: $V_{0} \to a V_{1}, V_{1} \to ab V_{0} ∣ b$
- 문법의 RE는 $a (aba)^{*} b$

DFA → 우선형 문법 DFA의 구조를 그대로 생성 규칙으로 옮긴다

언어: $L (aa b^{*} a)$

각 상태 $q_{0}, q_{1}, q_{2}, q_{F}$ 를 문법 변수로 설정
전이에 따라 규칙 생성:
- - $q_{0} \to a q_{1}$
- $q_{1} \to a q_{2}$
- $q_{2} \to b q_{2} ∣ a q_{F}$
- $q_{F} \to λ$

좌선형 문법 변환 우선형 문법은 “상태 $\to$ 입력 $\to$ 다음 상태”로 직관적으로 그려지지만, 좌선형은 최종 상태에서 거꾸로 거슬러 올라가는 구조이다. 따라서 동치를 이용해서 사용해 변환을 진행하면 된다

정규 언어의 기본 폐쇄 성질

정규 언어 $L_{1}, L_{2}$ 가 있을 때, 특정 연산을 거친 결과도 여전히 정규 언어라는 성질이다

연신 종류	설명 및 증명 방법
합집합 ( $L_{1} \cup L_{2}$ )	정규 표현식 $r_{1} + r_{2}$ 로 표현 가능
결합 ( $L_{1} L_{2}$ )	정규 표현식 $r_{1} r_{2}$ 로 표현 가능
여집합 ( $\overline{L_{1}}$ )	DFA의 수용 상태와 비수용 상태를 반전시켜 구성
교집합 ( $L_{1} \cap L_{2}$ )	드 모르간 법칙( $\overline{\overline{L_{1}} \cup \overline{L_{2}}}$ ) 혹은 Product Construction( $m \times n$ 상태 구성)으로 증명
차집합 ( $L_{1} - L_{2}$ )	$L_{1} \cap \overline{L_{2}}$ 와 같으므로 정규 언어임
역순 (Reversal)	문자열을 뒤집어도 정규 언어의 틀을 벗어나지 않음

동형 사상(Homomorphism)

동형 사상상

문자열의 각 알파벳을 특정 문자열로 치환하는 함수 $h$ 에 대해, 정규 언어 $L$ 의 상(Image)인 $h (L)$ 도 정규 언어이다

예시1: 문자열 집합의 변환

설정: $Σ = {a, b}, Γ = {a, b, c}, h (a) = ab, h (b) = bb c$
대상 언어: $L = {aa, aba}$
결과: $h (L) = {h (aa), h (aba)} = {abab, abbb c ab}$

예시2: 정규 표현식의 변환

설정: $Σ = {a, b}, Γ = {b, c, d}, h (a) = d b cc, h (b) = b d c$
정규 표현식: $r = (a + b^{*}) (aa)^{*}$
결과: $h (r) = (d b cc + (b d c)^{*}) (d b cc d b cc)^{*}$

Right-Quotient(우측 몫)

우측 몫몫

두 언어 $L_{1}, L_{2}$ 에 대해 $L_{1}$ 의 문자열에서 $L_{2}$ 에 속하는 접미사를 제거하고 남은 부분들의 집합입니다

정의:

$L_{1} / L_{2} = {x ∣ x y \in L_{1} for some y \in L_{2}}$

수식 예시

$L_{1} = {a^{n} b^{m} : n \geq 1, m > 0} \cup {ba}$
$L_{2} = {b^{m} : m \geq 1}$
결과: $L_{1} / L_{2} = {a^{n} b^{m} : n \geq 1, m \geq 0}$ (즉, $a a^{*} b^{*}$ )

체계적인 방법(DFA 기반 알고리즘) NFA나 DFA의 그래프 구조를 이용해 $L_{1} / L_{2}$ 를 수용하는 오토마타를 바로 만들 수 있다

시작: $L_{1}$ 을 인식하는 DFA를 준비한다
수용 상태 재설정: 어떤 상태 $q$ 에서 $L_{2}$ 에 속하는 문자열 $y$ 를 입력받아 원래 $L_{1}$ 의 수용 상태에 도달할 수 있다면, $q$ 를 새로운 수용 상태로 바꾼다
의미: 이는 “앞부분 $x$ 를 읽고 $q$ 에 도달했을 때, 뒤에 $y \in L_{2}$ 가 올 가능성이 있다면 $x$ 를 몫으로 인정하겠다”는 뜻이다

교집합 연산과 컨스트럭티브 증명

정규 언어 $L_{1}$ 과 $L_{2}$ 의 교집합( $L_{1} \cap L_{2}$ )이 정규 언어임을 증명하기 위해 두 DFA를 결합한 Product DFA를 구성한다

예시: $L_{1} = a a^{*}$ , $L_{2} = a b^{*}$

증명 방법: 각 DFA의 상태를 쌍( $(q_{i}, q_{j})$ )으로 묶어 새로운 상태를 만든다

새로운 수용 상태는 두 DFA가 모두 수용 상태인 경우( $1, 1$ )만 해당된다
결과적으로 $L_{1} \cap L_{2} = a$ 가 되며, 이는 정규 언어임이 증명된다

정규 언어의 표준 표현 (Standard Representation, SR)

정규 언어를 다룰 때 공통적으로 사용하는 세 가지 표준 표현 방식이다

정규 표현식 (RE)
유한 오토마타 (DFA/NFA)
정규 문법 (RG)

정규 언어에 대한 주요 판정 문제

특정 언어가 정규 언어의 표준 표현(SR)으로 주어졌을 때, 다음 질문들에 대해 알고리즘적으로 답을 할 수 있다

소속 문제 (Membership Problem) 임의의 문자열 $w$ 가 언어 $L$ 에 포함되는가? ( $w \in L$ ?)

판별 방법:
- 언어 $L$ 을 인식하는 DFA를 준비한다
- DFA의 시작 상태( $q_{0}$ )에서 시작하여 문자열 $w$ 의 각 심볼을 순서대로 따라간다
- 문자열을 모두 읽었을 때 도달한 최종 상태가 **수용 상태(Final State)**이면 Yes, 아니면 No이다
특징: 문자열의 길이를 $n$ 이라 할 때, $O (n)$ 시간 안에 아주 빠르게 계산할 수 있다

공백/유한/무한 판정 (Emptiness, Finiteness, Infiniteness) 언어 $L$ 이 비어 있는지, 문자열의 개수가 유한한지 혹은 무한한지를 판별한다

공백 판정 (Emptiness: $L = \emptyset$ ?)
- 방법: DFA의 시작 상태에서 수용 상태로 도달할 수 있는 경로(Path)가 하나라도 존재하는지 확인한다
- 알고리즘: BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색)를 사용하여 그래프의 연결성을 확인한다. 수용 상태에 전혀 도달할 수 없다면 해당 언어는 비어 있는( $\emptyset$ ) 것이다
무한 판정 (Infiniteness?)
- 방법: 시작 상태에서 수용 상태로 가는 경로 위에 사이클(Cycle)이 존재하는지 확인한다
- 알고리즘:
  - 시작 상태에서 도달 불가능한 상태와 수용 상태로 갈 수 없는 상태를 모두 제거한다
  - 남은 그래프에서 사이클이 존재하면 그 언어는 무한(Infinite)하다. 사이클이 없다면 유한(Finite)하다

동등성 문제 서로 다르게 생긴 두 표현 $L_{1}, L_{2}$ 가 실제로 같은 언어를 나타내는가? ( $L_{1} = L_{2}$ ?)

판별 방법: 두 언어의 대칭 차집합(Symmetric Difference)이 공집합인지 확인한다
단계별 과정:
- $L_{1}$ 과 $L_{2}$ 를 각각 DFA로 변환한다
- 다음 식에 해당하는 언어 $L_{d i ff}$ 를 구성한다
  
  $(L_{1} - L_{2}) \cup (L_{2} - L_{1}) = \emptyset$
- 이 $L_{d i ff}$ 가 위에서 언급한 공백 판정(Emptiness Test)을 통과하여 비어 있음이 확인되면, 두 언어는 동일하다
두 DFA를 최소화(Minimization)한 후, 상태의 구조가 완전히 일치(Isomorphic)하는지 확인하는 방법도 있다

타이의 노트

Explorer

[계산이론및오토마타] 4 정규 문법 (Regular Grammars, RG)

정규 문법 (Regular Grammars)

정규 표현식 유도 예시

문법과 오토마타의 상호 변환

정규 언어의 기본 폐쇄 성질

동형 사상(Homomorphism)

Right-Quotient(우측 몫)

교집합 연산과 컨스트럭티브 증명

정규 언어의 표준 표현 (Standard Representation, SR)

정규 언어에 대한 주요 판정 문제

Graph View

Table of Contents