将a*b*正则表达式转换为有限状态机

Question

如何将正则表达式a*b*转换为有限状态机？我才刚开始，不知道该怎么开始。

Answer 1

想想看，a*b*的意思是a 0次或更多次，然后b 0次或更多次。

正在生成状态转换表。。。

Transitions
0 - empty
1 - next a
2 - next b
3 - next not ( a or b )
State / Transitions
S | T | S
S | 0 | Y
S | 1 | a
S | 2 | b
S | 3 | N
a | 0 | Y
a | 1 | a
a | 2 | b
a | 3 | N
b | 0 | Y
b | 1 | N
b | 2 | b
b | 3 | N
States
S - start
Y - end - matches
N - end - doesn't match
a - is matchng a+
b - is matching b+

然后你可以用任何你喜欢的语言来编写代码。一些伪代码。。。

char state = 'S';
string s = gets(); // assume a 0 terminated string
for( int i = 0; ; i++ )
{
state = table[state][getTransition(s[i])];
if(state in ['Y','N']) break;
}
int getTransition(char c) { if c == 0 return 0; if c == 'a' return 1; if c == 'b' return 2; return 3; }