DFA (Deterministic Finite Automata): 결정적 유한 오토마타
- Q: 상태들의 유한집합(Finite set of states)
- ∑: 입력 알파벳이라고 불리는 유한개의 심볼들의 집합
- δ: Q X ∑ → Q인 전이 함수(transition function)
- q0: q0 ∈ Q인 시작 상태(start state)
- F: F ⊆ Q인 최종 상태의 집합(set of final state
- example DFA model
- State Diagrams
NFA (Nondeterministic Finite Automata): 비결정적 유한 오토마타
DFA and NFA
DFA의 표현
M = (Q, ∑, δ, q0, F)
- ∑: 입력 알파벳이라고 불리는 유한개의 심볼들의 집합
- δ: Q X ∑ → Q인 전이 함수(transition function)
- q0: q0 ∈ Q인 시작 상태(start state)
- F: F ⊆ Q인 최종 상태의 집합(set of final state
- example DFA model
- State Diagrams
NFA (Nondeterministic Finite Automata): 비결정적 유한 오토마타
- NFA의 표현
M = (Q, ∑, δ, q0, F)
δ: Q X ( ∑ ∪ { λ }) → 2Q
δ: Q X ( ∑ ∪ { λ }) → 2Q
- 2Q 란 수학적으로 P(Q)인 멱집합(Power set)인데 Q의 모든 부분집합의 집합을 의미
- NFA의 두 가지 형태로는
- 첫째, 어떤 상태에서 입력이 중복되어 나타나는 경우
- 둘째, λ-전이가 있는 경우
- NFA의 두 가지 형태로는
- 첫째, 어떤 상태에서 입력이 중복되어 나타나는 경우
- 둘째, λ-전이가 있는 경우
DFA and NFA
- 차이점
■ 치역
@ NFA에서의 치역이 멱집합 2Q 내에 있고, 그 값이 Q의 단일 원소가 아닌 Q의 부분집합
■ NFA에서 전이함수의 인수로 허용
@ 입력 심볼을 읽지 않고도 전이가 가능함
■ NFA에서는 집합 (qi, a)가 공집합을 허용
@ 특정 상황에 대하여 정의된 전이가 없을 수 있음
■ 치역
@ NFA에서의 치역이 멱집합 2Q 내에 있고, 그 값이 Q의 단일 원소가 아닌 Q의 부분집합
■ NFA에서 전이함수의 인수로 허용
@ 입력 심볼을 읽지 않고도 전이가 가능함
■ NFA에서는 집합 (qi, a)가 공집합을 허용
@ 특정 상황에 대하여 정의된 전이가 없을 수 있음
'Research & Paper' 카테고리의 다른 글
| DFA and NFA (0) | 2009/09/30 |
|---|---|
| Hash Operations in Database System (0) | 2009/09/29 |
| Performance Analysis (0) | 2009/09/23 |
| Challenge in 20s Ph.D. (2) | 2009/09/18 |
| EndNote X2 사용기 (0) | 2009/08/03 |
| VLDB, SIGMOD, ICDE Paper Search (0) | 2008/09/30 |
