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

핵심 정의와 기호

DFA는 M=(Q,Σ,δ,q₀,F)로 나타냅니다. Q는 유한 상태 집합, Σ(시그마)는 유한 입력 알파벳, δ(델타)는 전이 함수, q₀는 시작 상태, F⊆Q는 수용 상태 집합입니다. δ:Q×Σ→Q는 모든 상태·입력 쌍에 다음 상태를 정확히 하나 정합니다. 입력 전체를 읽은 뒤 상태가 F에 속하면 수용합니다.

ε(엡실론)는 길이 0의 빈 문자열입니다. ε-전이를 허용하지 않는 NFA는 δ:Q×Σ→P(Q)로 나타냅니다. 다음 상태 집합이 비어 있거나 여러 원소일 수 있습니다. 가능한 실행 중 하나라도 입력 전체를 읽고 수용 상태에 도달하면 수용합니다. ε-NFA는 입력 소비 없는 ε-전이를 추가로 허용하는 변형입니다.

가장 작은 예제

Σ={0,1}에서 마지막이 1인 문자열을 인식하는 DFA입니다. q₀는 입력 전 또는 마지막이 0, q₁은 마지막이 1인 상태이고 시작은 q₀, 수용 집합은 {q₁}입니다.

현재 상태	입력0	입력1
q₀	q₀	q₁
q₁	q₀	q₁

101은 q₀→q₁→q₀→q₁이어서 수용됩니다. 10은 q₀에서 끝나 거절되고 ε도 거절됩니다.

헷갈리는 반례

NFA의 여러 가능성은 임의로 하나만 골라 검사하라는 뜻이 아닙니다. 어느 경로든 하나가 수용하면 됩니다. NFA가 DFA보다 더 넓은 언어를 인식하는 것은 아닙니다. 둘 다 정확히 정규 언어를 인식하며 NFA의 가능한 상태 집합을 DFA의 상태로 표현할 수 있습니다.

손으로 풀어보기

Σ={a,b}에서 a의 개수가 짝수인 문자열을 설계합니다. 상태 E는 짝수, O는 홀수이며 시작과 유일한 수용 상태는 E입니다.

현재 상태	a	b
E	O	E
O	E	O

abba는 E→O→O→O→E이므로 수용, abb는 E→O→O→O이므로 거절입니다. aba도 a가 2개라 수용하고, ε는 a가 0개라 수용합니다.

이 DFA의 언어를 만드는 오른쪽 선형 문법 예시는 E→bE | aO | ε, O→bO | aE입니다. E,O는 비단말 기호, a,b는 단말 기호, |는 규칙 선택입니다. 예를 들어 E⇒aO⇒abO⇒abbO⇒abbaE⇒abba입니다. 일반 형식 문법은 더 넓은 분류를 갖지만 여기서는 정규 문법과 유한 상태 모델의 연결까지만 다룹니다.

선택: JavaScript로 검산하기

코드 직접 실행

본문 예제를 선택하고 실제 계산 결과를 확인합니다.

예제 크게 보기 (새 탭)

손풀이 뒤 선택해서 실행하는 짧은 전체 코드입니다. 브라우저 Console 또는 Node.js가 준비된 환경의 check.mjs에서 실행할 수 있으며 수학 학습에 설치는 필수가 아닙니다.

function acceptsEvenA(input) {
  let even = true;
  for (const ch of input) {
    if (ch === 'a') even = !even;
    if (ch !== 'a' && ch !== 'b') return false;
  }
  return even;
}
console.log(acceptsEvenA('abba'));
console.log(acceptsEvenA('aba'));
console.log(acceptsEvenA('abb'));
console.log(acceptsEvenA(''));
console.log(acceptsEvenA('abc'));

기대 결과: true, true, false, true, false가 차례로 출력됩니다. 입력은 abba, aba, abb, 빈 문자열, abc입니다.

몇 문자열의 실행 확인은 상태 설계 전체의 정확성 증명을 대신하지 않습니다. ‘현재 상태 E/O가 읽은 접두사의 a 개수의 홀짝과 같다’는 불변식을 유지하고 마지막에 E인지 확인하는 것이 설계 근거입니다.

자주 발생하는 오해와 교정

NFA는 모든 경로가 수용해야 하는 모델이 아니라 하나라도 수용하면 되는 모델입니다. DFA의 전이는 모든 상태·알파벳 입력쌍에 정의합니다. DFA에서 빈 문자열 수용 여부는 시작 상태가 수용 상태인지에 달려 있습니다.

직접 풀어볼 문제와 해설

쉬운 개념

DFA는 현재 상태와 입력 문자 하나에 대해 다음 상태가 정확히 하나입니다. 문자열을 끝까지 읽었을 때 수용 상태인지 확인하며, 빈 문자열은 시작 상태 그대로 판정합니다.

단계별 예제

1. 알파벳 {a,b}에서 b의 개수가 홀수인 문자열을 받는 DFA를 만듭니다.
2. 상태 E는 지금까지 b가 짝수 번, O는 홀수 번 나온 상태입니다. 시작 E, 수용 O입니다.
3. a를 읽으면 상태를 유지하고 b를 읽으면 E↔O로 바꿉니다.

직접 풀 문제

이 DFA는 aba, abba, 빈 문자열 ε를 각각 수용하나요? 상태 이동을 적으세요.

정답·해설 보기

1. aba: E→E→O→O이므로 수용합니다. b가 한 번입니다.
2. abba: E→E→O→E→E이므로 거절합니다. b가 두 번입니다.
3. ε: 이동 없이 E에 있으므로 거절합니다. 시작 상태 E가 수용 상태가 아니기 때문입니다.

다음 학습

다음 필수 과정인 자료구조에서 그래프·집합·상태 표현을 자료 저장 구조에 연결합니다. 다음 글 읽기

학습 완료 체크리스트

• 정의의 적용 범위와 기호를 말로 설명할 수 있습니다.
• 위 손풀이를 답을 가린 상태에서 다시 계산합니다.
• 반례가 어떤 조건을 어기는지 설명합니다.

알고리즘 수학 노트

누적 이전 체크포인트: discrete-step-12-number-theory. 아래는 이번 회차의 완성 예시입니다. 자신의 다른 예제 하나를 덧붙여도 좋습니다.

상태는 집합 Q, 입력은 집합 Σ, 전이는 곱집합 위 함수, 그림은 방향 그래프입니다. 앞 회차 개념을 한 모델로 연결합니다. 최종 노트에는 01명제·02집합·03증명·04관계·05함수·06부울·07계수·08행열·09행렬·10그래프·11문제구분·12정수론·13전이표를 모으고, 각 항목의 정의·예제·반례·손풀이를 설명합니다. 다음 필수 과정은 자료구조이며 코딩테스트 JavaScript 리뉴얼은 보류 상태입니다.

완료 체크포인트

discrete-step-13-final

다음 학습

다음 필수 과정은 자료구조입니다. 코딩테스트 JavaScript는 관련 후속 학습이며 현재 리뉴얼이 보류되어 있습니다.