编译原理：偶数个0偶数个1 的正规式为什么是(00|11 | ( (01|10) (00|11) * (01| 10)))*

首先应该明确一下问题

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

可以想一下，在二进制串中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;
        else
            om=1;
        break;
    case 1:
        if(b==0)
            om=3;
        else
            om=0;
        break;
    case 2:
        if(b==0)
            om=0;
        else
            om=3;
        break;
    case 3:
        if(b==0)
            om=1;
        else
            om=2;
        break;
    default:
        ;
    }
    return om;
}

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