[Automata] Deterministic Finite Automata(DFA)

Deterministic Finite Automata(DFA)

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Deterministic Finite Automata(DFA)

이전 Automata 포스트에서 기본적인 정의하는 방법에 대해서 알아보았다.

이번 포스트에서는 DFA에 대해서 이야기를 해보도록 하자.

 

Automata에는 다양한 방식의 automata 구현 방식들이 존재한다.

그렇다 보니 DFA를 정확히 이해하면 막상 어렵지 않지만 다른 방식과 헷갈려서 어렵게 느껴지는 경우가 종종 있다.

우선 Finite automaton이라고 하면 input 된 string에 따른 과정을 identify 하는 것을 의미한다.

우리는 이러한 과정 자체를 추상적으로 표현하여 이해하기 쉽도록 만들어주는데, 이것이 바로 Finite automaton이고 그중 하나가 바로 Deterministic finite automata인 셈이다.

한마디로 DFA는 오토마톤(Automaton)의 한 종류인 셈이다.

 

---

# DFA 정의

DFA는 tuple이라고 정의할 수 있다.

 

DFA에 포함되어 있는 요소는 아래와 같다.

• Σ: Alphabet
• K: All states
• s: Initial state
• F: final states
• σ: K x Σ -> K

이것을 이해하기 쉽게 tree structure로 만들어보면 아래와 같다.

Fig01.

Captial sigma의 경우는 전체 Alphabet을 의미한다.

K는 전체 states들의 set을 의미한다.

s는 initial state를 의미하는데 starting point라고 이해하면 된다.

F는 final states들의 set을 의미하는데 여기서 유의할 점은 s처럼 state가 아니라 states라는 점이다.

왜냐하면 F의 경우는 한가지 state만 존재하지 않을 수 있기 때문이다.

또한 s와 F 모두 K에 속한다.

마지막으로 small sigma의 경우에는 function을 의미하며 transition function from K and alpha to K라고 정의한다.

---