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

계산이론및 오토마타

오토마타

추상적인 계산 모델을 의미한다. 물리적인 하드웨어가 아니라, “이런 상태에서 이런 입력을 받으면 다음 상태로 넘어간다”는 수학적 논리 구조를 공부한다

계산이론

오토마타를 도구로 삼아 다음 세 가지를 탐구한다

• 오토마타 이론: 계산 모델의 종류와 특징 연구
• 가해성 이론 (Computability): 어떤 문제가 컴퓨터로 풀릴 수 있는가?
• 복잡도 이론 (Complexity): 문제를 푸는 데 자원(시간, 메모리)이 얼마나 드는가?

언어

언어라는 것은 먼저 alphabet과 string을 정의 해야 한다

알파벳

알파벳(Alphabet, $\Sigma$)

알파벳은 더 이상 쪼갤 수 없는 기호들의 유한한 집합이다. 보통 시그마($\Sigma$)로 표시한다. 집합은 비어있지 않아야 하며, 원소의 개수가 유한해야 한다

예시:

• 영문 소문자 알파벳: $\Sigma =\{a,b,c,...,z\}$
• 이진 알파벳: $\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 }$에서 빈 문자열만 뺀 집합입니다. 즉, 길이가 최소 1 이상인 문자열들만 모은 것이다
  • ${\Sigma }^{\ast }-\{\lambda \}$
  • 예시: $\Sigma =\{0,1\}$ 이면, ${\Sigma }^{+}=\{0,1,00,01,10,11,\dots \}$

문자열

문자열(String, $w$)

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

개념

• 길이(Length, $|w|$): 문자열에 포함된 기호의 개수이다
  • 예: $w=a,b,b,a$ 이면 $|w|=4$
• 빈 문자열(Empty String, $ϵ$ 또는 $\lambda$): 기호가 하나도 없는 문자열입니다. 길이는 $0$이다
• 연접(Concatenation): 두 문자열을 이어 붙이는 연산이다
  • 예: $x=apple,y=pie$ 이면 $xy=applepie$
• 반전(Reverse, $w^R$): 문자열을 뒤집은 문자열이다
  • 예: $w=a,b,c,d$ 이면 $w^R=d,c,b,a$

문자열의 부분 구조(Substring) 문자열 $w$가 있을 때, 그 안에 포함된 마디들을 어떻게 부르는지에 대한 정의이다

• Prefix (접두사): 문자열의 앞부분부터 시작하는 부분 문자열이다
  • 예: $w=apple$ 일 때, Prefix는 $ϵ,a,ap,app,appl,apple$입니다. (빈 문자열 $ϵ$도 항상 포함된다)
• Suffix (접미사): 문자열의 뒷부분으로 끝나는 부분 문자열이다
  • 예: $w=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$번 반복한 결과이다

언어

언어

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

예: ${\Sigma }^{\ast }=\{\lambda ,a,b,aa,ab,\dots \}$ 일 때, $L=\{a,aa,aab,...\}$

문장(Sentence): 언어 $L$에 포함되어 있는 각각의 스트링 $w\in L$을 그 언어의 문장이라고 부른다

언어의 주요 연산 언어는 집합이므로 일반적인 집합 연산 외에도 언어 특유의 연산이 존재한다

연산 종류	기호	정의 및 설명
여집합	$\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 \}$ (공집합과 다르다)
클레이니 스타	$L^{\ast }=L^0\cup L^1\cup L^2\dots$	0번 이상의 결합이다
양의 폐쇄	$L^{+}=L^{+}{L}^1\cup L^2\cup L^3\dots$	$L^{\ast }-\lambda$와 유사하다

문법(Grammar, $G$)

문법

문법은 언어의 구조를 정의하는 규칙의 집합이다. 수학적으로는 $G=(V,T,S,P)$로 정의한다

문법의 구성 요소: $G=(V,T,S,P)$

