해당 문서에서는 유한 오토마타(FA)를 통해 검증 가능한 언어를 의미하는 정규 언어에 대해 다룬다.
Definition of Regular Languages
어떤 언어 R이 정규 언어(regular language) 라고 불리려면, 어떤 유한 오토마타(FA) M이 R을 인식해야 한다. 이는 아래와 같다:
[math]\displaystyle{ \exists M. M = FA \land M\,\, recognizes\,\,R }[/math]
이때 이를 증명하기 위해서는 아래와 같은 절차를 걸친다:
특정한 FA [math]\displaystyle{ M=(Q,\Sigma,\delta,q_0,F) }[/math]를 정의한다.
M이 FA임을 보인다.(이는 M이 FA의 정의에 맞게 잘 구성되었는지를 확인하는 방식이다.)
M이 언어 R을 인식(recognize)하는 것을 보인다. 즉,
a) 모든 문자열 [math]\displaystyle{ w\in \Sigma^* }[/math]에 대해, [math]\displaystyle{ w \in R \Rightarrow M }[/math]이 [math]\displaystyle{ w }[/math]를 수용(accept)
b) 모든 문자열 [math]\displaystyle{ w\in \Sigma^* }[/math]에 대해, M이 [math]\displaystyle{ w }[/math]를 수용 [math]\displaystyle{ \Rightarrow w \in R }[/math]
(a), (b)를 모두 만족해야 정확히 [math]\displaystyle{ L(M)=R }[/math][1]임을 보일 수 있다.
목표) [math]\displaystyle{ \forall w \in \Sigma^*.(M \,\,accepts\,\,w\Rightarrow w\in R) }[/math]
[math]\displaystyle{ w \in \Sigma^* }[/math]와, [math]\displaystyle{ M \,\,accepts\,\,w }[/math]를 가정.
상태열 [math]\displaystyle{ r_0,r_1, \cdots, r_n }[/math]을 얻는(obtain)다. 이때 상태열 [math]\displaystyle{ r }[/math]는 아래와 같다: [math]\displaystyle{ r_0=q_0 }[/math] [math]\displaystyle{ r_{i+1}=\delta(r_i, w_{i+1}),i=0,1,\cdots,n-1 }[/math]
이로부터 [math]\displaystyle{ r_n\in F }[/math]임을 입증
(귀납법을 통해) [math]\displaystyle{ r_n \Rightarrow F }[/math]일 때, 곧 [math]\displaystyle{ w\in R }[/math]임을 보인다.
귀납법을 이용해 [math]\displaystyle{ r_n \in F }[/math]임을 입증
Example Problem
위에 대해 이해하기 위해, figure 3를 참고하여 아래와 같은 문제를 풀어보자:
Consider the example FA,
[math]\displaystyle{ M = (\{Q_1, Q_2\}, \{0, 1\}, \delta, Q_1, \{Q_1\}), }[/math]
where [math]\displaystyle{ \delta }[/math] is given by the transition diagram figure 3.
Let [math]\displaystyle{ L = \{w \in \{0,1\}^*. w\,\, has\,\, an\,\, even\,\, number\,\, of\,\, 0's \} }[/math]
Show: The language recognized by [math]\displaystyle{ M }[/math] is [math]\displaystyle{ L }[/math].
이를 해결하기 위한 핵심적인 아이디어는 모든 정수 [math]\displaystyle{ n \ge 0 }[/math]에 대해 아래와 같은 명제 P(n)을 만드들고 증명하는 것이다:
P(n): For all [math]\displaystyle{ w = w_1w_2\cdots w_n }[/math]과 [math]\displaystyle{ r = r_1r_2\cdots r_n }[/math]에 대해:
* [math]\displaystyle{ r_0 = Q_1 }[/math]
* [math]\displaystyle{ r_{i+1}=\delta\{r_i, w_{i+1}\} }[/math]
을 만족할 때, [math]\displaystyle{ r_n \in \{Q_1\} \leftrightarrow w }[/math]에 포함된 0의 개수가 짝수
즉, “길이 n짜리 문자열을 처리했을 때, Q1에 도달하는 것 ↔ 0의 개수가 짝수”이라는 명제를 모든 n에 대해 성립함을 보이면 된다. 먼저, base case를 먼저 보자:
n = 0이면 입력이 빈 문자열이므로, 상태열은 [math]\displaystyle{ r_0 = Q_1 }[/math]이다.
이때 0의 개수는 0개이므로, 짝수개이다. 따라서 P(0)는 성립한다.
이제 귀납단계는 아래와 같다.
P(n)이 임의의 자연수 n에 대해 성립한다고 가정하자.
길이 n+1인 문자열 [math]\displaystyle{ w_1w_2\cdots w_nw_{n+1} }[/math]에 대해 P(n+1)이 성립함을 보여야 한다.
.png){kind=link}
.png){kind=link}