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의 원소를 이어붙인 문자열만을 포함하는 집합이다.
  • 더욱 엄밀히 기술하면, $A\circ B=\{w|\mathrm{\exists }x,y.w=xy\wedge x\in A\wedge y\in B\}$
• Kleene Star: $A*=\{x_1{x}_2\cdots x_k|k\ge 0,x_i\in A\}$
  • 즉, A의 원소들을 0번 이상 반복해서 이어붙인 문자열들의 집합을 의미한다.
  • 더욱 엄밀히 기술하면 $A*=\bigcup _{i\ge 0}{A}^i$이며, 이는 $A^0,A^1,A^2,...$ 전부 합친 집합이다. 이때,
    $A^0=\{ϵ\}$
    $A^{i+1}=A^i\circ A$(귀납적으로 정의됨 → i번 이어붙인 것에 추가로 A를 붙인 것)
  • 따라서 $A*$는 "A를 반복적으로(concatenation) 이어붙인 결과"라고 할 수 있다.

이 세 연산들 만으로 정규 언어 전체를 기술할 수 있다. 이때 kleene star에 대한 중요한 정리가 존재한다:

$A*\circ A\subseteq A*$

즉, $A*$의 원소 하나와 A의 원소 하나를 이어붙여도 여전히 $A*$ 안에 포함된다. 또한, 정규 언어의 합집합(union)에 대한 폐쇄성(closure)에 대한 정리가 존재한다.

$\mathrm{\forall }{A}_1,A_2.(A_{1}regular\wedge A_{2}regular)\Rightarrow (A_1\cup A_{2}regular)$

즉, 두 정규 언어 $A_1{A}_2$가 있으면 $A_1\cup A_2$도 정규 언어라는 의미이다. 이때 중요한 것은 앞에서 다룬 $A*$에 대한 정리는 "한 언어 안에서"의 성질이지만, 위의 정리는 “정규 언어 전체(class)”라는 집합에 대한 성질이다. 이 정리는 알파벳이 고정되어 있지 않아도 항상 성립한다. 즉, 정규 언어들은 서로 합집합을 취해도 여전히 정규 언어라는 사실을 보장한다.
이 외에도, 정규 언어의 집합은 Concatenation(연접) 연산에 대해 닫혀 있다. 이는 아래와 같이 표현된다:

$\mathrm{\forall }{A}_1,A_2.(A_{1}regular\wedge A_{2}regular)\Rightarrow (A_1\circ A_{2}regular)$

이는 두 정규 언어 $A_1,A_2$가 있으면 $A_1$에 속하는 문자열과 $A_2$에 속하는 문자열을 붙여 만든 새로운 언어 $A_1\circ A_2$ 역시 정규 언어이다. ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$