형식언어와 오토마타.02.02

• 비결정적 오토마타
  • 결정적 오토마타와의 비교
  • 비결정적 인식기의 정의
  • 확장 전이 함수
    • w를 갖는 walk의 길이 구하기
  • nfa가 accept하는 언어
• 왜 비결정적 머신을 연구하는가?
  • 탐색-백트랙 알고리즘의 모델
  • 비결정성을 쓰면 쉽게 풀리는 문제들이 있다
  • 복잡한 언어를 간단하게 정의할 때 효과적이다
  • nfa와 dfa 사이에 근본적인 차이가 없다

• 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)로 정의한다.

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

참고: dfa의 정의

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

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

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

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

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

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

확장 전이 함수

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

• \(\delta^*(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)\)도 없다.
• \(\lambda\) 입력을 받는 경우가 있다.
  • 따라서 이 전이 그래프는 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)의 길이가 얼마나 길어질 수 있는지 계산할 수 있다.

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

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

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

1. 정점 \(v_i\)에서 출발하면서, 길이가 \(\Lambda + ( 1 + \Lambda ) \times \vert w \vert\) 이하인 보행을 모두 찾는다.
2. 찾아낸 보행들 중에서 라벨이 w인 보행을 골라낸다.
3. 골라낸 보행들의 승인 정점들이 \(\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.

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

다음 전이 그래프를 보자.

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

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

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

• \(\delta^*(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)의 정의 자체가 비결정적 요소를 포함하고 있다.
• 예를 들어 다음 생성규칙을 보자.

• 어느 단계에서건 \(aSb\) 또는 \(\lambda\)를 선택할 수 있다.
  • 딱 이 두 개의 규칙만으로도 수많은 다양한 문자열을 규정할 수 있는 것이다.

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

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