有限狀態(tài)自動(dòng)機(jī)概述
有限狀態(tài)自動(dòng)機(jī)-守衛(wèi)版
狀態(tài)機(jī)實(shí)戰(zhàn)-監(jiān)聽
github: https://github.com/wenyu7980/statemachine

有限狀態(tài)自動(dòng)機(jī)

有限狀態(tài)自動(dòng)機(jī)（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限內(nèi)存的計(jì)算過程和某些語言類而抽象出的一種計(jì)算模型。有限狀態(tài)自動(dòng)機(jī)擁有有限數(shù)量的狀態(tài)，每個(gè)狀態(tài)可以遷移到零個(gè)或多個(gè)狀態(tài)，輸入字串決定執(zhí)行哪個(gè)狀態(tài)的遷移。有限狀態(tài)自動(dòng)機(jī)可以表示為一個(gè)有向圖。有限狀態(tài)自動(dòng)機(jī)是自動(dòng)機(jī)理論的研究對(duì)象

其主要特點(diǎn)有以下幾個(gè)方面：

1. 系統(tǒng)具有有限個(gè)狀態(tài)，不同的狀態(tài)代表不同的意義。按照實(shí)際的需要，系統(tǒng)可以在不同的狀態(tài)下完成規(guī)定的任務(wù)。
2. 我們可以將輸入字符串中出現(xiàn)的字符匯集在一起構(gòu)成一個(gè)字母表。系統(tǒng)處理的所有字符串都是這個(gè)字母表上的字符串。
3. 系統(tǒng)在任何一個(gè)狀態(tài)下，從輸入字符串中讀入一個(gè)字符，根據(jù)當(dāng)前狀態(tài)和讀入的這個(gè)字符轉(zhuǎn)到新的狀態(tài)。
4. 系統(tǒng)中有一個(gè)狀態(tài)，它是系統(tǒng)的開始狀態(tài)。
5. 系統(tǒng)中還有一些狀態(tài)表示它到目前為止所讀入的字符構(gòu)成的字符串是語言的一個(gè)句子。

形式定義

定義：有限狀態(tài)自動(dòng)機(jī)(FA—finite automaton)是一個(gè)五元組：

M=(Q, Σ, δ, q0, F)

其中，

• Q :狀態(tài)的非空有窮集合。?q∈Q，q稱為M的一個(gè)狀態(tài)。
• Σ :輸入字母表。
• δ :狀態(tài)轉(zhuǎn)移函數(shù)，有時(shí)又叫作狀態(tài)轉(zhuǎn)換函數(shù)或者移動(dòng)函數(shù)，δ：Q×Σ→Q，δ(q,a)=p。
• q0 :M的開始狀態(tài)，也可叫作初始狀態(tài)或啟動(dòng)狀態(tài)。q0∈Q。
• F :M的終止狀態(tài)集合。F被Q包含。任給q∈F，q稱為M的終止?fàn)顟B(tài)。

例：

文字描述：

• Q 狀態(tài)集合： START，WALKING，RUNNING，STOP
• q0 始狀態(tài)：START
• F 結(jié)束狀態(tài)：[STOP] (集合)
• Σ 事件集合：[WALK,RUN,STOP]
• δ 狀態(tài)轉(zhuǎn)移函數(shù)： 參考下表

表：

圖：

（visio UML狀態(tài)機(jī)圖）

image.png

圖表關(guān)系
表中每一行線都代表者圖中的每一條線