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

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

國立空中大學
http://prompt.nou.edu.tw/web/sno204/content/w01/01-02-01t.htm