编译原理：偶数个0偶数个1 的正规式为什么是(00

编译原理：偶数个0偶数个1 的正规式为什么是(00

首先应该明确一下问题

我们的问题等价于“偶数个0偶数个1的正规式是什么”，而不是“(00|11 | ( (01|10) (00|11) * (01| 10))) *就能表示偶数个0偶数个1 的正规式”。

可以想一下，在二进制串中0和1的个数的状态无非以下四种:

1. 偶数个0，偶数个1 -------------0
2. 偶数个0，奇数个1 -------------①
3. 奇数个0，偶数个1 -------------②
4. 奇数个0，奇数个1 -------------③

注：虚线后面的数值是相应的状态，我们将在接下来的状态转换图中看到

• 接下来我们画一下状态转换图：

注：圆内的是状态值，箭头旁边的是二进制值
箭头的方向和箭头旁的数值需要结合状态值的意义理解

• 接下来，我们把1状态拿掉，整理之后是这样的：
  

• 接下来，把2状态拿掉，整理之后是这样的：
  

• 接下来，把状态3拿掉，整理之后是这样的：
  

• 进而可以表示为：(00|11 | (01|10) (00|11) * (01| 10))*
  注：该式与题目中的少一个括号，其实是一样的，因为连接运算的优先级大于选择运算 |

• 现在我们尝试用代码实现图一：

#include<iostream>
int main()
{using namespace std;int mov(int,int);string s="";cout<<"请输入一个二进制序列"<<endl;cin>>s;int i=0;int b=-1;int im=0;int om=-1;for(i=0;i<s.size();++i){b=s[i]-'0';//将字符转换为数字om=mov(im,b);im=om;}switch(om){case 0:cout<<"成功，您输入了偶数个0偶数个1！！"<<endl;break;case 1:cout<<"您输入了偶数个0奇数个1，下次可以多输入一个1"<<endl;break;case 2:cout<<"您输入了奇数个0偶数个1，下次可以多输入一个0"<<endl;break;case 3:cout<<"您输入了奇数个0奇数个1，下次可以01各多输入一个"<<endl;break;default:;}return 0;
}
int mov(int im, int b)//b是0或1
{int om=0;//保存move函数的输出，将作为返回值switch(im){case 0:if(b==0)om=2;elseom=1;break;case 1:if(b==0)om=3;elseom=0;break;case 2:if(b==0)om=0;elseom=3;break;case 3:if(b==0)om=1;elseom=2;break;default:;}return om;
}

运行一下，就可以判断输入的二进制串是否包含偶数个0和偶数个1啦