Automata

컴퓨터 과학과 수학에서 계산 과정을 이해하고 설계하며 분석하기 위해 사용하는 수학적 모델이다. 이는 형식 언어와 계산 이론의 기초를 이루는 중요한 개념이다.
오토마타는 이론적 연구뿐만 아니라, 실제 컴퓨터 시스템 설계와 분석에도 필수적인 도구로 사용할 수 있다.

Definition

오토마타는 입력 문자열을 받아들이거나 거부하는 형식적인 계산 장치를 나타내며, 계산 및 문제 해결 과정을 추상적으로 모델링한 것이다.

Elements

1. 상태(State)

   • 시스템이 특정 시점에 있는 상태를 나타내며, 유한하거나 무한한 상태 집합으로 구성된다.

2. 입력 알파벳(Input Alphabet)

   • 기계가 처리할 수 있는 기호(문자)들의 집합이다.

3. 전이 함수(Transition Function)

   • 현재 상태와 입력 기호에 따라 다음 상태를 결정하는 함수이다.

4. 초기 상태(Start State)

   • 계산이 시작되는 상태이다.

5. 종료 상태(Accept or Reject States)

   • 입력을 받아들이거나 거부하는 상태이다.

Types

1. 유한 상태 기계(Finite Automata)

   • 상태가 유한한 개수로 제한되는 계산 모델이다.
   • 형식 언어와 문법 분석에 사용되며, 다음과 같은 두 가지 유형이 있다.
     • DFA(Deterministic Finite Automaton): 한 입력에서 하나의 상태로만 전이하는 유한 상태 기계이다.
     • NFA(Nondeterministic Finite Automaton): 한 입력에서 여러 상태로 전이할 수 있는 유한 상태 기계이다.

2. 스택 오토마타(Pushdown Automata)

   • 유한 상태 기계에 스택이 추가된 모델로, 문맥 자유 문법(Context-Free Grammar)을 처리할 수 있다.

3. 튜링 기계(Turing Machine)

   • 계산 가능한 모든 것을 처리할 수 있는 가장 강력한 오토마타 모델이다.
   • 무한 테이프를 사용하여 계산한다.

4. 선형 한정 오토마타(Linear Bounded Automaton)

   • 테이프 길이가 제한된 튜링 기계이다.

Applications

• 형식 언어와 컴파일러 설계
  • 프로그래밍 언어의 문법 확인 및 구문 분석에 사용된다.
• 정규 표현식과 검색 알고리즘
  • 문자열 검색 및 패턴 매칭에 활용된다.
• 인공지능과 로봇 공학
  • 유한 상태 기계를 기반으로 한 제어 논리 설계에 응용된다.
• 네트워크 통신 및 프로토콜 설계
  • 통신 프로토콜의 상태 기반 모델링에 사용된다.

Reference

[1] Michael Sipser, Introduction to the Theory of Computation
[2] John E. Hopcroft, et al., Automata Theory, Languages, and Computation"
[3] Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation
[4] Wikipedia