Free Forum

오토마타론 계층 구조

오토마타 이론과 컴파일러 이론의 체계적 정리

오토마타 이론 기호 정리

공통 기호

q₀, q₁, q₂...: 상태 (q₀은 시작 상태)

qf, F: 최종/수락 상태

○: 일반 상태 (원)

◎: 최종 상태 (이중원)

→: 상태 전이

⟲: 자기 자신으로 돌아오는 전이

ε (엡실론): "아무것도 안 함" 또는 "빈 문자열"

FSM 전용 기호

q₀ --a--> q₁    // 'a' 읽기로 q₀에서 q₁로 전이

PDA 전용 기호

읽기, 팝/푸시

a, ε/A         // 'a' 읽고, 팝 안 하고, 'A' 푸시

b, A/ε         // 'b' 읽고, 'A' 팝하고, 푸시 안 함

TM 전용 기호

읽은심볼/쓸심볼, 방향

a/b, R         // 'a' 읽고 'b' 쓰고 오른쪽 이동

R: 오른쪽 (Right), L: 왼쪽 (Left)

계산 모델별 능력

CL (조합논리): [논리연산(산술연산)] 순수 함수

add(3, 5) = 8  ✅

sub(add(3, 5), 2) = 6  ✅ (함수 합성으로 가능)

상태/메모리 저장  ❌

CL 예시: AND 게이트

A ────┤ |‾‾‾\

                   │ |          \

                   │ |             |──── Y = A∧B

                   │ |          /

B ────┤ |___/

FSM: [논리연산(산술연산) + 유한 상태] 패턴 인식 + 상태 기반 제어

정규 표현식 "a*b+" 매칭  ✅

균형 괄호 "((()))"  ❌ (중첩 구조 불가)

FSM 예시: 정규표현식 "a*b+" 인식

   a

q₀ ⟲

 │

 │b

 ↓

◎q₁ ⟲ b

PDA: [논리연산(산술연산) + 유한 상태 + 무한 스택] 중첩 구조 인식, 문맥자유 문법 처리

수식 구조 "((3+5)*2)+1" 파싱  ✅ (문법적 올바름 검사)

균형 괄호 "((()))" 검사  ✅

문맥자유 문법 "a^n b^n" 인식  ✅

메모리 접근 제한 ❌ (심볼 조작만)

PDA 예시: 균형 괄호 "((()))" 검사

