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

1. 정규 문법 (Regular Grammars, RG)

정규 문법 (Regular Grammar)

정규 문법은 정규 언어를 생성하는 생성 규칙(Production Rule)의 집합이다. 변수 전개가 일어나는 방향에 따라 크게 두 가지 형태로 나뉜다

정규 문법의 두 가지 종류

• 우선형 문법 (Right-linear Grammar):
  • 모든 생성 규칙이 $A\to xB$ 또는 $A\to x$ 형태이다
  • (단, $x\in {\Sigma }^{\ast }$ 이며 단말 기호의 문자열을 의미, $A,B$는 변수)
  • 변수가 항상 문자열의 오른쪽 끝에만 나타난다
• 좌선형 문법 (Left-linear Grammar):
  • 모든 생성 규칙이 $A\to Bx$ 또는 $A\to x$ 형태이다
  • 변수가 항상 문자열의 왼쪽 끝에만 나타난다

1.1 정규 표현식 유도 예시

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

• 우선형 예시: $S\to abS\mid a$
  • 유도 과정: $S\Rightarrow abS\Rightarrow ababS\Rightarrow \cdots \Rightarrow (ab{)}^{\ast }a$
• 좌선형 예시: $S\to S_{1}ab,S_1\to S_{1}ab\mid S_2,S_2\to a$
  • 유도 과정: $S\Rightarrow S_{1}ab\Rightarrow (S_{1}ab)ab\Rightarrow \cdots \Rightarrow a(ab{)}^{\ast }$
  • (참고: 유도 방향이 왼쪽에서 오른쪽으로 뻗어나갑니다.)

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

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

우선형 문법 $\to$ DFA 변환 문법의 생성 규칙을 오토마타의 상태 전이 화살표로 바로 바꿀 수 있다

• 규칙: $V_i\to a{V}_j$는 상태 $V_i$에서 입력 $a$를 받아 상태 $V_j$로 가는 전이($\delta (V_i,a)=V_j$)가 된다
• 예시: $V_0\to a{V}_1,V_1\to ab{V}_0\mid b$
  • (생성되는 RE: $a(aba{)}^{\ast }b$)

DFA $\to$ 우선형 문법 변환 DFA의 그래프 구조를 그대로 생성 규칙으로 옮겨 적는다

• 예시 언어: $L(aa{b}^{\ast }a)$

• 각 상태 $q_0,q_1,q_2,q_F$를 문법 변수($V$)로 설정하고 전이에 따라 규칙을 생성한
  • $q_0\to a{q}_1$
  • $q_1\to a{q}_2$
  • $q_2\to b{q}_2\mid a{q}_F$
  • $q_F\to \lambda$ (수락 상태는 $\lambda$ 전이로 종료)

좌선형 문법 변환

우선형 문법은 “상태 $\to$ 입력 $\to$ 다음 상태” 순서로 직관적인 변환이 가능하지만, 좌선형은 최종 상태에서 거꾸로 거슬러 올라가는 역방향 구조이다. 따라서 직접 변환하기보다는, 오토마타를 뒤집은(Reverse) 뒤 우선형으로 구하고 다시 뒤집는 동치 성질을 이용해 변환하는 것이 일반적이다

---

2. 정규 언어의 폐쇄 성질 (Closure Properties)

정규 언어 $L_1,L_2$가 있을 때, 특정 연산을 거쳐 만들어진 새로운 언어 역시 여전히 정규 언어의 범주에 속한다는 수학적 성질이다

연산 종류	기호	설명 및 증명 아이디어
합집합	$L_1\cup L_2$	정규 표현식 $r_1+r_2$ 로 쉽게 표현 가능
결합	$L_1{L}_2$	정규 표현식 $r_1\cdot r_2$ 로 표현 가능
여집합	$\overline{L_1}$	DFA의 수락 상태($F$)와 비수락 상태($Q-F$)를 반전시켜 구성
교집합	$L_1\cap L_2$	1. 드 모르간의 법칙($\overline{\overline{L_1}\cup \overline{L_2}}$) 적용 2. Product Construction ($m\times n$ 상태 교차 곱) 증명
차집합	$L_1-L_2$	$L_1\cap \overline{L_2}$ 와 동일하므로 정규 언어 연산의 조합임
역순	$L^R$	오토마타의 방향을 뒤집고 시작/수락 상태를 교체하면 됨

2.1 동형 사상 (Homomorphism, $h$)

동형 사상

언어에 속한 각각의 단일 알파벳을 특정 문자열로 통째로 치환하는 함수 $h$에 대해, 정규 언어 $L$의 치환 결과 집합인 $h(L)$ 역시 정규 언어이다

• 예시 1 (집합 치환):
  • 설정: $\Sigma =\{a,b\},\Gamma =\{a,b,c\}$
  • 치환 함수: $h(a)=ab,h(b)=bbc$
  • 대상 언어: $L=\{aa,aba\}$
  • 결과: $h(L)=\{h(aa),h(aba)\}=\{abab,abbbcab\}$
