[계산이론및오토마타] 1 기본 개념과 DFA(The Basic Concepts & Deterministic Finite Accepters)

계산이론 및 오토마타 (Automata Theory & Computability)

오토마타 (Automata)

물리적인 하드웨어가 아닌 추상적인 계산 모델을 의미한다. “어떤 상태에서 특정 입력을 받으면 다음 상태로 어떻게 전이하는가?”에 대한 수학적 논리 구조를 다룬다

오토마타를 도구로 삼아 계산 이론에서는 크게 다음 세 가지 분야를 탐구한다

• 오토마타 이론 (Automata Theory): 다양한 계산 모델의 종류와 그 특징을 연구
• 가해성 이론 (Computability Theory): “어떤 문제가 컴퓨터(알고리즘)로 풀릴 수 있는가?”를 판별
• 복잡도 이론 (Complexity Theory): 문제를 푸는 데 시간이나 메모리 같은 자원이 얼마나 소모되는가를 분석

---

1. 언어 (Language)

계산 이론에서 언어를 정의하기 위해서는 먼저 알파벳(Alphabet)과 문자열(String)의 개념을 명확히 해야 한다

1.1 알파벳 (Alphabet, $\Sigma$)

알파벳 정의

더 이상 쪼갤 수 없는 기호들의 유한한 집합이다. 기호 $\Sigma$로 표기하며, 집합은 비어있지 않아야 하고 원소의 개수는 유한해야 한다

• 예시 1: 영문 소문자 알파벳 $\Sigma =\{a,b,c,\dots ,z\}$
• 예시 2: 이진 알파벳 $\Sigma =\{0,1\}$

알파벳의 확장 연산 알파벳 $\Sigma$를 이용해 만들 수 있는 모든 문자열의 집합을 정의할 수 있습니다.

• 클레이니 스타 (Kleene Star, ${\Sigma }^{\ast }$): 알파벳 $\Sigma$로 만들 수 있는 길이가 0 이상인 모든 문자열의 집합
  • 특징: 반드시 빈 문자열($ϵ$ 또는 $\lambda$)을 포함하는 무한 집합입니다.
  • 예시: $\Sigma =\{0,1\}$ 이면, ${\Sigma }^{\ast }=\{\lambda ,0,1,00,01,10,11,000,\dots \}$
• 양의 폐쇄 (Positive Closure, ${\Sigma }^{+}$): ${\Sigma }^{\ast }$에서 빈 문자열을 제외한 집합
  • 정의: ${\Sigma }^{+}={\Sigma }^{\ast }-\{\lambda \}$ (길이가 최소 1 이상인 문자열만 포함)
  • 예시: $\Sigma =\{0,1\}$ 이면, ${\Sigma }^{+}=\{0,1,00,01,10,11,\dots \}$

1.2 문자열 (String, $w$)

문자열 정의

알파벳 집합에서 선택한 기호들을 순서대로 나열한 유한한 수열이다

• 길이 (Length, $|w|$): 문자열에 포함된 기호의 총 개수 (예: $w=abba$ 이면 $|w|=4$)
• 빈 문자열 (Empty String, $ϵ$ 또는 $\lambda$): 기호가 하나도 없는 문자열. 길이는 $0$이다
• 연접 (Concatenation): 두 문자열을 순서대로 이어 붙이는 연산 (예: $x=apple$, $y=pie$ 이면 $xy=applepie$)
• 반전 (Reverse, $w^R$): 문자열의 순서를 완전히 뒤집은 문자열 (예: $w=abcd$ 이면 $w^R=dcba$)

문자열의 부분 구조(Substring) 문자열 $w$ 내부에 포함된 조각들을 지칭하는 용어이다(예시 기준: $w=apple$)

• 접두사 (Prefix): 문자열의 앞부분부터 시작하는 부분 문자열 (예: $ϵ,a,ap,app,appl,apple$)
• 접미사 (Suffix): 문자열의 뒷부분으로 끝나는 부분 문자열 (예: $e,le,ple,pple,apple,ϵ$)
• 부분 문자열 (Substring): 문자열 내부에 연속적으로 나타나는 모든 조각 (Prefix와 Suffix 모두 Substring에 포함된다)

문자열의 거듭제곱 ($w^n$) 문자열을 자기 자신과 여러 번 연접하는 연산입니다.

