前幾天在
神人的網誌上拜讀了關於RegExp的整理,除了順便(worship)一下,熊熊想起自動機好像跟正規表示式有點關係,剛剛找到了修`自動機與形式語言'的筆記,作些整理於下。
如有錯誤還請指教,謝謝 :-)
語言(Language)
一個所謂的語言,是由許多的單字(Word)組成,而單字則是由字母(Alphabet)所組成。字母指的是一個有限的符號集合,像是英文字母就是由A 到Z 等字母所組成;而binary alphabet 就是{0,1}。
單字則是由有限個數的字母所組合而成的字串。一堆單字就能組成語言。而一個語言是不會超過字母以任何長度任意排列所形成的的這個集合。
有限自動機(Finite Automata)
一個有限自動機M 是由以下五個要素所構成:
- 有限的狀態集合Q
- 字母Σ
- 一個狀態在遇到不同字母時該跳轉到哪一個狀態的轉換function δ
- 起始狀態q0
- 終止狀態F
寫成M=(Q,Σ,δ,q0,F),例如: