[계산이론] #02. DFA & NFA

저번 글에서 보았던 Finite Automaton의 예시를 몇 개 보면서 Automaton의 수학적 표시에 대한 이해를 조금 더 하고 넘어가도록 하겠습니다.

 

홀수개의 1을 포함하는 문자열

홀수개의 1을 포함하고 있는 Binary String(0과 1로만 이루어진 문자열)의 집합을 $A$라고 할 때, Language $A$가 Regular라는 사실을 증명하고 싶다고 생각해 봅시다. Language $A$가 Regular라는 것은, $A$에 속하는 모든 문자열만을 Accept 하는 Automata $M$이 존재한다는 뜻이라고 했었죠? 다시 말해 $A=L\left(M\right)$을 만족하는 Automaton $M$이 존재함을 증명하면, $A$가 Regular 하다는 것을 증명할 수 있습니다.

가장 간단하게 생각해서 아래와 같은 Machine을 떠올릴 수 있는데요.

가장 먼저 떠오르는 전략

1을 입력받으면 앞으로 한칸씩 이동하고, 0을 입력받으면 그 상태로 멈추어 있는 Machine입니다. 이러면 $i$개의 1을 입력받았을 때의 State가 $q_i$가 되므로, $i$가 홀수인 $q_i$들을 Accept State로 두면 저희가 원하는 조건을 모두 충족합니다.

하지만 위 Machine은 한가지 문제점이 있는데요, 바로 유한하지 않다는 것입니다. 저희가 이때까지 다루어왔던 모든 Machine들은 유한했습니다. 그래서 Finite Automaton이라고 불렀던 것이고요. 당연히 $M=\left ( Q, \Sigma ,\delta ,q,F \right )$과 같은 수학적 표현으로도 나타낼 수 없습니다.

그러면 아래와 같이 한번 해볼까요?

위의 Automaton과 유사하게 동작하는 유한한 Automaton

이 Automaton도 위의 무한한 Automaton과 비슷하게 동작하는데요, 차이점이라면 이 Automaton은 State가 단 2개로 유한합니다. $q_e$ 상태는 1을 짝수개 입력받았다는 것을 의미하며 (e는 짝수의 even에서 따온 것입니다.) $q_o$ 상태는 1을 홀수개 입력받았다는 것을 의미합니다. (역시 o는 홀수의 odd에서 따온 것입니다.)

이 Automaton을 수학적 표현으로 바꾸면 아래와 같습니다.

• $Q=\left\{q_e, q_o \right\}$
• $\Sigma =\left\{0, 1 \right\} $
• $q=q_e$
• $F=\left\{q_o \right\}$
• $\delta$는 아래의 표로 나타낼 수 있습니다.

위 Finite Automaton의 Transition Function

 

그럼 이제 $A=L\left(M\right)$를 만족하는 $M$이 생겼으니 $A$는 Regular하다고 말할 수 있을까요? 엄밀히 말하면 아닙니다. 우리는 직관적으로 위에 그려진 Automaton을 보고 "이 Automaton은 홀수개의 1을 가진 문자열만 Accept 하는구나"라고 추론할 수는 있지만, 이것이 $A=L\left(M\right)$임의 엄밀한 증명은 아니기 때문입니다.

수학적으로 $A=L\left(M\right)$를 증명하기 위해서는 조금 더 복잡한 과정이 필요합니다. 명제 $ P\left ( n \right )$을 아래와 같이 정의해보겠습니다.

길이가 $n$인 모든 문자열 $w$에 대하여

$$\bar{\delta}\left ( q_e, w \right )=\begin{cases}
q_e\quad if\; w\; contains\; even\; number\; of\; 1\\
q_o\quad if\; w\; contains\; odd\; number\; of\; 1
\end{cases}$$

위 식을 한글로 풀어보자면, Start State인 $q_e$에서 문자열 $w$를 입력받았을 때 $w$가 짝수개의 1을 가지고 있다면 최종 상태는 $q_e$이고 $w$가 홀수개의 1을 가지고 있다면 최종 상태는 $q_o$가 된다는 것을 의미합니다.

그리고 이제 Induction(수학적 귀납법)을 사용해 모든 자연수 $n$에 대해 $P\left ( n \right )$이 성립함을 보일 건데요, 그러면 자연스럽게 1을 홀수개 포함하는 어떤 문자열을 입력받았더라도 이 Automaton의 상태는 $q_o$임을 의미하므로 $A=L\left(M\right)$을 증명했다고 할 수 있겠죠. 따라서, $A$가 Regular Language임을 수학적으로 증명할 수 있게 됩니다.

 

