Regular Languages

상위 문서: Finite Automata

개요

해당 문서에서는 유한 오토마타(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) 이어붙인 결과"라고 할 수 있다.

Theorem for Kleene Star

Kleene Star에 대한 중요한 정리가 존재한다:

$A*\circ A\subseteq A*$

즉, $A*$의 원소 하나와 A의 원소 하나를 이어붙여도 여전히 $A*$ 안에 포함된다. NFA를 이용한 증명은 해당 문서를 참조하십시오.

Theorem for Union

정규 언어의 합집합(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)”라는 집합에 대한 성질이다. 이 정리는 알파벳이 고정되어 있지 않아도 항상 성립한다. 즉, 정규 언어들은 서로 합집합을 취해도 여전히 정규 언어라는 사실을 보장한다.

이를 증명하는 것은 아래와 같은 과정을 필요로 한다:

1. $A_1,A_2$를 임의의 정규 언어라 하자.
2. $A_1,A_2$가 정규 언어이므로, 이를 인식하는 유한 오토마타(FA) $M_1,M_2$가 존재한다.
3. 이 두 오토마타를 기반으로 새로운 오토마타 $M$을 정의한다.
4. M이 정확히 $A_1\cup A_2$를 인식한다는 것을 보인다. 증명 완료!

따라서, 우리가 해야하는 것은 두 오토마타를 합쳐서 새로운 오토마타 $M$을 설계하는 방법이다. 이를 위한 아이디어는, $M_1,M_2$를 병렬로 동시에 돌리는 것이다. 이는 입력 문자열을 같은 속도로 읽으면서, 두 오토마타를 동시에 시뮬레이션하는 것이며, 둘 중 하나라도 accept 상태에 도달하면 최종적으로 accept하는 오토마타이다. 이는 형식적으로 아래와 같이 설계된다:

• $M_1=(\mathrm{\Sigma },Q_1,{\delta }_1,q_1,F_1)$
• $M_2=(\mathrm{\Sigma },Q_2,{\delta }_2,q_2,F_2)$
• $M_1=(\mathrm{\Sigma },Q_1\times Q_2,\delta ,(q_1,q_2),F)$

즉, $M$의 상태는 "$M_1$의 상태와 $M_2$의 쌍"으로 구성된다. 이를 위한 전이 함수와 Accept 조건은 아래와 같이 설정된다:

$\delta ((r_1,r_2),a)=({\delta }_1(r_1,a),{\delta }_2(r_2,a))$
$F=\{(r_1,r_2)|r_1\in F_1\vee r_2\in F_2\}$

하지만 단순히 $M$을 정의하는 것 만으로는 부족하며, 실제로 $Mrecognizes{A}_1\cup A_2$를 증명해야 한다. 따라서 아래의 명제를 증명해야 한다.

$\mathrm{\forall }w\in \mathrm{\Sigma }*.(Macceptsw\leftrightarrow w\in A_1\cup A_2)$

• Only if 방향의 증명
  1. 가정: $Macceptsw$
  2. (1)에서 $w$를 처리한 후의 최종 상태는 $(r_{n,1},r_{n,2})$
  3. 이는 $r_{n,1}\in F_1$이거나 $r_{n,2}\in F_2$라는 뜻이다. 따라서:
     • $r_{n,1}\in F_1$이면, $M_{1}acceptsw\to w\in A_1$
     • $r_{n,2}\in F_2$이면, $M_{2}acceptsw\to w\in A_2$
  4. 결론: $w\in A_1\cup A_2$
• If 방향의 증명
  1. 가정: $w\in A_1\cup A_2$
     • Case 1: $w\in A_1$
       1. $M_{1}acceptsw$
       2. $M$의 첫 성분 $r_{n,1}\in F_1$
       3. 따라서 $(r_{n,1},r_{n,2})\in F$, 즉 $Macceptsw$
     • Case 2: $w\in A_2$
       1. 대칭적인 논리로 $M_{2}acceptsw$
       2. 그러면 $r_{n,2}\in F_2$, 따라서 $Macceptsw$

최종적으로, $M$이 정의되었고, $Mrecognizes{A}_1\cup A_2$를 보였다. 따라서 $A_1\cup A_2$도 정규 언어이다. 즉, 정규 언어들은 합집합 연산에 대해 닫혀있음이 증명된다.

NFA를 이용한 증명은 해당 문서를 참조하십시오.

Theorem for Concatenation

정규 언어의 집합은 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$ 역시 정규 언어이다.

이를 증명할 때, 정규언어의 합집합에 대한 정리의 증명과 같이 증명할 수 있을까? 이를 위해, concatenation의 정의가 $A\circ B=\{xy|x\in \wedge y\in B\}$이므로, 우리가 만들어야 하는 것은 $M_1,M_2$를 이용해서 $A_1\circ A_2$를 인식하는 새로운 오토마톤 $M$을 만드는 것이다. 이를 위한 직관적인 아이디어는 먼저 $M_1$을 돌려서 문자열의 앞부분 $x_1$을 읽고, 그 뒤에 $M_2$을 돌려서 문자열의 앞부분 $x_2$를 처리하는 것이다. 하지만 이를 적용할때 $x_1$과 $x_2$의 경계를 나누는 기준이 불명확하다는 문제가 있다. 따라서 Deterministic하게는 이 경계 인식을 구현하기가 어렵다.

이를 해결하기 위해서는 두 가지 방식이 있다.

