오토마타와 형식언어: 유한 오토마타 (Finite Automata) (2)

이어서 유한 오토마타다 (Finite Automata).

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한다.