2012年8月14日 星期二

自動機與正規表示式

前幾天在神人的網誌上拜讀了關於RegExp的整理,除了順便(worship)一下,熊熊想起自動機好像跟正規表示式有點關係,剛剛找到了修`自動機與形式語言'的筆記,作些整理於下。

如有錯誤還請指教,謝謝 :-)

語言(Language)


一個所謂的語言,是由許多的單字(Word)組成,而單字則是由字母(Alphabet)所組成。字母指的是一個有限的符號集合,像是英文字母就是由A 到Z 等字母所組成;而binary alphabet 就是{0,1}。

單字則是由有限個數的字母所組合而成的字串。一堆單字就能組成語言。而一個語言是不會超過字母以任何長度任意排列所形成的的這個集合。


有限自動機(Finite Automata)


一個有限自動機M 是由以下五個要素所構成:
  1. 有限的狀態集合Q
  2. 字母Σ
  3. 一個狀態在遇到不同字母時該跳轉到哪一個狀態的轉換function δ
  4. 起始狀態q0
  5. 終止狀態F
寫成M=(Q,Σ,δ,q0,F),例如:




                 1              0
    => (q0) --->((q1))---> (q2)
            |_|         |_|  \______|
             0         1        0,1

Q = {q0,q1,q2}
字母 = {0,1}
δ:
q0q1q2
0q0q2q1
1q1q1q1

起始狀態q0
終止狀態F=q1


要能夠使這樣一個自動機(畫的不是很好,囧)走到終止狀態,只有輸入至少有一個`1' 且最後一個`1' 的後面有偶數個`0' 的單字(感謝強者阿蹦指正)。而被這台自動機接受(也就是輸入可以走到終止狀態)的單字集合就形成了一個語言。

我們用L(M)來表示被M 這台自動機所接受的語言L 。換個角度來想,也就是這台自動機M 是用來表示L(M)這個語言的。

如果說,一個語言可以被一台有限自動機接受,那這個語言便稱作「正規語言(Regular Language)」。

正規表示式(Regular Expression)



Theorem
A Language L is regular iff exists regular expression R s.t. L = L(R)
一個語言L 是正規語言若且唯若存在一個正規表示式使該語言為該正規表示式所表述。(不知道這樣翻譯的到不到位XD)

因此我們所見的正規表示式是用來描述語言的,事實上一個正規表示式與有限自動機甚至是等價的。我們可以依照正規表示式的規則將之轉換為一台NFA(Nondeteministic finite state automaton),而也可以將NFA 轉為DFA (即上述之有限自動機)。

給定字母(集合)Σ:


  1. 對於屬於Σ的每個字母a, a是一個正規表示式
  2. Σ與ε(空字串)是正規表示式
  3. Φ(空集合)是正規表示式
  4. 如果R1與R2是正規表示式,則R1與R2的聯集、R1的單字尾接上R2的單字、R1的單字尾接上R1的單字等亦為正規表示式

給定正規表示式R 可以透過以下方式轉為NFA



R = a
可以換成
            a
=>(q0)--->((F))

R = ε
可以換成
=>((q0))        //起始狀態就是終止狀態

R = Σ
可以換成
=>(q0)--------------->((F))
        for any a 屬於Σ

R = R1聯集R2
可以換成
             ε
=>(q0)------>[R1的自動機]
        \   ε
         `----->[R2的自動機]



R = R1。R2
可以換成
            ε                             ε
=>(q0)---->[R1的自動機]---->[R2的自動機]

R = R1*
可以換成
             ε
=>(q0)---->[R1的自動機]
       ^             |
       |_______|
               ε

總之,透過類似上述的方法,就可以將正規表示式一步一步的變成一台有限自動機,當我們在寫正規表示式時,就像是在建立一台只吃符合我們所想要的規則的字串所組成的語言的自動機。

在寫正規表示式的時候偶而想一下那個有限自動機的樣子,或許會有些幫助吧 :-)