08 비결정성 유한 오토마톤

비결정성유한오토마톤(nondeterministic finite automaton, NFA) 1개의 상태에서 같은 입력기호에서 0개 이상의 상태전이가 가능 상태전이처가 입력문자에 의해 일의적으로 결정되지 않는다 입력이 없더라도 상태전이 가능 비결정성이 아닌 오토마톤은 결정성(deterministic) 오토마톤(DFA) 비결정성유한오토마톤에서 수리가능한 집합은 결정성유한오토마톤에서도 수리가능 비결정성유한오토마톤은 논리전개상 불가결하다 NFA의 상태전이도 유한오토마톤의 정식화 (Q, Σ, δ, q0, F) Q : 상태 (state)의 유한집합 Σ : 입력알파벳 (input alphabet) δ : Q×Σ→2Q의 전이함수 (transition function) δ(q, a)는 상태 q와 라벨 a에 전이가능한 모든상태의 집합 q0 : q0∈Q의 초기상태 (initial state) F : F⊆Q의 최종상태 (final state)의 집합 NFA의 상태전이도 δ의 확장 δ의 치역을 2Q로 확장...

원문링크 : 08 비결정성 유한 오토마톤