[C- compiler] 유한 오토마톤

유한 오토마톤(Finite automation)은 컴퓨터 프로그래밍과 전자 논리 회로를 설계하는 데 주로 쓰이는 모델입니다. 또다른 말로 상태 기계라고 불리지요. 유한 오토마톤은 컴파일러 과학에서 오토마톤 이론에 파생된 모델로써, 컴파일러의 설계, 파싱, 정형화 등에 있어 중요한 역할을 담당합니다. 

참고로 유한 오토마톤을 통해 정의한 패턴 인식 알고리즘은 정규 표현식이 표현할 수 없는 문자열 패턴을 나타낼 수 있습니다. 

유한 오토마톤은 크게 4가지로 구성됩니다.

1. state(상태)

2. transition(전이)

3. start state(시작 상태)

4. accepting states(허용 상태)

이 4가지로 구성된 모델을 토대로 패턴 인식 알고리즘을 구현할 수 있습니다. 유한 오토마톤은 어떤 특정 입력(문자)과 현재 오토마톤의 상태에 의해 계속해서 상태 전이가 일어나게 됩니다. 그리고 입력으로 주어진 모든 문자들이 처리되었을 때(모든 문자들은 문자열들의 구성 요소들을 나타냅니다), accepting state에 도달하게 되면 그 문자열의 패턴을 인식하게 되는 겁니다.