X

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