【系統分析與驗證筆記】關于自動機的規範語言（Specification Language）

本章目錄

• 有限字的自動機（Automata on Finite Words）
• • 不确定的有窮自動機（Nondeterministic Finite Automaton，簡稱NFA）
  • 正規表達式（Regular expressions）
  • 關于正則語言和有限自動機之間的關系
• 無限字的自動機（Automata on Finite Words）
• • ω \omega ω正規表達式（ ω \omega ω-Regular expressions）
  • 非确定性 B u ¨ c h i B\ddot{u}chi Bu¨chi自動機（ N o n d e t e r m i n i s t i c   B u ¨ c h i   A u t o m a t o n Nondeterministic \ B\ddot{u}chi \ Automaton Nondeterministic Bu¨chi Automaton，簡稱NBA）
  • 有環的情況下的NBA和NFA
• NBA和 ω \omega ω-正則語言
• • 對于任何一個 ω \omega ω-正則語言，都存在一個可接收它的NBA
  • 通過 ω \omega ω方法将NFA轉換為NBA
  • 加法運算
  • 連接配接運算
• Generalized NBA（簡寫為GNBA）
• • GNBA轉NBA

有限字的自動機（Automata on Finite Words）

不确定的有窮自動機（Nondeterministic Finite Automaton，簡稱NFA）

• NFA是一個五元組： A = ( Q , Σ , δ , Q 0 , F ) \mathcal{A}=(Q,\Sigma ,\delta,Q_0,F) A=(Q,Σ,δ,Q0​,F)
  • Q Q Q：一組有限的狀态，例如下圖NFA的 q 0 ， q 1 ， q 2 q_0，q_1，q_2 q0​，q1​，q2​
  • Σ \Sigma Σ：代表26個字母，例如下圖NFA用到了 A 、 B A、B A、B兩個字母
  • δ \delta δ： Q × Σ → 2 Q Q \times \Sigma \to 2^Q Q×Σ→2Q，是一個變遷函數，例如下圖NFA中的有箭頭的線段，線段上面的字母，表示從一個狀态讀到這個字母，可以跳轉到另一個狀态
  • Q 0 Q_0 Q0​： Q 0 ∈ Q Q_0 \in Q Q0​∈Q，是初始狀态集合，例如下圖NFA的 q 0 q_0 q0​，NFA可能有多個初始狀态
  • F F F： F ∈ Q F \in Q F∈Q，是可接收（最終）狀态，例如下圖NFA的 q 2 q_2 q2​