• $w^0=\lambda$: 어떤 문자열이든 0번 반복하면 빈 문자열이 됩니다.
• $w^1=w$: 1번 반복은 자기 자신입니다.
• $w^2=ww$: 2번 반복
• $w^n=w^{n-1}w$: $n$번 반복한 결과

1.3 언어 (Language, $L$)

언어 정의

알파벳 $\Sigma$로부터 만들어지는 모든 가능한 스트링의 집합 ${\Sigma }^{\ast }$의 임의의 부분집합이다. 언어는 일반적으로 무한한 크기를 가진다

• 문장 (Sentence): 언어 $L$에 포함되어 있는 각각의 스트링 $w\in L$을 뜻한다
• 예시: ${\Sigma }^{\ast }=\{\lambda ,a,b,aa,ab,\dots \}$ 일 때, 언어 $L=\{a,aa,aab\}$ 일 수 있다

언어의 주요 연산 언어는 집합이므로 일반적인 집합 연산 외에도 문자열의 특성을 반영한 고유 연산이 존재한다

연산 종류	기호	정의 및 설명
여집합	$\bar{L}={\Sigma }^{\ast }-L$	전체 가능한 문자열 집합에서 $L$에 속한 것을 제외한 나머지
역어	$L^R=\{w^R:w\in L\}$	언어 $L$에 속한 모든 스트링의 순서를 뒤집은 집합
결합	$L_1{L}_2$	두 언어의 원소를 순서대로 이어 붙여 만든 모든 문자열의 집합
거듭제곱	$L^n$	언어 $L$을 $n$번 결합한 집합. ($L^0=\{\lambda \}$ 이며, 공집합 $\varnothing$과는 다름)
클레이니 스타	$L^{\ast }=L^0\cup L^1\cup L^2\dots$	언어 $L$을 0번 이상 무한히 결합한 합집합
양의 폐쇄	$L^{+}=L^{+}{L}^1\cup L^2\cup L^3\dots$	$L$을 1번 이상 결합한 합집합 ($L^{\ast }-\{\lambda \}$와 유사)

---

2. 문법 (Grammar, $G$)

문법 정의

언어의 구조를 정의하고 문장을 생성해내는 규칙의 집합이다. 수학적으로는 4-튜플 $G=(V,T,S,P)$로 정의한다

문법의 4가지 구성 요소

• $V$ (Variables): 문장을 만드는 과정에서 임시로 사용하는 중간 매개체 (Non-terminals)
• $T$ (Terminal symbols): 최종적으로 생성된 문장에 나타나는 실제 기호들
• $S$ (Start variable): 유도 과정을 시작하는 단 하나의 시작 기호 ($S\in V$)
• $P$ (Productions): 변수를 다른 변수나 터미널로 변환하는 생성 규칙

유도 (Derivation)

• $\Rightarrow$ (Yields): 단계를 한 번 거쳐 변환됨
• $\stackrel{\ast }{\Rightarrow }$ (Derives): 0번 이상의 단계를 거쳐 최종적으로 변환됨
• 문장 형태 (Sentential Form): 유도 과정 중에 나타나는 기호들의 혼합 형태 (변수 $V$와 터미널 $T$가 섞여 있을 수 있음)
• 문장 (Sentence): 유도가 완료되어 터미널 기호($T$)로만 구성된 최종 결과물

문법 $G$가 생성하는 언어 $L(G)$

$L(G)=\{w\in T^{\ast }:S\stackrel{\ast }{\Rightarrow }w\}$ 생성 규칙을 따라 시작 기호 $S$에서 출발하여, 변수가 하나도 남지 않을 때까지 치환해서 만들 수 있는 모든 유효한 문자열의 집합을 의미한다 (동일한 언어 $L$을 생성하더라도 이를 기술하는 문법 $G$는 여러 개 존재할 수 있다)

문법 설계 예시

예시 1: $L=\{a^n{b}^{n+1}:n\ge 0\}$ (설명: $a$의 개수보다 $b$의 개수가 항상 1개 더 많은 문자열의 집합)

• 생성 규칙 ($P$):
  • $S\to Ab$ (마지막에 $b$를 하나 추가하여 $+1$ 조건을 맞춤)
  • $A\to aAb\mid \lambda$ ($a$와 $b$를 양쪽에 동시 생성하여 $n$개의 개수를 동일하게 맞춤)

예시 2: $n_a(w)=n_b(w)$ (설명: 순서에 상관없이 $a$와 $b$의 개수가 동일한 문자열의 집합)

