본문으로 건너뛰기

Modeling Computation

Discrete Mathematics and its Applications · Kenneth H. Rosen · Ch. 12

Intuition

컴퓨터가 무엇을 할 수 있고(가해성), 어떻게 할 것인지(알고리즘)를 정의하기 위해 추상적인 수학적 모델인 문법과 기계를 구축한다.

One-liner​

문법, 유한 상태 기계, 튜링 기계라는 세 가지 계층적 구조를 통해 언어를 생성 및 인식하고 계산의 한계를 규명한다.

Prerequisites​

Goals​

  • 형식 언어를 생성하는 문법의 구성 요소를 정의하고 촘스키 계층(Chomsky Hierarchy)을 분류한다.
  • 유한 상태 기계(FSM)의 출력 유무에 따른 동작 차이를 이해하고 상태도(State Diagram)를 작성한다.
  • 결정적 유한 오토마타(DFA)와 비결정적 유한 오토마타(NFA)의 등가성을 파악한다.
  • 정규 집합과 정규 표현식, 그리고 이를 인식하는 오토마타 사이의 관계(클레이니의 정리)를 이해한다.
  • 튜링 기계의 정의와 계산 능력, 그리고 P-NP 문제 및 가해성(Decidability)의 기초를 학습한다.

Core Concepts​

12.1 Languages and Grammars (언어와 문법)​

Definition

Phrase-Structure Grammar (구구조 문법) G=(V,T,S,P)G = (V, T, S, P)는 다음 네 요소로 구성된다.

  • VV (Vocabulary): 기호들의 유한 집합
  • TT (Terminals): 최종 문자열을 구성하는 종단 기호들의 집합 (T⊂VT \subset V)
  • SS (Start Symbol): 생성을 시작하는 시작 기호 (S∈V−TS \in V-T)
  • PP (Productions): 문자열의 치환 규칙 집합 (z0→z1z_0 \rightarrow z_1)
  • Derivation (유도): 규칙 PP를 적용하여 시작 기호 SS로부터 문자열 ww를 만들어내는 과정이다.
  • Language (언어) L(G)L(G): 문법 GG에 의해 유도될 수 있는 모든 종단 기호 문자열의 집합이다.
  • Chomsky Hierarchy (촘스키 계층): 생성 규칙에 가해지는 제약에 따라 언어를 4단계(Type 0~3)로 분류한다.
    • Type 2 (Context-Free): 프로그래밍 언어의 구문을 정의하는 데 주로 사용된다.
    • Type 3 (Regular): 가장 제약이 많으며 유한 오토마타로 인식이 가능하다.

12.2 Finite-State Machines with Output (출력이 있는 유한 상태 기계)​

Definition

Finite-State Machine (유한 상태 기계) M=(S,I,O,f,g,s0)M = (S, I, O, f, g, s_0)는 다음으로 정의된다.

  • SS: 유한 상태 집합
  • II: 입력 알파벳
  • OO: 출력 알파벳
  • ff: 전이 함수 (S×I→SS \times I \rightarrow S)
  • gg: 출력 함수 (S×I→OS \times I \rightarrow O)
  • s0s_0: 초기 상태
  • Mealy Machine: 출력이 현재 상태와 입력 모두에 의해 결정되는 모델이다.
  • Moore Machine: 출력이 오직 현재 상태에 의해서만 결정되는 모델이다.

12.3 Finite-State Machines with No Output (출력이 없는 유한 상태 기계)​

Definition

Finite-State Automaton (유한 상태 오토마타) M=(S,I,f,s0,F)M = (S, I, f, s_0, F)는 출력 대신 Final States (최종 상태) F⊆SF \subseteq S를 가진다. 입력 문자열을 모두 처리했을 때 기계가 최종 상태에 도달하면 해당 문자열을 Recognize (인식)한다고 한다.

  • Deterministic Finite-State Automaton (DFA): 모든 (상태, 입력) 쌍에 대해 다음 상태가 유일하게 결정된다.
  • Nondeterministic Finite-State Automaton (NFA): 하나의 (상태, 입력) 쌍에 대해 여러 개의 다음 상태가 가능하거나 없을 수 있다.

12.4 Language Recognition (언어 인식)​

  • Regular Sets (정규 집합): 공집합, 빈 문자열, 단일 기호로부터 합집합, 연접(Concatenation), 클레이니 폐쇄(Kleene Closure, A∗A^*) 연산을 통해 만들어지는 집합이다.
  • Kleene's Theorem (클레이니의 정리): 한 집합이 정규 집합일 필요충분조건은 유한 상태 오토마타에 의해 인식되는 것이다.

12.5 Turing Machines (튜링 기계)​

Definition

Turing Machine (튜링 기계) T=(S,I,f,s0)T = (S, I, f, s_0)는 무한한 테이프와 읽기/쓰기 헤드를 가진 모델이다. 부분 함수 f:S×I→S×I×{R,L}f: S \times I \rightarrow S \times I \times \{R, L\}를 통해 다음 상태, 테이프에 쓸 기호, 헤드의 이동 방향을 결정한다.

  • Church-Turing Thesis: "효과적인 알고리즘으로 계산 가능한 모든 문제는 튜링 기계로 계산할 수 있다"는 가설이다.
  • Halting Problem (정지 문제): 주어진 튜링 기계가 특정 입력에 대해 정지할지 여부를 판별하는 알고리즘은 존재하지 않는다(Unsolvable).

Notation​

