Non-deterministic Finite Automata

○Non-determinstic Finite Automata

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

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

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

  ▷Δ: Q×(Σ∪{λ})×Q - transition relation의 subset -> 라벨이 있는 directed edge

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

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

 

 ▷input character에 대해 하나 이상의 transition이 존재한다.

  ▷deterministic : 각 input에 대해 단 하나의 transition

 ▷λ-transition이 가능하다.

 ▷Final State에 도착하는 하나 이상의 길이 있다 -> Acceptable String

 

 

 ▶Transition function (Δ_f)

  ▷Transition relation을 Function으로 취급한 것

  ▷Δ_f : Q x ( Σ ∪ {λ} ) -> ρ(Q)

   ▷ρ(Q) : power set of Q

 

 ▶Extended Transition Function (Δ_s)

  ▷Transition relation의 집합

  ▷Δ_s = ρ(Q) x ( Σ ∪ {λ} ) -> ρ(Q)

  ▷Δ_s(P, a) = ∪_q∈p Δ_f(q,a)

 ▶λ-Closure ( E(q) / E_s(P) )

  ▷E(q) : 어떤 Symbol도 읽지 않고 도달 가능한 State들의 집합

  ▷원래 State + λ를 통해 이동가능한 State

  ▷E_s(P) : ∪_q∈P E(q)

 ▶Reachable State Function ( Δ^*(q, s) )

  ▷State q에서 String w을 읽었을 때 도달 가능한 State set

  ▷NFA를 해석하는 방법. (Update)

  ▷Δ^* : Q × Σ^* -> ρ(Q)

 

 

 ▶NFA Language

  ▷해당 NFA에서 Accepted되는 Language들

  ▷Δ^*(q₀, w)가 하나 이상의 Final State를 가진다.

 

 ▶NFA Design

  ▷일반적으로 DFA Design보다 쉽다.

 

 ◎Regex (010+01)* 허용하는 String

 

 ◎Regex (0+1)*1(0+1) 허용하는 String