本文共 724 字，大约阅读时间需要 2 分钟。

首先应该明确一下问题

我们的问题等价于“偶数个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
   
    int main(){
       using namespace std;    int mov(int,int);    string s="";    cout<<"请输入一个二进制序列"<
    
     >s;    int i=0;    int b=-1;    int im=0;    int om=-1;    for(i=0;i
    
   

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