상태가 기억하는 정보
상태는 지금까지의 모든 입력을 그대로 저장하는 대신 이후 처리에 필요한 구분을 나타낸다. 예를 들어 이진 입력에서 1의 개수가 짝수인지 홀수인지만 기억한다면 두 상태면 충분하다.
간단한 전이
짝수 상태에서 1을 읽으면 홀수 상태로, 홀수 상태에서 1을 읽으면 짝수 상태로 바꾼다. 0을 읽으면 상태를 유지한다. 시작을 짝수 상태로 두면 빈 입력도 1의 개수가 0인 짝수 경우에 해당한다.
입력 인식과 출력
문자열을 인식할 때에는 수용 상태를 정하고 입력을 끝까지 처리한 뒤의 상태로 수용 여부를 판단한다. 다른 형태의 상태 기계는 전이나 상태에 따라 출력도 만든다. 상태가 변한다는 것과 출력이 있다는 것은 구별한다.
모형의 범위
상태가 유한하다는 조건은 표현할 수 있는 기억에 제한을 준다. 입력 길이가 길어질 때 그 전체를 새 상태 하나씩으로 무한히 늘리는 기계는 유한 상태 모형이 아니다. 결정적 형태와 비결정적 형태도 구분한다.
관련 문서
결정적 유한 오토마타 / 비결정적 유한 오토마타 / 문자열 / 이진법 / 짝수 / 홀수 / KMP 알고리즘 / 알고리즘