먼저 Base Case, $n=0$일 경우를 봅시다. $n=0$은 곧 $w$는 빈 문자열임을 의미하므로, $\bar{\delta}\left ( q_e, w \right )=q_e$임을 알 수 있습니다. 빈 문자열은 짝수개의 1을 포함하므로, $P\left ( 0 \right )$는 항상 참입니다.

이제 Induction Step, $P\left ( n \right )$이 참이라는 가정 하에 $P\left ( n+1 \right )$이 참임을 보이면 됩니다. 설명을 위해 길이가 $n$인 임의의 문자열을 $v$, 그리고 $v$뒤에 임의의 알파벳 $a$를 붙여 길이가 $n+1$인 문자열 $w$를 만들었다고 생각하겠습니다.

만약 $v$가 짝수개의 1을 포함한다면, $P\left ( n \right )$에 의해 $\bar{\delta}\left ( q_e, v \right )=q_e$입니다. $P\left ( n \right )$을 참이라고 가정했으니깐요. $a=0$일 경우 $\bar{\delta}\left ( q_e, w \right )=q_e$이며 $w$는 여전히 짝수개의 1을 포함하므로 조건에 부합합니다. $a=1$일 경우 $\bar{\delta}\left ( q_e, w \right )=q_o$이며 $w$는 짝수개의 1을 포함하는 $v$에 1이 하나 더 추가된 꼴이고, 이는 $w$는 홀수개의 1을 포함한다는 사실을 의미하므로 역시 조건에 부합합니다.

만약 $v$가 홀수개의 1을 포함한다면, $P\left ( n \right )$에 의해 $\bar{\delta}\left ( q_e, v \right )=q_o$입니다. $a=0$일 경우 $\bar{\delta}\left ( q_e, w \right )=q_o$이며 $w$는 여전히 홀수개의 1을 포함하므로 조건에 부합합니다. $a=1$일 경우 $\bar{\delta}\left ( q_e, w \right )=q_e$이며 $w$는 홀수개의 1을 포함하는 $v$에 1이 하나 더 추가된 꼴이고, 이는 $w$는 짝수개의 1을 포함한다는 사실을 의미하므로 역시 조건에 부합합니다.

(혹시 설명이 이해가 안 되시면 전 글의 마지막 부분에 있는 Extended Transition Function의 정의와 함께 찬찬히 읽어보시는 것을 추천드립니다.)

이렇게 Induction을 사용하여 모든 자연수 $n$에 대해 $ P\left ( n \right )$이 성립한다는 사실을 보일 수 있으므로, 제가 제시했던 Automaton $M$은 $A=L\left(M\right)$를 만족하고, 이를 통해 $A$는 Regular Language임을 증명할 수 있었습니다.

 

101을 포함하는 문자열

이번에는 조금 다른 예시로, "101"이라는 문자열을 포함하는 Binary String의 집합을 $A$라고 생각해 보겠습니다. 비슷한 방법으로, $A$가 Regular Language라는 사실을 한번 보여보겠습니다. 역시 $A=L\left(M\right)$을 만족하는 Automaton $M$을 찾아봐야겠죠?

IDEA

기본적인 아이디어는 위와 같습니다. 1, 0, 1을 순서대로 입력받으면 Accept State인 $q_{101}$에 도달할 수 있고, 그렇지 않으면 도달할 수 없는 그런 Automaton입니다. 위 그림에서도 대충의 아이디어는 얻을 수 있지만, 빠져있는 경우들이 조금 있으므로 ($q_1$에서 1을 입력받는다던가 등..) 화살표를 조금 더 채워주도록 하겠습니다.

101을 포함하는 문자열만 Accept하는 Automaton

그림을 조금 쳐다보고 있으면 이 Machine이 저희가 찾던 Automaton이라는 사실을 확인하실 수 있을 겁니다. 수학적 표현으로 나타내보면 아래와 같습니다.

• $Q=\left\{q, q_1, q_{10}, q_{101} \right\}$
• $\Sigma =\left\{0, 1 \right\} $
• $q=q$
• $F=\left\{q_{101} \right\}$
• $\delta$는 아래의 표로 나타낼 수 있습니다.

위 Finite Automaton의 Transition Function

 

