유한 오토마타 어떤 알파벳 Σ로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템에서 변화할 수 있는 상태가 유한개이다. 컴퓨터의 여러 분야에서 널리 사용되고 있다. 특히 플립플롭(flip-flop)을 비롯한 여러 컴퓨터 관련 고안물들, 형식언어의 연구, 그리고 컴파일러 등에 유용하게 쓰인다 또, 컴파일러의 어휘 분석(lexical analysis) 또한 유한 오토마타의 대표적인 것이다. 상태 전이 함수의 형태에 따라 결정적 유한 오토마타 (Deterministic Finite Automata; DFA)와 비결정적 유한 오토마타(Nondeterministic Finite Automata; NFA)를 구분한다. 오토마타의 전이 함수는 유한 오토마타의 상태 전이를 행렬(m..
개발/오토마타
NFA와 DFA DFA와 NFA는 서로 동등하다 DFA보다 NFA가 언어의 구조를 쉽게 표현 NFA는 DFA보다 프로그램으로 구현하기 어려움 DFA는 NFA보다 프로그램으로 구현했을 경우에 효율면에서 훨씬 우수 일반적인 구현은 DFA로 해야 되는데 NFA가 언어의 구조를 쉽게 표현할 수 있기 때문에 서로가 변환이 필요하다 DFA의 상태수 최소화(state minimization) DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임 기억공간을 적게 차지하도록 하고 또한 어휘분석 프로그램을 간단히 하는데 큰 도움 상태수를 최소화하는 방법 동치관계(equivalence relation)을 이용 상태수를 합침(state merge) [정의 3.22] 구별가능(distinguishable) [정의 3.23..
