image

前言與心得整理

進入到第二週,不知道會不會有更困難的主題出現.寫筆記寫著寫著,發現自己筆記內容比原本老師講的還要多,代表自己不懂得真的太多,需要不斷的補充資料來讓自己更清楚.

相關文章

第二週課程內容:

Regular Express 基本定義 與 運算

符號定義:

通常顯示E來表達一個regular expression,而L(E) 就表示一個regular expression 能表達出來的語言(language).

Language的運算: (Union/Concatenation/Kleene Star)

  • Union (U): 就是把兩個language做一個簡單的聯集.
    • ex: {01, 11, 101} U {10, 11, 101} = {01, 10, 11, 101}
  • Concatenaion (LM): 把兩個language做一個連接,但是注意這裡跟字串的concatenation是不同的.基本定義而顏,把語言L跟語言M連接在一起就稱為LM. LM = wx | w in L and x in M
    • ex:
      • L = { 01, 11}
      • M = { 10, 11}
      • LM = { 0110, 0111, 1110, 1111} 也就是 第一個L元素配上第一個M元素,第二個L元素配上第一個M元素.繼續類推.
  • Kleene Star (*): 就是regex裡面的*,表達任何子集合在L中與空集合或是一個以上的子集合的聯集. L* = {ε} U L U LL ...
    • ex: L = {01, 11} L*= {} or {01, 11} or {0101, 0111, 1101, 1111} ....

Regular Expression定義

  • a是一個symbol, 如果a是一個regular express(記作RE),則 L(A) = {a}
  • L{ε} = {ε}
  • L(empty set) = empty set

將Langugage的運算套用過來,其中E1E2代表兩個RE:

  • U運算: L(E1+ E2) = L(E1) U L(E2)
  • Concatenation: L(E1E2) = L(E1)L(E2)
  • Kleene Star (*) : L(E*) = (L(E))*

以下列出一些範例:

  • 基本定義: L(0) = {0}, L(01) = {01}
  • Union: L(01+0) = L(01) U L(0)= {01} U {0} = {01, 0}
  • Concatenation: L(0(1+0))= L(0)L(1+0) = {0}{1,0} = {01, 00}
  • Kleene Star: L(0*)={ε, 0, 00, 000, ... }
  • 複雜一點的綜合運算: L((0+10)*(ε+1)) = L((0+10)*) L(ε+1) = L({0, 10}*) L(1)
    • 根據以上得結果,所有的Language,不論是0開頭或是1開頭,1結尾,但是只要沒有兩個連續的1就符合.
    • ex: {01} {0001} {0101010101}
    • 連續兩個1不再其中,因為是 ({0} + {10})* U {1}

將RE用ε-NFA表示:

要將RE(Regular Expression)用ε-NFA來表示,基礎的概念如下:

    邊線(arc)代表一個symbol,而路徑可以表示成 a, ε, empty set

image

(image from coursera Automata Course)

套用基礎運算的上如下:

Union: 就是一個分支的圖形

image

(image from coursera Automata Course)

Concatenation: 就是一個連接的圖形

image

(image from coursera Automata Course)

Closure: (CL) 就是一個自己與自己迴圈的圖形(簡單來說 Kleene Star -> Closure)

image

(image from coursera Automata Course)

將RE用DFA表示

概念上就是依照以下的方式:

    狀態(state)也就是我們節點
    而邊線(arc)就是我們會出現的symbol
    所以DFA所能接受的路線(path)就是我們要的語言(language).

image

拿前一章節出現過的圖,舉例來說:

  • 這個DFA要表達的A->B 的Language可以是{11} 或是 {0011} 或是 {0001} 也可以說L(E)={1,01,0101...}
  • 所以這個RE可以表達為E=(0)*1+(10)*1 也就是說
    • 0可以出現一次或是無限次,但是最後一定要有一個1
    • 或是(01)可以出現一次或是無限次,但是最後一定要接著1

k-Path