• $V$ (Variables): 문장을 만드는 과정에서 사용하는 중간 매개체이다
• $T$ (Terminal symbols): 최종적으로 생성된 문장에 나타나는 기호이다
• $S$ (Start variable): 시작 기호이다
• $P$ (Productions): 변수를 어떻게 변환할지 정의하는 규칙이다

데리베이션(Derivation, 유도)

• $\Rightarrow$ (Yields): 한 단계를 거쳐 변환한다
• $\stackrel{\ast }{\Rightarrow }$ (Derives): 0번 이상의 단계를 거쳐 변환한다 (여러 단계의 과정을 축약)
• 문장 형태 (Sentential Form): 유도 과정 중에 나타나는 모든 형태이다 (변수와 터미널의 혼합)
• 문장 (Sentence): 터미널 기호($T$)로만 구성된 최종 결과물이다

문법 $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$의 개수가 항상 하나 더 많은 구조이다

• 생성 규칙(P):
  • $S\to Ab$ (마지막에 $b$ 하나를 추가하여 균형을 맞춤)
  • $A\to aAb\mid \lambda$ ($a$와 $b$를 동시에 생성하여 개수를 맞춤)

예시 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$ (종료 조건)

DFA(Deterministic Finite Accepters)

DFA

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

DFA의 수학적 정의 DFA, $M$은 다음과 같이 5개의 요소로 정의된다

$M=(Q,\Sigma ,\delta ,q_0,F)$

• $Q$ (Set of all states): 시스템이 가질 수 있는 모든 상태들의 유한 집합
• $\Sigma$ (Input alphabet): 입력 가능한 기호들의 유한 집합
• $\delta$ (Transition function): 가장 중요한 요소. 현재 상태에서 입력 기호를 받았을 때 다음 상태로 가는 규칙 ($\delta :Q\times \Sigma \to Q$)
• $q_0$ (Initial state): 시작 상태($q_0\in Q$, 단 하나만 존재)
• $F$ (Final states): 수락 상태들의 집합($F\subseteq Q$, 여러 개일 수 있음)

표현 방식

사람이 이해하기 쉬운 그래프 방식과 컴퓨터가 처리하기 쉬운 표 방식이 있다

상태 전이 그래프(Transition Graph)

• 노드(Node): 상태($Q$)를 나타냄
• 에지(Edge): 전이 함수($\delta$)를 나타냄
• 이중 원: 수락 상태($F$)를 표시
• 화살표(Entry): 시작 상태($q_0$)를 표시
• Trap State(Dead State): 한 번 들어가면 절대로 수락 상태로 갈 수 없는 상태를 말한다
  • 모든 입력 기호에 대해 자신으로 되돌아오는 루프를 가진다
  • 문제 조건을 어기는 스트링이 들어왔을 때 이를 Reject 처리하기 위해 사용한다다

상태 전이표(Transition Table) 그래프를 행렬 형태로 표현한 것이다

현재 상태	입력 0	입력 1
$q_0$	$q_0$	$q_1$
$q_1$	$q_0$	$q_2$
$q_2$	$q_2$	$q_1$

확장 전이 함수와 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$이 수락하는 언어는 다음과 같이 정의된다

$L(M)=\{w\in {\Sigma }^{\ast }:{\delta }^{\ast }(q_0,w)\in F\}$ 즉, 시작 상태에서 스트링 $w$를 따라갔을 때 마지막에 도착한 곳이 수락 상태($F$)에 포함되면 그 스트링은 이 언어의 멤버이다

정규 언어(Regular Language)

정규 언어

어떤 언어 $L$이 정규 언어라는 것은, 그 언어를 인식할 수 있는 유한 오토마타가 적어도 하나 존재한다는 것을 의미한다 $L$ is regular $⟺$ there exists a DFA $M$ such that $L=L(M)$

특징: 복잡한 언어라도 DFA로 표현 가능하다면 그것은 정규 언어이디