형식언어와 오토마타.02.01

결정적 유한 인식기와 전이 그래프
언어와 결정적 유한 인식기
정규 언어
- 예제 2.5

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)의 집합.
Σ는 입력 가능한 문자열의 유한집합.
- 즉 가능한 input의 집합.
δ는 상태를 변화시키는 함수라고 생각하자.
- $\delta$ (현재상태, 입력문자) = 다음 상태
- 입력 문자는 문자열이 아니다는 점에 주의. 한 글자만 받는다.
- 예) δ(q0,a)=q1
  - 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}$

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

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

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

확장 전이 함수

확장 전이 함수 : 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 상태의 집합.
- δ∗(q0,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는 Σ∗의 모든 문자열을 처리할 수 있다.
- 처리 결과로 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가 있다고 하자.

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

$\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}$

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

예제 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}$

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

정규 언어

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 전이 그래프를 그릴 수 있으면 정규 언어임을 보일 수 있다.

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