1.cpp

一个根据所构造的确定有穷自动机进行识别句子的程序,识别由0,1所构成的字符串,并且该字符串不能含有两个连续的0.运行效果良好,是个值得参考的程序.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Rule
{
	string rule1;//各个状态的转换规则1
	string rule2;//各个状态的转换规则2
};

struct State
{
	string CurrentState; //各个状态的状态标识符
	Rule rule;      //各个状态的转换规则
	bool IsTeminal; //标识状态是否为最终状态
};

void Init(vector<State> & a)
{   //初始化DFA对应的状态转换图
	Rule r;
    //初始化状态q0
	a[0].CurrentState="q0";
	r.rule1="0q1";
	r.rule2="1q2";
	a[0].rule=r;
    a[0].IsTeminal=false;
    //初始化状态q1
	a[1].CurrentState="q1";
	r.rule1="0qt";
	r.rule2="1q2";
	a[1].rule=r;
    a[1].IsTeminal=true;
    //初始化状态q2
	a[2].CurrentState="q2";
	r.rule1="0q1";
	r.rule2="1q2";
	a[2].rule=r;
    a[2].IsTeminal=true;
    //初始化状态qt
	a[3].CurrentState="qt";
	r.rule1="0qt";
	r.rule2="1qt";
	a[3].rule=r;
    a[3].IsTeminal=false;
}

bool TestString(string InputString)
{   //检测字符串是否是0，1字符串
	for(int i=0;i<InputString.size();i++)
	{   //一个循环，完成对字符串的检测
		if(InputString[i]!='0' && InputString[i]!='1')
			return false;
	}
	return true;
}

void AnalyseString(string InputString,vector<State> SArray)
{
	//循环变量
	int i,j;
	//存储判断的结果
    bool ResultIsTerminal;
	//用来存储下一个状态标识符
	string NextState;
	//当前的输入字符
	char CurrentCharacter;
	//状态节点
    State s;
	//各个状态的转换规则
	Rule rule;
	if(InputString.size()==0)
	{
		cout<<"输入字符串为空串，该确定的有穷自动机无法识别";
		return;
	}
    //第一个状态一定是q0
    NextState="q0";
    for(i=0;i<InputString.size();i++)
	{   //当前输入字符
		CurrentCharacter=InputString[i];
		for(j=0;j<SArray.size();j++)
		{   
			s=SArray[j];
			if(s.CurrentState==NextState)
			{   //搜索到当前状态
				rule=s.rule;
				//当前状态的两个规则
				string rulestring1=rule.rule1;
				string rulestring2=rule.rule2;
				//若满足转换规则，则转换到下一个状态，用NextState存储下一个状态标识符
				if(rulestring1[0]==CurrentCharacter)
				{   
					NextState=rulestring1.substr(1,2);
				}
				else
				{
					NextState=rulestring2.substr(1,2);
				}
				break;
			}
		}
	}

	for(i=0;i<SArray.size();i++)
	{   //遍历每一个状态
		State ss=SArray[i];
		if(ss.CurrentState==NextState)
		{   //判断根据DFA最终所进入的状态是否是所希望的最终状态
			ResultIsTerminal= ss.IsTeminal;
			break;
		}
	}

	if(ResultIsTerminal==true)
	{   //若最终状态是合理的
		cout<<"该字符串能被确定的有穷自动机识别"<<endl;
	}
	else
	{
        cout<<"该字符串不能被确定的有穷自动机识别"<<endl;
	}
}

void main()
{
	//定义一个向量，用来存储DFA,即存储状态转换图中各个状态的状态标识符，
	//转换规则，和状态是否为最终状态
	vector<State> SArray(4);
	//用来存储输入的字符串
    string InputString;
    //直接用来判断DFA是否能够识别
	bool IsInputRight;
	//初始化DFA对应的状态转换图
    Init(SArray);

	cout<<"**********欢迎进入形式语言与自动机实验系统***********"<<endl;
	cout<<endl;
	cout<<"此系统主要用来检测字符串中是否不含两个连续的0"<<endl;
	cout<<endl;
	cout<<"***注意事项：本系统只允许输入在字母表{0,1}的字符串***"<<endl;

	while(true)
	{
	cout<<"请输入一个字符串："<<endl;
	//一个循环，直到能够接收输入一个0，1字符串为止
	do
	{   //输入一个字符串
	    cin>>InputString;
        //判断此字符串是否是0，1字符串
	    IsInputRight=TestString(InputString);
       
	    if(!IsInputRight)
		{    //提示用户输入有误
		     cout<<"输入的字符串中含有0和1以外的字符串，显然该确定的有穷自动机无法识别."<<endl;
             cout<<"请输入其他串："<<endl;
		}
	}while(!IsInputRight);
    
	cout<<endl;
	//利用DFA对0，1字符串进行分析处理
	AnalyseString(InputString,SArray);

	char c;
	cout<<endl<<"是否还要继续输入字符串(y/n):"<<endl;
	cin>>c;
	if(c=='n') break;
	}
}