為何要定義有限自動機(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
- $Q$ : is a finite set called the states
- $Σ$ : is a finite set called the alphabet
- $δ$ : $Q \times Σ \rightarrow Q$, is the transition function //箭頭線段代表狀態的變化
- $q_0 ∈ Q$ : is the start state //開始狀態
- $F ⊆ Q$ : is the set of accept states or final states //接受狀態
看一個狀態圖例子最容易理解:
- 從$q_1$開始,接受輸入1,到$q_2$。
- 接著$q_2$接受輸入1,到$q_2$。
- 接著$q_2$接受輸入0,到$q_3$。
- 接著$q_3$接受輸入1,到$q_2$。
- 輸出accept。
有限自動機下的「計算」定義
如果一系列的狀態 $r_1,r_2,...r_n \in Q$ 符合下面三個條件,則稱這個有限自動機 $M = (Q,Σ,δ,q_0,F)$ 接受一個字串 $w = w_1w_2w_3 \dots w_n$
- $r_0 = q_0$,意思是機器M從他的初始狀態出發
- $δ(r_i, w_{i+1}) = r_{i+1}, i = 0,...,n-1$,意思是機器M慢慢吃字串根據轉移函式而轉移狀態的過程
- $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)下具有封閉性。
- 聯集 Union : $A \cup B = \{x\ |\ x \in A\ or\ x \in B\}$,就是普通的集合聯集操作
- 字串串接 Concatenation : $A\cdot B = \{xy\ |\ x \in A\ and\ y \in B\}$,就是字串串接字面上的意思,把兩個字串接起來。
- 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 ... $ (平方表示自己跟自己串接)
- 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
交大陳穎平教授正規語言講義
沒有留言:
張貼留言