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

결정적 유한 인식기와 전이 그래프

결정적 유한 인식기 : A deterministic finite accepter or dfa

DEFINITION 2.1

A deterministic finite accepter or dfa is defined by the quintuple
,
where
is a finite set of internal states,
is a finite set of symbols called the input alphabet,
is a total function called the transition function,
is the initial state,
is a set of final states.

dfa는 5개 원소 튜플(quintuple)로 정의한다.

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

결정적 유한 인식기의 작동법

A deterministic finite accepter operates in the following manner. At the initial time, it is assumed to be in the initial state , with its input mechanism on the leftmost symbol of the input string. During each move of the automaton, the input mechanism advances one position to the right, so each move consumes one input symbol. When the end of the string is reached, the string is accepted if the automaton is in one of its final states. Otherwise the string is rejected. The input mechanism can move only from left to right and reads exactly one symbol on each step. The transitions from one internal state to another are governed by the transition function δ.

초기 상태는 다음과 같다.

  • 상태.
  • 입력 장치(input mechanism)는 입력 문자열의 가장 왼쪽 문자에 놓여 있다.

오토마톤이 한 번 작동할 때마다, 다음과 같은 일이 일어난다.

  • 입력 장치가 오른쪽으로 한 칸 이동한다.
    • 입력장치는 한 칸씩 이동하며, 한 글자만 읽을 수 있다.

입력 장치가 input string의 마지막에 도달하면…

  • 오토마톤의 상태가 final states 중 하나이면 string은 accept 되고, 그렇지 않으면 reject 된다.
    • 참고: dfa는 deterministic finite accepter.

전이 그래프

transition graphs : finite automata를 표현하기 위해 사용하는 그림.

To visualize and represent finite automata, we use transition graphs, in which the vertices represent states and the edges represent transitions. The labels on the vertices are the names of the states, while the labels on the edges are the current values of the input symbol. For example, if and are internal states of some dfa M, then the graph associated with M will have one vertex labeled and another labeled . An edge labeled a represents the transition . The initial state will be identified by an incoming unlabeled arrow not originating at any vertex. Final states are drawn with a double circle.

  • 정점(vertices)
    • 정점은 상태(states)를 나타낸다.
    • 즉, dfa는 개의 정점을 갖는다.
    • 참고: vertices 는 vertex의 복수형.
  • 간선(edge)
    • 간선은 상태 변화(transition)를 나타낸다.
  • 라벨(labels)
    • 정점에 붙은 라벨: 상태의 이름.
      • 시작 정점엔 라벨 이 붙어 있다.
    • 간선에 붙은 라벨: 현재 입력 값.
  • 상태
    • 초기 상태는 외부에서 진입하는 간선으로 지정된다.
    • 승인 상태는 double circle로 표시한다.

예제: 전이 그래프 그려보기

다음과 같은 dfa가 있다고 하자.

그리고 다음의 전이 함수들이 있다고 하자.

가 초기 상태이니 정점을 하나 찍을 수 있을 것이다.

그리고 초기 상태는 외부 진입 간선이 하나 있어야 한다.

  • 외부 진입 간선이라 하면 말이 어려운데, 그냥 시작 화살표라 생각하자.
  • 정점은 원래 동그라미로 그려야 하지만 편의상 네모로 그렸다.

이제 상태에서 전이 가능한 다른 상태가 무엇이 있는지를 살펴보자.

  • 딱 두 가지가 있다.
    • 0 이 입력되면 상태가 그대로가 된다.
    • 1 이 입력되면 상태가 로 바뀐다.

부터 그려보자.

상태에서 0 은 입력되어도 그대로 상태가 안 바뀐다는 것이니까 자신으로 돌아가도록 그리면 된다.

  • 은 원래 그대로 돌아가는 한 개의 화살표인데, 표현이 힘들어서 그냥 이렇게 했다.
  • 위에 그린 이유는… 오른쪽에 앞으로 그릴 게 많을 것 같아서 그렇게 했다.

이번엔 을 그리자.

상태일 때, 1 이 입력되면 상태로 간다.

그런데 은 최종 상태 집합 의 원소이므로 테두리를 두 개로 하자.

이제 을 기준으로 그리기 위해 다음 두 식을 참고하자.

일 때 0 이 입력되면 으로 가니까, 화살표 하나를 더 추가해야겠다.

