1. 오토마타 이론
문제를 해결하는 과정 중 한 시점을 "상태(state)"라고 하면 유한한 상태로 해결할 수 있는 문제들과 그렇지 않은 문제로 나눌 수 있다. 이 때 유한한 상태를 갖고 입력에 따라 한 상태에서 다른 상태로 전이되며 최초 상태(S0)에서 최종 상태(F)까지 이어져 출력을 내놓는 것을 유한 상태 기계(FSM, Finite-State Machine), 유한 오토마타(Automata)라고 부른다. 좀 더 쉽게 이해해보면 우리가 풀고 있는 거의 모든 PS의 문제들이 오토마타 문제로 분류될 수 있다.
오토마타는 순서도와도 매우 비슷하다. 순서도에서도 표현하는 방식이 있듯이 오토마타도 표현 방법이 정해져있다.
- M: 오토마타( M = {Q, ∑, δ, S0, F} )
- Q: 상태의 집합(Q ≠ { })
- ∑: 입출력 문자의 합(∑ ≠ { })
- δ: Q × ∑ → Q, 상태 전이함수, Q의 원소가 입력에 따라 어떤 상태로 전이되는가를 나타냄
- S0: 최초 상태(Initial state)
- F: 최종 상태(Final state)
2. 결정적 유한 오토마타
유한 오토마타는 결정적인 것과 비결정적인 것으로 나뉜다. 둘의 차이는 전이의 유일성이다. 결정적 유한 오토마타는 상태의 전이가 유일하게 정의되고 비결정적 유한 오토마타는 그렇지 않다.
위키에 소개된 DFA를 보자. 이 DFA는 3의 배수를 판별한다. 최종 상태에서 입력이 끝나면 해당 입력은 3의 배수다. S0은 최초 상태이자 최종 상태로, 최종 상태는 다이어그램에서 두 개의 원으로 겹쳐서 표현된다. 입력을 "5(1012)"로 제시해보자. 최초 상태에서 1은 S1으로 전이된다. 0은 S2로, 1은 다시 S2로 전이되어 입력이 끝났다. 최종 상태에 도달하지 못했으므로 5는 3의 배수가 아니다.
"9(10012)"를 입력해보자. 최초 상대에서 1은 S1으로, S1에서 0은 S2로, S2에서 0은 S1으로, S1에서 1은 S0로 전이되며 최종 상태에서 입력이 끝났다. 9는 3의 배수가 맞다. DFA를 직접 구성하는 것은 어려워서 아직 직접 해보지 못했지만 일단 돌아가는 원리는 이해했다.
3. 활용
DFA는 문자열 패턴 매칭에서 매우 유용하게 활용될 수 있다. 이 개념을 공부하게 된 계기도 같은 유형의 문제를 풀다가 이 개념이 필요하게 되어서였다.
KMP, 아호코라식 등의 "트라이(tri)"에 DFA가 그대로 적용되어 있다.
4. 문제
백준 15910: 바나나나빠나나 https://www.acmicpc.net/problem/15910
힌트에 아예 대놓고 DFA 다이어그램이 제시되어있다.
