2019년 1월 24일
유한 오토마타 (FA, Finite Automata)
I. 유한 오토마타의 개요
가. 유한 오토마타의 정의
- 컴퓨터 프로그램과 전자회로 설계 시 사용하는 이산적 입력과 출력을 가지는 시스템 모형
나. 유한 오토마타의 특징
| 단일 상태 | – 한 번에 하나의 상태만 가지는 모형 |
| 전이 | – 사건에 의해 다른 상태로 변화하는 성질 |
| 상태 | – 전이를 시작하기 위해 대기하는 행동적 노드 |
II. 유한 오토마타의 유형
가. 결정적 유한 오토마타 (DFA, Deterministic Finite Automata)
| 항목 | 설명 | |
|---|---|---|
| 정의 | – 모든 상태는 각 가능한 입력에 대해 정확히 하나의 변화된 상태를 가질 수 있는 유한 오토마타 | |
| 설명 |  | – a 입력 시 B 로 전이 – a → B, b → C 상태 전이 – 입력에 따라 상태 결정 |
| 표현 |  | |
- 컴퓨터의 효율적 활용 위해 NFA를 DFA로 변환하기도 함
나. 비결정적 유한 오토마타 (NFA, Non-Deterministic Finite Automata)
| 항목 | 설명 | |
|---|---|---|
| 정의 | – 입력은 주어진 상태에 대해 여러 가지의 변환된 상태를 가질 수 있는 유한 오토마타 | |
| 설명 |  | – a 입력 시 B 로 전이 – b 입력 시 B, C 로 전이 – 하나의 입력에 대해 여러 상태가 가능 |
| 표현 |
* 입력 기호에 e-transition에 의해 0개 이상의 이동이 가능하며, 가능한 다음 상태의 경우 없다면, 기계는 입력 거부 | |
- 어떠한 NFA 라도 동일한 기능을 가지는 DFA로 변환 가능
III. 유한 오토마타 활용 분야
| 구분 | 활용 분야 | 설명 |
|---|---|---|
| H/W 활용 | 디지털 회로 | – 설계 가능 논리소자, PLC, 논리회로, FF, 전자계전기 |
| S/W 활용 | 응용 프로그램 설계 | – 프로그램 대응 이벤트 – 이벤트 프로그램 상태 |
| 텍스트 필터링 | – 텍스트 적합성 판별 예) “문자열”+”@”+”도메인” 판별 | |
| 컴파일러 설계 (어휘 분석기) | – 특정 언어를 다른 언어로 옮김 – 입력 코드를 의미 단위로 분리 | |
| 패리티 비트 생성 | – 오류 검사 위해 패리티 추가 – 짝/홀 패리티를 오토마타로 생성 |
- 유한 오토마타는 다양한 많은 유형들의 이벤트에 의해 작동이 이루어지는 상황에 유용
About The Author