이 경우 역시 Induction을 이용한 엄밀한 증명을 거쳐야 $A=L\left(M\right)$가 성립함을 보일 수 있으나.. 제가 귀찮은 관계로 하지 않도록 하겠습니다.

혹시나 증명을 해보실 분들은 위와 똑같이 명제 $ P\left ( n \right )$을 정의하여

• $q_1$인 경우 마지막 입력값이 1이지만 101은 아직 입력받지 않은 상태
• $q_{10}$인 경우 마지막 두 입력값이 10이지만 101은 아직 입력받지 않은 상태
• $q_{101}$인 경우 101을 한 번이라도 입력받은 상태
• $q$의 경우 그 외의 모든 상태

임을 Induction을 통해 증명하면 $A=L\left(M\right)$에 대한 엄밀한 증명을 완성할 수 있습니다. 방법은 위의 예시와 완벽하게 동일합니다. 경우의 수를 하나하나 나누어서 $ P\left ( n+1 \right )$이 성립함을 보이면 됩니다.

 

Regular Operations

같은 Alphabet에 대한 두 Language $A$와 $B$가 있다고 생각합시다. 이 두 Language에 대해서 Regular Operations라 불리는 3가지 연산자가 있는데요, Union / Concatenation / Star입니다.

$$A\cup B=\left\{w:w\in A\; or\; w\in B \right\}$$
$$AB=\left\{ww':w\in A\; and\; w'\in B \right\}$$
$$A^{*} =\left\{u_1 u_2 \cdots u_k:u_i \in A \; for\; all \; i=1, 2,\cdots k \right\}$$

식으로 봤을 때 살짝 복잡해 보이니 예시를 한번 보겠습니다. $A=\left\{0, 01 \right\},\quad B=\left\{1, 10 \right\}$ 이렇게 2개의 Language를 봅시다.

먼저 Union, $A\cup B$의 경우는 단순히 두 Language를 합친 $\left\{0, 01, 1, 10 \right\}$이 됩니다. Concatenation은 $A$에서 문자열 하나, $B$에서 문자열 하나를 골라 합친 문자열들의 집합입니다. 적어보자면 $\left\{01, 010, 011, 0110 \right\}$입니다. 마지막으로 Star는 $A$에 존재하는 문자열을 쭉 나열해 만들 수 있는 모든 문자열의 집합입니다. 물론 빈 문자열 $\epsilon$ 역시 포함됩니다. 나머지 2개와 다르게 $A^{*}$는 무한집합이지만 몇 개만 예시로 적어보면 $\left\{\epsilon, 0, 01, 00, 001, 010, 0101, 000, \cdots \right\}$ 정도가 있겠네요.

우리가 이 3개의 Operation을 Regular Operation이라고 부르는 이유는 단순합니다. 바로 A와 B가 Regular일 경우, 이 Operation들을 이용해 만들어진 $A\cup B, AB, A^{*}$등의 Langugae 역시 Regular이기 때문입니다. 우리는 이를 보고, Regular Language는 Regular Operation에 대해 닫쳐 있다고 표현하죠.

 

왜 Regular Language는 Union에 대해 닫쳐 있는가?

이제 $A$, $B$가 Regular Language일 때, $A\cup B$ 역시 Regular Language임을 한번 증명해 보겠습니다.

먼저 $A$, $B$가 Regular Language이므로 이 둘에 해당하는 두 Automata $M_1$과 $M_2$가 존재합니다. 이 두 Automata를 $M_1=\left\{Q_1, \Sigma, \delta_1, q_1, F_1 \right\},\; M_2=\left\{Q_2, \Sigma, \delta_2, q_2, F_2 \right\}$와 같이 정의합시다. 그럼 이제 $A\cup B$에 해당하는 Automata $M=\left\{Q, \Sigma, \delta, q, F \right\}$를 찾는 것을 목표로 한번 해봅시다.

아이디어 자체는 꽤나 간단합니다. $M_1$과 $M_2$를 동시에 돌리는 것과 같은 효과를 내도록 $M$을 설계하는 것인데요. 예를 들어 어떤 문자열 $w$를 받았을 때 $M_1$이 $r_a$, $M_2$가 $r_b$ 상태가 된다고 하면, $M$에는 $\left(r_a, r_b\right)$라는 상태를 만드는 것입니다. 그리고 $M$은 $w$를 입력받았을 때 $\left(r_a, r_b\right)$가 되는 것이죠.

