Formal language and automata - ch2

Ch2. Finite automata

Deterministic Finite Accepter(dfa)

● deterministic accepter
  ○ definition:
    M = (Q, Σ, δ, q₀, F)
      Q: set of internal state
      Σ: set of symbol (input alphabet)
      δ:  Q × Σ → Q transition function   (表示state的轉換)
        e.g.  
         δ(q₀, 0) = q₁
         即在q₀ state 、當input alphbet為0時，移動到state q₁
      q₀ ∈ Q: initial state
      F: set of final state

     每一步都要清楚定義(每個state都要考慮所有alphbet的可能)

  ○ operate:

     1. 一開始在initial state(q₀)
     2. 每次移動(move)，讀入一個input alphabet，根據讀到的input和當前的state，移動到下一個state
     3. 讀完所有input時，若在final state則為accept，否則為not accept

  ○ transition graph:

    state: 以圓圈表示
    transition function: 以箭頭表示
    input: 箭頭上的label
    initial state: 一個圓圈有一個箭頭沒有前一個state
    final state: 雙圓圈

      ※ transition graph 可以表示所有的dfa
    e.g.
      M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀, {q₁})
     with transition function δ:
        δ(q₀, 0) = q_0,   δ(q₀, 1) = q₁
        δ(q₁, 0) = q_0,   δ(q₁, 1) = q₂
        δ(q₂, 0) = q_2,   δ(q₂, 1) = q₁

  ○ extended transition function:
     δ(q₀, a) = q₁
     δ(q₁, b) = q₂
⇒ δ*(q₀, ab) = q₂

● Language and dfa:

   dfa可以接受的language即為所有dfa產生的字串的集合

   L(M) = {w ∈ Σ*: δ*(q₀, w) ∈ F}

  Language L is regular language if and only if there exist a dfa M使得
    L = L(M)

Nondeterministic finite accepter (nfa)

● definition:
    M = (Q, Σ, δ, q₀, F)
      和dfa類似，除了transion function不同:
      δ:  Q × (Σ ∪ λ) → 2^Q transition function   (表示state的轉換)

● 和dfa不同處:
          1. transition function 對應出來為一個set，而不是單一state (next state有多種可能性)
              e.g. δ(q₀, a) = {q₀, q₁}  

          2. transition function 第二的element可為λ                              (可不消耗alphabet切換到下一個state)

          3.  δ(q₀, a) 可為empty                                                               (transition 沒有定義)

          4. 可接受的string為：只要可以停在final state的string
● extended transition function: same as dfa

● transition graph:
 

                δ*(q₁, a) = {q₀, q₁, q₂}

                δ*(q₂, λ) = {q₀, q₂}

                δ*(q₂, a) = {q₀, q₁, q₂}

                note: 每個state本身都有一個λ cycle  (即透過λ 可在原本的state)

● language:

   nfa可以接受的language即為所有nfa產生的字串的集合

   L(M) = {w ∈ Σ*: δ*(q₀, w)  ∩ F ≠ φ}

  即w可以走到final state (有一個state即可)

Equivalence of deterministic and nondeterministic finite accepter

● equivalence of finite accepter:
   two finite accepter are same

   L(M₁) = L(M₂)

  if both accept same language

● equivalence of nfa and dfa:

    dfa 為一種nfa

    nfa 可以轉為dfa

      利用powerset ，新的graph的vertex為nfa的powerset

  ○ nfa轉換為 dfa:
          1. 創造一個新的graph G從 {q₀} 開始
          2. 對於所有G上的vertex {q_i, q_j, ..., q_l}，和一個 a ∈ Σ
              找出所有從 {qi, qj, ..., ,ql} 經過a 可以到的vertex，並標為一個新的state
          3. 重複2直到沒有新的vertex
              (必定結束，因為新的graph最多2^Q |Σ| edge)

          4. 標上final state: 任何有包含原本final state的vertex在新的graph均為final state
          5. 若 λ 也accept，則q₀也是final state

        e.g. 

           nfa

            第一步：

            第二步：

            完成所有vertex：

            完成圖：

Reduce the number of state

● indistinguishable/ distinguishable state:
   two state are indistinguishable if
       δ(p, w) ∈ F implies δ(q, w) ∈ F
   and
       δ(p, w) ∉ F implies δ(q, w) ∉ F

    for all w ∈ Σ*

● reducing produce :

  ○ produce mark:

     1. remove 所有無法到達的state

     2. 對所有state進行區分，分成final state和非final state (兩者為distinguishable，同set裡為distinguishable)

     3. 對所有indistinguishable state區分：

         若有 a ∈ Σ 使得兩個state p, q

            δ(p, a) = p_a

            δ(q, a) = q_a

       且p_a 和q_a為distinguishable，則p q為distinguishable

即
     對於所有字母a
     若p q經過接受a產生的state不再同一個set(distinguishable)，則p q不是同個state (distinguishable)

     4. 重複3直到沒有新的state被區分

  ○ produce reduce: 利用procedure mark找出所有相同的state，並根據相同state建立新的dfa

     1. 找出相同state: {q_i, q_j,...}，在新的dfa M' 中視為一個state

     2. 對於原本的dfa所有transition rule δ(p, a) ＝ q: 找出在M'中，p 和q 所在的state p' 和q'
         建立新的transition: δ(p', a) = q'

     3. 重複2直到原本的的dfa所有transition rule完成

     4. 標示initial state: M'中，包含initial state 的state即為initial state

     5. 標示final state: M'中，包含原本dfa final state的state均為final state