確定優(yōu)先狀態(tài)自動(dòng)機(jī)（Deterministic Finite Automation, DFA）是一種計(jì)算模型。它包含一系列狀態(tài)，這些狀態(tài)中：
- 有一個(gè)特殊的狀態(tài)，被稱作初始狀態(tài)
- 還有一系列狀態(tài)被稱為接受狀態(tài)，它們組成了一個(gè)特殊的集合。其中，一個(gè)狀態(tài)可能既是初始狀態(tài)，也是接受狀態(tài)。
起初，這個(gè)自動(dòng)機(jī)處于初始狀態(tài)。隨后，它順序地讀取字符串中的每一個(gè)字符，并根據(jù)當(dāng)前狀態(tài)和讀入的字符，按照某個(gè)事先約定好的轉(zhuǎn)移規(guī)則，從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)；當(dāng)狀態(tài)轉(zhuǎn)移完成后，它就讀取下一個(gè)字符。當(dāng)字符串全部讀取完畢后，如果自動(dòng)機(jī)處于某個(gè)接受狀態(tài)，則判定該字符串被接受；否則，判定該字符串被拒絕。
如果輸入的過程中某一步轉(zhuǎn)移失敗了，即不存在對應(yīng)的轉(zhuǎn)移規(guī)則，此時(shí)計(jì)算將提前中止。在這種情況下我們也判定該字符串被拒絕。
確定有限狀態(tài)自動(dòng)機(jī)總是能夠回答某種形式的對于給定的輸入字符串S，判斷其是否滿足條件P的問題。
確定有限狀態(tài)自動(dòng)機(jī)驅(qū)動(dòng)的編程，可以被看做一種暴力枚舉方法的延伸：它窮盡了在任何一種情況下，對應(yīng)任何的輸入，需要做的事情。
自動(dòng)機(jī)在計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用。在算法領(lǐng)域，它與大名鼎鼎的字符串查找算法KMP算法有著密切的關(guān)聯(lián)；在工程領(lǐng)域，它是實(shí)現(xiàn)正則表達(dá)式的基礎(chǔ)。
以劍指 Offer 20. 表示數(shù)值的字符串為例：
class Solution {
public boolean isNumber(String s) {
Map<State, Map<CharType, State>> transfer = new HashMap<>();
transfer.put(State.STATE_INITIAL, new HashMap<CharType, State>() {{
put(CharType.CHAR_SPACE, State.STATE_INITIAL);
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
}}
);
transfer.put(State.STATE_INT_SIGN, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
}}
);
transfer.put(State.STATE_INTEGER, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_POINT, State.STATE_POINT);
put(CharType.CHAR_SPACE, State.STATE_END);
}}
);
transfer.put(State.STATE_POINT, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}}
);
transfer.put(State.STATE_POINT_WITHOUT_INT, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
}}
);
transfer.put(State.STATE_FRACTION, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
put(CharType.CHAR_EXP, State.STATE_EXP);
put(CharType.CHAR_SPACE, State.STATE_END);
}}
);
transfer.put(State.STATE_EXP, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
}}
);
transfer.put(State.STATE_EXP_SIGN, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
}}
);
transfer.put(State.STATE_EXP_NUMBER, new HashMap<CharType, State>() {{
put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
put(CharType.CHAR_SPACE, State.STATE_END);
}}
);
transfer.put(State.STATE_END, new HashMap<CharType, State>() {{
put(CharType.CHAR_SPACE, State.STATE_END);
}}
);
int len = s.length();
State state = State.STATE_INITIAL;
for (int i = 0; i < len; i++) {
CharType type = toCharType(s.charAt(i));
if (!transfer.get(state).containsKey(type)) return false;
else state = transfer.get(state).get(type);
}
return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_END || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER;
}
public CharType toCharType(char c) {
if (c >= '0' && c <= '9') return CharType.CHAR_NUMBER;
if (c == 'e' || c == 'E') return CharType.CHAR_EXP;
if (c == '.') return CharType.CHAR_POINT;
if (c == '+' || c == '-') return CharType.CHAR_SIGN;
if (c == ' ') return CharType.CHAR_SPACE;
return CharType.CHAR_ILLEGAL;
}
enum State {
STATE_INITIAL,
STATE_INT_SIGN,
STATE_INTEGER,
STATE_POINT,
STATE_POINT_WITHOUT_INT,
STATE_FRACTION,
STATE_EXP,
STATE_EXP_SIGN,
STATE_EXP_NUMBER,
STATE_END
}
enum CharType {
CHAR_NUMBER,
CHAR_EXP,
CHAR_POINT,
CHAR_SIGN,
CHAR_SPACE,
CHAR_ILLEGAL
}
}
狀態(tài)一定要定義好，小數(shù)后的整數(shù)和小數(shù)的前的整數(shù)是不一致的，需要使用不同的狀態(tài)
STATE_INTEGER和STATE_FRACTION
參考文獻(xiàn)：
