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

비결정적 오토마타

결정적 오토마타와의 비교

If you examine the automata we have seen so far, you will notice a common feature: a unique transition is defined for each state and each input symbol. In the formal definition, this is expressed by saying that δ is a total function. This is the reason we call these automata deterministic. We now complicate matters by giving some automata choices in some situations where more than one transition is possible. We will call such automata nondeterministic.

  • 지금까지 공부한 오토마타의 공통적인 특징
    • 특정 상태에서 특정 입력 문자가 있으면 딱 한 가지 상태로만 전이가 된다.
      • 상태, 입력이 똑같으면 결과도 똑같다.
      • 공식 정의에서 가 total function 이라고 한 게 이걸 말하는 것이다.
    • 이 특징 때문에 결정적(deterministic) 오토마타라 부른다.
  • 이제 하나 이상의 상태로 전이 가능한 오토마타를 공부할 것이다.
    • 이런 오토마타를 비결정적(nondeterministic) 오토마타라 부른다.

비결정적 인식기의 정의

Nondeterministic finite accepter, nfa

Nondeterminism means a choice of moves for an automaton. Rather than prescribing a unique move in each situation, we allow a set of possible moves. Formally, we achieve this by defining the transition function so that its range is a set of possible states.

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

DEFINITION 2.4
A nondeterministic finite accepter or nfa is defined by the quintuple
,
where are defined as for deterministic finite accepters, but
.

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

이 때, 결정적 유한 인식기(dfa)와 똑같이 정의한다.

참고: dfa의 정의

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

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

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

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

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

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

image

확장 전이 함수

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

  • .
    • 상태일 때 문자열 w 가 입력되면…
  • .
    • 가능한 다음 상태들의 집합

DEFINITION 2.5
For an nfa, the extended transition function is defined so that contains if and only if there is a walk in the transition graph from to labeled . This holds for all , and .

  • 전이 그래프(transition graph)에서 에서 로 가는 문자열 가 존재한다면…
    • 가 포함된다.
      • 을 실행한 결과로 출력되는 집합에 가 포함된다는 말로 생각하자.

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

image

  • 가 없다.
  • 도 없다.
  • 입력을 받는 경우가 있다.
    • 따라서 이 전이 그래프는 nfa를 나타낸 것이다.

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

전이 함수 는 없지만, 확장 전이 함수 는 있다는 것을 알 수 있다.

이유는 다음과 같다.

  • a를 한 번 써서 에서 으로 가기
    • .
  • a를 한 번 써서 에서 로 가기
    • .
  • a를 한 번 써서 에서 로 가기
    • .

w를 갖는 walk의 길이 구하기

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

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

  • : 그래프 내의 간선의 개수.
  • 문자열 w의 길이.

이를 이용하면 를 알아내는 방법을 다음과 같이 정리할 수 있다.

  1. 정점 에서 출발하면서, 길이가 이하인 보행을 모두 찾는다.
  2. 찾아낸 보행들 중에서 라벨이 w인 보행을 골라낸다.
  3. 골라낸 보행들의 승인 정점들이 의 원소이다.

nfa가 accept하는 언어

DEFINITION 2.6
The language L accepted by an nfa is defined as the set of all strings accepted in the above sense. Formally,

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.

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

다음 전이 그래프를 보자.

image

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

  • 이므로 승인된다.

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

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

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

Why Nondeterminism?

In reasoning about nondeterministic machines, we should be quite cautious in using intuitive notions. Intuition can easily lead us astray, and we must be able to give precise arguments to substantiate our conclusions. Nondeterminism is a difficult concept. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state. Thus it is natural to ask why we study nondeterministic machines at all. We are trying to model real systems, so why include such non-mechanical features as choice? We can answer this question in various ways.

  • 디지털 컴퓨터는 완벽히 결정적이다.
    • 초기 상태와 입력만 알고 있으면 디지털 컴퓨터의 상태는 언제나 예측 가능하다.
    • 그렇다면 비결정적인 기능을 왜 추가하려 하는가?

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

Many deterministic algorithms require that one make a choice at some stage. A typical example is a game-playing program. Frequently, the best move is not known, but can be found using an exhaustive search with backtracking. When several alternatives are possible, we choose one and follow it until it becomes clear whether or not it was best. If not, we retreat to the last decision point and explore the other choices. A nondeterministic algorithm that can make the best choice would be able to solve the problem without backtracking, but a deterministic one can simulate nondeterminism with some extra work. For this reason, nondeterministic machines can serve as models of search-and-backtrack algorithms.

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

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

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

Nondeterminism is sometimes helpful in solving problems easily. Look at the nfa in Figure 2.8. It is clear that there is a choice to be made. The first alternative leads to the acceptance of the string , while the second accepts all strings with an even number of a’s. The language accepted by the nfa is . While it is possible to find a dfa for this language, the nondeterminism is quite natural. The language is the union of two quite different sets, and the nondeterminism lets us decide at the outset which case we want. The deterministic solution is not as obviously related to the definition, and so is a little harder to find. As we go on, we will see other and more convincing examples of the usefulness of nondeterminism.

  • 예를 들어 다음 nfa를 보자.

image

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

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

In the same vein, nondeterminism is an effective mechanism for describing some complicated languages concisely. Notice that the definition of a grammar involves a nondeterministic element. In

we can at any point choose either the first or the second production. This lets us specify many different strings using only two rules.

이유 2와 같은 맥락.

  • 문법(grammar)의 정의 자체가 비결정적 요소를 포함하고 있다.
  • 예를 들어 다음 생성규칙을 보자.
  • 어느 단계에서건 또는 를 선택할 수 있다.
    • 딱 이 두 개의 규칙만으로도 수많은 다양한 문자열을 규정할 수 있는 것이다.

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

Finally, there is a technical reason for introducing nondeterminism. As we will see, certain theoretical results are more easily established for nfa’s than for dfa’s. Our next major result indicates that there is no essential difference between these two types of automata. Consequently, allowing nondeterminism often simplifies formal arguments without affecting the generality of the conclusion.

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