浅谈DFA确定有限状态自动机

本文介绍确定有限状态自动机DFA的基本原理,并结合具体示例进行实践

abstract.png

基本原理

对于DFA确定有限状态自动机A而言,其通常包含以下几个元素:

  1. 非空有限的状态集合 Q
  2. 非空有限的输入集合 ∑
  3. 转移函数 𝜹: Q x ∑ -> Q。其决定了当前状态在某输入的作用下自动进入的下一个状态。例如 𝜹(q,𝝈)=p,其中:p∈Q,q∈Q,𝝈∈∑
  4. 初始状态 s∈Q
  5. 可接受状态集合 F⊆Q。其表明当输入结束时,自动机所处状态为合法状态的集合

换言之一个DFA可以表述为A=(Q,∑,𝜹,s,F)。其基本工作流程:DFA从初始状态开始,每当从输入集合中读入一个输入元素时,DFA便根据转移函数自动转移至下一个状态。当输入完毕时,自动机的状态如果为可接受状态,则表示输入合法;反之即为非法。至此可以看出DFA能够处理的场景为:对于给定的输入字符串S,判断其是否满足条件P

实践

学习过程中要善于理论联系实际。故在介绍完DFA的基本原理后,现在我们来进行实践。这里以LeetCode的剑指Offer(第2版)题单中的第20题——表示数值的字符串为例

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)