이렇게 동작하는 Automata $M$을 수학적 표현으로 나타내면 아래와 같습니다.

• $Q=Q_1 \times Q_2$
• $q=\left(q_1, q_2\right)$
• $F=\left\{\left ( r_1, r_2 \right ):r_1\in F_1\; or \; r_2 \in F_2 \right\}=\left ( F_1\times Q_2 \right )\cup \left ( Q_1 \times F_2 \right )$
• $\delta\left (\left ( r_1, r_2 \right ), a  \right )=\left ( \delta_1 \left ( r_1, a \right ),\delta_2 \left ( r_2, a \right ) \right )$

 

이렇게 $M$을 정의하게 되면 $A\cup B$에 대응되는 Machine이 존재하는 것이므로 $A\cup B$가 Regular Language임을 증명할 수 있습니다. 수학적 표현이 조금 어려워 보이기는 하는데, 위쪽에 한글로 설명해 둔 부분과 함께 차근차근 보시면 이해가 될 것입니다.

 

왜 Regular Language는 Concatenation, Star에 대해 닫쳐 있는가?

Union에 대해 Regular Language가 닫쳐 있음을 보였으니 이제 $A$, $B$가 Regular Language일 때, $AB$ 역시 Regular Language임을 한번 증명해 봐야겠죠?

하지만 쉽지 않습니다. 왜냐? 새로운 Automata $M$은 두 문자열 $w, w'$을 합친 $ww'$를 입력받을 텐데, $M$ 입장에서는 이 문자열이 어디까지 $w$이고 어디서부터 $w'$인지 알 방법이 전혀 없기 때문이죠. 이에 대한 증명을 위해서는 이때까지 저희가 봐왔던 Automata와는 다른 새로운 종류의 Automata가 필요합니다.

 

Nondeterministic Finite Automata (NFA)

저희가 지금까지 봐왔던 Finite Automata는 전부 Deterministic Finite Automata(DFA)였습니다. 이제부터 저희는 Nondeterministic Finite Automata(NFA)에 대해 알아볼 건데요,

NFA의 예시

이것이 NFA의 예시인데요, 이때까지 보던 것이랑 뭔가 많이 다르죠? 하나하나 알아봅시다.

먼저 $q_1$을 보면, 이 상태에서 0을 입력받으면 그대로 상태가 유지된다는 건 알겠는데 1이라고 적힌 화살표가 2개나 있죠? 이는 $q_1$ 상태에서 1을 입력받으면 $q_1$이 될 수도 있고, $q_2$가 될 수도 있다는 의미입니다.

그리고 $q_2$에서는 $\epsilon$이 있는데, 이것은 아무 문자를 입력받지 않아도 $q_3$ 상태로 넘어올 수 있다는 뜻입니다. 예를 들어 초기 상태인 $q_1$ 에서 "1"을 입력받으면 $q_1$일 수도 있고, $q_2$일 수도 있고, $q_3$일 수도 있는 것입니다. 게다가, $q_2$에서는 1이 적힌 화살표가 나가고 있지 않죠? 이 말은 $q_3$ 상태에서 1을 입력받으면 더 이상 진행할 수 없다는 것을 의미합니다. 이렇게 더 이상 진행할 수 없는 상태에 도달했을 때 이 상태를 Hang이라고 부릅니다.

보시면 알 수 있듯 NFA는 하나의 문자열을 입력받아도 최종 State가 여러 가지가 될 수 있습니다. 예를 들어 010110을 입력받았다고 생각하면, 아래 7가지 경우의 수가 가능합니다.

위 NFA가 010110을 입력받았을 때 가능한 모든 경우의 수

여기서 7개의 경우의 수 중 Accept State인 것은 단 2개밖에 없는데요, 그럼에도 우리는 이 NFA가 010110을 Accept 한다고 말합니다. 일반화시켜서 말하면, 어떤 문자열을 입력했을 때 모든 경우의 수 중 하나의 경우의 수라도 Accept State에 도달한다면 그 문자열을 Accept 한다고 합니다.

 

여러 NFA의 예시

마지막 3번째 문자가 1인 Binary String(1111111, 000100, 0101 등)만을 Accept 하는 NFA는 아래와 같습니다.

마지막 3번째 문자가 1인 문자열만을 Accept 하는 NFA

