各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

正规式到最小化DFA

October 13, 2018 • Read: 648 • 编译原理

整体的步骤是三步:
一、先把正规式转换为NFA(非确定有穷自动机)
二、在把NFA通过“子集构造法”转化为DFA
三、在把DFA通过“分割法”进行最小化

一、正规式转换为NFA

第一步很简单,就是反复运用下图的规则:

给出一个例题,来自Google book。本文主要根据这个例题来讲

二、子集构造法

NFA转换为DFA——子集构造法

三、DFA最小化

Hopcroft算法

Archives Tip
QR Code for this page
Tipping QR Code