유한 상태 기계

공식적인 정의

지금까지는 상태 도식을 통해 유한 상태 기계를 정의해 왔다. 이제부터 유한 상태 기계를 공식적으로 정의해보자. 상태 도식이 직관적으로 이해하기 쉬운데, 공식적인 정의가 필요한 이유는 무엇일까?

첫째, 공식적인 정의는 엄밀하다. 유한 오토마타에서 무엇이 허용되는지에 대한 모호함을 해결해 준다. 유한 오토마타가 0개의 인식 상태를 가질 수 있는지, 아니면 가능한 입력 기호마다 모든 상태를 종료하는 전이가 반드시 하나씩 있어야 하는지 확실하지 않을 때, 공식적인 정의를 통해 두 경우 모두 '예'라는 답을 확인할 수 있다. 둘째, 공식적인 정의는 표기법을 제공한다. 좋은 표기법은 생각을 명확하게 하고 표현하는 데 도움이 된다.

공식적인 정의의 언어는 마치 법 문서처럼 다소 난해하다. 둘 모두 정확해야 하며 모든 세부 사항을 철자로 표기해야 한다는 공통점이 있다.

유한 상태 기계는 여러 부분으로 구성된다. 입력 기호에 따라 한 상태에서 다른 상태로 이동하는 일련의 상태와 규칙이 있다. 허용되는 입력 기호를 나타내는 입력 알파벳이 있다. 또, 시작 상태와 인식 상태 집합이 있다. 공식적인 정의에 따르면 유한 상태 기계는 상태 집합, 입력 알파벳, 이동 규칙, 시작 상태, 수락 상태라는 다섯 가지 객체의 목록이다. 수학의 언어에서는 5개의 요소로 이루어진 목록을 5-튜플이라고 부른다. 따라서 유한 상태 기계를 이 다섯 부분으로 구성된 5-튜플로 정의한다.

이동 규칙을 정의하기 위해 흔히 로 표시되는 전이 함수라는 것을 사용한다. 유한 오토마톤에 상태 에서 상태 로 가는 입력 기호 로 표시된 화살표가 있다면, 이는 상태 기계가 을 읽을 때 상태 에 있으면 상태 로 이동한다는 의미이다. 이는 라고 간단히 표현할 수 있다. 이 모든 것을 종합하면 유한 상태 기계의 공식적인 정의를 완성하게 된다.

참고 문헌

1. M. Sipser, Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012.