오토마타 이론 쉽게 이해하기: DFA NFA와 형식 문법 기준

알파벳·문자열·언어를 먼저 구분한다

용어	뜻	예시
알파벳 Σ	사용할 기호의 유한 집합	{0,1}
문자열	알파벳 기호의 유한한 순서열	0101
빈 문자열 ε	길이가 0인 문자열	|ε|=0
Σ*	Σ로 만들 수 있는 모든 유한 문자열	ε, 0, 1, 00, ...
언어 L	Σ*의 부분집합	끝이 01인 모든 이진 문자열

오토마타는 입력 문자열 하나를 읽고 수락 또는 거부합니다. 그 오토마타가 수락하는 모든 문자열의 집합이 그 오토마타의 언어입니다. 상태 그래프의 모양과 언어 자체를 구분해야 서로 다른 그래프가 같은 언어를 인식할 수 있다는 사실을 이해하기 쉽습니다.

DFA는 5-튜플과 전이 함수로 정의한다

결정적 유한 오토마타(DFA)는 M=(Q, Σ, δ, q₀, F)라는 5-튜플로 정의합니다. Stanford CS103 참고 자료는 DFA에서 모든 상태와 모든 입력 기호마다 정확히 하나의 전이가 정의되어야 한다고 정리합니다.

Q   : 유한한 상태 집합
Σ   : 입력 알파벳
δ   : 전이 함수 Q × Σ → Q
q₀  : 시작 상태, q₀ ∈ Q
F   : 수락 상태 집합, F ⊆ Q

예를 들어 ‘끝 두 글자가 01인 이진 문자열’을 인식하는 DFA를 생각해 봅시다. q0는 아직 유효한 접미사가 없는 상태, q1은 마지막 글자가 0인 상태, q2는 현재 문자열이 01로 끝나는 수락 상태입니다.

현재 상태	입력 0	입력 1	수락 상태
q0	q1	q0	아니요
q1	q1	q2	아니요
q2	q1	q0	예

입력 101
q0 --1→ q0 --0→ q1 --1→ q2
마지막 상태 q2 ∈ F → 수락

입력 011
q0 --0→ q1 --1→ q2 --1→ q0
마지막 상태 q0 ∉ F → 거부

DFA는 어떤 중간 상태를 거쳤는지가 아니라 입력을 모두 소비한 뒤 도착한 상태가 F에 포함되는지로 수락을 결정합니다. 입력을 덜 읽고 수락 상태를 잠깐 지나갔다고 최종 수락되는 것은 아닙니다.

NFA는 가능한 상태 집합을 추적한다

비결정적 유한 오토마타(NFA)는 하나의 상태와 입력에서 가능한 다음 상태가 0개 이상입니다. ε-NFA 표기에서는 입력을 소비하지 않고 이동하는 ε-전이도 허용합니다. NFA가 문자열을 수락하려면 가능한 실행 경로 중 하나 이상이 입력 전체를 소비하고 수락 상태에 도착하면 됩니다.

DFA 전이: δ(q, a) = 다음 상태 하나
NFA 전이: δ(q, a) = 가능한 상태들의 집합

ε-전이: 입력 글자를 읽지 않고 상태 이동
ε-closure(S): S에서 ε-전이만 0번 이상 따라가 도달할 수 있는 상태 집합

부분 문자열 01을 찾는 NFA 예시

상태 s0: 0과 1을 읽으며 s0에 머물 수 있음
s0에서 0을 읽을 때 s1로도 갈 수 있음
s1에서 1을 읽으면 수락 상태 s2
s2에서 0과 1을 읽으며 s2에 머물 수 있음

입력 11010의 가능한 한 경로
s0 --1→ s0 --1→ s0 --0→ s1 --1→ s2 --0→ s2
입력을 모두 읽고 s2에 도착 → 수락

‘어느 경로를 선택한다’는 표현은 구현이 미래를 미리 안다는 뜻이 아닙니다. 수학적으로 가능한 상태들을 동시에 추적한다고 이해하면 됩니다. 어떤 경로가 실패해도 다른 경로가 수락할 수 있습니다.

NFA를 DFA로 바꾸는 부분집합 구성

Stanford CS103 부분집합 구성 가이드는 새 DFA의 각 상태가 원래 NFA 상태들의 집합에 대응한다고 설명합니다. ε-전이가 있다면 시작부터 ε-closure를 취하고, 각 입력 뒤에도 다시 ε-closure를 계산합니다.

1. DFA 시작 상태를 NFA 시작 상태의 ε-closure로 둡니다.
2. 현재 NFA 상태 집합의 모든 상태에서 입력 기호 a로 갈 수 있는 상태를 합칩니다.
3. 그 결과에 ε-closure를 적용해 다음 DFA 상태 집합을 만듭니다.
4. 새 상태 집합이 나오지 않을 때까지 각 알파벳 기호에 대해 반복합니다.
5. NFA 수락 상태를 하나라도 포함한 집합을 DFA 수락 상태로 표시합니다.

이 예시에는 ε-전이가 없으므로 시작 집합 {s0}에서 0과 1의 이동만 반복합니다. s0가 두 입력에서 모두 자기 자신으로 돌아가므로 모든 도달 가능한 집합에 s0가 남습니다. 따라서 빈 집합 ∅는 도달 불가능하며, 실제로 만들어지는 DFA 상태는 아래 네 개뿐입니다.

