欢迎关注公众号:DeepL Newer

MENU

正规式到最小化DFA

October 13, 2018 • Read: 2574 • 编译原理阅读设置

整体的步骤是三步:

  1. 先把正规式转换为NFA(非确定有穷自动机)
  2. 再将NFA通过"子集构造法"转化为DFA
  3. 最后将DFA通过"分割法"进行最小化

1. 正规式转换为NFA

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

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

2. 子集构造法

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

3. DFA最小化

Hopcroft算法

Last Modified: April 5, 2020
Archives Tip
QR Code for this page
Tipping QR Code