형식언어와 오토마타.02.02

비결정적 오토마타
왜 비결정적 머신을 연구하는가?

CHAPTER 2. Finite Automata
- 2.1 DETERMINISTIC FINITE ACCEPTERS
- 2.2 NONDETERMINISTIC FINITE ACCEPTERS
챕터 2. 유한 오토마타
- 2.1 결정적 유한 인식기
- 2.2 비결정적 유한 인식기

비결정적 오토마타

결정적 오토마타와의 비교

결정적(deterministic) 오토마타의 특징

특정 상태에서 특정 입력 문자가 있으면 딱 한 가지 상태로만 전이가 된다.
- 상태, 입력이 똑같으면 결과도 똑같다.
- 공식 정의에서 $\delta$ 가 total function 이라고 한 게 이걸 말하는 것이다.

비결정적(nondeterministic) 오토마타

하나 이상의 상태로 전이 가능한 오토마타.

비결정적 인식기의 정의

Nondeterministic finite accepter, nfa

비결정성(Nondeterminism) : 오토마톤이 다음 상태로 이동할 때 선택을 할 수 있음을 의미.
- 가능한 상태 이동의 집합을 허용.
- 전이 함수가 상태들의 집합(a set of possible states)을 치역(range)으로 갖도록 정의하는 방식.

DEFINITION 2.4
A nondeterministic finite accepter or nfa is defined by the quintuple
$M = (Q, Σ, δ, q_0, F)$ ,
where $Q, Σ, q_0, F$ are defined as for deterministic finite accepters, but
$δ : Q \times (Σ \cup \{ λ \}) \rightarrow 2^Q$ .

비결정적 인식기, nfa는 5개 원소를 가진 튜플(quintuple)로 정의한다.

M = (Q, Σ, δ, q_{0}, F)

$M = (Q, Σ, δ, q_0, F)$

이 때, $Q, Σ, q_0, F$ 는 결정적 유한 인식기(dfa)와 똑같이 정의한다.

참고: dfa의 정의

$Q$ 는 dfa가 가질 수 있는 모든 상태의 유한집합.
- $q_0$ 는 초기 상태(initial state).
- $F$ 는 최종 상태(final state)의 집합.
$Σ$ 는 입력 가능한 문자열의 유한집합.
- 즉 가능한 input의 집합.
$δ$ 는 상태를 변화시키는 함수라고 생각하자.
- $\delta$ (현재상태, 입력문자) = 다음 상태
- 입력 문자는 문자열이 아니다는 점에 주의. 한 글자만 받는다.
- 예) $δ (q_{0}, a) = q_{1}$
  - dfa가 상태 $q_0$ 이고 입력 문자가 $a$ 이면, 상태가 $q_1$ 으로 바뀐다.

하지만 nfa에서의 $\delta$ 는 dfa와는 달리 다음과 같이 정의한다.

δ : Q \times (Σ \cup {λ}) \to 2^{Q}

$δ : Q \times (Σ \cup \{ λ \}) \rightarrow 2^Q$

그냥 보면 어려우니 조금씩 이해해 보자.

Q
- nfa가 가질 수 있는 모든 상태의 유한집합.
- $q_0$ 는 초기 상태.
- $F$ 는 최종 상태의 집합.
$(Σ \cup {λ})$ .
- 입력 가능한 모든 string( $\Sigma$ )과 길이가 0인 string( $\lambda$ )의 집합.
- $δ$ 함수의 두 번째 인자로 빈 문자열( $λ$ )을 넣을 수 있다는 말.
  - 예) $\delta(q_1, \lambda)$
  - 입력 장치가 문자를 읽지 않아도(!) 상태 전이가 가능함을 의미.
  - dfa에서의 입력 장치는 오른쪽으로만 움직였는데, 이것 덕분에 nfa는 멈춰 있을 수도 있다.
$2^{Q}$ .
- $Q$ 의 멱집합.
- $2^Q =$ 집합 $Q$ 의 모든 부분 집합의 집합.
- nfa에서 $δ$ 함수의 결과는 $Q$ 의 부분 집합이다.
  - 상태집합 $Q$ 의 단일 원소가 아니다.
- $2^{Q}$ 에는 공집합도 포함되어 있다.
  - 정의되지 않은 전이 상태(공집합: 없는 상태)로 갈 수도 있음.