그리고 일 때 1이 입력되면, 로 가니까, 다음과 같이 될 것이다.

이제 전이 함수는 상태에서의 상태변화를 의미하는 두 개만 남았다. 마저 그리면 된다.

일 때 0 이 입력되면 상태가 변하지 않으므로 자신에게 돌아오는 화살표를 추가하자.

그리고 일 때 1이 입력되면 로 바뀌므로…

이렇게 전이 그래프를 완성했다.

이 그래프를 제대로 그리면 다음과 같이 된다.

image

  • 화살표 방향이나, 정점의 위치 등은 그리는 방법이 정해진 건 아니고 알아보기 쉽게 그리면 된다.
  • 연결과 라벨 등만 맞으면 된다.

확장 전이 함수

확장 전이 함수 : extended transition function

It is convenient to introduce the extended transition function . The second argument of is a string, rather than a single symbol, and its value gives the state the automaton will be in after reading that string.

  • 전이 함수 는 문자 한 개만 입력받는다는 불편함이 있었다.
  • 편의를 위해 문자열을 입력으로 받는 확장 전이 함수를 쓰도록 하자.
    • 확장 전이 함수는 전이 함수가 못하는 걸 하는 함수가 아니라, 일종의 축약표현이다.

다음과 같은 전이 함수가 있다고 하자.

이 전이 함수대로라면, ab가 입력으로 들어왔을 때 상태는 로 바뀐다.

그렇다면 상태일 때 문자열 ab가 입력된다면, 상태는 로 바뀐다고도 볼 수 있을 것이다.

확장 전이 함수 를 쓰면 이런 것을 표현할 수 있다.

언어와 결정적 유한 인식기

Languages and Dfa’s

Having made a precise definition of an accepter, we are now ready to define formally what we mean by an associated language. The association is obvious: The language is the set of all the strings accepted by the automaton.

dfa(acceptor)를 정의했으므로, 이제 관련 언어(associated language)를 정의하자.

관련 언어 : 오토마톤이 accept하는 모든 문자열의 집합.

DEFINITION 2.2
The language accepted by a dfa is the set of all strings on Σ accepted by M. In formal notation,
.

  • dfa M 이 accept 하는 언어는, M에 의해 accept 되는 (알파벳의 집합)에 대한 모든 문자열의 집합이다.

말이 어려우니 쉽게 풀어 표현해보자.

  • dfa에 집어넣을 수 있는 문자열 : 약속한 문자들로만 이루어진 문자열.
    • 약속한 문자들의 유한 집합을 라 한다.
    • 그런 문자들로만 이루어진 문자열의 집합을 라 한다.
  • dfa가 accept하는 문자열 : dfa에 입력했을 때 accept 결과가 나오는 문자열.
    • dfa가 accept하는 상태 : 문자열을 dfa에 넣고 돌렸을 때 최종 상태가 에 정의된 상태 중에 있는 것.
    • : accept 상태의 집합.
    • .
      • 초기 상태()의 dfa에 문자열 를 넣은 결과가 accept.
  • dfa가 accept하는 언어 : dfa가 accept 하는 모든 문자열의 집합.
    • 이 accept 하는 모든 문자열의 집합을 짧게 라고 쓴다.

Note that we require that , and consequently , be total functions. At each step, a unique move is defined, so that we are justified in calling such an automaton deterministic. A dfa will process every string in and either accept it or not accept it. Nonacceptance means that the dfa stops in a nonfinal state, so that

  • 각 단계에서 딱 하나의 move 만이 정의되어 있다.
    • 이런 오토마톤을 결정적(deterministic)이라 부른다.
  • dfa는 의 모든 문자열을 처리할 수 있다.
    • 처리 결과로 accept / not accept 를 내놓는다.
  • Nonacceptance는 dfa가 멈췄을 때 accept 가 아닌 상태인 것을 말한다.

그러므로 의 여집합, 즉 은 다음과 같다.

  • 언어 에 속하지 않은 문자열들의 집합.

예제 2.2

다음 전이 그래프와 같은 dfa가 있다고 하자.

image

그래프를 잘 살펴보니 다음과 같은 전이 함수를 알아낼 수 있었다.

이를 다음과 같이 테이블로 표현할 수도 있을 것이다.

  a b

한편, 이 dfa가 accept 하는 문자열은 어떨지 생각해 보자.

