自动机的幂集构造法详解

幂集构造,又叫子集构造,是一种将 NFA 转换为 DFA 的算法。下面通过一个例子学习。

【例子】 这是识别 101 结尾的二进制串的 NFA。将其转换为 DFA。

image-20210625220012542

分析:

NFA 的状态转移表:

				0			1
->	{q0}		{q0}		{q0,q1}
	{q1}		{q2}		/
	{q2}		/			{q3}
*	{q3}		/			/

我们逐行看,第一行产生了新的状态 {q0,q1}。考察这个状态的两个子状态 q0, q1

当输入 0 时:

  • {q0} 跳至 {q0}

  • {q1} 跳至 {q2}

所以我们有:

image-20210625221009781

同理,输入 1 时有:

image-20210625221044408

据此在状态转移表添加一行 {q0,q1},得到:

				0			1
->	{q0}		{q0}		{q0,q1}
	{q1}		{q2}		/
	{q2}		/			{q3}
*	{q3}		/			/
	{q0,q1}		{q0,q2}		{q0,q1}

重复这样的操作(称为子集构造),得到:

				0			1
->	{q0}		{q0}		{q0,q1}
	{q1}		{q2}		/
	{q2}		/			{q3}
*	{q3}		/			/
	{q0,q1}		{q0,q2}		{q0,q1}
	{q0,q2}		{q0}		{q0,q1,q3}
*	{q0,q1,q3}	{q0,q2}		{q0,q1}

注:最初接受状态是 {q3},则要把所有构造出的含有 q3 的状态标记为接受。

重命名,得到:

			0		1
->	s0		s0		s4
	s1		s2		/
	s2		/		s3
*	s3		/		/
	s4		s5		s4
	s5		s0		s6
*	s6		s5		s4

从而得到如下的状态机:

image-20210625222730516

可以看到有三个冗余状态 s1, s2, s3

所以一般而言(尤其对于复杂的 DFA),我们还要通过 DFA 的最小化技术消去无用的状态。

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志