给定正规文法为G[S]：
S→aB｜bA
A→aC｜bA
B→bE｜dD｜cB
C→cB｜bF｜dD
D→aC
E→bE｜ε
F→bE｜ε
（1）构造与G[S]等价的NFA。
（2）将所得NFA确定化为DFA。
（3）将DFA最小化。
（4）将最小化后的DFA转换为等价的正规式
S→aB｜bA
A→aC｜bA
B→bE｜dD｜cB
C→cB｜bF｜dD
D→aC
E→bE｜ε
F→bE｜ε
（1）构造与G[S]等价的NFA。
（2）将所得NFA确定化为DFA。
（3）将DFA最小化。
（4）将最小化后的DFA转换为等价的正规式
（1）首先为G中每个非终结符生成NFA的一个状态，开始符为初态，增加一新状态Z，做为NFA的终态。然后检查所有规则，对形如A→aB或A→B的产生式，构造M的转换函数f(A,a)=B或f(A,ε)=B；对形如A→a的产生式，构造M的转换函数f(A,a)=Z。故与G[S]等价的NFA如下图3-25所示。
（2）用造表法将NFA确定化为DFA的步骤如下表3-11所示 ：新状态
IaIb
IcId
1{S}
{B}{A}
ΦΦ
2{B}
Φ{E，Z}
{B}{D}
3{A}
{C}{B}
ΦΦ
4{E，Z}
Φ{E，Z}
ΦΦ
5{D}
{C}Φ
ΦΦ
6{C}
Φ{F，Z }
{B}{D}
7{F，Z }
Φ{E，Z}
ΦΦ
所得DFA如下图3-26所示。（3）用子集分割法将所得的DFA最小化过程：
①根据是否为终态，划分DFA的状态集为：P0={{1，2，3，5，6}，{4，7}}。②根据各子集输出弧a、b、c、d所达到状态是否等价，最终划分为：P1={{1，3}，{5}，{2，6}，{4，7}}。
③将P1的子集分别对应状态S、A、B、Z，得最小化后DFA如图3-27所示。（4）将最小化后的DFA转换为等价的正规式的过程如下。
①将DFA的状态分为三部分：{S}，{A，B}，{Z}。分别求出这三部分对应的正规式为：R1=b*a，R2=(c｜da)*b，R3=b*。②将R1、R2和R3连接后得NFA对应的正规式为R=b*a(c｜da)*bb*。
（2）用造表法将NFA确定化为DFA的步骤如下表3-11所示 ：新状态
IaIb
IcId
1{S}
{B}{A}
ΦΦ
2{B}
Φ{E，Z}
{B}{D}
3{A}
{C}{B}
ΦΦ
4{E，Z}
Φ{E，Z}
ΦΦ
5{D}
{C}Φ
ΦΦ
6{C}
Φ{F，Z }
{B}{D}
7{F，Z }
Φ{E，Z}
ΦΦ
所得DFA如下图3-26所示。（3）用子集分割法将所得的DFA最小化过程：
①根据是否为终态，划分DFA的状态集为：P0={{1，2，3，5，6}，{4，7}}。②根据各子集输出弧a、b、c、d所达到状态是否等价，最终划分为：P1={{1，3}，{5}，{2，6}，{4，7}}。
③将P1的子集分别对应状态S、A、B、Z，得最小化后DFA如图3-27所示。（4）将最小化后的DFA转换为等价的正规式的过程如下。
①将DFA的状态分为三部分：{S}，{A，B}，{Z}。分别求出这三部分对应的正规式为：R1=b*a，R2=(c｜da)*b，R3=b*。②将R1、R2和R3连接后得NFA对应的正规式为R=b*a(c｜da)*bb*。
举一反三
- NFA确定化为DFA，则所得DFA与原NFA识别的语言完全一致
- NFA确定化为DFA，所得的DFA是唯一的
- NFA和DFA都可以用一个五元组M=(Q,Σ,f, S, Z)表示,Q表示的是______ ;DFA与NFA的区别之一在于DFA中的S是______ 。
- 写一个文法G,使其语言为不以0开头的偶数集。 A: G[S]:S→AB|BA→AD|CB→2|4|6|8｜0C→1|3|5||7|9|B B: G[S]:S→AB|BA→AD|CB→1|2|3|4|5|6|7|8|9C→2|4|6|8｜0 C: G[S]:S→AB|BA→AD|CB→2|4|6|8｜0C→1|2|3|4|5|6|7|8|9D→0|C D: G[S]:S→AB|BA→AD|DB→2|4|6|8｜0D→1|2|3|4|5|6|7|8|9|0
- 将识别各类单词的有限自动机合并后得到的有限自动机（ ）。 A: 一定是DFA B: 一定是NFA C: 是最小的DFA D: 可能是NFA也可能是DFA
内容
- 0
与某一NFA等价的DFA是唯一的
- 1
对任一NFA,都存在DFA和它等价。
- 2
下列哪种方式能更直观的描述高级语言中的单词 A: 正规文法 B: NFA C: 正规式 D: DFA
- 3
任何一个NFA总存在一个DFA与之等价()
- 4
任何一个NFA都可以找到一个DFA与之等价。