[오토마타] 4. DFA (Deterministic Finite Accepter)

DFA

지난 글에서 오토마톤에 대해 정리하면서 오토마톤은 다양한 기준으로 분류할 수 있다고 하였다.

그 중에서 이번 글에는 DFA 오토마톤에 대해 정리해보려고 한다.

 

DFA (Deterministic Finite Accepter)는 지난 내용에 따라 다음과 같이 이해할 수 있다.

 

- 결정적이며 (Deterministic, 각 상태에서 주어진 입력에 대해 갈 수 있는 경로가 유일하다.)

- 유한한 (Finite, 메모리 == 저장공간이 유한하다.)

- Accepter (기계의 output 이 yes(accept) / no(reject) 로 이진적이다.)

 

 

DFA는 오토마톤의 일종이지만, 특이하게 temporary storage 가 없다.

그렇다고 저장공간이 없는 것은 아니고, control unit 에 마치 플립플랍처럼 자신의 상태를 0, 1, 2 이렇게 조절할 수 있는 저장 공간이 있다.

하지만 이 공간의 크기는 유한하다.

 

DFA는 다음과 같이 정의된다.

 

M = (Q, Σ, 𝛅, q₀, F)

 

 

오토마톤은 기계이므로 머신의 앞글자를 따서 M이라고 지칭한다.

 

Q = 기계가 가질 수 있는 모든 상태의 집합

Σ = 기계의 인풋으로 들어올 수 있는 알파벳 (심볼의 집합)

𝛅 = 하나의 상태에서 특정 인풋이 주어졌을 때 다른 상태로 이동하는 transition function

q₀ = Q에 있는 상태 중 기계의 초기 상태

F = Q에 있는 상태 중 Yes 라는 답을 내리는 상태들의 집합

 

transition function은 𝛅 : Q X Σ → Q 로 표현하며, 화살표 왼쪽에 있는 집합이 정의역과 일치하는 total function 이다.

즉, 이 함수의 입력 집합과 정의역이 일치한다.

화살표 왼쪽에 있는 기호는 두 집합의 카르테시안 곱을 의미한다.

따라서 모든 (상태, 심볼) 쌍에 대해 다른 상태로 넘어가는 함수가 존재한다.

 

만약  Q = {q₀, q₁, q₂}, Σ = {a, b} 이면,

 

Q X Σ = { (q₀, a), (q₁, a), (q₂, a), (q₀, b), (q₁, b), (q₂, b) }

 

이다. 그리고 이 모든 경우의 수가 transtion function 의 정의역이다.

(모든 경우의 수에 대해 함수가 정의되어 있다.)

 

 

이 그림은 transition function 을 그래프로 나타낸 모습이다.

특정 타임 프레임에서 qᵢ 상태일 때 input symbol 로 a 를 읽었다면 qⱼ상태로 넘어간다.

이런 그래프를 transition graph 라고 부른다.

 

 

 

DFA를 이제 지금까지 배웠던 언어와 문장의 개념에 확장해서 적용해보면, Input 으로 주어지는 string 이 어떤 언어 L 에 속하는 sentence 인지 yes, no 로 판별하는 기계로 동작하도록 할 수 있다.

 

그러면 위 그림과 같이 symbol 이 각각의 셀에 채워진 Input tape 가 주어질 것이고, 이 테이프를 왼쪽에서부터 하나씩 읽으면서 DFA 기계의 상태가 변화할 것이다. 주어진 스트링의 모든 심볼을 다 읽었을 때 기계의 최종 상태가 Yes 라면 이 스트링은 문장인 것이고, No 라면 이 스트링은 이 기계가 정의한 언어의 문장이 아니라고 판단한다.

 

이 과정에서 컨트롤 유닛은 지금까지 판단했던 서브스트링의 판별 결과 (상태) 를 기억하고 있어야 하기 때문에 유한한 크기의 저장 공간, 기억 능력은 갖고 있어야 한다. (DFA에서 임시 저장 공간은 없기 때문에 컨트롤 유닛 내에 있는 저장공간에 기억한다.)

 

 

