Regular Languages 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]

상위 문서: [[Finite Automata#Finite Automata as Language Recognizers#Formal Definition of Finite Automaton|계산 이론 개론]]

==개요==
해당 문서에서는 [[Finite Automata|유한 오토마타(FA)]]를 통해 검증 가능한 언어를 의미하는 정규 언어에 대해 다룬다.

==Definition of Regular Languages==
어떤 언어 R이 정규 언어(regular language) 라고 불리려면, 어떤 [[Finite Automata|유한 오토마타(FA)]] M이 R을 인식해야 한다. 이는 아래와 같다:
 <math>\exists M. M = FA \land M\,\, recognizes\,\,R</math>
이때 이를 증명하기 위해서는 아래와 같은 절차를 걸친다:
# 특정한 FA <math>M=(Q,\Sigma,\delta,q_0,F)</math>를 정의한다.
# M이 FA임을 보인다.(이는 M이 FA의 정의에 맞게 잘 구성되었는지를 확인하는 방식이다.)
# M이 언어 R을 인식(recognize)하는 것을 보인다. 즉,
#* a) 모든 문자열 <math>w\in \Sigma^*</math>에 대해, <math>w \in R \Rightarrow M</math>이 <math>w</math>를 수용(accept) 
#* b) 모든 문자열 <math>w\in \Sigma^*</math>에 대해, M이 <math>w</math>를 수용 <math>\Rightarrow w \in R</math>
#* (a), (b)를 모두 만족해야 정확히 <math>L(M)=R</math><ref><math>L(M)</math>은 M이 인식하는 문자열의 집합을 의미한다.</ref>임을 보일 수 있다. 
[[파일:Figure 1. Proof of 3(a).png|섬네일|Figure 1. Proof of 3(a)]]
Figure 1, 2는 각각 3(a), 3(b)를 증명하는 과정이다. 먼저, figure 1은 아래와 같은 과정을 설명하는 fitch-stlye 증명이다:
# 목표) <math>\forall w \in \Sigma^*.(w\in R\Rightarrow M \,\,accepts\,\,w)</math>
# <math>w \in \Sigma^*</math>이고, <math>w \in R</math>이라고 가정.
#* 상태열 <math>r_0,r_1, \cdots, r_n</math>을 정의:<br><math>r_0=q_0</math><br><math>r_{i+1}=\delta(r_i, w_{i+1}),i=0,1,\cdots,n-1</math>
#* 귀납법을 이용해 <math>r_n \in F</math>임을 입증
# [[파일:Figure 2. Proof of 3(b).png|섬네일|Figure 2. Proof of 3(b)]]따라서 M이 <math>w</math>를 수용한다.

Figure 2는 아래와 같은 과정을 설명하는 fitch-stlye 증명이다:
# 목표) <math>\forall w \in \Sigma^*.(M \,\,accepts\,\,w\Rightarrow w\in R)</math>
# <math>w \in \Sigma^*</math>와, <math>M \,\,accepts\,\,w</math>를 가정.
#* 상태열 <math>r_0,r_1, \cdots, r_n</math>을 얻는(obtain)다. 이때 상태열 <math>r</math>는 아래와 같다:<br><math>r_0=q_0</math><br><math>r_{i+1}=\delta(r_i, w_{i+1}),i=0,1,\cdots,n-1</math>
#* 이로부터 <math>r_n\in F</math>임을 입증
# (귀납법을 통해) <math>r_n \Rightarrow F</math>일 때, 곧 <math>w\in R</math>임을 보인다.
귀납법을 이용해 <math>r_n \in F</math>임을 입증

===Example Problem===
위에 대해 이해하기 위해, figure 3를 참고하여 아래와 같은 문제를 풀어보자:
 Consider the example FA,
 <math>M = (\{Q_1, Q_2\}, \{0, 1\}, \delta, Q_1, \{Q_1\}),</math>
 where <math>\delta</math> is given by the transition diagram figure 3.
 Let <math>L = \{w \in \{0,1\}^*. w\,\, has\,\, an\,\, even\,\, number\,\, of\,\, 0's \}</math>
 Show: The language recognized by <math>M</math> is <math>L</math>.
이를 해결하기 위한 핵심적인 아이디어는 모든 정수 <math>n \ge 0</math>에 대해 아래와 같은 명제 P(n)을 만드들고 증명하는 것이다:
 P(n): For all <math>w = w_1w_2\cdots w_n</math>과 <math>r = r_1r_2\cdots r_n</math>에 대해: 
 * <math>r_0 = Q_1</math>
 * <math>r_{i+1}=\delta\{r_i, w_{i+1}\}</math>
 을 만족할 때, <math>r_n \in \{Q_1\} \leftrightarrow w</math>에 포함된 0의 개수가 짝수
즉, “길이 n짜리 문자열을 처리했을 때, Q1에 도달하는 것 ↔ 0의 개수가 짝수”이라는 명제를 모든 n에 대해 성립함을 보이면 된다. 먼저, base case를 먼저 보자:
* n = 0이면 입력이 빈 문자열이므로, 상태열은 <math>r_0 = Q_1</math>이다.
* 이때 0의 개수는 0개이므로, 짝수개이다. 따라서 P(0)는 성립한다.
이제 귀납단계는 아래와 같다.
* P(n)이 임의의 자연수 n에 대해 성립한다고 가정하자.
** 길이 n+1인 문자열 <math>w_1w_2\cdots w_nw_{n+1}</math>에 대해 P(n+1)이 성립함을 보여야 한다. 
** 경우를 나누어 분석
*** <math>r_n \in Q_1, w_{n+1} = 0 \rightarrow r_{n+1} = Q_2.</math> 따라서 0의 개수가 홀수
*** <math>r_n \in Q_1, w_{n+1} = 1 \rightarrow r_{n+1} = Q_1.</math> 따라서 0의 개수가 짝수
*** <math>r_n \in Q_2, w_{n+1} = 0 \rightarrow r_{n+1} = Q_1.</math> 따라서 0의 개수가 짝수
*** <math>r_n \in Q_2, w_{n+1} = 1 \rightarrow r_{n+1} = Q_2.</math> 따라서 0의 개수가 홀수
** 따라서 모든 경우에서 <math>r_{n+1} \in Q_1</math>이면 0의 개수가 짝수이다.

==The Regular Operations==
정규 연산(The Regular Operations)은 정규 언어를 다루는 기본적인 세가지 연산이다. 이는 아래와 같다:
* Union: <math>A \cup B = \{x|x\in A \lor x \in B\} </math>
** 즉, 언어 A 또는 언어 B 중 하나에 속하는 모든 문자열을 의미한다.
* Concatenation: <math>A \circ B = \{xy|x\in \land y\in B\}</math>
** 즉, A의 원소와 B의 원소를 이어붙인 문자열만을 포함하는 집합이다.
** 더욱 엄밀히 기술하면, <math>A \circ B = \{w|\exists x,y. w=xy \land x \in A \and y \in B\}</math>
* Kleene Star: <math>A*=\{x_1x_2\cdots x_k|k\ge 0, x_i \in A\}</math>
** 즉, A의 원소들을 0번 이상 반복해서 이어붙인 문자열들의 집합을 의미한다.
** 더욱 엄밀히 기술하면 <math>A*=\bigcup_{i \ge 0}A^i</math>이며, 이는 <math>A^0, A^1, A^2,...</math> 전부 합친 집합이다. 이때,<br><math>A^0=\{\epsilon\}</math><br><math>A^{i+1}=A^i\circ A</math>(귀납적으로 정의됨 → i번 이어붙인 것에 추가로 A를 붙인 것)
** 따라서 <math>A*</math>는 "A를 반복적으로(concatenation) 이어붙인 결과"라고 할 수 있다.
이 세 연산들 만으로 정규 언어 전체를 기술할 수 있다. 이때 kleene star에 대한 중요한 정리가 존재한다:
 <math>A*\circ A \subseteq A*</math>
즉, <math>A*</math>의 원소 하나와 A의 원소 하나를 이어붙여도 여전히 <math>A*</math> 안에 포함된다. 또한, 정규 언어의 합집합(union)에 대한 폐쇄성(closure)에 대한 정리가 존재한다.
 <math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \cup A_2\,\, regular)</math>
즉, 두 정규 언어 <math>A_1\,\, A_2</math>가 있으면 <math>A_1 \cup A_2</math>도 정규 언어라는 의미이다. 이때 중요한 것은 앞에서 다룬 <math>A*</math>에 대한 정리는 "한 언어 안에서"의 성질이지만, 위의 정리는 “정규 언어 전체(class)”라는 집합에 대한 성질이다. 이 정리는 알파벳이 고정되어 있지 않아도 항상 성립한다. 즉, 정규 언어들은 서로 합집합을 취해도 여전히 정규 언어라는 사실을 보장한다.<br>
이 외에도, 정규 언어의 집합은 Concatenation(연접) 연산에 대해 닫혀 있다. 이는 아래와 같이 표현된다:
 <math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \circ A_2\,\, regular)</math>
이는 두 정규 언어 <math>A_1,\,\, A_2</math>가 있으면 <math>A_1</math>에 속하는 문자열과 <math>A_2</math>에 속하는 문자열을 붙여 만든 새로운 언어 <math>A_1 \circ \A_2</math> 역시 정규 언어이다. 
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>

==각주==