5주차 1차시

Class

``Class``는 문제의 집합을 말한다. 예를 들어 ``DFA``가 풀 수 있는 문제의 집합은 class이다. 그럼 class의 개수는 몇 개일까?

 

$\sum = \{0, 1\}$일 때 $|\sum^{*}| = |N|$이고, 가능한 모든 문제의 수 $|2^{\sum^{*}}|=|2^{N}|=|R|$이므로 문제의 집합의 수는 $|2^{R}|$이다.

 

설명 가능한 문제의 수가 $|N|$이므로, 설명 가능한 class의 수는 $|2^{N}|$이다.

Class DFA

Class DFA는 ``DFA``로 풀 수 있는 문제의 집합이다. 여기서 헷갈리면 안 된다. 문제는 string의 집합이고, class는 문제의 집합이다. 예를 들어 $\{ 0, 10, 100, \cdots\}$는 ``DFA``가 풀 수 있는 문제이다. 참고로 원소의 수가 유한한 문제는 모두 ``DFA``로 풀 수 있다.

 

다음의 위계질서를 기억하자.

알파벳 - 문자열 - 문제(language) - class

NFA (Nondeterministic Finite Automata)

``NFA``: $M = \{ Q, \sum, q, F, s \}$

• $Q$: 상태의 집합
• $\sum$: 알파벳
• $q$: 초기 상태
• $F$: 최종 상태(문자열을 accpet하는 경우)의 집합
• $s$: 전이함수 $(q, a) \rightarrow r$, $q$는 읽기 전 상태, $a$는 읽은 알파벳, $r$은 전이할 상태

``NFA``가 ``DFA``와 다른 점은, 하나의 $(q, a)$ 쌍에 대해 여러 개의 $r$을 가질 수 있다는 점이다. 심지어 $r$이 없을 수도 있다. 그래서 ``NFA``를 설명할 때 모든 가능성을 동시에 시도한다고도 한다.

Acceptance by NFA

``NFA``는 동일한 입력에 대해 매번 다른 결과를 출력할 수 있다. ``NFA`` $M$이 $x$를 읽었을 때 최소한 하나의 경우에서 최종 상태로 갈 수 있다면 $M$은 $x$를 accept한다. 

 

``DFA``를 다시 생각해 보자. $X_{3} = $ ``입력에 101이 있는가?``는 $L_{3} = \{ 101, 0101, 01010, \cdots\}$이고, $X_{3}$을 푸는 ``DFA``는 다음과 같다.

검은색 화살표가 초기 상태

이제 $X_{3}$을 푸는 ``NFA``를 그려 보자.

끝!

이 ``NFA``는 $101$을 accept한다. 처음 상태에서 계속 머물러 있을 수도 있지만, 오른쪽으로 계속 가면 최종 상태를 만날 수 있기 때문에 ``NFA``는 $101$을 accept한다. 

 

어떤 문자열에 $101$이 없다면 절대로 최종 상태에 도착할 수 있다. 반대로 말하면 최종 상태에 도착한 문자열은 중간에 $101$을 포함하고 있다는 뜻이 되므로 이 ``NFA``는 $X_{3}$을 푼다고 말할 수 있다.

그래서 ``NFA``를 언제 쓰는데?

``NFA``는 시뮬레이션 하기는 어렵지만 생각하기에는 더 쉽다. 또, ``NFA``로 풀 수 있는 문제는 ``DFA``로도 풀 수 있고, 역도 성립한다.

 

위의 ``NFA``를 ``DFA``로 바꿔 보자. ``DFA``는 한 번에 하나의 상태밖에 가질 수 없기 때문에 ``NFA``의 상태가 $n$개일 때 $2^{N}$개의 상태를 가져야 한다. 또한 ``DFA``의 각 상태에서 알파벳을 읽었을 때 갈 수 있는 모든 상태로 가는 전이함수를 생각해야 한다. 예를 들어, 위의 ``NFA``에서 $p$에 있을 때 $1$을 읽으면 $p$ 또는 $q$에 있을 수 있으므로 $(\{p\}, 1) \rightarrow \{p, q\}$이다.

 

