有限狀態(tài)自動(dòng)機(jī)是具有離散輸入和輸出的系統(tǒng)的一種數(shù)學(xué)模型。
其主要特點(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的終止?fàn)顟B(tài)集合。F被Q包含。任給q∈F，q稱為M的終止?fàn)顟B(tài)。