Regular Languages

상위 문서: 계산 이론 개론

개요

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

Definition of Regular Languages

어떤 언어 R이 정규 언어(regular language) 라고 불리려면, 어떤 유한 오토마타(FA) M이 R을 인식해야 한다. 이는 아래와 같다:

[math]\displaystyle{ \exists M. M = FA \land M\,\, recognizes\,\,R }[/math]

이때 이를 증명하기 위해서는 아래와 같은 절차를 걸친다:

1. 특정한 FA [math]\displaystyle{ M=(Q,\Sigma,\delta,q_0,F) }[/math]를 정의한다.
2. M이 FA임을 보인다.(이는 M이 FA의 정의에 맞게 잘 구성되었는지를 확인하는 방식이다.)
3. 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]임을 보일 수 있다.

파일:Figure 1. Proof of 3(a).png

Figure 1. Proof of 3(a)

Figure 1, 2는 각각 3(a), 3(b)를 증명하는 과정이다. 먼저, figure 1은 아래와 같은 과정을 설명하는 fitch-stlye 증명이다:

1. 목표) [math]\displaystyle{ \forall w \in \Sigma^*.(w\in R\Rightarrow M \,\,accepts\,\,w) }[/math]
2. [math]\displaystyle{ w \in \Sigma^* }[/math]이고, [math]\displaystyle{ w \in R }[/math]이라고 가정.
   • 상태열 [math]\displaystyle{ r_0,r_1, \cdots, r_n }[/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]임을 입증

3. 파일:Figure 2. Proof of 3(b).png

   Figure 2. Proof of 3(b)

   따라서 M이 [math]\displaystyle{ w }[/math]를 수용한다.

Figure 2는 아래와 같은 과정을 설명하는 fitch-stlye 증명이다:

1. 목표) [math]\displaystyle{ \forall w \in \Sigma^*.(M \,\,accepts\,\,w\Rightarrow w\in R) }[/math]
2. [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]임을 입증
3. (귀납법을 통해) [math]\displaystyle{ r_n \Rightarrow F }[/math]일 때, 곧 [math]\displaystyle{ w\in R }[/math]임을 보인다.

귀납법을 이용해 [math]\displaystyle{ r_n \in F }[/math]임을 입증

Example Problem

[math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]