• CHAPTER 2. Finite Automata
    • 2.1 DETERMINISTIC FINITE ACCEPTERS
  • 챕터 2. 유한 오토마타
    • 2.1 결정적 유한 인식기
\[\def\right#1{ \overset{#1}{\longrightarrow} } \def\left#1{ \overset{#1}{\longleftarrow} } \def\bboxed#1{ \boxed{ \boxed{ #1 } } } \def\return{ \uparrow \downarrow }\]

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

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

DEFINITION 2.1

A deterministic finite accepter or dfa is defined by the quintuple
\(M = (Q, Σ, δ, q_0, F)\),
where
\(Q\) is a finite set of internal states,
\(Σ\) is a finite set of symbols called the input alphabet,
\(δ : Q × Σ → Q\) is a total function called the transition function,
\(q_0 ∈ Q\) is the initial state,
\(F ⊆ Q\) is a set of final states.

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

\[M = (Q, \Sigma, \delta, q_0, F)\]
  • \(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\)으로 바뀐다.

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

초기 상태는 다음과 같다.

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

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

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

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

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

전이 그래프

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

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

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

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

\[M = ( \{q_0, q_1, q_2\}, \{ 0,1 \}, \delta, q_0, \{ q_1 \} )\]

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

\[\begin{align} \delta(q_0, 0) & = q_0 \\ \delta(q_0, 1) & = q_1 \\ \delta(q_1, 0) & = q_0 \\ \delta(q_1, 1) & = q_2 \\ \delta(q_2, 0) & = q_2 \\ \delta(q_2, 1) & = q_1 \\ \end{align}\]

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

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

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

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

\[\begin{align} \delta(q_0, 0) & = q_0 \\ \delta(q_0, 1) & = q_1 \\ \end{align}\]
  • 딱 두 가지가 있다.
    • 0 이 입력되면 상태가 \(q_0\) 그대로가 된다.
    • 1 이 입력되면 상태가 \(q_1\)로 바뀐다.

\(\delta(q_0, 0) = q_0\) 부터 그려보자.

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

\[\begin{array}{rl} \return 0 & \\ \right{} \boxed{ q0 } & \\ \end{array}\]
  • \(\uparrow \downarrow 0\) 은 원래 그대로 돌아가는 한 개의 화살표인데, 표현이 힘들어서 그냥 이렇게 했다.
  • 위에 그린 이유는… 오른쪽에 앞으로 그릴 게 많을 것 같아서 그렇게 했다.

이번엔 \(\delta(q_0, 1) = q_1\) 을 그리자.

\(q_0\) 상태일 때, 1 이 입력되면 \(q_1\) 상태로 간다.

\[\begin{array}{rl} \return 0 \\ \right{} \boxed{ q0 } & \color{red}{ \right{1} } & \boxed{ q1 } & \\ \end{array}\]

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

\[\begin{array}{rl} \return 0 \\ \right{} \boxed{ q0 } & \right{1} & \color{red}{\bboxed{ q1 }}\\ \end{array}\]

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

\[\begin{align} \delta(q_1, 0) & = q_0 \\ \delta(q_1, 1) & = q_2 \\ \end{align}\]

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

\[\begin{array}{rl} \return 0 \\ \right{} \boxed{q0} & \right{1} & \bboxed{q1}\\ & \color{red}{ \left{0} } \\ \end{array}\]

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

\[\begin{array}{rl} \return 0 \\ \right{} \boxed{q0} & \right{1} & \bboxed{q1} & \color{red}{\right{1}} & \boxed{ q_2 } \\ & \left{0} \\ \end{array}\]

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

\[\begin{align} \delta(q_2, 0) & = q_2 \\ \delta(q_2, 1) & = q_1 \\ \end{align}\]

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

\[\begin{array}{rl} \return 0 & & & & \color{red}{\return 0} \\ \right{} \boxed{q0} & \right{1} & \bboxed{q1} & \right{1} & \boxed{q_2} \\ & \left{0} \\ \end{array}\]

그리고 \(q_2\) 일 때 1이 입력되면 \(q_1\) 로 바뀌므로…

\[\begin{array}{rl} \return 0 & & & & \return 0 \\ \right{} \boxed{q0} & \right{1} & \bboxed{q1} & \right{1} & \boxed{q_2} \\ & \left{0} & & \color{red}{ \left{1} } \\ \end{array}\]

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

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

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

확장 전이 함수

확장 전이 함수 : extended transition function

It is convenient to introduce the extended transition function \(δ* : Q × Σ* → Q\). 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.

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

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

\[\begin{align} \delta(q_0, a) & = q_1 \\ \delta(q_1, b) & = q_2 \\ \end{align}\]

이 전이 함수대로라면, ab가 입력으로 들어왔을 때 상태는 \(\boxed{q_0} \ \right{a} \ \boxed{q_1} \ \right{b} \ \boxed{q_2}\) 로 바뀐다.

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

확장 전이 함수 \(\delta^*\) 를 쓰면 이런 것을 표현할 수 있다.

\[\delta^*(q_0, ab) = q_2\]

언어와 결정적 유한 인식기

Languages and Dfa’s

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

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

DEFINITION 2.2
The language accepted by a dfa \(M = (Q, Σ, δ, q_0, F)\) is the set of all strings on Σ accepted by M. In formal notation,
\(L (M) = \{w ∈ Σ^* : δ^* (q_0, w) ∈ F \}\).

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

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

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

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
\(\overline{ L(M) } = \{ w ∈ Σ^* :δ^* (q_0, w) ∉ F \}\)

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

그러므로 \(L(M)\)의 여집합, 즉 \(\overline{L(M)}\)은 다음과 같다.

\[\overline{ L(M) } = \{ w ∈ Σ^* :δ^* (q_0, w) ∉ F \}\]
  • \(\overline{L(M)} =\)언어 \(L(M)\)에 속하지 않은 문자열들의 집합.

예제 2.2

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

q₀ q₁ q₂ a a, b b a, b

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

\[\begin{align} \delta(q_0, a) & = q_0 \\ \delta(q_0, b) & = q_1 \\ \delta(q_1, a) & = q_2 \\ \delta(q_1, b) & = q_2 \\ \delta(q_2, a) & = q_2 \\ \delta(q_2, b) & = q_2 \\ \end{align}\]

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

  a b
\(q_0\) \(q_0\) \(q_1\)
\(q_1\) \(q_2\) \(q_2\)
\(q_2\) \(q_2\) \(q_2\)

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

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

  • a가 0~n 번 반복되고 b로 끝남.
  • \(L = \{ a^n b : n \ge 0 \}\).

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

예제 2.3

Find a deterministic finite accepter that recognizes the set of all strings on \(Σ = \{a, b\}\) starting with the prefix ab.

\(\Sigma = \{ a, b \}\) 일 때, ab로 시작하는 모든 문자열을 인식하는 dfa를 찾아라.

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

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

\[\right{} \boxed{q0}\]

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

\[\begin{array}{ccc} & & \\ \right{} \boxed{q_0} & \color{red}{ \right{a} } & \boxed{q_1} \\ \end{array}\]

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

\[\begin{array}{ccc} & & \\ \right{} \boxed{q_0} & \right{a} & \boxed{q_1} & \color{red}{\right{b}} & \bboxed{q_2}\\ \end{array}\]

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

\[\begin{array}{rlc} & & & & \color{red}{\return a, b} \\ \right{} \boxed{q_0} & \right{a} & \boxed{q_1} & \right{b} & \bboxed{q_2}\\ \end{array}\]

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

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

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

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

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

\[\begin{array}{rlc} & & & & \return a, b \\ \right{} \boxed{q_0} & \right{a} & \boxed{q_1} & \right{b} & \bboxed{q_2}\\ & \color{red}{ \right{b} }& \boxed{q_3} \\ \end{array}\]

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

\[\begin{array}{rlc} & & & & \return a, b \\ \right{} \boxed{q_0} & \right{a} & \boxed{q_1} & \right{b} & \bboxed{q_2} \\ & \right{b} & \boxed{q_3} \\ & & \color{red}{\return a, b} \\ \end{array}\]

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

\[\begin{array}{rlc} & & & & \return a, b \\ \right{} \boxed{q_0} & \right{a} & \boxed{q_1} & \right{b} & \bboxed{q_2}\\ & & \color{red}{\downarrow a} \\ & \right{b} & \boxed{q_3} \\ & & \return a, b \\ \end{array}\]

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

q₀ q₁ q₂ q₃ a, b a b a b a, b

예제 2.4

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

  • \(\Sigma = \{ 0, 1 \}\) 일 때, 001이 substring으로 포함되지 않는 모든 문자열을 accept하는 dfa를 찾아라.

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

\[\begin{array}{ccc} & & & & & & \return 0,1 \\ \right{} \boxed{q_0} & \right{0} & \boxed{0} & \right{0} & \boxed{00} & \right{1} & \boxed{001} \\ \end{array}\]

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

\[\begin{array}{rrr} & & & & & & \return 0,1 \\ \right{} \bboxed{q_0} & \right{0} & \bboxed{0} & \right{0} & \bboxed{00} & \right{1} & \boxed{001} \\ \end{array}\]

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

\[\begin{array}{rrr} \return 1 & & & & & & \return 0,1 \\ \right{} \bboxed{q_0} & \right{0} & \bboxed{0} & \right{0} & \bboxed{00} & \right{1} & \boxed{001} \\ \end{array}\]

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

\[\begin{array}{rrr} \return 1 & & & & \return 0 & & \return 0,1 \\ \right{} \bboxed{q_0} & \right{0} & \bboxed{0} & \right{0} & \bboxed{00} & \right{1} & \boxed{001} \\ \end{array}\]

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

\[\begin{array}{rrr} \return 1 & & & & \return 0 & & \return 0,1 \\ \right{} \bboxed{q_0} & \right{0} & \bboxed{0} & \right{0} & \bboxed{00} & \right{1} & \boxed{001} \\ & \left{1} \\ \end{array}\]

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

λ 0 00 001 0 1 1 0 0 1 0, 1

정규 언어

Regular Languages

  • 모든 유한 오토마톤은 특정 언어를 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 = L(M)\).

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

예제 2.5

Show that the language
\(L = \{ awa : w \in \{ a, b \}^* \}\)
is regular.

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

우선 식을 이해하자.

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

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

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

q₀ q₂ q₃ q₁ a b a b a b a, b