---

 

DFA 예시

 

위와 같은 DFA 를 생각해보자.

가질 수 있는 모든 상태는 3개, 알파벳은 0, 1 이며, 초기 상태는 q₀ 이고, yes 를 반환하는 상태는 q₁ 이다.

그리고 트랜지션 함수가 일부 축약된 채 주어졌다.

 

이 DFA 의 트랜지션 그래프를 아래와 같이 그릴 수 있다.

(트랜지션 함수가 생략되었으니 이렇게 그릴 수 있다는 정도로만 참고하자.)

 

 

이 그림에서 몇 가지 살펴볼 점들이 있다.

 

1. 초기 상태는 자신을 향해 들어오는 출처없는 화살표를 갖는다. 이를 통해 initial vertex (state) 를 알 수 있다.

2. F 에 속하는 상태는 2개의 원으로 표시한다. 이를 통해 final vertex (state) 를 알 수 있다.

3. 모든 상태는 알파벳의 심볼 개수만큼 나가는 화살표가 존재한다.

(상태의 개수와 알파벳의 심볼 개수를 곱한 카르테시안 곱의 경우의 수 만큼 엣지가 존재해야 한다.)

 

이 DFA 에 한번 0과 1로 구성된 임의의 문자열을 넣어보자.

만약 0111 이라는 문자열을 넣는다면 이 기계의 동작을 따라 갔을 때 다음과 같이 상태가 변화한다.

 

q0 → q0 ( 0 )

q0 → q1 ( 1 )

q1 → q2( 1 )

q2 → q1 ( 1 )

 

최종적으로는 final state 에 존재하므로 이 기계는 yes 라고 답할 것이다.

만약 이 기계가 0, 1로 구성된 임의 문자열이 어떤 언어에 속한 문장인지 판별하는 기계라면 yes 라고 답한 0111 을 그 언어의 문장이라고 판별할 것이다.

 

반면 1111 이라는 문자열을 넣는다면 다음과 같이 상태가 변한다.

 

q0 → q1 ( 1 )

q1 → q2 ( 1 )

q2 → q1( 1 )

q1 → q2 ( 1 )

 

 

최종 상태가 q2 이고, 이 상태는 final state 가 아니므로 이 기계는 No 라고 답할 것이다.

즉, 0111 은 어떤 언어에 속한 문장이 아니라고 판별하는 것이다.

 

 

이제 트랜지션 함수를 조금 더 확장한 형태를 살펴보자.

만약 트랜지션 함수에 star closure 처럼 * 첨자를 추가하면 다음과 같이 나타낼 수 있다.

 

 

 

이런 트랜지션 함수를 Extended transition function 이라고 한다.

이 함수도 역시 total function 이며, 기존의 트랜지션 함수가 하나의 상태에서 인풋이 주어지면 결과 함수를 유일하게 결정할 수 있었기 때문에, 이 함수도 하나의 결과를 유일하게 결정할 수 있다.

 

이때 알파벳에는 positive closure 가 아니라 star closure 가 들어갔으므로 λ도 들어올 수 있다!

따라서 확장된 트랜지션 함수는 아래와 같이 재귀적으로 정의할 수 있다.

 

 

 

 

기존에는 트랜지션 함수에 심볼 하나만 들어올 수 있었다면, 확장된 트랜지션 함수는 '문자열' 을 입력으로 받아서, 그 문자열을 따라서 순차적으로 상태를 바꾼 '최종 상태' 를 결과로 내보낸다.

간단히 말하면 모든 상태 변환 과정을 보여주는게 아니라, 중간 과정을 생략하여 표기하는 방법이라고 보면 된다.

 

예를 들어보자.

 

𝛅(q0, a) → q1

𝛅(q1, b) → q2

 