기호의미
V∗V^*VV의 기호들로 만들 수 있는 모든 유한 길이 문자열의 집합
λ\lambda빈 문자열 (Null string)
w0⇒w1w_0 \Rightarrow w_1w0w_0에서 w1w_1이 직접 유도됨
L(M)L(M)기계 MM이 인식하는 언어
P,NPP, NP결정적/비결정적 다항 시간 내에 해결 가능한 문제의 클래스

Key Theorems & Formulas​

Theorem (Kleene's Theorem)

조건: 언어 LL이 정규 표현식으로 표현될 수 있는 정규 집합이다.

결론: LL을 인식하는 유한 상태 오토마타(DFA 또는 NFA)가 반드시 존재한다. (반대의 경우도 성립한다.)

Theorem (DFA와 NFA의 등가성)

조건: 언어 LL이 비결정적 유한 오토마타(NFA)에 의해 인식된다.

결론: LL을 인식하는 결정적 유한 오토마타(DFA)가 항상 존재한다.

Theorem (Pumping Lemma)

내용: 정규 언어는 일정 길이 이상의 문자열에 대해 특정 부분을 반복(Pumping)해도 여전히 그 언어에 속해야 한다. 이 정리는 특정 언어가 정규 언어가 아님을 증명할 때 사용된다.

Intuitions​

  • FSM의 기억력: 유한 상태 기계의 "기억"은 오직 현재 도달한 상태에 저장된다. 따라서 상태의 개수가 유한하다는 것은 기억 장치가 제한적임을 의미한다. (p.785)
  • 비결정성의 의미: NFA는 여러 가능성 중 하나라도 최종 상태에 도달하면 성공으로 간주한다. 이는 "완벽한 추측"을 할 수 있는 능력을 모델링한 것과 같다. (p.812)
  • 튜링 기계와 테이프: 튜링 기계의 핵심은 무한한 테이프(외부 메모리)를 통해 이전 계산 결과를 기록하고 다시 읽을 수 있다는 점에 있다. 이는 유한 오토마타가 가진 메모리 한계를 극복하게 한다. (p.828)

Worked Examples​

Example 1: 정규 문법을 이용한 언어 생성​

문제: S→0S,S→1A,S→λ,A→1A,A→1S \rightarrow 0S, S \rightarrow 1A, S \rightarrow \lambda, A \rightarrow 1A, A \rightarrow 1 규칙을 가진 문법이 생성하는 언어는?

핵심 단계:

  1. SS 규칙은 문자열 앞에 0을 임의 개수만큼 붙일 수 있게 한다.
  2. S→1AS \rightarrow 1A와 A→1A,A→1A \rightarrow 1A, A \rightarrow 1은 0 이후에 최소 한 개 이상의 1이 나오도록 강제한다.
  3. S→λS \rightarrow \lambda는 빈 문자열을 허용한다.

요점: 결과적으로 이 언어는 {0m1n∣m≥0,n≥0}\{0^m 1^n \mid m \ge 0, n \ge 0\} 형태의 문자열을 생성한다. (p.789)

Example 2: 자판기 모델링 (FSM with Output)​

문제: 5, 10, 25센트 동전을 받아 30센트가 되면 음료를 선택할 수 있는 기계를 설계하라.

핵심 단계:

  1. 상태 sis_i를 현재까지 투입된 금액 5i5i센트로 정의한다 (i=0i=0 to 66).
  2. 30센트 이상 투입 시 초과분은 반환(Output)하고 상태 s6s_6에 머문다.
  3. 버튼 입력(O/R) 시 제품을 출력하고 초기 상태 s0s_0로 복귀한다.

요점: 상태 전이는 투입 금액의 누적을 "기억"하는 역할을 한다. (p.797)

Common Pitfalls​

Pitfall

비어 있음의 구분: 빈 문자열 λ\lambda와 공집합 ∅\emptyset은 다르다. {λ}\{\lambda\}는 빈 문자열을 하나 포함하는 집합이지만, ∅\emptyset은 원소가 아예 없는 집합이다. (p.787)

Pitfall

문맥 자유 vs 정규: {0n1n∣n≥0}\{0^n 1^n \mid n \ge 0\}은 문맥 자유(Type 2) 언어이지만 정규(Type 3) 언어는 아니다. 유한 오토마타는 0의 개수를 "세어서 기억"할 수 없기 때문이다. (p.824)

Connections​

  • 선행 개념: Ch. 2 집합과 함수, Ch. 8 관계 (동치 관계·폐쇄), Ch. 9 그래프 (전이도 작성 시 활용), Ch. 11 부울 대수 (조합 회로는 상태가 없는 계산 모델).
  • 후속 개념: 컴파일러 설계(어휘 분석 및 구문 분석), 알고리즘의 시간 복잡도 이론(PP vs NPNP) — Ch. 3의 정지 문제와 직접 연결됨.
  • 응용 분야: 자연어 처리, 하드웨어 회로 설계, 네트워크 프로토콜 검증.

Critical Notes​

교재가 강조하는 것

  • 언어의 구문(Syntax)과 의미(Semantics)의 분리. (p.785)
  • 결정적 모델과 비결정적 모델의 수학적 동등성 증명.
  • 계산의 한계(Unsolvable problems)에 대한 인식.

실제로 중요한 것

  • DFA 최소화: 효율적인 시스템 설계를 위해 상태 수를 줄이는 과정이 실무적으로 중요하다. (p.810)
  • BNF 표기법: 프로그래밍 언어 사양서(Java, SQL 등)를 읽기 위해 반드시 숙지해야 하는 도구이다. (p.792)

교재가 생략하거나 얼버무리는 것

  • 튜링 기계의 복잡한 계산 과정(곱셈 등)은 매우 방대하여 예시로만 갈음하고 상세 구현은 생략되어 있다. (p.832)