예를 들어, 어떤 nfa가 $q_1$ 상태에서 a를 입력 받았을 때, $q_0, q_2$ 가 다음 상태로 가능하다면 다음과 같이 표현할 수 있다.

δ (q_{1}, a) = {q_{0}, q_{2}}

$\delta(q_1, a) = \{ q_0, q_2 \}$

다음 전이 그래프를 보자. 이 그래프로 표현된 오토마타는 $q_0$ 에서 a를 입력 받았을 때 두 가지 상태로 이동할 수 있으므로 nfa다.

확장 전이 함수

dfa의 확장 전이 함수와 비슷하다.

δ^{*} (q_{i}, w) = Q_{j}

$δ^*(q_i, w) = Q_j$

$δ^{*} (q_{i}, w)$ .
- $q_i$ 상태일 때 문자열 w 가 입력되면…
$Q_{j}$ .
- 가능한 다음 상태들의 집합

DEFINITION 2.5
For an nfa, the extended transition function is defined so that $δ^*(q_i, w)$ contains $q_j$ if and only if there is a walk in the transition graph from $q_i$ to $q_j$ labeled $w$ . This holds for all $q_i, q_j ∈ Q$ , and $w ∈ Σ^*$ .

전이 그래프(transition graph)에서 $q_{i}$ 에서 $q_{j}$ 로 가는 문자열 $w$ 가 존재한다면…
- $δ^{*} (q_{i}, w)$ 에 $q_{j}$ 가 포함된다.
  - $δ^*(q_i, w)$ 을 실행한 결과로 출력되는 집합에 $q_j$ 가 포함된다는 말로 생각하자.

다음 전이 그래프(예제 2.9)를 보자.

$\delta(q_1, a)$ 가 없다.
$\delta(q_2, a)$ 도 없다.
$λ$ 입력을 받는 경우가 있다.
- 따라서 이 전이 그래프는 nfa를 나타낸 것이다.

한편 nfa에서는 $\lambda$ (입력이 없음) 입력으로 전이(상태 변화)가 가능하므로…

전이 함수 $\delta(q_1, a)$ 는 없지만, 확장 전이 함수 $\delta^*(q_1, a) = \{ q_0, q_1, q_2 \}$ 는 있다는 것을 알 수 있다.

이유는 다음과 같다.

a를 한 번 써서 $q_{1}$ 에서 $q_{0}$ 으로 가기
- $\lambda, \lambda, a, \lambda, \lambda$ .
a를 한 번 써서 $q_{1}$ 에서 $q_{1}$ 로 가기
- $\lambda, \lambda, a$ .
a를 한 번 써서 $q_{1}$ 에서 $q_{2}$ 로 가기
- $\lambda, \lambda, a, \lambda$ .

w를 갖는 walk의 길이 구하기

문자열 w에 대해서 보행(walk)의 길이가 얼마나 길어질 수 있는지 계산할 수 있다.

다음 공식을 사용하면 보행의 길이의 최대값을 계산할 수 있다.

Λ + (1 + Λ) \times | w |

$\Lambda + ( 1 + \Lambda ) \times \vert w \vert$

$\Lambda$ : 그래프 내의 $\lambda$ 간선의 개수.
$\vert w \vert$ 문자열 w의 길이.

이를 이용하면 $\delta^*(q_i, w)$ 를 알아내는 방법을 다음과 같이 정리할 수 있다.

정점 $v_i$ 에서 출발하면서, 길이가 $\Lambda + ( 1 + \Lambda ) \times \vert w \vert$ 이하인 보행을 모두 찾는다.
찾아낸 보행들 중에서 라벨이 w인 보행을 골라낸다.
골라낸 보행들의 승인 정점들이 $\delta^*(q_i, w)$ 의 원소이다.

nfa가 accept하는 언어

DEFINITION 2.6
The language L accepted by an nfa $M = (Q, Σ, δ, q_0, F)$ is defined as the set of all strings accepted in the above sense. Formally,
$L (M) = \{w ∈ Σ^* : δ^*(q_0, w) ∩ F ≠ ∅\}.$
In words, the language consists of all strings w for which there is a walk labeled w from the initial vertex of the transition graph to some final vertex.