'(', ε/(

')', (/ε

q₀ ⟲

│

│ε, Z/ε 

↓

◎qf

스택 동작:

읽기: ((()))

1. '(' → 스택: [Z, (]

2. '(' → 스택: [Z, (, (]  

3. '(' → 스택: [Z, (, (, (]

4. ')' → 스택: [Z, (, (]

5. ')' → 스택: [Z, (]

6. ')' → 스택: [Z]

스택이 비어있거나 바닥 마커만 남으면 수락

TM: [논리연산(산술연산) + 유한 상태 + 무한 테이프] 모든 계산 가능한 문제

        헤드

         ↓

... │□│1│0│1│1│0│□│ ...

    ←─────────────→

    (무한 테이프)

이론적 기본 연산: Read, Write, Move

TM 예시: palindrome "aba" 판별

실행 과정: q₀ → q₁ → q₂ → q₃ → q₀ → (가운데 문자 확인) → qf

     a/X,R          b/b,R          a/Y,L

q₀ ────────→ q₁ ──────────→ q₂ ────────→ q₃

 ↑                                        │

 │                                        │Y/Y,L, X/X,L

 │                                        ↓

 └──────── 다시 처리할 문자 찾기 ←──────── 시작으로 돌아감

 │

 │처리할 문자 없음(가운데 문자만 남음)

 ↓

◎qf

상세한 실행 과정:

읽기: "aba"

1. q₀에서 시작: [a][b][a] ^

2. 'a' 읽음 → q₁: 'a'를 'X'로 마킹 [X][b][a] ^

3. q₁에서 끝까지 이동: [X][b][a] ^ (b 통과, a까지)

4. q₂에서 끝 'a' 발견: 'a'를 'Y'로 마킹 [X][b][Y] ^

5. q₃에서 시작으로 돌아감: [X][b][Y] ^ ('Y'와 'b' 통과)

6. 다시 q₀: 'X' 발견, 다음 처리할 문자는 'b'

7. 'b'는 가운데 문자(더 매칭할 문자 없음) → qf 수락

언어 계층 대응

정규언어(RL) ↔ FSM

문맥자유언어(CFL) ↔ PDA

문맥민감언어(CSL) ↔ LBA

재귀열거언어(REL) ↔ TM

튜링 완전성

이론적 기본: Read, Write, Move (TM의 primitive operation)

실용적 구현: 논리연산(산술연산(SUBTRACT)) + 메모리 접근 + 조건문 + 분기문

어셈블리: sub, mov, cmp, jmp/je/jne

C: 논리연산(산술연산(-)), 포인터, if, goto

계산 모델의 계층적 구조

오토마타 이론 계층

CL:     논리연산(산술연산)

FSM:  논리연산(산술연산) + 유한 상태

PDA:  논리연산(산술연산) + 유한 상태 + 무한 스택

TM:    논리연산(산술연산) + 유한 상태 + 무한 테이프

메모리 구조

CL:    메모리 없음

FSM: 유한 상태

PDA: 유한 상태 + 무한 스택

TM:   유한 상태 + 무한 테이프

각 오토마타의 실제 활용 예시

FSM: 정규표현식 엔진, 네트워크 프로토콜

PDA: JSON/XML 파서, 프로그래밍 언어 구문 분석

TM: 컴파일러 최적화, 정적 분석 도구

이론적 기반

형식언어: 규칙에 맞는 모든 문자열 집합

오토마타 이론: 그 언어를 처리하는 추상기계의 능력 연구

컴파일러 이론: 오토마타 이론의 실제 구현

발전 과정

오토마타 이론 (1940-50년대 이론) → 컴파일러 이론 (1960년대 구현)

계산 모델의 두 갈래

TM (Turing Machine) ≡ LC (Lambda Calculus)

    ↓                                             ↓

C, Java, Python                 Haskell, Lisp

(명령형)                                (함수형)

Compilation Process

Source Code

→ Preprocessing (Macro processing/file inclusion) → Preprocessed Source

→ Lexical Analysis (Regular Expression/Finite State Machine/Lexer) → Tokens

→ Syntax Analysis (Context-Free Grammar/Pushdown Automaton/Parser) → Parse Tree/AST

→ Semantic Analysis (Type checking, scope analysis, semantic validation) → Annotated AST

→ Intermediate Code Generation (Generate intermediate representation) → IR (Intermediate Representation)

→ Code Optimization (IR-level optimization) → Optimized IR

→ Code Generation (Target code generation) → Target Code

→ Machine-Level Optimization (Peephole optimization, etc.) → Optimized Target Code

Cross-Process Elements

Symbol Table: Identifier information storage that is continuously referenced and updated throughout all stages

Error Handling: Error detection and reporting at each stage (Lexical Errors, Syntax Errors, Semantic Errors, Runtime Errors)

Compiler Phases

Frontend: Preprocessing → Lexical Analysis → Syntax Analysis → Semantic Analysis → IR Generation

Middle-end: Code Optimization

Backend: Code Generation → Machine-Level Optimization

Post-Compilation (External Tools)

→ Assembling (Convert assembly to machine code) → Object File

→ Linking (Combine object files, library linking) → Executable File

→ Loading (Memory loading) → Running Program

C Compilation Example

C Source Code

→ Preprocessing → Preprocessed Source

→ Lexical Analysis (FSM) → Tokens

→ Syntax Analysis (PDA) → Parse Tree/AST

→ Semantic Analysis → Annotated AST

→ Intermediate Code Generation → IR

→ Code Optimization → Optimized IR

→ Assembly Code Generation → Assembly Code

컴파일러의 실용적 가치

CS 이론의 종합: 자료구조, 알고리즘, 오토마타 이론이 모두 녹아있음

SW 개발 필수: 언어 이해도, 최적화, 디버깅 실력 향상

AI/NLP 기초: 토크나이저(FSM), 파서(PDA), 의미분석(TM) 직접 활용

취업 경쟁력: CS 기초 소양의 핵심

결론 컴파일러 이론 = 이론 CS의 실전 종합반