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) 이어붙인 결과"라고 할 수 있다.

===Theorem for Kleene Star===
Kleene Star에 대한 중요한 정리가 존재한다:
 <math>A*\circ A \subseteq A*</math>
즉, <math>A*</math>의 원소 하나와 A의 원소 하나를 이어붙여도 여전히 <math>A*</math> 안에 포함된다. [[Nondeterministic Finite Automata#Proof for Closure|NFA를 이용한 증명]]은 해당 문서를 참조하십시오.

===Theorem for Union===
정규 언어의 합집합(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)”라는 집합에 대한 성질이다. 이 정리는 알파벳이 고정되어 있지 않아도 항상 성립한다. 즉, 정규 언어들은 서로 합집합을 취해도 여전히 정규 언어라는 사실을 보장한다.

이를 증명하는 것은 아래와 같은 과정을 필요로 한다:
# <math>A_1,\,\, A_2</math>를 임의의 정규 언어라 하자.
# <math>A_1,\,\, A_2</math>가 정규 언어이므로, 이를 인식하는 유한 오토마타(FA) <math>M_1, M_2</math>가 존재한다.
# 이 두 오토마타를 기반으로 새로운 오토마타 <math>M</math>을 정의한다.
# M이 정확히 <math>A_1 \cup A_2</math>를 인식한다는 것을 보인다. 증명 완료!
따라서, 우리가 해야하는 것은 두 오토마타를 합쳐서 새로운 오토마타 <math>M</math>을 설계하는 방법이다. 이를 위한 아이디어는, <math>M_1,\,\, M_2</math>를 병렬로 동시에 돌리는 것이다. 이는 입력 문자열을 같은 속도로 읽으면서, 두 오토마타를 동시에 시뮬레이션하는 것이며, 둘 중 하나라도 accept 상태에 도달하면 최종적으로 accept하는 오토마타이다. 이는 형식적으로 아래와 같이 설계된다:
* <math>M_1 = (\Sigma, Q_1, \delta_1, q_1, F_1)</math>
* <math>M_2 = (\Sigma, Q_2, \delta_2, q_2, F_2)</math>
* <math>M_1 = (\Sigma, Q_1 \times Q_2, \delta, (q_1,q_2), F)</math>
즉, <math>M</math>의 상태는 "<math>M_1</math>의 상태와 <math>M_2</math>의 쌍"으로 구성된다. 이를 위한 전이 함수와 Accept 조건은 아래와 같이 설정된다:
 <math>\delta((r_1, r_2), a)=(\delta_1(r_1,a),\delta_2(r_2, a))</math><ref>이는 입력 a를 읽을 때, 각각의 오토마타가 이동한 결과를 쌍으로 저장하는 함수이다.</ref>
 <math>F = \{(r_1, r_2)|r_1\in F_1 \lor r_2\in F_2\}</math><ref>이는 둘 중 하나라도 accept 상태이면 M이 accept한다는 의미이다.</ref>
하지만 단순히 <math>M</math>을 정의하는 것 만으로는 부족하며, 실제로 <math>M\,\, recognizes\,\, A_1\cup A_2</math>를 증명해야 한다. 따라서 아래의 명제를 증명해야 한다.
 <math>\forall w \in \Sigma*.\,\, (M\,\, accepts\,\, w\leftrightarrow w \in A_1 \cup A_2)</math>
* Only if 방향의 증명
*# 가정: <math>M\,\, accepts\,\, w</math>
*# (1)에서 <math>w</math>를 처리한 후의 최종 상태는 <math>(r_{n, 1}, r_{n,2})</math><ref><math>r_{n, 1}</math>는 n번째 문자까지 읽었을 때, 오토마톤 <math>M_1</math>의 상태를 의미한다.</ref>
*# 이는 <math>r_{n,1} \in F_1</math>이거나 <math>r_{n,2}\in F_2</math>라는 뜻이다. 따라서:
*#* <math>r_{n,1}\in F_1</math>이면, <math>M_1\,\, accepts\,\, w \rightarrow w\in A_1</math>
*#* <math>r_{n,2}\in F_2</math>이면, <math>M_2\,\, accepts\,\, w \rightarrow w\in A_2</math>
*# 결론: <math>w \in A_1 \cup A_2</math>
* If 방향의 증명
*# 가정: <math>w\in A_1 \cup A_2</math>
*#* Case 1: <math>w \in A_1</math>
*#*# <math>M_1\,\, accepts\,\, w </math>
*#*# <math>M</math>의 첫 성분 <math>r_{n,1}\in F_1</math>
*#*# 따라서 <math>(r_{n,1},r_{n,2})\in F</math>, 즉 <math>M\,\, accepts\,\, w</math>
*#* Case 2: <math>w \in A_2</math>
*#*# 대칭적인 논리로 <math>M_2\,\, accepts\,\, w </math>
*#*# 그러면 <math>r_{n,2}\in F_2</math>, 따라서 <math>M\,\, accepts\,\, w</math>
최종적으로, <math>M</math>이 정의되었고, <math>M\,\, recognizes\,\, A_1 \cup A_2</math>를 보였다. 따라서 <math>A_1 \cup A_2</math>도 정규 언어이다. 즉, 정규 언어들은 합집합 연산에 대해 닫혀있음이 증명된다.

[[Nondeterministic Finite Automata#Proof for Closure|NFA를 이용한 증명]]은 해당 문서를 참조하십시오.

===Theorem for Concatenation===
정규 언어의 집합은 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> 역시 정규 언어이다. 

이를 증명할 때, 정규언어의 합집합에 대한 정리의 증명과 같이 증명할 수 있을까? 이를 위해, concatenation의 정의가 <math>A \circ B = \{xy|x\in \land y\in B\}</math>이므로, 우리가 만들어야 하는 것은 <math>M_1,\,\, M_2</math>를 이용해서 <math>A_1\circ A_2</math>를 인식하는 새로운 오토마톤 <math>M</math>을 만드는 것이다. 이를 위한 직관적인 아이디어는 먼저 <math>M_1</math>을 돌려서 문자열의 앞부분 <math>x_1</math>을 읽고, 그 뒤에 <math>M_2</math>을 돌려서 문자열의 앞부분 <math>x_2</math>를 처리하는 것이다. 하지만 이를 적용할때 <math>x_1</math>과 <math>x_2</math>의 경계를 나누는 기준이 불명확하다는 문제가 있다. 따라서 Deterministic하게는 이 경계 인식을 구현하기가 어렵다.

이를 해결하기 위해서는 두 가지 방식이 있다. 
# 모든 가능한 분할 지점을 동시에 고려
#* 즉, 입력 문자열의 모든 위치를 "여기서 <math>x_1</math>이 끝나고 <math>x_2</math>가 시작할 수 있다"고 가정하고 병렬적으로 시도한다. 
#* 하지만 이는 DFA(Deterministic Finite Automata) 수준에서 명시적으로 구현하기는 매우 복잡하다.
# Lucky Guess (행운의 추측): 우리가 마치 "여기서 <math>x_1</math>이 끝났어" 라고 딱 맞게 추측을 하고, 그 지점부터 <math>M_2</math>를 실행하는 방식이다. 추측이 맞으면 정규 언어에 속하고, 틀리면 속하지 않는다.
#* 이는 [[Nondeterministic Finite Automata|NFA(Nondeterministic Finite Automata)]]의 핵심적인 아이디어이며, 이를 이용하는 것이 더욱 간단하다. 
[[Nondeterministic Finite Automata#Proof for Closure|NFA를 이용한 증명]]은 해당 문서를 참조하십시오.

==각주==