数值(按顺序)可以分成以下几个部分:

  • 若干空格
  • 一个 小数 或者 整数
  • (可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数
  • 若干空格

小数(按顺序)可以分成以下几个部分:

  • (可选)一个符号字符(’+’ 或 ‘-‘)
  • 下述格式之一:
    1. 至少一位数字,后面跟着一个点 ‘.’
    2. 至少一位数字,后面跟着一个点 ‘.’ ,后面再跟着至少一位数字
    3. 一个点 ‘.’ ,后面跟着至少一位数字

整数(按顺序)可以分成以下几个部分:

  • (可选)一个符号字符(’+’ 或 ‘-‘)
  • 至少一位数字

部分数值列举如下:
[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非数值列举如下:
[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

对于本题而言,非常适合通过DFA解决。现在按照DFA的五元素依次进行分析。对于输入集合而言,可以看出其有效的输入字符只能是以下几种:

  1. 空格
  2. 数字
  3. 符号位:+正号、-负号
  4. 小数点
  5. 指数符号:e、E

下一步,则可以根据处理到字符串的哪个部分作为自动机的状态。至此不难分析出,对于本题其状态集合为:

  1. 起始空格
  2. 数字的符号位
  3. 整数部分
  4. 左侧有整数的小数点
  5. 左侧无整数的小数点
  6. 小数部分
  7. 指数符号
  8. 指数的符号位
  9. 指数部分的整数
  10. 结束空格

不难看出,自动机的初始化状态为起始空格。同时可以看到当字符串全部输入结束时,如果自动机处于以下状态之一时,则该字符串显然是可以表示为数值的。换言之,下述状态即为本自动机的可接受状态

  1. 整数部分
  2. 左侧有整数的小数点
  3. 小数部分
  4. 指数部分的整数
  5. 结束空格

现在根据状态集合、输入集合实际上不难分析出本自动机的转移函数。具体如下所示

figure 1.jpeg

至此,DFA的五个元素就已经完全具备了。这里给出Java下的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
/**
* DFA 确定有限状态自动机
*/
class Solution {
/**
* 状态转移规则, 当前状态 + 输入类型 -> 下一个状态
* 第一层Map, key: 当前状态
* 第二层Map, key: 输入类型; value: 下一个状态
*/
private static Map<State, Map<InputType, State>> transferRule;

/**
* 定义状态转移规则
*/
static{
transferRule = new HashMap<>();

Map<InputType, State> map = new HashMap<>();
map.put( InputType.BLANK, State.START_BANK );
map.put( InputType.SIGN, State.NUMBER_SIGN );
map.put( InputType.NUMBER, State.INTEGER );
map.put( InputType.DOT, State.DOT_WITHOUT_INTEGER );
transferRule.put( State.START_BANK, map );

map = new HashMap<>();
map.put( InputType.NUMBER, State.INTEGER );
map.put( InputType.DOT, State.DOT_WITHOUT_INTEGER );
transferRule.put( State.NUMBER_SIGN, map );

map = new HashMap<>();
map.put( InputType.NUMBER, State.INTEGER );
map.put( InputType.DOT, State.DOT_WITH_INTEGER );
map.put( InputType.POWER, State.POWER_LOGO );
map.put( InputType.BLANK, State.END_BLANK );
transferRule.put( State.INTEGER, map );

map = new HashMap<>();
map.put( InputType.BLANK, State.END_BLANK );
map.put( InputType.POWER, State.POWER_LOGO );
map.put( InputType.NUMBER, State.FLOAT );
transferRule.put( State.DOT_WITH_INTEGER, map );

map = new HashMap<>();
map.put( InputType.NUMBER, State.FLOAT );
transferRule.put( State.DOT_WITHOUT_INTEGER, map );

map = new HashMap<>();
map.put( InputType.NUMBER, State.FLOAT );
map.put( InputType.POWER, State.POWER_LOGO );
map.put( InputType.BLANK, State.END_BLANK );
transferRule.put( State.FLOAT, map );

map = new HashMap<>();
map.put( InputType.SIGN, State.POWER_SIGN );
map.put( InputType.NUMBER, State.POWER_NUMBER );
transferRule.put( State.POWER_LOGO, map );

map = new HashMap<>();
map.put( InputType.NUMBER, State.POWER_NUMBER );
transferRule.put( State.POWER_SIGN, map );

map = new HashMap<>();
map.put( InputType.BLANK, State.END_BLANK );
map.put( InputType.NUMBER, State.POWER_NUMBER );
transferRule.put( State.POWER_NUMBER, map );

map = new HashMap<>();
map.put( InputType.BLANK, State.END_BLANK );
transferRule.put( State.END_BLANK, map );
}

/**
* 判断字符串是否表示数值
* @param s
* @return
*/
public boolean isNumber(String s) {
if( s==null || s.length()==0) {
return false;
}

char[] chars = s.toCharArray();
// DFA的起始状态为 <起始空格>
State state = State.START_BANK;
for (char ch : chars) {
// 根据字符计算输入类型
InputType inputType = InputType.calcInputType(ch);
// 根据当前状态获取下一步的状态转移规则
Map<InputType, State> map = transferRule.get(state);
// 根据当前状态的转移规则、输入类型计算出下一个状态
State nextState = map.get(inputType);
if( nextState==null ) {
// 下一个状态为空, 说明相应的输入类型不合法
return false;
}
// 更新当前状态
state = nextState;
}

// 如果最终的状态为可接受的, 则返回true; 反之为false
return state.isAccept();
}
}

/**
* 状态
*/
enum State {
START_BANK("起始空格", false),
NUMBER_SIGN("数字的符号位", false),
INTEGER("整数部分", true),
DOT_WITH_INTEGER("左侧有整数的小数点", true),
DOT_WITHOUT_INTEGER("左侧无整数的小数点", false),
FLOAT("小数部分", true),
POWER_LOGO("指数符号", false),
POWER_SIGN("指数的符号位", false),
POWER_NUMBER("指数部分的整数", true),
END_BLANK( "结束空格", true),
;

/**
* 状态名称
*/
private String name;

/**
* 是否为接受状态
* true: 接受状态
* false: 非接受状态
*/
private boolean accept;

State(String name, boolean accept) {
this.name = name;
this.accept = accept;
}

public boolean isAccept() {
return accept;
}
}

/**
* 输入类型
*/
enum InputType {
OTHER("非法输入"),
BLANK("空格"),
NUMBER("数字"),
SIGN("符号位"),
DOT("小数点"),
POWER("指数符号"),
;

private String name;

InputType(String name) {
this.name = name;
}

/**
* 根据字符计算输入类型
* @param ch
* @return
*/
public static InputType calcInputType(char ch) {
if ( ch==' ' ) {
return BLANK;
} else if( ch>='0' && ch<='9' ) {
return NUMBER;
} else if ( ch=='+' || ch=='-' ) {
return SIGN;
} else if ( ch=='.' ) {
return DOT;
} else if ( ch=='e' || ch=='E' ) {
return POWER;
}
return OTHER;
}
}
0%