dfa.cpp

DFA的一个例子

#include<iostream>
using namespace std;

char DFA[3][3]={
	{'b','a','c'},
    {'c','a','b'},
	{'b','a','b'}
};

int testDFA(char , int );
void main()
{
	cout<<"the regExpression is (a|b)*ab"<<endl;
	cout<<"请输入要分析的字符个数："<<endl;
	int num=0;
	cin>>num;
	char *a;
    a = new char[num]; 

	cout<<"请输入要分析的串："<<endl;    
	for(int i=0;i<num;i++)
	{
	    cin>>a[i];
	}

	int c= 0 ,n= 1;//0状态为起始状态，n为中间状态
	cout<<"所输入的串为："<<endl;
	for(int q=0;q< num; q++)
	cout<<a[q];	
	cout<<endl;
    for(int j=0;j<num; j++)
	{
       n=testDFA(a[j],c);
	   cout<<"State is from "<<c<<" to "<<n<<endl;//由于给定的DFA的情况，所以分析会是0->1...
	   c =n;//从当前状态继续向下判断，即(0,0)->(0,1)->(0,2)
	   if(c==4)
	   {		   
		   cout<<"the string does not meet the needs."<<endl;
		   break;
	   }	   
	   
	}

	if(c==2)
	{
		cout<<"the string meet the needs.";
	}
    	else
		{
		  cout<<"the string does not meet the needs."<<endl;
		}

}

int testDFA(char x, int cur)//匹配函数
{
	for(int state=0; state< 4; state++)
	{
		if(DFA[cur][state]==x)
		{
			return state;
		}	
	}
	return 4;//4状态为空的状态，即没有这个状态
}