• 一個簡單的NFA

  

  • 字（word，簡寫w）： w = A 1 ⋯ A n ∈ Σ ∗ w = A_1 \cdots A_n \in \Sigma^* w=A1​⋯An​∈Σ∗，是一串字母組成的字元串，表示一個NFA所要接收的一組輸入（也叫做可接收的執行）。例如上圖的NFA，可以接收 w = A B A w=ABA w=ABA或 w = A A B B w=AABB w=AABB這樣的字

    • Σ ∗ \Sigma^* Σ∗表示的是一組有限字，比如 Σ = { a , b } \Sigma =\{a,b\} Σ={a,b}，則 Σ ∗ = { ∅ , a , a b , a a , a a a , ⋯   } \Sigma^*= \{\varnothing,a,ab,aa,aaa,\cdots\} Σ∗={∅,a,ab,aa,aaa,⋯}，隻要是有限的字，都在這個集合裡面，但集合内的字的數量可以是無限的
    • Σ ∗ Σ = Σ Σ ∗ = Σ \Sigma^*\Sigma=\Sigma \Sigma^*=\Sigma Σ∗Σ=ΣΣ∗=Σ

  • 狀态變遷：

    • 公式說明： q 0 ∈ Q 0   a n d   q i → A i + 1 q i + 1   f o r   a l l   0 ⩽ i ⩽ n , a n d   q n ∈ F q_0 \in Q_0 \ and \ q_i \xrightarrow {A_{i+1}} q_{i+1} \ for \ all \ 0 \leqslant i \leqslant n,and \ q_n \in F q0​∈Q0​ and qi​Ai+1​

      ​qi+1​ for all 0⩽i⩽n,and qn​∈F

    • 文字解釋：
      • q 0 q_0 q0​是一個初始狀态（可能存在多個初始狀态， q 0 q_0 q0​隻是其中一個）
      • q i q_i qi​狀态下，讀取字母 A i + 1 A_{i+1} Ai+1​後，移動到狀态 q i + 1 q_{i+1} qi+1​，其中 0 ⩽ i ⩽ n 0 \leqslant i \leqslant n 0⩽i⩽n
      • 最後一個狀态 q n q_n qn​為最終狀态，也叫可接收狀态
  • L ( A ) \mathcal{L}(\mathcal{A}) L(A)：表示自動機所有可接收的字的集合，稱為自動機 A \mathcal{A} A的語言，例如： L ( A ) = { A B A , A A B B , A B A B B B , A A B B A , ⋯   } \mathcal{L}(\mathcal{A})=\{ABA,AABB,ABABBB,AABBA,\cdots\} L(A)={ABA,AABB,ABABBB,AABBA,⋯}
  • 如果兩個NFA可接收的語言相同，則他們是等價的，即 L ( A ) = L ( A ′ ) \mathcal{L}(\mathcal{A})=\mathcal{L}(\mathcal{A'}) L(A)=L(A′)

正規表達式（Regular expressions）

• 文法： E : : = ∅ ∣ ε ∣ A ∣ E + E ′ ∣ E . E ′ ∣ E ∗ E ::= \varnothing | \varepsilon | A | E + E' | E.E' | E^∗ E::=∅∣ε∣A∣E+E′∣E.E′∣E∗
  • ∅ \varnothing ∅表示空集，長度為零
  • ε \varepsilon ε表示空字母，也就是一個沒有任何字母的輸入，比如 A B ε A A AB\varepsilon AA ABεAA，長度為一
  • A A A是字母表 Σ \Sigma Σ裡的一個字母
  • E + E ′ E + E' E+E′表示兩個正規表達式相加
  • E . E ′ E.E' E.E′表示兩個正規表達式連接配接
  • E ∗ E^∗ E∗表示正規表達式 E E E的有限次連接配接，如 E . E . E E.E.E E.E.E，其中包含零次連接配接，零次連接配接的結果為 ∅ \varnothing ∅
• 語義：自動機可以接收的語言，用 L \mathcal{L} L表示， L ( A ) = { A A B , A B B B A } \mathcal{L}(\mathcal{A})=\{AAB,ABBBA\} L(A)={AAB,ABBBA}表示自動機 A \mathcal{A} A可以接收的語言為 A A B AAB AAB和 A B B B A ABBBA ABBBA。具體規則如下
  • L ( ∅ ) = ∅ \mathcal{L}(\varnothing)=\varnothing L(∅)=∅
  • L ( ε ) = ε \mathcal{L}(\varepsilon )=\varepsilon L(ε)=ε
  • L ( E + E ′ ) = L ( E ) ∪ L ( E ′ ) \mathcal{L}(E+E')=\mathcal{L}(E)\cup \mathcal{L}(E') L(E+E′)=L(E)∪L(E′)
  • L ( E . E ′ ) = L ( E ) . L ( E ′ ) \mathcal{L}(E.E')=\mathcal{L}(E). \mathcal{L}(E') L(E.E′)=L(E).L(E′)
  • L ( E ∗ ) = L ( E ) ∗ \mathcal{L}(E^*)=\mathcal{L}(E)^* L(E∗)=L(E)∗

  例如 L ( E ) = { a , a b } , L ( E ′ ) = { b , a b } \mathcal{L}(E)=\{a,ab\},\mathcal{L}(E')=\{b,ab\} L(E)={a,ab},L(E′)={b,ab}，則 L ( E . E ′ ) = L ( E ) . L ( E ′ ) = { a b , a a b , a b b , a b a b } \mathcal{L}(E.E')=\mathcal{L}(E). \mathcal{L}(E')=\{ab,aab,abb,abab\} L(E.E′)=L(E).L(E′)={ab,aab,abb,abab}

關于正則語言和有限自動機之間的關系

• 有限自動機所接收的語言和正規表達式所接收的語言是等價的，有相同的表達能力，都是正則語言
• 他們的交（ ∩ \cap ∩）和補（complementation）是封閉的

  • 封閉性表示兩個正則語言的交，結果仍然為正則語言，兩個正則語言的補，結果也仍然為正則語言
  • NFA的 A ⊗ B \mathcal{A} \otimes \mathcal{B} A⊗B等于正則語言 L ( A ) ∩ L ( B ) \mathcal{L}(A)\cap \mathcal{L}(B) L(A)∩L(B)
  • 确定的有窮自動機（Deterministic Finite Automaton，簡稱DFA）的 A ‾ \overline{\mathcal{A}} A等于語言 L ( A ) ‾ = Σ ∗ \ L ( A ) \overline{\mathcal{L}(A)}=\Sigma^* \backslash \mathcal{L}(A) L(A)​=Σ∗\L(A)，解釋： Σ ∗ \Sigma^* Σ∗裡去掉 L ( A ) \mathcal{L}(A) L(A)，就是 L ( A ) \mathcal{L}(A) L(A)的補

• 基于确定性的封閉性：有限自動機可以用正規表達式來表示，正規表達式可以用有限自動機來表示

  • 用KS來表示一個系統，用NFA來表示一個性質，如果KS ⊗ \otimes ⊗NFA的結果為 ∅ \varnothing ∅，則表示該KS沒有字能夠滿足NFA的性質，否則，結果表示為該KS存在滿足該NFA的字。
  • NFA是我們對性質的一種圖形表示

無限字的自動機（Automata on Finite Words）

ω \omega ω正規表達式（ ω \omega ω-Regular expressions）

• 文法： G = E 1 . F 1 ω + ⋯ + E n . F n ω G = E_1.F_1^\omega + \cdots + E_n.F_n^\omega G=E1​.F1ω​+⋯+En​.Fnω​
  • n > 0 n > 0 n>0
  • E i 和 F i E_i和F_i Ei​和Fi​是 Σ \Sigma Σ上的正規表達式
  • ε ∉ L ( F i ) \varepsilon \notin \mathcal{L}(F_i) ε∈/​L(Fi​)

  • 正規表達式表示有限字的語義， ω \omega ω正規表達式表示無限字的語義
  • Σ ω \Sigma^\omega Σω表示的是一組無限字，比如 Σ = { a , b } \Sigma =\{a,b\} Σ={a,b}，則 Σ ω = { a ⋯ a , a b a ⋯ a a a , ⋯   } \Sigma^\omega= \{a\cdots a,aba \cdots aaa,\cdots\} Σω={a⋯a,aba⋯aaa,⋯}，隻要是無限的字，都在這裡面（不可能是0字），同時，集合内的元素也是無限的

• 範例： ( B ∗ . A ) ω (B^*.A)^\omega (B∗.A)ω展開後為 B ∗ . A . B ∗ . A ⋯ B^*.A.B^*.A\cdots B∗.A.B∗.A⋯
• 語義： L ω ( G ) = L ( E 1 ) . L ( F 1 ) ω ∪ ⋯ ∪ L ( E n ) . L ( F n ) ω \mathcal{L}_\omega(G) = \mathcal{L}(E_1).\mathcal{L}(F_1)^\omega \cup \cdots \cup \mathcal{L}(E_n).\mathcal{L}(F_n)^\omega Lω​(G)=L(E1​).L(F1​)ω∪⋯∪L(En​).L(Fn​)ω
  • L ⊆ Σ ∗ \mathcal{L} \subseteq \Sigma^* L⊆Σ∗
  • L ( G ) ⊆ Σ ω \mathcal{L}(G) \subseteq \Sigma^\omega L(G)⊆Σω
  • L ω = { w 1 w 2 w 3 ⋯ ∣ ∀ i ⩾ 0 , w i ∈ L } \mathcal{L}^\omega=\{w_1w_2w_3\cdots|\forall _i\geqslant 0,w_i \in \mathcal{L}\} Lω={w1​w2​w3​⋯∣∀i​⩾0,wi​∈L}

  如果 G 1 G_1 G1​和 G 2 G_2 G2​所接收的語言相等，即 L ω ( G 1 ) = L ω ( G 2 ) \mathcal{L}_\omega(G_1)=\mathcal{L}_\omega(G_2) Lω​(G1​)=Lω​(G2​)，則這兩個 ω \omega ω正規表達式 G 1 G_1 G1​和 G 2 G_2 G2​等價，即 G 1 ≡ G 2 G_1 \equiv G_2 G1​≡G2​

• 舉例： Σ = { A , B } \Sigma = \{A,B\} Σ={A,B}的情況下
  • 一個包含無限多個 A A A的語言： ( B ∗ . A ) ω (B^*.A)^\omega (B∗.A)ω
  • 一個包含有限多個 A A A的語言： ( A + B ) ∗ . B ω (A+B)^*.B^\omega (A+B)∗.Bω
  • 空語言： ∅ ω \varnothing^\omega ∅ω

關于交并補都是封閉的，也就是兩個 ω \omega ω正則語言交的結果仍然為 ω \omega ω正則語言，并的結果仍然為 ω \omega ω正則語言，補的結果仍然為 ω \omega ω正則語言

非确定性 B u ¨ c h i B\ddot{u}chi Bu¨chi自動機（ N o n d e t e r m i n i s t i c   B u ¨ c h i   A u t o m a t o n Nondeterministic \ B\ddot{u}chi \ Automaton Nondeterministic Bu¨chi Automaton，簡稱NBA）

• NFA和DFA自動機隻能接收有限字的自動機， B u ¨ c h i B\ddot{u}chi Bu¨chi自動機可以接收無限字的自動機
• NBA是一個五元組 A = ( Q , Σ , δ , Q 0 , F ) \mathcal{A} = (Q,\Sigma,\delta,Q_0,F) A=(Q,Σ,δ,Q0​,F)，字 σ = A 0 A 1 A 2 ⋯ ∈ Σ ω \sigma=A_0A_1A_2\cdots \in \Sigma^\omega σ=A0​A1​A2​⋯∈Σω
• A \mathcal{A} A可接收的字是無限序列 q 0 q 1 q 2 ⋯ q_0q_1q_2\cdots q0​q1​q2​⋯
  • q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​

  • 對于所有 i ⩾ 0 i\geqslant 0 i⩾0，都有 q i → A i + 1 q i + 1 q_i\xrightarrow {A_{i+1}}q_{i+1} qi​Ai+1​

    ​qi+1​

  • 存在無限經常次出現的 q i ∈ F q_i \in F qi​∈F
  • 一個NBA自動機可接收的語言為可接收語言對應的無限字的集合，即 A \mathcal{A} A可以被接收的語義為： L ω ( A ) = { σ ∈ Σ ω ∣ \mathcal{L}_\omega(\mathcal{A})=\{\sigma \in \Sigma^\omega| Lω​(A)={σ∈Σω∣存在可接收的語言 A ， A \mathcal{A}，\mathcal{A} A，A由 σ \sigma σ組成 } \} }
• 如果兩個NBA可以被接收的語言相同，則他們是等價的

有環的情況下的NBA和NFA

• 性質1：從NFA的相等，并不能推出NBA的相等

  

  • 上圖分析

    L ( A 1 ) = A A ∗ = A ∗ \mathcal{L}(\mathcal{A_1})=AA^*=A^* L(A1​)=AA∗=A∗

    L ( A 2 ) = A ∗ A = A ∗ \mathcal{L}(\mathcal{A_2})=A^*A=A^* L(A2​)=A∗A=A∗

    L ω ( A 1 ) = A A ω = A ω \mathcal{L}_\omega(\mathcal{A_1})=AA^\omega=A^\omega Lω​(A1​)=AAω=Aω

    L ω ( A 2 ) = ∅ \mathcal{L}_\omega(\mathcal{A_2})=\varnothing Lω​(A2​)=∅

  • 雖然 L ( A 1 ) = L ( A 2 ) \mathcal{L}(\mathcal{A_1})=\mathcal{L}(\mathcal{A_2}) L(A1​)=L(A2​)，但 L ω ( A 1 ) ≠ L ω ( A 2 ) \mathcal{L}_\omega(\mathcal{A_1})\neq \mathcal{L}_\omega(\mathcal{A_2}) Lω​(A1​)​=Lω​(A2​)

  L ω ( A 2 ) = ∅ \mathcal{L}_\omega(\mathcal{A_2})=\varnothing Lω​(A2​)=∅的原因是，NBA隻能接收無限字的自動機，如果接收 A ∗ A A^*A A∗A，那麼不滿足無限字的情況，如果接收 A ω A A^\omega A AωA，那麼 A ω A^\omega Aω永遠也不會結束，不屬于自動機了，是以 L ω ( A 2 ) \mathcal{L}_\omega(\mathcal{A_2}) Lω​(A2​)

• 性質2：從NBA的相等，并不能推出NFA的相等

  

  • 上圖分析

    L ( A 1 ) = { ∅ , A A , A A A A , ⋯   } \mathcal{L}(\mathcal{A_1})=\{\varnothing,AA,AAAA,\cdots\} L(A1​)={∅,AA,AAAA,⋯}

    L ( A 2 ) = { A , A A A , A A A A A , ⋯   } \mathcal{L}(\mathcal{A_2})=\{A,AAA,AAAAA,\cdots\} L(A2​)={A,AAA,AAAAA,⋯}

    L ω ( A 1 ) = A A ω = A ω \mathcal{L}_\omega(\mathcal{A_1})=AA^\omega=A^\omega Lω​(A1​)=AAω=Aω

    L ω ( A 2 ) = A ω A = A ω \mathcal{L}_\omega(\mathcal{A_2})=A^\omega A=A^\omega Lω​(A2​)=AωA=Aω

  • 雖然 L ω ( A 1 ) = L ω ( A 2 ) \mathcal{L}_\omega(\mathcal{A_1})=\mathcal{L}_\omega(\mathcal{A_2}) Lω​(A1​)=Lω​(A2​)，但 L ( A 1 ) ≠ L ( A 2 ) \mathcal{L}(\mathcal{A_1})\neq \mathcal{L}(\mathcal{A_2}) L(A1​)​=L(A2​)

NBA和 ω \omega ω-正則語言

• 關系：NBA可接收的語言為 ω \omega ω-正則語言，他們具有相同的表達能力
  • 任何 ω \omega ω-正則語言都可以被一個NBA自動機所接收
  • 對于任何一個NBA： A \mathcal{A} A，它可接收的語言 L ω ( A ) \mathcal{L}_\omega(\mathcal{A}) Lω​(A)都是 ω \omega ω-正則語言

對于任何一個 ω \omega ω-正則語言，都存在一個可接收它的NBA

如何為一個 ω \omega ω-正則語言尋找一個可接收它的NBA呢

• ω \omega ω-正規表達式的構成： G = E 1 . F 1 ω + ⋯ + E n . F n ω G = E_1.F_1^\omega + \cdots + E_n.F_n^\omega G=E1​.F1ω​+⋯+En​.Fnω​，其中， E i E_i Ei​和 F i F_i Fi​都是在字母表 Σ \Sigma Σ上的正規表達式，且 ε ∉ F i \varepsilon \notin F_i ε∈/​Fi​

  E i E_i Ei​是正規表達式， F i ω F_i^\omega Fiω​是一個 ω \omega ω-正規表達式，他們倆連接配接運算後形成了一個 ω \omega ω-正規表達式： E i . F i ω E_i.F_i^\omega Ei​.Fiω​

• ω \omega ω-正規表達式，得到一個可接收它的NBA的過程
  • 加法運算：兩個NBA可接收語言的加法是： L ω ( A 1 ) ∪ L ω ( A 2 ) \mathcal{L}_\omega(\mathcal{A}_1)\cup\mathcal{L}_\omega(\mathcal{A}_2) Lω​(A1​)∪Lω​(A2​)

    • 這兩個NBA是 A 1 \mathcal{A}_1 A1​和 A 2 \mathcal{A}_2 A2​，他們可接收的語言分别是 L ω ( A 1 ) \mathcal{L}_\omega(\mathcal{A}_1) Lω​(A1​)和 L ω ( A 2 ) \mathcal{L}_\omega(\mathcal{A}_2) Lω​(A2​)
    • 多個求加法運算和兩個也是一緻的，先求出兩個的加法運算結果，再進行下一次加法運算

  • ω \omega ω次方運算：對于任意的正規表達式 L \mathcal{L} L，如果 ε ∉ L \varepsilon \notin \mathcal{L} ε∈/​L，則存在NBA可接收 L ω \mathcal{L}^\omega Lω

    L ω \mathcal{L}^\omega Lω表示無限次重複，也就是存在NBA可以接收 L L L ⋯ \mathcal{L}\mathcal{L}\mathcal{L}\cdots LLL⋯

  • 連接配接運算：對于正規表達式 L \mathcal{L} L和NBA： A ′ \mathcal{A'} A′，存在另一個NBA可接收 L . L ω ( A ′ ) \mathcal{L}.\mathcal{L}_\omega(\mathcal{A'}) L.Lω​(A′)

通過 ω \omega ω方法将NFA轉換為NBA

• 目的：讓一個可接收有限字的NFA： A = ( Q , Σ , δ , Q 0 , F ) \mathcal{A} = (Q,\Sigma,\delta,Q_0,F) A=(Q,Σ,δ,Q0​,F)構造成一個可接收無限字的NBA
• A \mathcal{A} A需滿足的條件： A \mathcal{A} A中的所有的初始狀态都沒有攝入轉移，并且 Q 0 ∩ F = ∅ Q_0 \cap F = \varnothing Q0​∩F=∅
  • 如果上述條件不滿足，則要進行如下轉移
    • 增加一個新的初始狀态 q n e w ∉ F q_{new} \notin F qnew​∈/​F，

    • 增加邊：對于一些 q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​，當且僅當 q 0 → A q q_{0} \xrightarrow {A}q q0​A

      ​q，則 q n e w → A q q_{new} \xrightarrow {A}q qnew​A

      ​q

    • 其他的變遷不用變
  • 轉移完成後，得到了一個新的NFA，初始狀态無攝入轉移，此時NFA滿足上述條件了

  Q 0 ∩ F = ∅ Q_0 \cap F = \varnothing Q0​∩F=∅表示初始狀态和可接收狀态是不能相交的

  基本原則：原來初始狀态能到達的狀态，新的狀态也要能到達

  • 轉移範例：

    下圖的NFA中，初始狀态 S 1 S_1 S1​有一條攝入邊，需要進行轉移

    

    是以我們要建立一個新的狀态 S n e w S_{new} Snew​作為新的初始狀态，并且取代 S 1 S_1 S1​接收字所能達到的狀态，也就是需要加上 S n e w → A S 2 S_{new} \xrightarrow {A} S_2 Snew​A

    ​S2​和 S n e w → B S 3 S_{new} \xrightarrow {B} S_3 Snew​B

    ​S3​，再删除掉 S 1 S_1 S1​的攝入邊，此時的 NFA則滿足上述條件： A \mathcal{A} A中的所有的初始狀态都沒有攝入轉移，并且 Q 0 ∩ F = ∅ Q_0 \cap F = \varnothing Q0​∩F=∅

    

• 構造NBA的過程：建構一個新的NBA： A ′ = ( Q , Σ , δ ′ , Q 0 ′ , F ′ ) \mathcal{A'}=(Q,\Sigma ,\delta',Q_0',F') A′=(Q,Σ,δ′,Q0′​,F′)，規則如下

  • 如果存在 q → A q ′ q \xrightarrow {A}q' qA

    ​q′且 q ′ ∈ F q' \in F q′∈F，則加上一條路徑 q → A q 0 q \xrightarrow {A}q_0 qA

    ​q0​，且對于任意的 q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​

  • 其他的變遷不用變
  • Q 0 ′ = Q 0 Q_0'=Q_0 Q0′​=Q0​且 F ′ = Q 0 F'=Q_0 F′=Q0​

  基本原則：原來能到達可接收狀态的，也要能到達新的狀态

• 建構NBA範例：用接收 ( A ∗ B ) (A^∗B) (A∗B)的NFA構造一個接收 ( A ∗ B ) ω (A^∗B)^\omega (A∗B)ω的NBA

  

• 因為初始狀态 q 0 q_0 q0​有兩種能到達的狀态： q 0 → A q 0 , q 0 → B q 1 q_{0} \xrightarrow {A}q_0,q_{0} \xrightarrow {B}q_1 q0​A

  ​q0​,q0​B

  ​q1​，是以，需要以 q n e w q_{new} qnew​為初始狀态，加這兩種情況： q n e w → A q 0 , q n e w → B q 1 q_{new} \xrightarrow {A}q_{0},q_{new} \xrightarrow {B}q_{1} qnew​A

  ​q0​,qnew​B

  ​q1​

  比較複雜的解釋：

  • 這是一個NFA， q 0 q_0 q0​有攝入邊，但我們構造的時候不能有涉入邊，是以我們要進行轉換，增加一個新的狀态 q n e w q_{new} qnew​和兩個新的轉移 q n e w → B q 1 q_{new} \xrightarrow {B}q_1 qnew​B

    ​q1​， q n e w → A q 0 q_{new} \xrightarrow {A}q_0 qnew​A

    ​q0​

  • 根據“對于一些 q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​，當且僅當 q 0 → A q q_{0} \xrightarrow {A}q q0​A

    ​q，則 q n e w → A q q_{new} \xrightarrow {A}q qnew​A

    ​q”，将性質中的 A A A換成了 B B B， q q q換成了 q 1 q_1 q1​得到 q n e w → B q 1 q_{new} \xrightarrow {B}q_1 qnew​B

    ​q1​，将性質中的 q 0 q_0 q0​換成了 q q q得到 q n e w → A q 0 q_{new} \xrightarrow {A}q_0 qnew​A

    ​q0​

  • 此時 q 0 q_0 q0​讀 A A A到 q 0 q_0 q0​， q n e w q_{new} qnew​讀 A A A到 q 0 q_0 q0​， q 0 q_{0} q0​讀 B B B到 q 1 q_1 q1​， q n e w q_{new} qnew​讀 B B B到 q 1 q_1 q1​，對于這個狀态來說，就沒有涉入邊了，該對它進行轉換了

  

• 因為有兩種情況可以轉換到可接收狀态 q 1 q_1 q1​： q 0 → A q 1 , q n e w → B q 1 q_{0} \xrightarrow {A}q_1,q_{new} \xrightarrow {B}q_1 q0​A

  ​q1​,qnew​B

  ​q1​，是以，需要加兩種情況将他們轉換到 q n e w q_{new} qnew​： q 0 → A q n e w , q n e w → B q n e w q_{0} \xrightarrow {A}q_{new},q_{new} \xrightarrow {B}q_{new} q0​A

  ​qnew​,qnew​B

  ​qnew​

  比較複雜的解釋：

  • 先看 q n e w q_{new} qnew​讀 B B B轉換到 q 1 q_1 q1​， q 1 q_1 q1​是可接收狀态，那我們再增加一條邊， q n e w q_{new} qnew​讀 B B B轉到初始狀态，也就是 q n e w q_{new} qnew​本身，增加了一個自回路

  • 根據性質“如果 q → A q ′ q \xrightarrow {A}q' qA

    ​q′且 q ′ ∈ F q' \in F q′∈F，則加上一條路徑 q → A q 0 q \xrightarrow {A}q_0 qA

    ​q0​，且對于任意的 q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​”，把性質裡的 A A A換成了 B B B，把 q q q和 q 0 q_0 q0​換成了 q n e w q_{new} qnew​，得到 q n e w → B q n e w q_{new} \xrightarrow {B}q_{new} qnew​B

    ​qnew​這條邊

  • 我們再看 q 0 q_0 q0​， q 0 q_{0} q0​讀 B B B到 q 1 q_1 q1​， q 1 q_1 q1​是可接收狀态，那我們再增加一條邊， q 0 q_{0} q0​讀 B B B到初始狀态 q n e w q_{new} qnew​

  • 根據性質“對于一些 q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​，當且僅當 q 0 → A q q_{0} \xrightarrow {A}q q0​A

    ​q，則 q n e w → A q q_{new} \xrightarrow {A}q qnew​A

    ​q”，把性質裡的 A A A換成了 B B B，把 q q q和 q 0 q_0 q0​換成了 q n e w q_{new} qnew​，得到 q 0 → B q n e w q_{0} \xrightarrow {B}q_{new} q0​B

    ​qnew​這條邊

  

• 最後再把可接收狀态轉換為

  可接收狀态從 q 1 q_1 q1​換到 q n e w q_{new} qnew​的原因： q 1 q_1 q1​的存在其實已經毫無意義，他被 q n e w q_{new} qnew​完全取代，是以将可接收狀态轉移給 q n e w q_{new} qnew​即可，但我們不能把他删掉，即便已經不需要用了。具體依據性質“ Q 0 ′ = Q 0 Q_0'=Q_0 Q0′​=Q0​且 F ′ = Q 0 F'=Q_0 F′=Q0​”

  • 增加了兩條邊之後，這個就是可接收 F ω = ( A ∗ B ) ω F^\omega=(A^*B)^\omega Fω=(A∗B)ω的NBA了

加法運算

對于任意的NBA： A 1 \mathcal{A_1} A1​和 A 2 \mathcal{A_2} A2​

• A 1 + A 2 = ( Q 1 ∪ Q 2 , Σ , δ , Q 0 , 1 , F 1 ∪ F 2 ) \mathcal{A_1}+\mathcal{A_2}=(Q_1 \cup Q_2,\Sigma,\delta ,Q_{0,1},F_1 \cup F_2) A1​+A2​=(Q1​∪Q2​,Σ,δ,Q0,1​,F1​∪F2​)
• δ ( q , A ) = δ i ( q , A ) \delta(q,A)=\delta_i(q,A) δ(q,A)=δi​(q,A)

  δ \delta δ是一個變遷函數，之前怎麼變遷的，合并後還是怎麼進行變遷

• Q 1 ∩ Q 2 = ∅ Q_1 \cap Q_2= \varnothing Q1​∩Q2​=∅
• L ω ( A 1 + A 2 ) = L ω ( A 1 ) ∪ L ω ( A 2 ) \mathcal{L}_\omega(\mathcal{A_1}+\mathcal{A_2})=\mathcal{L}_\omega(\mathcal{A_1})\cup \mathcal{L}_\omega(\mathcal{A_2}) Lω​(A1​+A2​)=Lω​(A1​)∪Lω​(A2​)

連接配接運算

對于正規表達式 L \mathcal{L} L和NBA： A ′ \mathcal{A'} A′，存在另一個NBA可接收 L . L ω ( A ′ ) \mathcal{L}.\mathcal{L}_\omega(\mathcal{A'}) L.Lω​(A′)， A \mathcal{A} A和 A ′ \mathcal{A'} A′滿足如下條件：

• NFA： A = ( Q , Σ , δ , Q 0 , F ) \mathcal{A}=(Q,\Sigma,\delta,Q_0,F) A=(Q,Σ,δ,Q0​,F)
• FBA： A ′ = ( Q ′ , Σ , δ ′ , Q 0 ′ , F ′ ) \mathcal{A'}=(Q',\Sigma,\delta',Q_0',F') A′=(Q′,Σ,δ′,Q0′​,F′)
• 在 Q ∩ Q ′ = ∅ Q \cap Q'=\varnothing Q∩Q′=∅的前提下， A ′ ′ = A . A ′ = ( Q ′ ′ , Σ , δ ′ ′ , Q 0 ′ ′ , F ′ ′ ) \mathcal{A''}= \mathcal{A}.\mathcal{A'} =(Q'',\Sigma,\delta'',Q_0'',F'') A′′=A.A′=(Q′′,Σ,δ′′,Q0′′​,F′′)
  • Q 0 ′ ′ Q_0'' Q0′′​的取值：
    • 如果 Q 0 ∩ F = ∅ Q_0 \cap F = \varnothing Q0​∩F=∅，則： Q 0 ′ ′ = Q 0 Q_0''=Q_0 Q0′′​=Q0​
    • 否則： Q 0 ′ ′ = Q 0 ∪ Q 0 ′ Q_0'' = Q_0 \cup Q_0' Q0′′​=Q0​∪Q0′​
  • F ′ ′ = F ′ F''=F' F′′=F′
  • δ ′ ′ ( q , A ) \delta''(q,A) δ′′(q,A)的取值：
    • 如果 q ∈ Q q \in Q q∈Q且 δ ( q , A ) ∩ F = ∅ \delta(q,A) \cap F=\varnothing δ(q,A)∩F=∅，則 δ ′ ′ ( q , A ) = δ ( q , A ) \delta''(q,A)=\delta(q,A) δ′′(q,A)=δ(q,A)
    • 如果 q ∈ Q q \in Q q∈Q且 δ ( q , A ) ∩ F = ∅ \delta(q,A) \cap F=\varnothing δ(q,A)∩F=∅，則 δ ′ ′ ( q , A ) ≠ δ ( q , A ) \delta''(q,A)\neq \delta(q,A) δ′′(q,A)​=δ(q,A)
    • 如果 q ∈ Q ′ q \in Q' q∈Q′，則 δ ′ ′ ( q , A ) ≠ δ ′ ( q , A ) \delta''(q,A)\neq \delta'(q,A) δ′′(q,A)​=δ′(q,A)

• 兩個NBA進行連接配接的範例：

  L ( A ) = ( A B ) ∗ \mathcal{L}(\mathcal{A})=(AB)^* L(A)=(AB)∗

  

  L ( A ′ ) = ( A + B ) ∗ B A ω \mathcal{L}(\mathcal{A'})=(A+B)^*BA^\omega L(A′)=(A+B)∗BAω

  

  則 L ( A . A ′ ) = ( A B ) ∗ ( A + B ) ∗ B A ω \mathcal{L}(\mathcal{A.A'})=(AB)^*(A+B)^*BA^\omega L(A.A′)=(AB)∗(A+B)∗BAω

  

Generalized NBA（簡寫為GNBA）

• NBA具有和 ω \omega ω正規表達式一樣的表達能力，NBA的變體也有着相同的表達能力，比如Muller，Rabin，Streett automata，Generalized Büchi automata（GNBA）
• GNBA和NBA很相似，隻有可接收狀态不相同，也就是下面的 F \mathcal{F} F
  • 一個GNBA可以無限次接收多組 F 1 , ⋯   , F k ( k ≥ 0 ) F_1,\cdots,F_k(k\geq 0) F1​,⋯,Fk​(k≥0)
  • 對于每一次 k = 0 k=0 k=0，所有的運作都可接收，對于每一次 k = 1 k=1 k=1，它和NBA類似

  F F F是可接收狀态集合， F i F_i Fi​是 Q Q Q的子集

• GNBA對于線性時間和自動機有一些作用
• GNBA是一個五元組： G = ( Q , Σ , δ , Q 0 , F ) \mathcal{G}=(Q, \Sigma, \delta, Q_0, \mathcal{F}) G=(Q,Σ,δ,Q0​,F)
  • Q , Σ , δ , Q 0 Q, \Sigma, \delta, Q_0 Q,Σ,δ,Q0​和NBA一樣
  • F = { F 1 , ⋯   , F k } \mathcal{F}=\{F_1,\cdots,F_k\} F={F1​,⋯,Fk​}是 2 Q 2^Q 2Q的子集（ k ≥ 0 k\geq 0 k≥0），即 F n ⊆ Q F_n\subseteq Q Fn​⊆Q（ k ≥ n ≥ 0 k \geq n \geq 0 k≥n≥0）
  • 可接收的字 σ = A 0 A 1 A 2 ⋯ ∈ Σ ω \sigma =A_0A_1A_2\cdots \in \Sigma^\omega σ=A0​A1​A2​⋯∈Σω
  • 對于 G \mathcal{G} G每一個 σ \sigma σ都有一個可接收的運作 q 0 q 1 q 2 ⋯ q_0q_1q_2\cdots q0​q1​q2​⋯，這是一個無限序列，且滿足：

    • q 0 ∈ Q 0 q_0 \in Q_0 q0​∈Q0​且 q i → A i q i + 1 q_{i} \xrightarrow {A_i}q_{i+1} qi​Ai​

      ​qi+1​， 0 ⩽ i 0 \leqslant i 0⩽i

      q 0 q_0 q0​是初始狀态

    • F ∈ F : q i ∈ F F \in \mathcal{F}:q_i \in F F∈F:qi​∈F， q i q_i qi​無限經常次出現
  • GNBA可識别的語言 L ω ( G ) = { σ ∈ Σ ω 存 在 一 個 針 對 G 中 的 σ 的 一 個 可 接 收 的 運 行 } \mathcal{L}_\omega(\mathcal{G})=\{\sigma \in \Sigma ^ \omega 存在一個針對\mathcal{G}中的\sigma的一個可接收的運作\} Lω​(G)={σ∈Σω存在一個針對G中的σ的一個可接收的運作}
• GNBA的一個範例：

  

  • 此GNBA的 F = { { q 1 } , { q 2 } } \mathcal{F} = \{ \{ q1 \}, \{ q2 \} \} F={{q1},{q2}}，即 F \mathcal{F} F是由 q 1 q_1 q1​組成的集合和 q 2 q_2 q2​組成的集合構成
  • 當 c r i t 1 crit_1 crit1​和 c r i t 2 crit_2 crit2​無限經常次想要接收時， q 1 q_1 q1​和 q 2 q_2 q2​會無限經常次被通路

GNBA轉NBA

• 對于任何一個GNBA G \mathcal{G} G來說，都存在一個NBA A \mathcal{A} A，使得他們的接收語言是相同的，即 L ω ( G ) = L ω ( A ) \mathcal{L}_\omega(\mathcal{G})=\mathcal{L}_\omega(\mathcal{A}) Lω​(G)=Lω​(A)

  GNBA和NBA的表達能力是一樣的

• 思想：将 F \mathcal{F} F分成 k k k塊，從初始狀态出發，當我們到達 F 1 F_1 F1​的某個狀态之後，找的到達 F 1 F_1 F1​的某個狀态， ⋯ \cdots ⋯，一直到找 F k F_k Fk​的某一個狀态，當我們到達 F k F_k Fk​的某一個狀态後，回去，再找 F 1 F_1 F1​中的某一個狀态，這樣以來，我們依次把他都經過了 F 1 F_1 F1​到 F k F_k Fk​個狀态無線經常次重複，根據這種思想，進行變換，從GNBA到NBA的一個轉換

我們怎麼知道我目前要經過哪一個 F F F ？

我們要通過增加一個變元的方式，把經過的 F F F記錄下來

• 公式：
  • GNBA： G = ( Q , Σ , δ , Q 0 , F ) G=(Q,\Sigma,\delta,Q_0,F) G=(Q,Σ,δ,Q0​,F)
  • NBA： A = ( Q ′ , Σ ′ , δ ′ , Q 0 ′ , F ′ ) A=(Q',\Sigma',\delta',Q_0',F') A=(Q′,Σ′,δ′,Q0′​,F′)
  • Q ′ = Q × { 1 , ⋯   , k } Q'=Q \times \{1,\cdots,k\} Q′=Q×{1,⋯,k}

    k的值就是上面思想上的k塊

  • Q 0 ′ = Q 0 × { 1 } = { ⟨ q 0 , 1 ⟩ ∣ q 0 ∈ Q 0 } Q_0'=Q_0 \times \{1\}=\{\left \langle q_0,1 \right \rangle|q_0 \in Q_0\} Q0′​=Q0​×{1}={⟨q0​,1⟩∣q0​∈Q0​}
  • F ′ = F 1 × { 1 } = { ⟨ q F , 1 ⟩ ∣ q F ∈ F 1 } F'=F_1 \times \{1\}=\{\left \langle q_F,1 \right \rangle|q_F \in F_1\} F′=F1​×{1}={⟨qF​,1⟩∣qF​∈F1​}
  • δ ′ ( ⟨ q , i ⟩ , A ) = { ⟨ q ′ , i ⟩ ∣ q ′ ∈ δ ( q , A ) i f   q ∉ F i ⟨ q ′ , i + 1 ⟩ ∣ q ′ ∈ δ ( q , A ) o t h e r w i s e } \delta' (\left \langle q,i \right \rangle ,A)=\begin{Bmatrix} { \left \langle q',i \right \rangle|q' \in \delta (q,A) }& if \ q \notin F_i\\ { \left \langle q',i+1 \right \rangle|q' \in \delta (q,A) }& otherwise \end{Bmatrix} δ′(⟨q,i⟩,A)={⟨q′,i⟩∣q′∈δ(q,A)⟨q′,i+1⟩∣q′∈δ(q,A)​if q∈/​Fi​otherwise​}
• GNBA轉NBA範例：
  • GNBA：

    

    F = { F 1 , F 2 } \mathcal{F}=\{F_1,F_2\} F={F1​,F2​}

    F 1 = { q 1 } F_1=\{q_1\} F1​={q1​}

    F 2 = { q 2 } F_2=\{q_2\} F2​={q2​}

    由上述可知

    這個GNBA的 F \mathcal{F} F分成2塊，是以k=2

    是以 Q ′ = Q × { 1 , 2 } Q'=Q \times \{1,2\} Q′=Q×{1,2}

    因為 Q = { q 1 , q 2 } Q=\{q_1,q_2\} Q={q1​,q2​}

    是以 Q ′ = { ⟨ q 0 , 1 ⟩ ⟨ q 0 , 2 ⟩ ⟨ q 1 , 1 ⟩ ⟨ q 1 , 2 ⟩ ⟨ q 2 , 1 ⟩ ⟨ q 2 , 2 ⟩ } Q'=\{\left \langle q_0,1\right \rangle \left \langle q_0,2\right \rangle \left \langle q_1,1\right \rangle \left \langle q_1,2\right \rangle \left \langle q_2,1\right \rangle \left \langle q_2,2\right \rangle\} Q′={⟨q0​,1⟩⟨q0​,2⟩⟨q1​,1⟩⟨q1​,2⟩⟨q2​,1⟩⟨q2​,2⟩}

    F ′ = F 1 × { 1 } = { q 1 } × { 1 } = { q 1 , 1 } F'=F_1 \times \{1\}=\{q_1\} \times \{1\}=\{q_1,1\} F′=F1​×{1}={q1​}×{1}={q1​,1}

    δ \delta δ到 δ ′ \delta' δ′的變化就不一一列舉了，具體根據上述的公式都可以得出，舉一個吧：

    • 在GNBA中， q 1 → t r u e q 0 q_1 \xrightarrow {true}q_0 q1​true

      ​q0​

    • 因為 q 1 ∈ F i q_1 \in F_i q1​∈Fi​
    • 是以 δ ′ ( ⟨ q 1 , 1 ⟩ , t r u e ) = ⟨ q ′ , 1 + 1 ⟩ = ⟨ q ′ , 2 ⟩ \delta' (\left \langle q_1,1\right \rangle,true)=\left \langle q',1+1\right \rangle=\left \langle q',2\right \rangle δ′(⟨q1​,1⟩,true)=⟨q′,1+1⟩=⟨q′,2⟩
    • 因為 q ′ ∈ δ ( q 1 , t u r e ) q' \in \delta(q_1,ture) q′∈δ(q1​,ture)，而 δ ( q 1 , t u r e ) = q 0 \delta(q_1,ture)=q_0 δ(q1​,ture)=q0​
    • 是以 q ′ = q 0 q'=q_0 q′=q0​
    • 是以，在NBA中， δ ′ ( ⟨ q 1 , 1 ⟩ , t r u e ) = ⟨ q 0 , 2 ⟩ \delta' (\left \langle q_1,1\right \rangle,true)=\left \langle q_0,2\right \rangle δ′(⟨q1​,1⟩,true)=⟨q0​,2⟩

    對于 δ ′ ( ⟨ q 1 , 2 ⟩ , t r u e ) = ⟨ q 0 , 3 ⟩ \delta' (\left \langle q_1,2\right \rangle,true)=\left \langle q_0,3\right \rangle δ′(⟨q1​,2⟩,true)=⟨q0​,3⟩，因為k=2，沒有 ⟨ q 0 , 3 ⟩ \left \langle q_0,3\right \rangle ⟨q0​,3⟩這個狀态，是以當 i i i要大于2的時候，自動變為2，也就是 δ ′ ( ⟨ q 1 , 2 ⟩ , t r u e ) = ⟨ q 0 , 2 ⟩ \delta' (\left \langle q_1,2\right \rangle,true)=\left \langle q_0,2\right \rangle δ′(⟨q1​,2⟩,true)=⟨q0​,2⟩

  • 最終的NBA：