Regular Languages

상위 문서: 계산 이론 개론

개요

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

Definition of Regular Languages

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

$\mathrm{\exists }M.M=FA\wedge MrecognizesR$

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

1. 특정한 FA $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$를 정의한다.
2. M이 FA임을 보인다.(이는 M이 FA의 정의에 맞게 잘 구성되었는지를 확인하는 방식이다.)
3. M이 언어 R을 인식(recognize)하는 것을 보인다. 즉,
   • a) 모든 문자열 $w\in {\mathrm{\Sigma }}^{*}$에 대해, $w\in R\Rightarrow M$이 $w$를 수용(accept)
   • b) 모든 문자열 $w\in {\mathrm{\Sigma }}^{*}$에 대해, M이 $w$를 수용 $\Rightarrow w\in R$
   • (a), (b)를 모두 만족해야 정확히 $L(M)=R$임을 보일 수 있다.

Figure 1. Proof of 3(a)

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

1. 목표) $\mathrm{\forall }w\in {\mathrm{\Sigma }}^{*}.(w\in R\Rightarrow Macceptsw)$
2. $w\in {\mathrm{\Sigma }}^{*}$이고, $w\in R$이라고 가정.
   • 상태열 $r_0,r_1,\cdots ,r_n$을 정의:
     $r_0=q_0$
     $r_{i+1}=\delta (r_i,w_{i+1}),i=0,1,\cdots ,n-1$
   • 귀납법을 이용해 $r_n\in F$임을 입증

3. 

   Figure 2. Proof of 3(b)

   따라서 M이 $w$를 수용한다.

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

1. 목표) $\mathrm{\forall }w\in {\mathrm{\Sigma }}^{*}.(Macceptsw\Rightarrow w\in R)$
2. $w\in {\mathrm{\Sigma }}^{*}$와, $Macceptsw$를 가정.
   • 상태열 $r_0,r_1,\cdots ,r_n$을 얻는(obtain)다. 이때 상태열 $r$는 아래와 같다:
     $r_0=q_0$
     $r_{i+1}=\delta (r_i,w_{i+1}),i=0,1,\cdots ,n-1$
   • 이로부터 $r_n\in F$임을 입증
3. (귀납법을 통해) $r_n\Rightarrow F$일 때, 곧 $w\in R$임을 보인다.

귀납법을 이용해 $r_n\in F$임을 입증

Example Problem

위에 대해 이해하기 위해, figure 3를 참고하여 아래와 같은 문제를 풀어보자:

Consider the example FA,
$M=(\{Q_1,Q_2\},\{0,1\},\delta ,Q_1,\{Q_1\}),$
where $\delta$ is given by the transition diagram figure 3.
Let $L=\{w\in \{0,1{\}}^{*}.whasanevennumberof{0}^{\prime }s\}$
Show: The language recognized by $M$ is $L$.

이를 해결하기 위한 핵심적인 아이디어는 모든 정수 $n\ge 0$에 대해 아래와 같은 명제 P(n)을 만드들고 증명하는 것이다:

P(n): For all $w=w_1{w}_2\cdots w_n$과 $r=r_1{r}_2\cdots r_n$에 대해: 
* $r_0=Q_1$
* $r_{i+1}=\delta \{r_i,w_{i+1}\}$
을 만족할 때, $r_n\in \{Q_1\}\leftrightarrow w$에 포함된 0의 개수가 짝수

즉, “길이 n짜리 문자열을 처리했을 때, Q1에 도달하는 것 ↔ 0의 개수가 짝수”이라는 명제를 모든 n에 대해 성립함을 보이면 된다. 먼저, base case를 먼저 보자:

• n = 0이면 입력이 빈 문자열이므로, 상태열은 $r_0=Q_1$이다.
• 이때 0의 개수는 0개이므로, 짝수개이다. 따라서 P(0)는 성립한다.

이제 귀납단계는 아래와 같다.

• P(n)이 임의의 자연수 n에 대해 성립한다고 가정하자.
  • 길이 n+1인 문자열 $w_1{w}_2\cdots w_n{w}_{n+1}$에 대해 P(n+1)이 성립함을 보여야 한다.
  • 경우를 나누어 분석
    • $r_n\in Q_1,w_{n+1}=0\to r_{n+1}=Q_2.$ 따라서 0의 개수가 홀수
    • $r_n\in Q_1,w_{n+1}=1\to r_{n+1}=Q_1.$ 따라서 0의 개수가 짝수
    • $r_n\in Q_2,w_{n+1}=0\to r_{n+1}=Q_1.$ 따라서 0의 개수가 짝수
    • $r_n\in Q_2,w_{n+1}=1\to r_{n+1}=Q_2.$ 따라서 0의 개수가 홀수
  • 따라서 모든 경우에서 $r_{n+1}\in Q_1$이면 0의 개수가 짝수이다.

The Regular Operations

정규 연산(The Regular Operations)은 정규 언어를 다루는 기본적인 세가지 연산이다. 이는 아래와 같다:

• Union: $A\cup B=\{x|x\in A\vee x\in B\}$
  즉, 언어 A 또는 언어 B 중 하나에 속하는 모든 문자열을 의미한다.
• Concatenation: $A\circ B$$=\{xy|x\in \wedge y\in B\}$
  즉, A에서 하나 고르고 B에서 하나 골라 앞뒤로 붙인 문자열을 의미한다.
• Kleene Star: $A*=\{x_1{x}_2\cdots x_k|k\ge 0,x_i\in A\}$
  즉, A의 원소들을 0번 이상 반복해서 이어붙인 문자열들의 집합을 의미한다.

이 세 연산들 만으로 정규 언어 전체를 기술할 수 있다. ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$