---
title: "유한 오토마타: 제한된 상태로 문자열을 판정하기"
author: "Lee"
published_at: "2026-10-19T21:56:03.064Z"
updated_at: "2026-09-30T10:00:24.967Z"
tags: ["컴퓨터공학","계산이론"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EC%9C%A0%ED%95%9C-%EC%98%A4%ED%86%A0%EB%A7%88%ED%83%80-%EC%A0%9C%ED%95%9C%EB%90%9C-%EC%83%81%ED%83%9C%EB%A1%9C-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%84-%ED%8C%90%EC%A0%95%ED%95%98%EA%B8%B0"
ai_assisted: false
---

# 유한 오토마타: 제한된 상태로 문자열을 판정하기

[원문](https://ariser.io/@writer_a1cd615ab19e/%EC%9C%A0%ED%95%9C-%EC%98%A4%ED%86%A0%EB%A7%88%ED%83%80-%EC%A0%9C%ED%95%9C%EB%90%9C-%EC%83%81%ED%83%9C%EB%A1%9C-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%84-%ED%8C%90%EC%A0%95%ED%95%98%EA%B8%B0)

유한 오토마타는 입력을 왼쪽에서 오른쪽으로 읽으며 정해진 유한 상태 사이를 이동하는 계산 모델이다. 입력 전체를 저장하지 않고 현재 상태에 필요한 과거 정보만 요약한다. 다 읽은 뒤 현재 상태가 수락 상태인지로 문자열의 포함 여부를 판단한다.

![1을 읽을 때 짝수·홀수 상태를 바꾸고 0에서는 유지하는 유한 오토마타](/api/v1/media/d6260f89-5065-4a68-8fef-552daed63ab7)

*유한 오토마타의 상태는 입력의 전체 내용 대신 판정에 필요한 과거 정보를 요약한다.*

### 다섯 가지 구성 요소

결정적 유한 오토마타, DFA는 상태 집합, 입력 알파벳, 전이 함수, 시작 상태, 수락 상태 집합으로 정의한다. 전이 함수는 현재 상태와 다음 문자에 대해 정확히 한 다음 상태를 정한다. 모든 입력에 대해 규칙이 있어야 하며 불가능한 경로에는 실패 상태를 둘 수 있다.

0과 1로 이루어진 문자열에서 1의 개수가 짝수인지 판단하려면 두 상태면 충분하다. E는 지금까지 짝수, O는 홀수라는 뜻이다. 0을 읽으면 상태가 그대로이고 1을 읽으면 E와 O 사이를 바꾼다. 시작 상태와 수락 상태는 E다.

```python
def even_number_of_ones(text):
    state = "E"
    transition = {
        ("E", "0"): "E", ("E", "1"): "O",
        ("O", "0"): "O", ("O", "1"): "E",
    }
    for character in text:
        if character not in "01":
            raise ValueError("Alphabet is 0 or 1")
        state = transition[(state, character)]
    return state == "E"
```

1011은 E→O→O→E→O로 진행하여 거절된다. 110은 E→O→E→E라 수락된다. 빈 문자열에는 1이 0개 있어 수락된다. 문자열이 매우 길어도 기억해야 할 정보는 상태 두 개 중 하나뿐이다.

### 상태가 요약할 수 있는 범위

길이 n 입력을 한 번 읽으므로 시간 O(n), 고정된 오토마타의 실행 상태는 O(1) 공간이다. 오토마타를 저장하는 공간과 입력 길이에 따른 실행 공간은 별도로 센다. 더 복잡한 언어에는 더 많은 상태가 필요할 수 있다.

NFA는 한 상태와 문자에서 여러 다음 상태를 허용하며, 입력을 소비하지 않는 ε 전이도 사용할 수 있다. 하나라도 수락 경로가 있으면 수락한다. 이는 실제 기계가 마법처럼 정답 경로를 즉시 고른다는 뜻이 아니라 가능한 상태 집합을 추적할 수 있는 모델이다.

DFA와 NFA는 같은 정규 언어를 인식하지만 NFA를 DFA로 바꿀 때 상태 수가 크게 늘 수 있다. 모델의 표현 크기와 인식 능력은 다른 문제다.

유한 상태로는 임의 깊이의 중첩 괄호처럼 무한히 다양한 기억을 요구하는 구조를 일반적으로 구별할 수 없다. 반면 프로토콜의 제한된 상태 전이, 토큰 패턴, 입력 형식 검증에는 잘 맞는다. 상태마다 어떤 과거 정보를 요약하는지 설명하면 전이 규칙과 한계를 함께 이해할 수 있다.

수락 상태에서도 다음 입력을 계속 읽을 수 있다. 중간에 수락 상태를 방문했다는 사실만으로 전체 문자열을 수락하지 않는다. 마지막 입력을 처리한 뒤의 상태가 판정 기준이다.

### 참고 자료

- [MIT OpenCourseWare · Automata, Computability, and Complexity](https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/)