DFA 상태	NFA 상태 집합	입력 0	입력 1	수락
A	{s0}	B	A	아니요
B	{s0,s1}	B	C	아니요
C	{s0,s2}	D	C	예
D	{s0,s1,s2}	D	C	예

const nfaTransitions = {
  s0: { '0': ['s0', 's1'], '1': ['s0'] },
  s1: { '0': [], '1': ['s2'] },
  s2: { '0': ['s2'], '1': ['s2'] },
};

function move(states, symbol) {
  const next = new Set();
  for (const state of states) {
    for (const target of nfaTransitions[state][symbol]) next.add(target);
  }
  return next;
}

function nfaAccepts(word) {
  let states = new Set(['s0']);
  for (const symbol of word) states = move(states, symbol);
  return states.has('s2');
}

const dfaTransitions = {
  A: { '0': 'B', '1': 'A' },
  B: { '0': 'B', '1': 'C' },
  C: { '0': 'D', '1': 'C' },
  D: { '0': 'D', '1': 'C' },
};

function dfaAccepts(word) {
  let state = 'A';
  for (const symbol of word) state = dfaTransitions[state][symbol];
  return state === 'C' || state === 'D';
}

수락 상태 s2를 포함하는 C와 D가 DFA의 수락 상태입니다. NFA에 상태가 n개면 이론상 DFA에 최대 2ⁿ개의 상태 집합이 생길 수 있지만 실제 변환에서는 시작 상태에서 도달 가능한 집합만 만듭니다. 변환 뒤에는 언어를 보존하면서 동치 상태 최소화를 별도로 수행할 수 있습니다.

정규표현식·정규문법·유한 오토마타의 관계

DFA, NFA, 정규표현식, 정규문법은 표현 방식이 다르지만 정규 언어를 기술합니다. 정규표현식은 문자열 패턴을 대수적으로 표현하고, NFA는 선택과 반복을 상태 전이로 표현하며, DFA는 입력마다 하나의 상태를 따라 실행하기 좋습니다. Cornell CS381 강의 목록도 DFA 정의, NFA와 ε-전이, 부분집합 구성, 정규표현식 순으로 이 관계를 다룹니다.

표현	강점	주의
DFA	실행 경로가 하나라 구현과 추적이 단순	변환 시 상태 수가 커질 수 있음
NFA	선택과 패턴 구조를 간결하게 표현	가능한 상태 집합을 추적해야 함
정규표현식	문자열 패턴을 짧게 기술	프로그래밍 언어의 확장 기능은 순수 정규식보다 강할 수 있음
정규문법	생성 규칙으로 정규 언어를 표현	일반 문맥 자유 문법과 범위를 혼동하지 않음

{aⁿbⁿ | n ≥ 0}처럼 a의 개수를 기억했다가 같은 수의 b와 비교해야 하는 언어는 유한한 상태만으로 일반적으로 인식할 수 없는 대표적인 비정규 언어입니다. 이런 언어는 문맥 자유 문법과 푸시다운 오토마타 같은 더 강한 모델로 넘어갑니다.

DFA와 NFA에서 자주 틀리는 예외

• DFA 전이 누락: 모든 상태·입력 기호 쌍에 전이가 하나 있어야 하므로 필요하면 죽은 상태를 추가합니다.
• 중간 수락: 입력을 모두 읽기 전에 수락 상태를 지났어도 마지막 상태가 수락 상태가 아니면 DFA는 거부합니다.
• NFA의 ‘모든 경로’ 오해: 모든 경로가 아니라 하나 이상의 완전한 경로가 수락하면 됩니다.
• ε를 입력 문자로 취급: ε-전이는 입력을 소비하지 않습니다. 알파벳의 일반 기호와 구분합니다.
• ε-closure 누락: NFA→DFA 변환의 시작과 각 기호 이동 뒤에 ε-closure를 적용합니다.
• 같은 구조와 같은 언어 혼동: 상태 수와 그래프 모양이 달라도 수락 문자열 집합이 같으면 언어 관점에서 동치입니다.

문자열 수락과 변환을 검증하는 절차

1. 언어를 자연어와 집합 표기로 각각 적고 알파벳을 고정합니다.
2. 빈 문자열, 최소 수락 문자열, 수락 경계 바로 밖의 문자열을 테스트합니다.
3. DFA에서는 각 상태의 전이 수가 알파벳 크기와 같은지 확인합니다.
4. NFA에서는 각 입력 접두사 뒤 가능한 상태 집합과 ε-closure를 기록합니다.
5. NFA와 변환된 DFA에 짧은 문자열을 전수 입력해 수락 결과가 모두 같은지 비교합니다.
6. 도달 불가능한 상태와 동치 상태는 언어 보존을 확인한 뒤 정리합니다.

결론과 내부 학습 경로

결론: DFA와 NFA의 핵심 차이는 다음 상태가 하나인지 집합인지에 있습니다. NFA의 여러 가능성을 하나의 상태 집합으로 묶으면 DFA가 되며, 둘은 같은 정규 언어를 인식합니다. 문제를 풀 때는 5-튜플, 입력 전체 소비, ε-closure, 수락 상태 포함 여부를 순서대로 확인하면 됩니다.

1. 이산수학 집합과 부분집합으로 상태 집합과 멱집합을 익힙니다.
2. 곱집합과 관계로 전이 함수의 입력 쌍을 이해합니다.
3. 그래프 이론 기본 개념으로 상태 그래프의 경로를 읽습니다.
4. 직접증명과 귀납법으로 오토마타 동치와 불변식을 설명합니다.