這邊指的K-Path指的是要透過狀態i到達狀態j其中只能經過k(其中k代表1…k, 比如說k=2 也就是 0, 1, 2)能到達目的狀態的路線,先用簡單的DFA來舉例,舉例而言. 請注意所謂的 k-path不代表必須經過k,是可以不經過的.

image

由狀態A->B的k-path

  • 0-path 也就是A->B不經過任何其他狀態,結果1
  • A-path 也就是A->B可以經過狀態A,結果0*1+1,也就是可以走無限個0然後走到B或是直接走到B.
  • B-path 可以經過B,也可以經過A(這裏假設 A = B - 1),當然可以都不經過.所以推導出來也就是整個DFA的RE:也就是 0*1+(10)*1

關於 k-path的推導題

k-path通常指的是由狀態i 到狀態j 必須經過k狀態(其中k代表的是 0, 1, 2, … k).

    記作 R_ij^(k) (其中 ij 為下標,k為上標)

所以R_ij^(k) 也可以換成思考為:

  • 路徑由 i到j 不經過 k (k-path是可以不經過k,也代表經過k個數是0)
  • 或是:
    • 路徑由i到k
    • 路徑k走到過所有k-1的狀態回到k
    • 路徑由k走到j

如以下圖:

image

透過以上的圖示,可以推導出公式如下:

    R_ij^k = R_ij^(k-1) #也就是 i->j 不經過 k
            +  R_ik^(k-1)   R_kk^(k-1)*  R_kj^(k-1)   # 就是 i->k, k-k, k->j   

UNIX (REGEX) Regular Expression

接下來,課程談到介紹UNIX上面常使用的Regular Express.這邊大家應該比較熟悉,只把幾個常用符號整理一下:

  • [a-c] 指的是 a, b, c 都可以
  • [a-z] 同理可證,就是所有小寫字母.
  • “+” 指的是出現至少一次.
  • “*” 指的是零次或是以上.
  • “?” 指的是零或是一次.

還有一些跟RE與NFA跟DFA的轉換可以筆記一下:

  • UNIX RE 先轉換成 ε-NFA (並且擁有自己的final state)
  • 設定一個新的start state 並且將原本的ε-NFA 作為 ε-translations
  • 透過ε-translations就可以轉換成DFA
  • 透過DFA可以再度的轉換到RE去

詳細的轉換方式,可以參考以下圖片

image

Decision Properties of Regular Language

####定義:

Decision Properties of Regular Language指的是是一個演算法來作為正式敘述一個語言的方式.

舉例:

  • Is string w in language L?
  • Are those two language the same?

####The Emptiness Problem

指的是給予的Language是不是符合這個RE也就是說,假設是DFA給予的語言,能不能夠從start state 跑到 final state.

####The Infinitness Problem

指的是RE中是否有發生迴圈的圖形. 而檢查圖形是否為 Inifitness 最簡單的方法是:

    如果全部的狀態個數為n, 只要可以接受輸入language個數,而且 m >n.  代表就會有迴圈發生.

image

就會像是以上的圖形一樣.

Pumping Lemma

需要先定義一下,什麼是Pumping Lemma,根據wiki上面解釋如下:

    RE中一個長字串,其中有一段文字有出現超過一次以上.

簡單的說,Pumping Lemma 也就是上面圖形所呈現的狀態.

那接下來就要顯示.基礎定義:

  • 全部的狀態個數為n,輸入的語言為w
  • w = xyz
  • xz] <= n
    • 這邊解釋一下 xz 代表的是出現的alphabet個數,比如說 x=abca z=bcdb |xz|=abcd
  • y > 0
  • For all i>=0 xy^i z is in L

這幾個定義裡面,最重要的其實是|xz] <= n.因為找出y的方式不是在找出重複的,而是要確認|xz].以下舉一個例子:

Pumping Lemma 範例:

ex: 語言L他的狀態為1,2,3 輸入為{a, b, c} 輸入為 {abacca},他們的狀態變化是 1(a)->2(b)->3(a)->2(c)->1(c)->3(a)->2 找出他的w =xyz的pumping lemma