L (M) = {w \in Σ^{*} : δ^{*} (q_{0}, w) \cap F \neq \emptyset} .

$L (M) = \{w ∈ Σ^* : δ^*(q_0, w) ∩ F ≠ ∅\}.$

$δ^{*} (q_{0}, w) \cap F \neq \emptyset$ .
- $q_0$ 에 문자열 w를 입력했을 때 나올 수 있는 결과 중에, 최종 상태가 있어야 한다.
- 즉, w 문자열로 그래프의 초기 정점에서 승인 정점까지 보행이 가능해야 한다.

다음 전이 그래프를 보자.

문자열 "10"은 이 언어에서 승인되는가?

$\delta^*(q_0, 10) = \{ q_0 \}$ 이므로 승인된다.

문자열 "110"은 이 언어에서 승인되는가?

$δ^{*} (q_{0}, 110) = \emptyset$ 이므로 승인되지 않는다.
- $q_2$ 에서 갈 곳이 없게 된다.
- 입력에 따른 전이가 정의되지 않았기 때문.
- 이런 상황을 종말 형상(dead configuration)이라 한다.
- 하지만 이런 상태에서 오토마톤이 "멈추는" 것은 아니다. 그것은 알 수 없으며, 말 할 수 없다.
- 그냥 종말 형상은 결과가 없다고만 생각하도록 하자.

왜 비결정적 머신을 연구하는가?

Why Nondeterminism?

디지털 컴퓨터는 완벽히 결정적이다.
- 초기 상태와 입력만 알고 있으면 디지털 컴퓨터의 상태는 언제나 예측 가능하다.

그렇다면 비결정적인 기능을 왜 추가하려 하는가?

탐색-백트랙 알고리즘의 모델

결정적 알고리즘은 특정 단계에서 "하나"의 선택을 할 수 있어야 한다.
예를 들어, 최적의 이동 경로를 알 수 없는 상황에서 무식하게 백트래킹(backtracking)을 써서 찾아내는 방법이 있다.
- 하나를 확인하고, 결과가 맞지 않으면 마지막 결정 지점으로 돌아오고, 다시 다른 하나를 확인하고.. 를 반복.
비결정적 알고리즘은 백트래킹 없이 최선의 선택을 하도록 할 수 있다.
- 결정적 알고리즘은 몇몇 작업을 해 줘야 비결정적 알고리즘을 모방(simulate)할 수 있다.

그러므로, 비결정적 머신은 search-and-backtrack 알고리즘의 모델이 될 수 있다.

비결정성을 쓰면 쉽게 풀리는 문제들이 있다

예를 들어 다음 nfa를 보자.

이 그래프는 dfa로도 표현이 가능하지만, dfa로는 자연스럽게(쉽게?) 표현하기 어렵다.
이 그래프는 nfa로 보면 심플하다.
- 위쪽 화살표를 타고 가면 문자열 aaa 이 accept 된다(aaa가 accept 된다).
- 아래쪽 화살표를 타고 가면 aa, aaaa, aaaaaa, … 와 같이 짝수 개의 a가 있는 문자열이 accept 된다.
- 그러므로 이 nfa가 accept 하는 언어는 $\{a^3\} ∪ \{a^{2n} : n ≥ 1 \}$ 이다.

복잡한 언어를 간단하게 정의할 때 효과적이다

이유 2와 같은 맥락.

문법(grammar)의 정의 자체가 비결정적 요소를 포함하고 있다.
예를 들어 다음 생성규칙을 보자.

S \to a S b | λ

$S → aSb \vert λ$

어느 단계에서건 $a S b$ 또는 $λ$ 를 선택할 수 있다.
- 딱 이 두 개의 규칙만으로도 수많은 다양한 문자열을 규정할 수 있는 것이다.

nfa와 dfa 사이에 근본적인 차이가 없다

기술적인 이유도 있다.
이론적인 결과를 얻는 데에 있어서는 dfa보다 nfa가 더 쉽다.
다음 챕터의 결론을 보면 nfa와 dfa가 핵심적인 부분에서 차이가 없다는 것을 알 수 있게 된다.
즉, 비결정성을 사용하면 결론의 일반성(generality)에 영향을 끼치지 않고 공식적인 논증(formal arguments)을 심플하게 할 수 있다.