有限狀態(tài)自動機是具有離散輸入和輸出的系統(tǒng)的一種數(shù)學(xué)模型。
其主要特點有以下幾個方面：
– (1)系統(tǒng)具有有限個狀態(tài)，不同的狀態(tài)代表不同的意義。按照實際的需要，系統(tǒng)可以在不同的狀態(tài)下完成規(guī)定的任務(wù)。
– (2)我們可以將輸入字符串中出現(xiàn)的字符匯集在一起構(gòu)成一個字母表。系統(tǒng)處理的所有字符串都是這個字母表上的字符串。
– (3)系統(tǒng)在任何一個狀態(tài)下，從輸入字符串中讀入一個字符，根據(jù)當(dāng)前狀態(tài)和讀入的這個字符轉(zhuǎn)到新的狀態(tài)。
– (4)系統(tǒng)中有一個狀態(tài)，它是系統(tǒng)的開始狀態(tài)。
– (5)系統(tǒng)中還有一些狀態(tài)表示它到目前為止所讀入的字符構(gòu)成的字符串是語言的一個句子。
–
形式定義
? 定義：有限狀態(tài)自動機(FA—finite automaton)是一個五元組：
– M=(Q, Σ, δ, q0, F)
? 其中，
– Q——狀態(tài)的非空有窮集合。?q∈Q，q稱為M的一個狀態(tài)。
– Σ——輸入字母表。
– δ——狀態(tài)轉(zhuǎn)移函數(shù)，有時又叫作狀態(tài)轉(zhuǎn)換函數(shù)或者移動函數(shù)，δ：Q×Σ→Q，δ(q,a)=p。
– q0——M的開始狀態(tài)，也可叫作初始狀態(tài)或啟動狀態(tài)。q0∈Q。
– F——M的終止?fàn)顟B(tài)集合。F被Q包含。任給q∈F，q稱為M的終止?fàn)顟B(tài)。