잘 생각해 보면 이 dfa가 accept 하는 언어는 다음과 같음을 알 수 있다.

  • a가 0~n 번 반복되고 b로 끝남.
  • .

한편, 에 들어가면 다시는 못 나오는데 이런 경우를 트랩 상태(trap state)라고 한다.

예제 2.3

Find a deterministic finite accepter that recognizes the set of all strings on starting with the prefix ab.

일 때, ab로 시작하는 모든 문자열을 인식하는 dfa를 찾아라.

정규표현식으로 따지면 ^ab.*. 재밌겠다. 해보자.

일단 초기 상태로 진입하는 부분을 그려 보자.

그리고 입력 문자열이 a로 시작하는 경우를 표현해 보자.

여기에서 b가 추가된다면… ab로 시작하는 문자열이므로 accept 상태로 가면 된다!

상태에서 a나 b가 추가로 입력되어도 달라질 것은 없으므로, 되돌아가는 화살표를 추가해보자.

오… 이것으로 accept 되는 경우는 모두 표현한 것 같다.

그렇다면 이번에는 accept 되지 않는 경우, 트랩 상태로 빠지게 만들어 보자.

accept 되지 않는 경우는 모두 다음과 같다.

  • b로 시작하는 경우.
    • ba, bb…
  • aa 로 시작하는 경우.
    • aaa, aab…

일단은 b 로 시작하는 경우는 확실히 accept 가 아니므로 아래쪽으로 빼주자. 새로운 상태도 추가하자.

상태에서 a 나 b 가 추가되어도 accept가 아닌 것은 확실하므로 상태를 유지시켜주자.

이제 aa로 시작하는 경우만 추가하면 된다.

이걸 제대로 그리면 다음과 같다.

image

예제 2.4

Find a dfa that accepts all the strings on {0, 1}, except those containing the substring 001.

  • 일 때, 001이 substring으로 포함되지 않는 모든 문자열을 accept하는 dfa를 찾아라.

일단 001 이 연속되면 트랩 상태로 들어가도록 해보자.

초기상태(빈 문자열)와 상태 0, 00은 accept 할 수 있는 상태니까, 테두리를 두 개로 표시해 주자.

초기상태에서 1이 입력되면? accept.

00 상태에서 0이 더 추가되면? accept 니까 표시해 주자.

0 상태에서 1이 입력되면? 초기 상태로 보내면 될 것 같다.

제대로 그리면 다음과 같다.

image

정규 언어

Regular Languages

Every finite automaton accepts some language. If we consider all possible finite automata, we get a set of languages associated with them. We will call such a set of languages a family. The family of languages that is accepted by deterministic finite accepters is quite limited. The structure and properties of the languages in this family will become clearer as our study proceeds; for the moment we will simply attach a name to this family.

  • 모든 유한 오토마톤은 특정 언어를 accept 한다.
  • 모든 유한 오토마타를 고려하면, 그와 관련된 언어의 집합도 얻을 수 있을 것이다.
    • 그런 언어의 집합을 언어군(family)이라 부르자.
  • dfa 에 의해 accept 되는 언어군은 매우 제한적이다.
    • 앞으로 공부할 내용이다.
    • 일단 이름부터 붙여보자.

DEFINITION 2.3
A language L is called regular if and only if there exists some deterministic finite accepter M such that
.

  • 언어 L 에 대하여…
    • 을 만족하는 결정적 유한 인식기(deterministic finite accepter, dfa) M이 존재한다면, 언어 L을 정규(regular) 언어라고 부른다.

예제 2.5

Show that the language

is regular.

언어 L이 정규 언어인지 검증하면 된다.

우선 식을 이해하자.

  • .
    • *가 붙어있으므로 a, b 두 문자를 사용해 만들 수 있는 모든 string의 집합을 말한다.
    • 빈 문자열도 포함한다.
    • : w 는 길이가 0 이상이고, a 와 b 만으로 만들어진 문자열을 말한다.
  • awa
    • a 로 시작하고 a로 끝나는 문자열.
    • 문자열 w 의 앞뒤에 a 가 있어야 한다는 말.

dfa 전이 그래프를 그릴 수 있으면 정규 언어임을 보일 수 있다.

전이 그래프는 다음과 같다. 따라서 정규 언어라 할 수 있다.

image