1. 모든 가능한 분할 지점을 동시에 고려
   • 즉, 입력 문자열의 모든 위치를 "여기서 $x_1$이 끝나고 $x_2$가 시작할 수 있다"고 가정하고 병렬적으로 시도한다.
   • 하지만 이는 DFA(Deterministic Finite Automata) 수준에서 명시적으로 구현하기는 매우 복잡하다.
2. Lucky Guess (행운의 추측): 우리가 마치 "여기서 $x_1$이 끝났어" 라고 딱 맞게 추측을 하고, 그 지점부터 $M_2$를 실행하는 방식이다. 추측이 맞으면 정규 언어에 속하고, 틀리면 속하지 않는다.
   • 이는 NFA(Nondeterministic Finite Automata)의 핵심적인 아이디어이며, 이를 이용하는 것이 더욱 간단하다.

NFA를 이용한 증명은 해당 문서를 참조하십시오.

Regular Expressions

자세한 내용은 Regular Expressions 문서를 참조하십시오.

The Pumping Lemma

DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:

L이 정규언어라면, 어떤 펌핑 길이 p가 존재한다.(p는 DFA의 상태의 개수이다.)
이때 길이가 p 이상인 모든 문자열은 세 부분 x, y, z로 분해할 수 있으며, 아래 조건을 만족한다.
1. $\mathrm{\forall }i\ge 0.x{y}^{i}z\in L$
2. $|y|>0$
3. $|xy|\le p$

이를 논리식으로 나타내면 아래와 같다:

$\mathrm{\forall }Lregular\to$
$\mathrm{\exists }p.\mathrm{\forall }w.w\in L\wedge |w|\ge p\to$
$\mathrm{\exists }xyz.w=xyz\wedge (1)\wedge (2)\wedge (3)$

먼저, 1번 조건은 y 부분을 0번, 1번, 2번… 아무 번이든 반복해도 여전히 언어 L에 속해야 한다는 것을 의미한다. 예를 들어 $i=0$일때 $xz$, $i=1$일때 $xyz$, $i=2$일때 $xyyz$ 등등이 모두 L에 속해야 한다는 것이다.
또한 2번 조건은 반복 부분 y의 길이는 0이 아니며, 반드시 실제로 반복되는 구간이 존재해야 한다는 뜻이다.
마지막으로 3번째 조건은 반복되는 부분 y는 문자열의 처음 부분 p 이내에 존재해야 한다는 것이다. 즉, 반복(pumping)되는 부분은 문자열의 앞부분에 있다. 이는 DFA가 구조적으로 상태가 p개만 존재하기 때문에, 길이가 p 이상이면 반드시 어떤 상태가 다시 반복되기 때문이다.

Pumping Lemma를 다른 말로 표현하면, $L\subseteq \{1\}*$이 정규 언어라면 $L$의 문자열 길이들의 집합은 등차수열을 포함한다는 것이다.

Applying the Pumping Lemma

이는 어떤 언어가 정규언어는 아니라는 것을 보이는 데에 사용된다. 예를 들어, 아래와 같은 언어를 고려하자:

$B=\{0^n{1}^n|n\ge 0\}$

B가 정규 언어라고 가정하면, 아래와 같이 B가 정규 언어가 아님을 보일 수 있다:

1. Pumping Lemma에 따라 어떤 길이 p가 존재한다.
2. $w=0^p{1}^p$로 선택한다.(길이가 $\ge p$)
3. 이때 B는 정규언어이므로, 조건에 따라 $w=xyz$로 분해된다.
4. 이때 $|xy|\le p$이므로, y는 반드시 0으로만 구성된다. $0<k\le p.y=0^k$
5. 이때 $x=0^{p-k},1^p$이므로, pumping lemma에 따라 이때 $x{y}^{0}z=0^{p-k}{1}^p$도 B에 속해야 한다.
6. 하지만 0과 1의 개수가 다르므로 $x{y}^{0}z=0^{p-k}{1}^p$는 B에 속하지 않고, 모순이 발생한다.

위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.

Using Other Facts with the PL

Pumping Lemma를 직접 적용하기 전에, 정규언어에 대한 다른 성질(closure property) 을 함께 이용하면 증명이 쉬워진다. 아래와 같은 언어가 비정규 언어라는 것을 증명해보자:

$L=\{w\in \{0,1,2\}*|\mathrm{\#}0(w)+\mathrm{\#}(1)=\mathrm{\#}(2)\}$

위 언어는 자열 안의 0과 1의 개수의 합이 2의 개수와 같아야 하는 언어이다. 위 언어가 비정규임을 보이기 위해, L이 정규라고 가정하자. 또한 정규언어는 교집합에 대해 닫혀 있음(closure under intersection)을 이용하면, 아래와 같은 언어 또한 정규 언어이다:

$L\cap 0*1*2*=\{0^m{1}^n{2}^{m+n}|m\ge 0,n\ge 0\}$

이때 pumping lemma를 위 교집합 언어에 적용해보자:

• 펌핑 길이를 p라고 하고, $w=0^p{0}^p{2}^p$를 선택한다.
• PL에 따라 $|xy|\le p$이므로 $y$는 오직 0으로만 이루어 져야 한다.($y=0^k$)
• 따라서 $x{y}^{0}z=0^{p-k}{1}^p{2}^{2p}$가 되어야 하는데, 이는 $L\cap 0*1*2*$에 속하지 않는다.