``DFA``를 완성하면 다음과 같다. 이 ``DFA``는 위에 있는 ``DFA``와 같다. 

복잡하긴 하지만 이런 방법으로 ``NFA``를 ``DFA``로 바꿀 수 있다.

 

$(Class) ~DFA=NFA$임을 증명할 수도 있다. 

$DFA \subset NFA$

임의의 $L \in DFA$에 대해 $L$을 accept하는 ``DFA`` $M$이 존재한다. 그런데 $M$은 $NFA$이다. 왜냐하면 $DFA$가 $NFA$의 특수한 경우이기 때문이다. 따라서 $L \in NFA$이다.

$NFA \subset DFA$

임의의 $L' \in NFA$에 대해 $L$을 accept하는 ``NFA`` $M'$이 존재한다. 위에서와 같은 방법으로 $M'$을 ``DFA``로 바꿀 수 있다. 따라서 $L'$을 푸는 ``DFA``가 존재하고, $NFA \subset DFA$이다.

 

$DFA \subset NFA$이고 $NFA \subset DFA$이므로 $DFA = NFA$이다.

DPDA (Deterministic Pushdown Automata)

``DPDA``는 ``DFA``, ``NFA``와 Turing machine 사이에 있는 기계이다. Stack을 가진 ``DFA``라고 이해하면 좋다. ``DPDA``는 ``DFA``가 할 수 있는 모든 일을 할 수 있으며, ``DFA``가 하지 못하는 일도 할 수 있다.

 

예를 들어 ``DPDA``는 $L_{5}$를 풀 수 있다.

스택에 $0$을 쌓고, $1$이 나오면 스택에서 $0$을 꺼낸다. 스택이 비어 있는데 입력이 들어오거나, 입력이 끝났을 때 스택이 비어 있지 않다면 그 문자열은 accept되지 않는다. 반대로 $0$과 $1$의 개수가 같다면 이 ``DPDA``는 그 문자열을 accept한다.

 

``DPDA``는 $L_{6} = \{ x ~|~ x~=~y2y^{R},~ y \in \{0, 1\}^{*}\}$을 풀 수 있다. $y^{R}$은 문자열 $y$를 뒤집은 것이다. 예를 들어 $y=0101$이면 $x=010121010$이다. 

푸는 방법

$2$가 나올 때까지 문자를 스택에 넣는다. $2$가 나오지 않으면 accept하지 않는다. $2$를 읽고 난 후 나오는 글자가 스택의 맨 위에 있는 문자와 같으면 스택을 pop한다. 같지 않다면 accept하지 않는다. 입력을 다 읽은 후에 스택이 비어있지 않거나, 스택이 비어 있는데 입력이 끝나지 않는다면 accept하지 않는다. 

이런 것도 풀 수 있을까?

• $L_{7} = \{ x ~|~ x~=~yy^{R},~ y \in \{0, 1\}^{*}\}$

$L_{7}$은 $L_{6}$에서 가운데의 $2$가 없는 형태이다. 문자열을 다 읽기 전에는 어디서 대칭이 되는지 알 수 없으므로 ``DPDA``는 언제 pop을 시작해야 하는지 알 수 없고, 따라서 $L_{7}$을 accept할 수 없다. 하지만 ``NPDA(Nondeterministic Pushdown Automata)``는 $L_{7}$을 풀 수 있다. push에서 pop으로 언제 넘어가야 하는지는 모르지만, 모든 경우를 시도해볼 수 있기 때문이다.

 

따라서 Class $DPDA \ne NPDA$이다. 정확한 증명은 생략한다. $DFA = NFA$이지만 $DPDA \ne NPDA$라는 점을 기억하자.