解法:

  • 首先試著去找出第一個重複的狀態.也就是1->2->3->2->…
  • 這時候抽出2->3的輸入{ba} 即為 y
  • 同理,可以分解出前面的x={a} z={cca}.同時驗證 xz = {ac} <= 3

如何驗證兩個DFA L與M 是否equivalence

要證明兩個DFA是否equivalence,需要透過以下方式:

  • 計算 L product M
  • 找出 w 滿足L也滿足M(滿足:accept 代表能由start state到final state)
  • 這樣就可以證明 L與M是 equivalence

接下來,要如何做 L product M方法如下:

  • 假設Q1 是 L的所有狀態, Q2是M的所有狀態
  • 找出Q1與Q2的start state [q1, q2]
  • 開始iterate 每一個transition function,並且找出product DFA
  • 透過最後的Product DFA找出一個w 可以由start state走到final state.
  • 即代表兩個DFA L與M是equivalence

image (image from coursera Automata Course)

範例:
  • 起始點為[A, C]
  • 走第一個transition input 0
    • [A, D]
  • 走第二個transuion input 1
    • [B, C]
  • 依照這個方式… 慢慢建構出所有的DFA如上圖右

Closure Properties of Regular Language

這裏主要是敘述定理,還有一些證明方式,主要定義如下:

  • L 跟 M 都是 Regular Language (可以使用regular expression表示出來)

進行以下的操作,並且證明結果都是屬於regular language:

  • Union: L U M 仍然是regular language (可以用regular expression來表示)
    • R是L的regular expression, S 是 M的regular expression.L U M = R + S.可以得知 `R + S仍然是regular expression (根據 union law)
  • Concatenation / Kleene Star: 根據以上的方式, RS (concatenation),及 R* , S* 仍然都符合regular expression (concatenation and kleene star law)
  • Intersection: L intersect M 代表裡面的 R S要找出交集的部分,使用的方式是將兩個圖形做 product 然後找出product的regular expression 即為 L intersect M.
  • Difference: L - M 也會是符合regular language. 根據上一則的方式,透過 product DFA LM 可以找出一個流程是 L 可以由start state跑到 final state但是 M不行. 由於該流程regular expression 是存在於L的其中一個,所以該流程也是符合regular expression. 所以 L - M 也符合regular langugage
  • Completement: completement in L = sigma(Σ)* - L sigma(Σ) 是regular languge 當然Σ* 也是regular languge根據剛剛的difference 定理 L - M 也符合regular langugage自然而然 Σ* - L 也是.
  • Reversal: L^R 表示Reversal 代表的是 L = {0, 01, 11} L^R = { 0^R, (01)^R, (11)^R}= { 0, 10, 00}
    • 需要注意的是 (0)^R = 0 同理可證 (1)^R = 1
    • 相關的Reversal Law:
      • (F+G)^R= F^R + G^R
      • (FG)^R = G^R F^R
      • ((F)*)^R = ((F)^R)*
    • 範例: E = 01* + 10* + 1 找出 E^R
      • E^R = (01*)^R + (10*)^R + 1^R
      • (1*)^R 0^R + (0*)^R 1^R + 1
      • (1^R)* 0 + (0^R)* 1 + 1
      • 1*0 + 0*1 + 1
  • Homomorphism: h(L)就是透過某些轉換是來把原先的alphabet做一個替換.
    • ex L = {0, 10, 11} h(0)->A, h(1)->B 則 h(L) = { A, BA, BB}
  • Inverse Homomorphism: h^-1(L)是將把透過 h(L2)的結果轉換回 L2. h(L) = L1, h^-1(L1)= L

相關程式

我也把NFA的概念加以實現成一個小工具.放在https://github.com/kkdai/nfa

原本根據定義是無法實現,但是我透過BFS還是可以做出來.只是還在思考是不是有遺漏的案例.

參考網址


Evan

Attitude is everything