유한 오토마타 (Finte automata)

• 컴퓨터 프로그램과 전자논리회로를 설계하는데 쓰이는 수학적 모델이다.

• 유한상태기계는 유한한 갯수의 상태를 가질 수 있는 오토마타인데, 한 번에 하나의 상태만을 가진다.

• 현재 상태 (Current State)는 임의의 시간의 상태이며, 어떠한 사건 (Event)에 의해 다른 상태로 바뀐다. 이것을 전이 (Transition) 라고 한다.
• 유한 오토마톤 (Finite automaton, 단수형)은 현재 상태로부터 가능한 전이 상태와 전이를 유발하는 조건들의 집합으로 정의 된다.

유한 상태 변환기

• 상태와 주어진 입력 값에 기반하여 출력 값을 생성.
• 유한 상태 변환기는 2가지가 있다.

무어 모델 (Moore model)

오직 진입 동작 만을 사용한다. 출력 값은 현재 상태에 의해서 결정된다.

• $S$: 상태의 유한 집합.
• $S_0$: 초기 상태이며 $S$의 원소.
• $\Sigma$: 입력 값의 유한 집합.
• $\Lambda$: 출력값의 유한 집합.
• $T$: 현재 상태와 입력 값을 기반으로 다음 상태 값을 변환하는 상태 전이 함수: $S \times \Sigma \rarr S$
• $G$: 현재 상태를 기반으로 출력 값을 변환하는 상태 전이 함수: $S \rarr \Lambda$

밀리 모델 (Mealy model)

오직 입력 값 만을 사용한다. 출력 값은 입력 값과 현재 상태 모두에 의존한다. 일반적으로 상태의 수를 줄이는데 사용한다.

• $S$: 상태의 유한 집합.
• $S_0$: 초기 상태이며 $S$의 원소.
• $\Sigma$: 입력 값의 유한 집합.
• $\Lambda$: 출력값의 유한 집합.
• $T$: 현재 상태와 입력 값을 기반으로 다음 상태 값을 변환하는 상태 전이 함수: $S \times \Sigma \rarr S$
• $G$: 현재 상태를 기반으로 출력 값을 변환하는 상태 전이 함수: $S \rarr \Lambda$

유한 오토마타의 정의

정의

• 시작 상태 (start state)는 유한 오토마타가 입력값을 처리하기 전의 상태이다.
• 받아 들여지는 상태 (accept states 또는 final states)는 유한 오토마타가 모든 입력값을 처리했을 때의 상태가 받아 들여 질 경우 이 상태의 집합이다. 받아 들여지는 상태는 한 개 또는 여러 개일 수 있으며 이는 동치다. 일반적으로 받아 들여지는 상태는 이중 원으로 표현한다.

결정적 유한 오토마타 (Deterministic Finite Automata, DFA)

• $Q$: 상태의 공집합이 아닌 유한 집합.
• $\Sigma$: 입력 값으로 공집합이 아닌 유한 집합.
• $\delta$: 상태전이 함수: $\delta : Q \times \Sigma \rarr Q$.
• $s_0$: 초기 상태이며 $Q$의 원소.
• $F$: 최종 상태의 집합이며 $Q$의 원소.

비결정적 유한 오토마타 (Nondeterminstic Finite Automata, NFA)

• $Q$: 상태의 공집합이 아닌 유한 집합.
• $\Sigma$: 입력 값으로 공집합이 아닌 유한 집합.
• $S$: 공집합이 아닌 상태의 유한 집합.
• $\delta$: 상태 전이 함수: $\delta : Q \times \Sigma \rarr Q$.
• $s_0$: 초기 상태이며 $Q$의 원소.
• $F$: 최종 상태의 집합이며 $Q$의 원소.

비결정적 유한 오토마타는 결정적 유한 오토마타와는 다르게 입력 기호에 대해서 $\epsilon \text{-transition}$에 의해 0개 이상의 이동이 가능. 만약 가능한 다음 상태의 경우가 없다면, 기계는 입력을 거부.

참조

• 위키백과 - 유한상태기계