• 예시 2 (정규 표현식 치환):
  • 설정: 치환 함수 $h(a)=dbcc,h(b)=bdc$
  • 정규 표현식: $r=(a+b^{\ast })(aa{)}^{\ast }$
  • 결과: $h(r)=(dbcc+(bdc{)}^{\ast })(dbccdbcc{)}^{\ast }$

2.2 우측 몫 (Right-Quotient, $L_1/L_2$)

우측 몫

두 언어 $L_1,L_2$에 대해, $L_1$에 속하는 문자열 중 뒷부분(접미사)이 $L_2$의 패턴과 일치하는 경우, 그 뒷부분을 잘라내고 남은 앞부분들의 집합이다

$L_1/L_2=\{x\mid xy\in L_1\text{ for some }y\in L_2\}$

• 수식 예시:
  • $L_1=\{a^n{b}^m:n\ge 1,m>0\}\cup \{ba\}$
  • $L_2=\{b^m:m\ge 1\}$
  • 결과: $L_1/L_2=\{a^n{b}^m:n\ge 1,m\ge 0\}$ (즉, RE로는 $a{a}^{\ast }{b}^{\ast }$)
• DFA 기반 증명 아이디어: $L_1$을 인식하는 DFA에서, 특정 상태 $q$에서 출발해 $L_2$에 속하는 문자열을 읽고 기존 수락 상태에 도달할 수 있다면, 그 상태 $q$를 새로운 수락 상태로 바꾼. 이렇게 변형된 DFA가 인식하는 언어가 바로 $L_1/L_2$가 된다

2.3 교집합 연산과 Product Construction 증명

정규 언어의 교집합($L_1\cap L_2$)이 정규 언어임을 증명하기 위해 두 DFA를 병렬로 결합한 Product DFA를 구성한다

• 예시 언어: $L_1=a{a}^{\ast },L_2=a{b}^{\ast }$

• 증명 방법:
  • $M_1$의 상태 $q_i$와 $M_2$의 상태 $q_j$를 묶어 새로운 상태 쌍 $(q_i,q_j)$를 만든다
  • 새로운 오토마타의 수락 상태는 두 DFA가 동시에 수락 상태인 경우에만 해당한다
  • 결과적으로 교집합 $L_1\cap L_2=\{a\}$ 만을 인식하는 새로운 DFA가 완성되므로, 교집합 역시 정규 언어임이 증명한다

---

3. 정규 언어의 주요 판정 문제 (Decision Problems)

특정 언어가 정규 언어의 3대 표준 표현(RE, DFA, RG) 중 하나로 주어졌을 때, 컴퓨터(알고리즘)를 통해 다음 질문들에 대한 명확한 답(Yes/No)을 유한 시간 내에 도출할 수 있다

3.1 소속 문제 (Membership Problem: $w\in L$?)

질문: 임의의 문자열 $w$가 언어 $L$에 속하는가?

• 판별 알고리즘: 언어 $L$을 인식하는 DFA를 구성한 뒤, 문자열 $w$를 입력하여 시뮬레이션합니다. 문자열을 다 읽고 난 후 최종 상태가 수락 상태이면 Yes, 아니면 No를 반환한다
• 문자열 길이가 $n$일 때 $O(n)$ 시간에 빠르게 판독 가능하다

3.2 공백 / 유한 / 무한 판정 (Emptiness / Finiteness)

질문: 언어 $L$이 텅 비어있는가? 문자열 개수가 유한한가, 무한한가?

• 공백 판정 ($L=\varnothing$?):
  • DFA의 상태 그래프에서 시작 상태로부터 수락 상태로 도달할 수 있는 경로(Path)가 단 하나라도 존재하는지 확인한다(BFS, DFS 탐색 활용)
  • 경로가 아예 없다면 언어는 공집합이다
• 무한 판정 (Infinite?):
  • 불필요한 상태(시작점에서 도달 불가, 수락점으로 도달 불가)를 다 제거한다
  • 남은 유효한 상태 전이 그래프 내에 사이클(Cycle, 루프)이 존재하는지 확인한다
  • 유효한 경로 상에 루프가 있다면 무한히 많은 문자열 생성이 가능하므로 무한(Infinite), 루프가 하나도 없다면 유한(Finite)한다

3.3 동등성 문제 (Equivalence Problem: $L_1=L_2$?)

질문: 서로 다르게 생긴 두 정규 표현식이나 오토마타 $L_1,L_2$가 실제로는 완전히 같은 언어를 나타내는가?

• 판별 알고리즘 1 (대칭 차집합 이용):
  • 두 언어의 차집합을 결합하여 다음 식 $L_{diff}$를 구성한다
  • $L_{diff}=(L_1-L_2)\cup (L_2-L_1)$
  • 이 $L_{diff}$에 대해 위에서 배운 공백 판정(Emptiness Test)을 실행하여 결과가 $\varnothing$(비어 있음)으로 나오면, 두 언어는 완전히 동일하다
• 판별 알고리즘 2 (최소화 이용):
  • 두 DFA를 각각 최소화(Minimization) 알고리즘을 돌려 가장 작은 형태로 만든다
  • 최소화된 두 DFA의 구조(상태 개수와 전이 화살표)가 완전히 일치(Isomorphic)하는지 비교한다