• 생성 규칙 ($P$):
  • $S\to SS$ (두 개의 균형 잡힌 문자열 결합)
  • $S\to aSb$ (바깥에 $a$와 $b$를 두고 안쪽 유지)
  • $S\to bSa$ (바깥에 $b$와 $a$를 두고 안쪽 유지)
  • $S\to \lambda$ (재귀 종료 조건)

---

3. DFA (Deterministic Finite Accepters)

DFA (결정적 유한 인식기)

입력받은 스트링이 특정 언어에 속하는지(Accept) 아닌지(Reject)를 판별하는 가장 단순하고 결정적인 형태의 상태 기계 모델이다

DFA의 수학적 정의 DFA $M$은 5-튜플 $M=(Q,\Sigma ,\delta ,q_0,F)$로 정의됩니다.

• $Q$ (Set of states): 시스템이 가질 수 있는 모든 유한한 상태들의 집합
• $\Sigma$ (Input alphabet): 입력 가능한 기호들의 유한 집합
• $\delta$ (Transition function): (핵심) 현재 상태에서 특정 입력 기호를 받았을 때 다음 상태로 이동하는 규칙($\delta :Q\times \Sigma \to Q$)
• $q_0$ (Initial state): 단 하나만 존재하는 시작 상태 ($q_0\in Q$)
• $F$ (Final states): 기계가 문장을 수락(Accept)하는 수락 상태들의 집합 ($F\subseteq Q$)

3.1 DFA의 표현 방식

1. 상태 전이 그래프 (Transition Graph) 사람이 시각적으로 이해하기 쉬운 방식이다

• 노드(Node): 상태($Q$)
• 에지(Edge): 기호에 따른 전이 함수($\delta$) 화살표
• 이중 원: 수락 상태($F$)
• 빈 화살표(Entry): 시작 상태($q_0$)를 지칭
• Trap State (Dead State): 한 번 들어가면 절대 수락 상태로 빠져나올 수 없는 상태. 문제의 조건을 어기는 스트링을 처리(Reject)하기 위해 사용되며, 모든 입력에 대해 자기 자신으로 루프를 돈다

2. 상태 전이표 (Transition Table) 컴퓨터가 처리하기 쉽도록 그래프를 행렬 형태로 표현한 방식입니다.

현재 상태	입력 0	입력 1
$\to q_0$	$q_0$	$q_1$
$q_1$	$q_0$	$q_2$
$\ast q_2$	$q_2$	$q_1$
(참고: 보통 표에서 시작 상태는 화살표($\to$), 수락 상태는 별표($\ast$) 등으로 표기합니다.)

3.2 확장 전이 함수와 DFA의 언어

델타 스타 (${\delta }^{\ast }$) 노테이션 $\delta$가 기호 단 한 개에 대한 상태 이동이라면, ${\delta }^{\ast }$는 문자열 전체를 순차적으로 읽었을 때의 최종 이동 결과를 의미한다

• 정의: ${\delta }^{\ast }(q,w)$는 상태 $q$에서 시작해 문자열 $w$를 전부 읽었을 때 최종적으로 도달해 있는 상태이다
• 예시: ${\delta }^{\ast }(q_0,11)=\delta (\delta (q_0,1),1)$

DFA가 인식하는 언어 $L(M)$ DFA $M$이 수락(Accept)하는 언어 집합은 다음과 같이 정의된다

$L(M)=\{w\in {\Sigma }^{\ast }:{\delta }^{\ast }(q_0,w)\in F\}$ 즉, 시작 상태 $q_0$에서 문자열 $w$를 끝까지 읽었을 때, 마지막에 멈춘 상태가 수락 상태 집합 $F$에 포함되면 그 문자열은 해당 언어의 문장으로 인정받는다

---

4. 정규 언어 (Regular Language)

정규 언어의 정의

어떤 언어 $L$을 완벽하게 인식할 수 있는 DFA가 적어도 하나 이상 존재한다면, 그 언어 $L$을 ‘정규 언어(Regular Language)‘라고 부른다

조건: $L\text{ is regular}⟺\exists \text{ DFA }M\text{ such that }L=L(M)$

아무리 규칙이 복잡해 보이는 언어라도, 그것을 판별해 내는 유한 상태 기계(DFA)를 그려낼 수 있다면 그 언어는 수학적으로 ‘정규 언어’로 분류된다