라는 transition 함수가 있다고 해보자.

그러면 ab 라는 입력에서 대해서 다음과 같이 상태가 변화할 것이다.

 

q0 → q1 → q2

 

이때 확장된 트랜지션 함수를 사용하면

간단하게 한 줄로 q0 에 대해 ab 입력이 주어지면 q2로 바뀐다! 라고 표현할 수 있다.

 

𝛅*(q0, ab) → q2

 

q0 → q2

 

따라서 input string 위치에 임의의 문자열 w 를 넣으면 다음과 같이 표현할 수도 있다.

 

만약 어떤 문자열 w 를 입력으로 받은 확장된 트랜지션 함수의 결과가 F 에 속하는 상태라면, w 는 기계에 의해 yes 라고 판별된다.

그리고 이를 통해서 우리는 Language를 표현할 또 다른 수단을 얻게 된다.

 

 

Grammar 로 표현하는 언어를 L(G) 라고 했다면, DFA를 이용해서 표현하는 언어는 L(M) 이라고 표현할 수 있다.

집합 노테이션을 살펴보면, 어떤 알파벳의 star-closure 에 속하는 어떤 문장에 대해, 이 문장이 어떤 기계 M의 확장된 트랜지션 함수로 만드는 상태가 final state 가 되는 문장들을 가지고 구성된 집합을 통해 언어를 정의하겠다는 것이다.

 

쉽게 말해서, 어떤 DFA가 있을 때, 이 기계를 가지고 만들 수 있는 모든 문장을 언어로 본다는 것이다!

 

연습 문제

문제 1

 

 

 

 

한번 아까 보았던 이 DFA를 가지고 이 DFA가 만드는 언어 L(M) 을 생각해보자.

이 언어를 기존의 셋 노테이션으로 표현하려면 일단 여러가지 인풋을 넣어보면서 규칙을 찾으면 좋다.

 

먼저 시작 상태에서 0을 넣으면 다시 시작 상태로 돌아온다.

따라서 앞에 0은 얼마든지 넣어도 괜찮다.

그러다가 1이 주어지면 q1 이라는 final state 로 들어온다.

이를 토대로 다음과 같은 문장이 언어가 될 수 있다는 것을 유추할 수 있다.

 

1

01

001

0001

00001

....

 

그 다음에 q1 에서 생각해보자.

q1 상태에서 0이 들어오게 되면 다시 q0 상태로 돌아가며, 이후에는 다시 몇 개의 0을 받든 1이 나타나야 q1 로 되돌아 올 수 있다.

 

따라서 위 문장에 더해 아래와 같은 문자열도 문장이 될 수 있다. (그리고 이 문자열 맨 앞에는 임의의 개수의 0이 붙어도 문장이다!)

 

101

1001

10001

100001

1000...001

 

만약 q1 상태에서 1이 들어오게 되면 그때는 q2 상태로 변화하고, 몇개의 0을 더 받을 수 있으며, 최종적으로 1이 들어와야 final state로 돌아올 수 있다.

 

q1 상태에서부터 생각하면

 

...11

...1001

 

로 끝나는 문자열들도 문장이다.

이를 기존의 집합 노테이션으로 표현하면 다음과 같이 표현할 수 있다.

(사실 이 문제는 조금 어려운 문제라고 한다.. 꽤 익숙해졌다고 생각했는데 한번에 이해가 안되어서 당황했다.)

 

 

이 식을 잘 생각해보면, m = 0 또는 1 이므로 w0 이 한번만 나타나거나 그냥 λ 이다.

w0 의 결과는 q0 또는 q2 상태이다. (임의 문자열 뒤에 0이 붙은 상태인데, 0을 입력으로 받으면 반드시 q0, q2 중 한 군데로 간다.)

이 상태에서 1을 홀수번 나열하면 반드시 q1 상태로 들어가게 되므로 이렇게 언어를 표현해도 같은 언어를 표현한 것이다.

