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===

<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>

==각주==