Determinant Finite Automata

○Deterministic Finite Automata

 ▶다음과 같은 5개의 요소들로 구성된 FSM (M = (Q, Σ, δ, q₀, F))

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷δ: Q×Σ → Q인 transition function -> 라벨이 있는 directed edge

  ▷q₀: start state (q₀ ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 

 ▶Machine-Oriented Viewpoint

  ▷기계로 생각해 보는 DFA - cell들이 있는 input tape, read-only head, FA controller

  ▷메모리가 없음.

  ▷head는 가장 왼쪽(start state)에서 부터 오른쪽으로 움직임

  ▷δ(current state, tape symbol) -> next state

 

 ▶configuration (상황)

  ▷QΣ*

   ▷Q: 현재 State

   ▷Σ*: 아직 남아있는 input string

  ▶configuration sequence (px ┣ qy)

   ▷x = ay이고, δ(p, a) = q일 때. (a ∈ Σ)

   ▷px에서 qy으로 configuration이 transition 가능함.

 

   ▶px ┣^k qy

    ▷px에서 k-steps 이후 qy로 transition함.

    ▷px ┣ rz, rz ┣^k-1 qy

    ▷┣⁺ ≡ ┣^k (k ≥ 1) : transitve closure

    ▷┣^* ≡┣^k (k ≥ 0), 자기 자신도 포함. : reflexive transitive closure

    ▷┣⁺이 가능하면, ┣^*도 가능하다.

 

 

 ▶Accepted Language (L(M))

  ▷M = (Q, Σ, δ, S, F)에 대해서

  ▷Sx ┣^* fλ가 성립하는 x (x ∈ Σ^*, f ∈ F)

  ▷DFA Language: 어떤 DFA에 대해 Accepted Language인 L

 

 ▶Equivalence of DFA

  ▷DFA M₁, M₂에 대해서

  ▷L(M₁) = L(M₂)이면, M₁과 M₂는 equivalent하다.

 

 ▶DFA 설계

  ▷1. 기억해야할 정보 결정, State로 표현

  ▷2. Input마다 State transition을 결정.

 

  ◎1이 짝수개 있는 String (Σ = {0, 1})

 

  ◎Substring 0101을 가진 String (Σ = {0, 1})

   ▷0101을 찾는다면 Final State에서 빠져나가지 않는다.

 

  ◎Substring 0101을 가지지 않은 String (Σ = {0, 1})

   ▷Dead State: 들어간다면, Final State로 갈 수 없는 State

 

  ◎L( (010+01)* )

 

 

○Mealy vs Moore

 ▶Moore: M = (Q, Σ, δ, q_0, F)

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷δ: Q×Σ → Q인 transition function -> 라벨이 있는 directed edge

  ▷q_0: start state (q0 ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 

 ▶Mealy: M = (Q, Σ, Γ, δ, γ)

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨 (앞)

  ▷Γ: output symbols의 앞바벳 -> 라벨 (뒤)

  ▷δ: Q×Σ → Q인 next state function -> 라벨이 있는 directed edge

  ▷γ: Q×Σ → γ인 output function