유한 오토마타 (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
활용
응용 프로그램 설계– 프로그램 대응 이벤트
– 이벤트 프로그램 상태
텍스트 필터링– 텍스트 적합성 판별
예) “문자열”+”@”+”도메인” 판별
컴파일러 설계
(어휘 분석기)
– 특정 언어를 다른 언어로 옮김
– 입력 코드를 의미 단위로 분리
패리티 비트 생성– 오류 검사 위해 패리티 추가
– 짝/홀 패리티를 오토마타로 생성
  • 유한 오토마타는 다양한 많은 유형들의 이벤트에 의해 작동이 이루어지는 상황에 유용

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^