(참고로 m > 1 은 의미가 없다. 왜냐하면 m > 1 이어도, 그 문자열은 어차피 0으로 끝나서 w0 으로 표현할 수 있기 때문이다.)

 

---

 

문제 2

 

 

다른 예시를 보자.

이 예시로 주어진 DFA 가 만드는 언어를 기본적인 셋 노테이션으로 표현해보자.

이 DFA로 만들 수 있는 문장을 생각해보면

 

aa..aab 임을 알 수 있다.

이후에 추가적인 문자가 붙으면 절대로 final state 로 되돌아 올 수 없다.

(이렇게 final state로 돌아오지 못하는 q2와 같은 상태를 trap state 라고도 부른다.)

 

이런 표현이라면 간단하게 집합 노테이션으로 다음과 같이 작성할 수 있다.

 

L(M) = { aᵐb : m ≥ 0 }

 

---

 

문제 3

 

{a, b}를 알파벳으로 하며, ab로 시작하는 모든 문자열을 원소로 갖는 집합을 DFA 로 표현해보자.

 

 

나는 이렇게 그렸다.

DFA는 각 상태에서 이동가능한 모든 경우의 수를 다 엣지로 표현해야 하므로,

final state 로 갈 수 없는 경우는 모두 trap state로 빠지도록 만들었다.

 

이때 한 가지 유의하면 좋은 점은 trap state 는 final state, non-final state 와는 독립적인 개념이다.

따라서 위 그림에서는 q2도 trap state 에 포함된다.

이름에 '함정' 이라는 의미가 들어있어서 q2 는 내가 가려는 곳인데 그게 함정이겠어? 하고 놓치지 않도록 주의하자.

 

 

 

 

문제 4

 

001 이라는 서브 스트링을 포함하고 있지 않은 모든 종류의 {0, 1} 로 구성된 문자열을 찾는 문제이다.

여집합 방식으로 정의가 되어있어서 원하는 목표를 향하도록 DFA를 그리는 것이 어색하게 느껴진다.

 

 

 

하지만 여집합 표현이라면 거꾸로 001이 포함된 문자열을 찾는다고 생각한 다음 final 과 non-final state 를 뒤집어서 표현해서 간단히 해결할 수 있다.

 

위 그림에서 q0 은 연속으로 0이 0번 나온 상황

q1은 연속으로 0이 1번 나온 상황

q2는 연속으로 0이 2번 나온 상황을 나타낸다고 생각하면 된다.

 

 

 

---

Regular Langauge

DFA를 사용하면 regular 라는 개념을 정의할 수 있다.

어떤 언어 L은 그 언어를 표현할 수 있는 DFA가 존재하면 regular 하다고 말한다.

 

그래서 문장이 존재하기만 하면 굉장히 많은 언어가 만들어질 수 있지만, 그런 언어들 중에서 특히 DFA 로 언어를 나타낼 수 있는 언어를 Regular Language 라고 하는 것이다.

 

이 표현은 뒤에서 굉장히 자주 나오니 정의를 꼭 숙지해두자!

 

 

 

그래서 어떤 언어가 regular 하다는 것을 보이라는 것은 곧, 같은 언어를 DFA 로 정의하라는 것과 같다.

이 언어는 a로 시작해서 a로 끝나기만 하면 되는 언어이다.

DFA로 나타내면 다음과 같이 나타낼 수 있다.

 

 

 

이번엔 조금 더 확장된 예시를 보자.

 

L to the 2 에 대해 regular 함을 보이는 것이다.

역시 조금 복잡하지만 DFA를 그릴 수 있다.

 

 

결국 같은 DFA 를 옆으로 한번 더 붙인 그림인데, 이를 통해서 예상할 수 있는 성질은,

만약 어떤 L 이 regular 하다면, 그 언어를 여러 번 concatenate 한 언어 역시 regular 하다.