编译原理习题CH3-4

3.4.1 给出识别练习 3.3.2 中各个正则表达式所描述的语言状态转换图。

在解决这个问题时，我们需要依次按照以下步骤构造状态转换图：

1. 从NFA开始：首先构造非确定有限自动机（NFA）。这意味着我们需要定义一个NFA，其中可以有多个状态，并且在某些情况下会有多个可能的转换。
2. 转换为DFA：接下来，将NFA转换为确定性有限自动机（DFA）。在DFA中，每个状态都有且只有一个可能的转换。
3. 最少状态的DFA：最后，我们通过合并不可区分的状态，得到最少状态的DFA。不可区分的状态可以合并，从而减少DFA的状态数。

---

1. a(a|b)*a 语言的状态转换图

---

2. ((ε|a)b*)* 语言的状态转换图

---

3. (a|b)*a(a|b)(a|b) 语言的状态转换图

NFA：

DFA：

NFA	DFA	a	b
{0,1,2,4,7}	A	B	C
{1,2,3,4,6,7,8,9,11}	B	D	E
{1,2,4,5,6,7}	C	B	C
{1,2,3,4,6,7,8,9,10,11,13,14,16}	D	F	G
{1,2,4,5,6,7,12,13,14,16}	E	H	I
{1,2,3,4,6,7,8,9,10,11,13,14,15,16,18}	F	F	G
{1,2,4,5,6,7,12,13,14,16,17,18}	G	H	I
{1,2,3,4,6,7,8,9,11,15,18}	H	D	E
{1,2,4,5,6,7,17,18}	I	B	C

---

4. a*ba*ba*ba* 语言的状态转换图

NFA：