2015年4月27日 星期一

Formal Language - Ch1 決定性有限自動機 Deterministic Finite automata, DFA

沒有留言:
 

為何要定義有限自動機(finite automata)?
最早科學家想要定義「計算」這件非常基本的事,但在數學裡,越是基本的是越難找到一個完整精確的描述方式。而「計算」這個詞基本上是一個「動作」,就像定義「坐下」,沒有「人」這個對象來執行「大腿彎曲後把重心放在椅子上」的話很難定義「坐下」,因此科學家定義了一些不同版本的機器來試圖定義「計算」這個動作。

決定性有限自動機(Deterministic Finite automata, DFA)介紹
有限狀態機可以看成是一種模型,用來描述擁有極為有限的記憶體的電腦。如控制自動門的設備就像是一種有限自動機,只有單一位元的記憶體。在有限自動機的模型定義中,沒有限定輸入字串的長度是有限的,也就是說有限狀態機是「記憶」有限,但「輸入」可以無限長。(決定性的意思將於之後的章節解釋,通常只講有限狀態機的話是指決定性有限狀態機)

狀態圖(state diagram)來描述自動門作用:




有限自動機定義
一個有限自動機是含有5個元素的 5-tuple$(Q,Σ,δ,q_0,F)$ ,意義分別是 (狀態集$Q$, 字母集$Σ$, 轉移函式$δ$, 開始狀態$q_0$, 結束狀態$F$) ,從定義中可知F可以是空集合,表示沒有可以接受的狀態。

原文定義如下:
A finite automaton is a 5-tuple $(Q,Σ,δ,q_0,F)$ , where
  1. $Q$ : is a finite set called the states
  2. $Σ$ : is a finite set called the alphabet
  3. $δ$ : $Q \times Σ \rightarrow Q$, is the transition function //箭頭線段代表狀態的變化
  4. $q_0 ∈ Q$ : is the start state //開始狀態
  5. $F ⊆ Q$ : is the set of accept states or final states //接受狀態

看一個狀態圖例子最容易理解:



當$M_1$接受輸入字串1101時,會經過處理然後產生接受(accept)或是拒絕(reject)的輸出,字串1101從左到右依序進入$M_1$,從$q_1$開始, 由輸入的符號來判斷下一個狀態,最後輸入的符號將有限自動機引導到最後的狀態,若這個狀態是接受狀態,則輸出accept,否則就輸出reject。我們可以把處理的過程列出來 :
  1. 從$q_1$開始,接受輸入1,到$q_2$。
  2. 接著$q_2$接受輸入1,到$q_2$。
  3. 接著$q_2$接受輸入0,到$q_3$。
  4. 接著$q_3$接受輸入1,到$q_2$。
  5. 輸出accept。




有限自動機下的「計算」定義
如果一系列的狀態 $r_1,r_2,...r_n \in Q$ 符合下面三個條件,則稱這個有限自動機 $M = (Q,Σ,δ,q_0,F)$ 接受一個字串 $w = w_1w_2w_3 \dots w_n$
  1. $r_0 = q_0$,意思是機器M從他的初始狀態出發
  2. $δ(r_i, w_{i+1}) = r_{i+1}, i = 0,...,n-1$,意思是機器M慢慢吃字串根據轉移函式而轉移狀態的過程
  3. $r_n \in F$,意思是機器M吃完字串停在接受狀態





有限自動機相關的專有名詞
  • 語言 (Language) : 機器M的language A,意思是說language A是收集所有機器M可以接受的字串所形成的集合,寫成 $L(M) = A$。
  • 辨識 (Recognizes) : 通常寫成機器M recognizes A,意思是機器M可以「辨識」language A這個集合(所有裡面的字串)。
    • 注意[1] : 一個machine M只recognize一個language。
    • 注意[2] : 小心單位,language 是一種「集合」,因此 “Recognizes” 這個動詞後接 Language, “accept” 這個動詞後才接string。但後面接language時,也有些人用accept。
  • 正則語言 (Regular Language) : 假如一種語言能夠由某個有限狀態機辨識,則該語言就是一種正則語言。



正則算子 The Regular Operations
正則語言(Regular language)在這幾個算子(Operations)下具有封閉性。
  1. 聯集 Union : $A \cup B = \{x\ |\  x \in A\ or\ x \in B\}$,就是普通的集合聯集操作
  2. 字串串接 Concatenation : $A\cdot B = \{xy\ |\ x \in A\ and\ y \in B\}$,就是字串串接字面上的意思,把兩個字串接起來。
  3. Star : $A^* = \{x_1x_2...x_k\ |\ k \geq 0\ and\ x_i \in A\}$,就是這個字串可以隨意串接n次,出現0次也是可能的,用上面兩個算子來表達的話可以寫成 $A^* = \phi \cup A \cup A^2 \cup \cup A^3 ... $ (平方表示自己跟自己串接)



[用心去感覺] program vs finite automaton
  • A program behaves like a finite automaton:
    • Its start state is a function mapping program variables
    • to their initial values
    • Program execution goes from state to state by transitions performed according to program control flow
    • The language of this machine is the class of problems solved by program execution
  • A program computation differs from FA computation because:
    • A program may have a potential infinite set of states and can run forever
    • During execution a program may interact with its environment
    • The accepting state of the program has a larger interpretation




Reference

交大陳穎平教授正規語言講義





沒有留言:

張貼留言

技術提供:Blogger.