$q_4$가 Accept State이기 때문에 어떤 문자열이 Accept 되려면 마지막 문자를 입력받기 직전에 $q_3$여야 하고, 그러면 마지막 2번째 문자를 입력받기 전에 $q_2$여야 하고, 마지막 3번째 문자를 입력받기 전에 $q_1$이어야 하기 때문에 마지막 3번째 문자가 1인 문자열만 Accept 하는 것입니다.

또 다른 예시로, Alphabet이 0만으로 이루어진 문자열에서, 0의 개수가 짝수 개이거나 3의 배수 개인 문자열만을 Accept 하는 NFA를 보겠습니다.

0의 개수가 짝수이거나 3의 배수인 문자열만을 Accept 하는 NFA

이 NFA는 2개의 DFA를 합쳐놓은 형태인데요, Starting State에서 위쪽에 있는 DFA로 이동하느냐 아래쪽에 있는 DFA로 이동하느냐에 따라 0의 개수가 짝수인지를 감지할지, 3의 배수인지를 감지할지가 결정됩니다. 이를 우리는 NFA가 어떤 DFA를 사용할지 추측한다고 표현합니다.

 

NFA의 수학적 표현

NFA 역시 DFA처럼 수학적 표현으로 나타낼 수 있습니다.

$$M=\left ( Q, \Sigma ,\delta ,q,F \right )$$

• $Q$는 유한집합으로, 이 Machine에 존재하는 모든 State의 집합입니다. (DFA와 동일)
• $\Sigma$는 Alphabet이라고 불리는 유한집합으로, 이 Machine이 한 턴에 입력받을 수 있는 모든 문자의 집합입니다. 이 집합의 원소를 우리는 Sybmols라고 부릅니다. (DFA와 동일)
• $\delta$는 Transition Function이라고 불리는 $Q\times \Sigma_{\epsilon}\to P\left ( Q \right )$ 함수로, 현재 State와 입력받은 Symbol을 입력받아 다음 State로 가능한 것들의 집합을 출력하는 함수입니다. ($\Sigma_{\epsilon}$은 $\Sigma \cup \left\{\epsilon \right\}$을 의미합니다.)
• $q$는 $Q$의 원소 중 Start State인 것을 위미 합니다. (DFA와 동일)
• $F$는 $Q$의 부분집합으로, 모든 Accept State를 원소로 가집니다. (DFA와 동일)

 

Transition Function을 빼고는 전부 DFA와 동일한데요, DFA에서의 Transition Function은 상태 하나와 문자 하나를 입력받아 그다음 상태를 출력하는 함수였다면 NFA에서는 상태 하나와 문자 하나를 입력받아 그 다음 상태로 가능한 상태 전부를 출력하는 함수라고 생각하시면 됩니다.

이해를 위해 처음으로 봤던 NFA와 그 Transition Function은 아래와 같습니다.

NFA와 그 Transition Function

 

NFA와 DFA의 관계

언뜻 보면 NFA가 DFA보다 훨씬 많은 Langauge를 Accept 할 수 있는 것처럼 보이는데요, 사실은 그렇지 않습니다. NFA에 의해 Accept 되는 Languge는 DFA에 의해 Accept될 수 있으며, 그 반대로 DFA에 의해 Accept되는 Language는 NFA에 의해도 Accept 될 수 있습니다.

사실, 모든 NFA와 DFA는 근본적으로 같습니다. 어떤 NFA를 가져오더라도 이 NFA와 정확히 같은 Langauge를 Accept 하는 DFA를 만들 수 있고, 그 반대도 마찬가지입니다.

먼저 DFA가 있을 때 이에 대응되는 NFA를 만드는 건 따로 설명을 하지 않아도 당연히 가능한 부분입니다. 복잡한 건 NFA가 주어졌을 때 이에 대응되는 DFA를 만드는 과정입니다. 수학적인 표현으로, 주어진 NFA를 $N=\left ( Q, \Sigma ,\delta ,q,F \right )$이라고 할 때, $L\left ( M \right )=L\left ( N \right )$을 만족하는 DFA $M$을 한번 찾아보겠습니다.

먼저 아이디어 자체는 이렇습니다. $N$이 어떤 문자열을 받았을 때 도달할 가능성이 있는 State가 $r_1, r_2, r_4$ 라고 가정해 봅시다. 그러면 $\left\{r_1, r_2, r_4 \right\}$ 자체를 $M$의 하나의 State로 보는 것입니다. 

NFA

이런 NFA를 $N$이라고 하고 이에 대응되는 DFA $M$을 만들고 싶다고 가정합시다.

$q_1$에서 시작해서 0을 입력받았다고 가정해봅시다. 그러면 0을 입력받은 이후 이 NFA는 $q_1$ 상태일 수도, $q_2$ 상태일수도 있습니다. 그러면 $M$에 $\left\{q_1, q_2 \right\}$라는 State를 만들어서, $\left\{q_1 \right\}$에서 0을 입력하면 $\left\{q_1, q_2 \right\}$가 되도록 설계하는 것입니다.

이런 식으로 $M$을 만들면 아래와 같습니다.

위 NFA를 DFA로 변환한 것

이 DFA는 위에 있는 NFA와 완벽하게 같은 Lanauge를 Accpet 합니다. 이런 방식을 이용해서 NFA를 DFA로 변환할 수 있습니다. 이를 조금 더 일반화해서 수학적 표현으로 나타내보겠습니다.

새로운 DFA $M$을 $\left ( Q', \Sigma, \delta', q', F' \right )$라고 정의하면,

• $Q'=P\left (Q  \right )$
• $q'=\left\{q \right\} $
• $F'=\left\{R\in Q': R\cap F\neq \phi  \right\}$
• $\delta'=Q' \times \Sigma \to Q',\quad \delta'\left ( R, a \right )=\bigcup_{r\in R}^{}\delta\left ( r, a \right )$

 

다시, Regular Operation으로

정리하자면, 우리는 NFA라는 것에 대해서 알아보았고 어떤 NFA를 만들더라도 이 NFA와 같은 Language만을 Accept 하는 DFA를 만들 수 있다는 사실까지 증명해 보았습니다. 따라서, 만약 어떤 Lanauge를 Accept하는 NFA가 있다면, 이 Lanauge를 Accept하는 DFA 역시 존재하므로 이 Lanauge는 Regular Language라고 할 수 있겠죠.

아까 같은 Alphabet에 대한 두 Lanauge $A$와 $B$가 Regular일 때 $A \cup B$도 Regular라는 사실을 증명하기 위해 $A \cup B$를 Accept 하는 DFA가 존재함을 보였었습니다. 이제 저희는 NFA를 배웠으니, $A \cup B$를 Accept하는 NFA가 존재함을 보여도, Lanauge $A \cup B$가 Regular함을 보일 수 있습니다. (그 NFA는 DFA로 변환 가능하니깐요.)

이런 방식으로 $A \cup B$가 Regular임을 증명하는 것은 아까에 비해 아주아주 쉽습니다.

위의 그림과 같이 $A$를 Accept하는 DFA $M_1$과 $B$를 Accept하는 DFA $M_2$가 있다고 생각해 보겠습니다.

이때 이렇게 NFA $M$을 잡아주면, 이 $M$은 $A \cup B$를 Accept 하므로 $A \cup B$가 Regular임을 바로 증명할 수 있습니다. 이런 방식을 사용하면 아까는 불가능했던 $AB$가 Regular 함의 증명도 가능합니다.

위의 그림과 같이 $A$를 Accept 하는 DFA $M_1$과 $B$를 Accept하는 DFA $M_2$가 있다고 생각해 보겠습니다. 이때, 우리는 이 둘을 합친 $AB$의 Regular 함을 보이고 싶은 것이므로, 아래와 같이 NFA $M$을 잡아줍니다.

그러면 이 NFA는 Lanaguage $AB$를 Accept 하므로, $AB$가 Regular임을 증명할 수 있습니다. 마지막으로 $A^{*}$의 Regular 함도 한번 보여보겠습니다.

위의 그림과 같이 $A$를 Accept 하는 DFA $N$이 있다고 생각해 보겠습니다. $A^{*}$의 Regular 함을 보이기 위해, 아래와 같은 NFA $M$을 한번 잡아보겠습니다.

이 NFA $M$은 $A^{*}$를 Accept 하므로, $A^{*}$가 Regular 함을 증명할 수 있습니다.

이렇게 NFA를 이용하여 Regular Language는 Union, Concatenation, Star 이 3개의 Regular Operation들에 의해 닫쳐있다는 사실을 증명할 수 있었습니다.

 

마무리

이렇게 이번 글에서는 새로운 Automata의 종류인 NFA에 대해 알아보았고, 이 NFA와 DFA는 서로 변환 가능하며 이를 통해서 Regular Operation의 성질까지 증명할 수 있음을 알아보았습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.