computation theory (1) -DFA, NFA

    Finite Automaton은 states와 input을 이용해 계산을 수행하며 극도로 제한된 메모리를 가진 컴퓨터가 사용하기에 좋은 수학모델이다. Finite Automaton은 다음과 같이 5-tuple로 정의한다.

finite automaton M = (Q, Σ, δ, q0, F) Q : states의 집합 Σ : alphabets의 집합 δ : Q X Σ -> Q인 transition function q0 : start state F : accept states의 집합

    하나의 finite automaton은 one language만을 accept(recognize)할 수 있으며 finite automaton이 recognize하는 language를 regular language라고 정의한다.

Finite automaton 중 어떤 state애서 다음 state로 가는 가능한 선택들이 여러개일 때 Nondeterministic finite automaton(NFA)이라 하며 NFA역시 5-tuple로 정의한다.  

nondeterministic finite automaton N = (Q, Σ, δ, q0, F) Q : states의 집합 Σ : alphabets의 집합 δ : Q X Σε -> P(Q)인 transition function ( Σε = Σ ∪ {ε}, P(Q)는 Q의 power set) q0 : start state F : accept states의 집합

    NFA가 deterministic finite automaton(DFA)와 다른점은 transition function 뿐이다.

+) computation theory의 모든 포스팅은 Michael Sipser -  Introduction to the Theory of Computation을 공부한 내용입니다.