이산수학: 형식언어와 오토마타3- 유한상태기계(finite state machine)
유한 상태 기계
-
플립플롭이 대표적인 예시임
-
유한 상태 기계 (S, I, F)
S: 상태의 집합 (a set of states)
I: 입렵값의 집합 (a set of inputs)
f: 상태 추이 함수(state transition function)플립플롭을 이용한 예시
S = {0, 1}
I = {0,1}
f(현재상태, 입력값) = 결과상태
f(0, 0)=0, f(1, 0)=1, f(0, 1)=1, f(1, 1)=0 -
유한 상태 기계의 유형
- 출력이 있는 유한 상태 기계
- 출력이 상태의 추이함수에 의해 결정
- 출력이 상태에 의해 결정
- 출력이 없는 유한 상태 기계
- 출력이 있는 유한 상태 기계
-
출력이 있는 유한 상태 기계
S: 상태의 집합 (a set of states)
I: 입렵값의 집합 (a set of inputs)
f: 상태 추이 함수(state transition function)
g: 출력함수
s0: 초기상태
출력이 없는 유한 상태 기계
-
유한 상태 오토마타(finite state automata)라고도 함
-
출력은 없지만 최종 상태의 집합이 존재한다
-
언어를 인식하는 기계를 모델링할 때 사용된다
M = (S, I, f, s0, F)
S: 상태의 집합 (a set of states)
I: 입렵값의 집합 (a set of inputs)
f: 상태 추이 함수(state transition function)
s0: 초기상태(starting states)
F: 최종상태(acceptance states)의 집합
유한 상태 오토마타 예시
문제: 5L의 물통, 3L의 물통으로 4L의 물을 만들자
x: 5L 통에 물을 채운다
x': 5L 통에 물을 비운다
y: 3L 통에 물을 채운다
y': 3L 통에 물을 비운다
xy: 5L통 → 3L통
yx: 3L통 → 5L통
(0,0)-x→(5,0)-xy→(2,3)-y'→(2,0)-xy→(0,2)-x→(5,2)-xy→(4,3)
x, xy, y', xy, x, xy 라는 입력값을 통해 (4,3)이라는 최종 상태에 도달한 형태
