正则表达式表示语法
正则表达式转化为NFA（比较直观）
NFA转化未DFA（更快）
image.png
下面我们根据视频中的例子来实现下整个过程。
下面的图片依次是正则式转NFA的规则、（1+0）*1转化为NFA的实例、NFA转化DFA的例子、表驱动方式实现DFA、最后是对应的代码。
图片发自简书App
图片发自简书App
StateTable = [[1,2],[1,2],[1,2]]
def recognize(str,table,start,end):
i = 0
state = start
while i < len(str):
try:
state = table[state][int(str[i])]
except:
return False
i += 1
if state == end:
return True
else:
return False
def main():
str1 = '11101111111'
ret = recognize(str1,StateTable,0,2)
print('{str1} is {ret}'.format(str1=str1,ret=ret))
str2 = '11111111110'
ret = recognize(str2, StateTable, 0, 2)
print('{str1} is {ret}'.format(str1=str2, ret=ret))
if __name__ == '__main__':
main()
输出结果：
11101111111 is True
11111111110 is False
