dfa M 이 승인할 수 있는 Language 는 아래와 같다.
L (M )={w ∈ Σ∗ : δ∗ (q0,w) ∈ F }
dfa 가 승인하지 못한다면?
L (M )={w ∈ Σ∗ : δ∗ (q0,w) /∈ F }
확장 전이 함수(Extended Transition Function)
δ∗ : Q × Σ∗ → Q
δ∗의 값은? Automata가 주어진 string 을 모두 읽은 후에 놓이게 되는 상태
아래와 같은 dfa가 있다면?
Q: {q0, q1, q2}
Σ: {a,b}
δ: (q0,a) -> q0, (q0,b) -> q1, (q1,a) -> q2, (q1,b) -> q2
q0: Initial State
q1: Final State // F는 double circle 로 표현
위 dfa 승인/거절 string 샘플
aaab => 승인
abbab => 거절
baaba => 거절
b => 승인
쉽게 보자면, 위 dfa는 입력받은 string이 b가 끝에 와야하며, 이후에 무엇이라도 오면 reject한다.
Flutter App Developer