이 글에서 정리하는 내용
이 글에서는 오토마타 이론의 큰 흐름을 따라 유한 오토마타, 문자열 수락, 마르코프 연쇄, 형식 문법, 촘스키 계층을 한 번에 정리합니다. 상태 그래프를 읽는 법과 문자열 판별 방식, 문법이 언어를 생성하는 구조까지 연결해서 이해할 수 있도록 구성했습니다.
오토마타 이론은 무엇을 다루는가
오토마타 이론은 추상적인 계산 기계를 통해 어떤 문제가 계산 가능한지, 어떤 언어를 어떤 기계가 다룰 수 있는지 살펴보는 분야입니다. 계산이론 전체에서 보면 오토마타는 계산 모델의 출발점에 가깝고, 그중 유한 오토마타는 가장 단순하면서도 중요한 오토마타 모델입니다. 이 단원을 공부할 때는 개별 정의를 따로 외우기보다 어떤 오토마타가 어떤 언어를 다루는지 연결해서 보는 편이 훨씬 이해하기 쉽습니다.
튜링머신도 같은 흐름 안에 있는 모델이지만, 유한 오토마타보다 훨씬 강력한 계산 모델입니다. 튜링머신은 테이프, 헤드, 상태 기록부, 유한한 작업 표를 갖는 추상 기계로 설명되며, 여기서 중요한 포인트는 상태가 무한한 것이 아니라 유한하다는 점입니다. 시험에서는 이 부분을 혼동해서 틀리기 쉬우므로 먼저 기준을 잡아 두는 것이 좋습니다.
오토마타 이론의 큰 흐름 한눈에 보기
오토마타 이론
→ 계산 모델을 만든다
→ 문자열과 언어를 판별한다
→ 문법으로 언어를 생성한다
→ 어떤 언어가 어느 수준의 기계로 다뤄지는지 분류한다이 흐름을 먼저 머릿속에 넣어 두면 뒤에서 나오는 DFA, NFA, 형식 문법, 촘스키 계층이 따로 노는 내용처럼 보이지 않습니다. 앞부분은 언어를 인식하는 관점이고, 뒷부분은 언어를 생성하고 분류하는 관점이라고 보면 됩니다.
유한 오토마타와 상태 그래프 이해하기
유한 오토마타는 입력을 한 글자씩 읽으면서 현재 상태를 바꾸는 오토마타입니다. 핵심은 상태의 수가 유한하다는 점이며, 실제 문제에서는 이 구조를 상태 그래프로 많이 표현합니다. 원은 상태, 화살표는 입력에 따른 이동, 이중원은 수락 상태라고 생각하면 기본 틀이 잡힙니다. 즉 상태 그래프는 유한 오토마타를 눈으로 읽기 쉽게 바꾼 표현이라고 보면 됩니다.
유한 오토마타의 구성 요소를 쉬운 말로 읽기
M = (I, O, Q, f, g, σ)
I : 입력기호의 집합
O : 출력기호의 집합
Q : 상태의 집합
f : 상태 전이 함수
g : 출력 함수
σ : 초기 상태강의자료처럼 출력기호와 출력함수를 포함해 6-튜플로 소개하는 경우도 있지만, 문자열 수락을 다루는 DFA와 NFA는 보통 상태집합, 입력 알파벳, 전이함수, 시작상태, 수락상태를 중심으로 설명합니다. 따라서 처음에는 각 기호를 완벽히 외우기보다 역할 위주로 이해하는 편이 좋습니다. 입력이 들어오면 현재 상태와 입력기호를 바탕으로 다음 상태를 정하는 것이 전이 함수이고, 시작할 때 어디에서 출발하는지가 초기 상태입니다. 즉 유한 오토마타는 결국 현재 상태와 입력에 따라 반응하는 규칙표라고 볼 수 있습니다.
DFA와 NFA의 차이
DFA
현재 상태 + 입력기호가 주어지면
다음 상태가 정확히 하나로 정해진다.
NFA
현재 상태 + 입력기호가 주어졌을 때
다음 상태가 여러 개일 수도 있고 없을 수도 있다.DFA는 길을 하나만 따라가면 되기 때문에 판별 과정이 직관적입니다. 반면 NFA는 여러 갈래 가능성을 동시에 생각해야 해서 처음에는 더 복잡해 보입니다. 하지만 중요한 점은 두 모델이 다룰 수 있는 언어의 범위 자체는 같다는 것입니다. 따라서 학습 초반에는 DFA로 감각을 익히고, 그다음 NFA를 비교하는 방식이 가장 편합니다.
문자열 수락과 마르코프 연쇄
유한 오토마타를 공부할 때 가장 자주 나오는 문제는 어떤 문자열이 주어진 오토마타에 의해 수락되는지 판단하는 것입니다. 방법은 단순합니다. 초기 상태에서 출발해 문자열을 왼쪽부터 한 글자씩 읽고, 화살표를 따라 이동한 뒤 마지막 상태가 수락 상태인지 확인하면 됩니다.
문자열 수락 판단은 이렇게 따라간다
예시 문자열: 0101
초기 상태 q0에서 시작
1글자 읽을 때마다 전이 함수 적용
q0 → q1 → q2 → q2 → q3
마지막 상태 q3가 수락 상태이면 수락
수락 상태가 아니면 거부여기서 중요한 것은 중간에 어떤 상태를 거쳤는지가 아니라 입력을 모두 읽은 뒤 어디에 도착했는가입니다. 상태 그래프를 볼 줄 알아도 실제 문자열을 대입해 추적하는 연습이 부족하면 시험에서 막히기 쉬우므로, 짧은 문자열을 직접 여러 번 따라가 보는 것이 좋습니다.
마르코프 연쇄는 상태 전이에 확률이 붙은 구조다
상태: S1, S2
전이확률행렬 P =
[ 0.7 0.3 ]
[ 0.4 0.6 ]
의미
S1에 있으면 다음 단계에
S1로 갈 확률은 0.7, S2로 갈 확률은 0.3마르코프 연쇄는 현재 상태가 다음 상태의 확률을 결정하는 이산 확률 과정입니다. 유한 오토마타와 닮은 점은 둘 다 상태와 전이를 사용한다는 것이고, 차이는 마르코프 연쇄에서는 화살표마다 확률이 붙는다는 점입니다. 다시 말해 오토마타가 입력에 따라 상태를 옮기는 규칙을 본다면, 마르코프 연쇄는 확률에 따라 상태가 바뀌는 구조를 본다고 이해하면 됩니다. 그래서 이 단원에서는 상태전이도와 전이확률행렬을 함께 읽는 연습이 중요합니다.
| 비교 기준 | 핵심 차이 |
|---|---|
| 유한 오토마타 | 입력을 읽고 규칙에 따라 다음 상태로 이동하며, 마지막 상태로 수락 여부를 판단합니다. |
| 마르코프 연쇄 | 현재 상태에서 다음 상태로 이동할 확률을 사용하며, 상태 변화 자체를 확률적으로 분석합니다. |
형식 언어와 형식 문법의 기초
형식 언어는 어떤 알파벳 위에서 만들 수 있는 문자열들의 집합입니다. 여기서 중요한 것은 문장 뜻이 아니라 기호 배열 자체입니다. 프로그래밍 언어 문법이나 파서 이론을 공부할 때도 결국 이 관점이 바탕이 됩니다. 즉 언어는 문자열의 집합이고, 문법은 그 문자열들을 만들어 내는 규칙이라고 이해하면 됩니다.
자주 나오는 기호를 먼저 읽는 법
Σ : 시그마, 알파벳의 집합
Σⁿ : 시그마 엔, 길이가 n인 모든 문자열의 집합
Σ⁺ : 시그마 플러스, 길이가 1 이상인 모든 문자열의 집합
Σ＊ : 시그마 스타, 길이가 0 이상인 모든 문자열의 집합
→ : 생성 규칙 또는 전이 방향
ε : 엡실론, 빈 문자열이 파트에서 가장 먼저 막히는 이유는 내용보다 기호를 읽는 것이 낯설기 때문입니다. 특히 Σ＊는 알파벳으로 만들 수 있는 모든 문자열의 집합이라는 뜻이고, 공집합이 아니라 빈 문자열을 포함할 수 있다는 점을 같이 기억해야 합니다. Σ⁺는 빈 문자열을 제외하고 길이가 1 이상인 경우만 포함합니다.
형식 문법은 언어를 만드는 규칙표다
G = (V, T, P, S)
V : 비단말 기호의 집합
T : 단말 기호의 집합
P : 생성 규칙
S : 시작 기호
예시
S → aS | b
생성 가능 문자열: b, ab, aab, aaab, ...비단말은 아직 더 바뀔 수 있는 기호이고, 단말은 최종 문자열에 남는 기호입니다. 예를 들어 S → aS | b라는 규칙은 a를 계속 붙이다가 마지막에 b로 끝나는 문자열을 생성합니다. 따라서 문법은 문장을 분석하는 도구이기도 하지만, 처음 배우는 단계에서는 문자열을 만들어 내는 생성 장치로 보는 편이 이해하기 쉽습니다.
촘스키 계층으로 전체 구조 정리하기
촘스키 계층은 형식 언어를 문법의 제약 정도에 따라 나누는 분류 체계입니다. 제약이 강한 문법은 표현할 수 있는 언어 범위가 좁고, 제약이 느슨해질수록 더 복잡한 언어를 다룰 수 있습니다. 계산이론에서 이 분류가 중요한 이유는 각 언어 계층이 대응되는 계산 모델과 연결되기 때문입니다.
촘스키 계층은 포함 관계로 이해하는 것이 편하다
정규 언어 ⊂ 문맥 자유 언어 ⊂ 문맥 의존 언어 ⊂ 재귀 열거 언어
정규 언어 : 유한 오토마타와 연결
문맥 자유 언어 : 푸시다운 오토마타와 연결
문맥 의존 언어 : 더 강한 제약 해제
재귀 열거 언어 : 튜링머신과 연결이 파트는 이름이 비슷해서 헷갈리기 쉽습니다. 그래서 각각을 따로 외우기보다 포함 관계와 대표 예시를 함께 묶는 방식이 좋습니다. 예를 들어 정규 언어는 유한 오토마타로 처리할 수 있고, 괄호 짝 맞추기처럼 더 복잡한 구조는 문맥 자유 언어에서 다루는 식으로 범위를 넓혀 가면 정리가 잘 됩니다.
| 계층 | 핵심 연결 |
|---|---|
| 정규 언어 / 문맥 자유 언어 | 정규 언어는 DFA, NFA 같은 유한 오토마타와 연결되고, 문맥 자유 언어는 문법과 스택 구조 이해의 출발점이 됩니다. |
| 문맥 의존 언어 / 재귀 열거 언어 | 더 넓은 표현력을 가지며, 최종적으로는 튜링머신 수준의 계산 가능성과 연결됩니다. |
정리
이 장의 핵심은 서로 다른 용어를 따로 암기하는 것이 아니라 하나의 흐름으로 묶어 이해하는 것입니다. 유한 오토마타는 문자열을 판별하는 상태 기계이고, 마르코프 연쇄는 그 상태 이동을 확률적으로 본 구조이며, 형식 문법은 문자열을 생성하는 규칙 체계입니다. 마지막으로 촘스키 계층은 이 언어들과 문법, 계산 모델의 관계를 전체 지도처럼 보여 줍니다. 결국 이 글은 여러 오토마타 개념을 따로 나누기보다 계산 모델과 언어 이론의 연결로 정리하는 데 목적이 있습니다. 시험 준비를 할 때는 정의만 외우지 말고 상태 그래프 추적, 문자열 수락 판별, 간단한 문법 생성 과정을 직접 써 보면서 정리하는 방식이 가장 효과적입니다.
많이 받는 질문
Q. DFA와 NFA는 어떤 차이만 기억하면 되나요?
DFA는 현재 상태와 입력이 주어졌을 때 다음 상태가 하나로 정해지고, NFA는 여러 가능성을 둘 수 있다는 점만 먼저 기억하면 됩니다. 학습 초반에는 DFA로 상태 추적 감각을 익힌 뒤 NFA를 비교하는 편이 훨씬 쉽습니다.
Q. 문자열을 수락한다는 뜻은 정확히 무엇인가요?
초기 상태에서 시작해 문자열을 한 글자씩 모두 읽은 뒤, 마지막에 도착한 상태가 수락 상태이면 수락이라고 합니다. 중간에 수락 상태를 지나갔더라도 마지막 상태가 수락 상태가 아니면 수락으로 보지 않습니다.
Q. 형식 언어와 형식 문법은 무엇이 다른가요?
형식 언어는 문자열의 집합이고, 형식 문법은 그 문자열 집합을 만들어 내는 규칙입니다. 즉 결과물이 언어이고, 그 결과를 생성하는 방법이 문법이라고 구분하면 이해하기 편합니다.