• 正則表達 （regular expression）
    • 正則表達式就像一個公式，是純語法的；但是，每一個表達都展現了一個字元串的集合。
    • 正則表達跟DFA和NFA是等同的：
      • 每一個DFA A都有一個正則表達式 r， L(A)=L(r)；反之亦然。
  • 常用符號：
    • 字母表（alphabet）或辭彙表（vocabulary）是一系列字母（token or letter）的集合。記作： Σ
    • Σ上的字元串（string）是一系列字母，或空字元串 ε。
  • grammar 文法 （文法描述語言）
    • 定義：< Vt,Vn,S,P > 由四部分組成
      • Vt：終止符號的有限集合 （相當於樹結構中的葉子結點，或為空）
      • Vn：非終止符號的有限集合 （相當於樹結構中的枝節點，可以有孩子，可以被擴展）
      • S： 起始符號，是一個獨特的非終止符號 （相當於樹結構中的根結點）
      • P：一系列生產的集合： α→β （ α中至少有一個非終止符號，β是符號的任意數組）
    • 例如： 語法 G =?{a,b}, {S,A}, S, {S →aAb, aA→aaAb, A→ε}?
      • 其中 終止符號：{a, b}; 非終止符號:{S,A}; 起始符號：S; 操作： S → aAb aA → aaAb A→ε。
      • S -> aAb -> aaAbb -> aaaAbbb -> aaabbb (這裡aaabbb是一個句子）
        • 所以以上的文法可以推出的語言是：
          • L(G) = {a^nb^n |n∈N,n≥1}
          • 與他有相同語言的文法：例如： S → aSb, S → ab.可見，文法與語言並不是一對一的關係。
    • 喬姆斯基分層（ Chomsky Hierarchy ）：
      • Noam Chomsky是一個語言學家。
      • 文法進化的過程：
        • 不受限制的文法：沒有任何條件
        • 上下文敏感的文法： 文法生產公式的左面的長度必須比右面的長。（有一個例外，這裡沒查到）
        • 上下文無關的文法：每個生產的左面只能是單個的非終止符號。
        • 正則文法：對生產左面有跟上下文無關文法相同的限制，另外它對生產的右面也有限制。
      • 在上面的例子中，L=a^nb^n， 在上一篇DFA&NFA的筆記中提到過，是沒有DFA能接受L的（因為存儲有限），那就意味著它沒有對應的正則文法，所以，L是上下文無關的但不是正則的。
    • 正則文法：
      • 定義：正則文法的生產要麼是左線性 （A-> aB)，要麼是右線性(A->Ba)。左線性文法和右線性文法是等同的（以下均考慮右線性文法）。
      • 以下說法是等同的：
        • L是由右線性文法產生的。
        • L是由左線性文法產生的。
        • L可以被一些DFA接受。
        • L可以被一些NFA接受。
        • L是一種正則表達。
    • 上下文無關文法：A-> w， 左側A是非終止符號，右側可以是任何東西。
      • 例：為語言 L={ambncm?n |m≥n≥0} 設計一個上下文無關文法。
        • S → aSc | TT → aTb | ε （因為 ω=am?n |anbn |cm?n ）
    • 輔助存儲：
      • 沒有輔助存儲：NFAs和DFAs：正則表達
      • 棧存儲：下推機（push-down automata， PDA）：上下文無關文法。
      • 無止境帶子：圖靈機（Turing machines): 所有語言。
  • 下推機PDA
    • 組成：讀取指針，輸入存儲帶，棧存儲
    • 動作actions：改變內部狀態、壓入（push）和彈出（pop）棧、前進到下一個輸入字元。
      • 注意：動作通常依賴於當前狀態、輸入字元、棧頂端的字元。
    • 接受：下推機能夠接受這個字元串，如果
      • 輸入字元串被完全讀取
      • 下推機處於接受狀態
      • 棧是空的
    • 上下文無關文法可以被下推機識別，但不可以被DFA識別。
    • PDA的定義：（確定型） (Q,q0,F, Σ, Γ,Z, δ)

      Γ是棧符號，Z屬於 Γ，是初始棧符號； δ是轉化公式 Q×(Σ∪{ε})×Γ → Q×Γ?

    • PDA的兩種轉變形式：
      • 消耗輸入型： (q1,x,s) → q2/σ，消費了輸入字元x
      • 不消耗輸入型： (q1, ε, s) → q2/σ， 可以發生在任何時候，不消耗任何輸入字元。
    • 例： L = {a^nb^n | n ≥ 1}

定義轉換公式如下：

δ(q0,a,Z) → q1 /aZ 讀取並壓入第一個a到Z中，進入新狀態q1
δ(q1, a, a) → q1 /aa 讀取接下來的as並且壓入棧中，直到讀到第一個b
δ(q1, b, a) → q2 /a 讀到b，開始彈出a，
δ(q2, b, a) → q2/ε 彈出後續a
δ(q2,ε,Z) → q3/ε 輸入全部讀完，剩空棧Z

追蹤PDA：
(q0,aaabbb,Z) ?
（q1，aabbb，aZ) 讀取並壓入第一個a
? (q1,abbb,aaZ) 壓入第二個a

? (q1,bbb,aaaZ) 壓入第三個a

? (q2,bb,aaZ) 讀到第一個b，彈出第一個a

? (q2,b,aZ)
讀第二個b，彈出第二個a
? (q2,ε,Z)
讀第三個b，彈出第三個a
? (q3 , ε, ε) 消耗完了所有輸入字元，變空棧，接受。

  • 例2（PDA拒絕的例子）

（q0， aaba， Z）=> (q1, aba, aZ)
=> (q1, ba, aa)
=> (q2, a, az)
=> ??？ (狀態q2的條件下，讀入a沒有轉換定義）

  • 非確定性PDAs： δ ? Q×(Σ∪{ε})×Γ × Q×Γ?
    • 與確定性PDA的區別是：
      • 確定的：至多有一個轉換
      • 非確定：0個或多個轉換都可能
  • 定理：上下文無關語言（CFL）和非確定性PDA是等同的。
    • 對於任意一個CFL L都存在一個PDA接受L
    • 如果L被一個非確定性PDA所接受，那麼L是CFL

    推薦閱讀：

    相关文章