NLP实验一：形式语言和自动机

实验目的

掌握有限自动机的基本概念
掌握有限自动机与正则文法的联系，并设计程序实现有限自动机，判断字符串是否被接受

实验内容

请设计程序实现如下有限自动机, 并且输入三个不同的字符串, 对字符串进行合法性检测 (即判断字符串中的字符是否在输入符号集中), 之后由有限自动机判断字符串是否被接受。
状态集： \left{q_0,q_1,q_2,q_3\right} (可用其他字符代替)
输入符号集： {0,1}
初始状态: q_0
终止状态： q_0
状态转移函数：开始

三、实验过程

3.1 变量定义
枚举类型State，定义了q0,q1,q2,q3四个状态，值得一提的是c++中枚举型变量默认与int型变量一一对应（即q0 == 0，q1 ==1等）。
用nowState记录当前状态
enum State{q0,q1,q2,q3};
State nowState;nextState是一个二维数组，用来确定下一个状态。第一维为当前状态，值得注意的是，我将每个状态都映射到了一个非负整数，如q0映射到了0，q1映射到了1。第二维为接受的符号，我同样将字符串符号映射到了非负整数（字符‘0’映射到整数 0，字符‘1’映射到整数1）。
int nextState[4][2]str是输入的字符串，ans用来储存状态序列
string str;
vector<int> ans;3.2 程序思路
首先调用init()，初始化状态转移函数。对nextState的初始化思路如下：
该二维数组第一维为当前状态，第二维为接受的符号（已完成映射）。例如：当前状
态是q3，接受字符‘0’后转移到状态q1，则表示为nextState[3][0]=q1。特别地，如果不存在状态a接收字符‘x’后的转移，那么下一个转态就为-1，表示不存在。
void init(){memset(nextState,-1,sizeof nextState);nextState[1][1]=nextState[2][0]=q0;nextState[0][1]=nextState[3][0]=q1;nextState[0][0]=nextState[3][1]=q2;nextState[2][1]=nextState[1][0]=q3;}之后循环三次，每次读入一个字符串。初始状态为q0，初始化flg=1。flg==1表示能被接收，flg==-1表示字符串中的字符不在输入符号集中，flg==0表示字符串不可以被有限自动机接收。清空ans并初始化第一个状态为q0。
cin>>str;
nowState=q0;
int flg= 1;
ans.clear();
ans.push_back(0);然后遍历每一个字符，如果该字符不在输入符号集中，则flg=-1，跳出循环。如果当前flg==1，则通过nextState[][]查询当前状态在接收该字符后是否能转移到下一个状态。如果不能转移，则flg=0，但不能跳出循环（因为后面的字符可能有不在输入符号集中的情况）；如果可以转移则进行转移。
for(char i : str){if(i!='0'&&i!='1'){flg = -1;break;}if(flg==1){int next=nextState[nowState][i-'0'];if(next==-1){flg=0;}else{ans.push_back(next);nowState = (State)next;}}}print(flg);}最后调用print函数，通过flg的值输出信息。
void print(int nowflg){if(nowflg==-1){cout<<"字符串中的字符不在输入符号集中\n";}else if(nowflg==0||nowState!=q0){cout<<"字符串不可以被有限自动机接受\n";}else{cout<<"字符串可以被有限自动机接受，状态序列为：";for(int x=0;x<ans.size();x++){cout<<"q"<<ans[x];if(x!=ans.size()-1) cout<<"->";}cout<<endl;}}3.3 复杂度分析
程序时间复杂度为\mathbit{O}(\mathbit{n}),其中n为字符串长度。
程序的空间复杂度为\mathbit{O}(\mathbit{n}\times\mathbit{m}),其中n为状态的数量，m为可接受字符的数量。
程序使用nextState[][]数组，能够以\mathbit{O}(\mathbf{1})的时间复杂度完成状态转移，运行效率高。
程序有较好的拓展性，只需修改小部分代码，就能完成对特定有限自动机接受字符串
的判定。

四、结果展示

如图2所示，字符串为110101时，该字符串可以被有限自动机接受，对应的状态序列
q0->q1->q0->q2->q3->q1->q0。
字符串为2313时，2和3都不在输入符号集中，所以输出“字符串中的字符不在输入符号集中”。
字符串为1111110时，最后状态是q2，并不属于终止状态，故输出“字符串不可以被有限自动机接受”。如图3所示，字符串为1101时，最后状态是q3，并不属于终止状态，故输出“字符串不可以被有限自动机接受”。
字符串为11016时，6不在输入符号集中，所以输出“字符串中的字符不在输入符号集中”。
字符串为111111时，最后状态是q2，该字符串可以被有限自动机接受，对应的状态序列
q0->q1->q0->q1->q0->q1->q0。

五、代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
enum State{q0,q1,q2,q3};
int nextState[4][2];
string str;
State nowState;
vector<int> ans;
int t;
void init(){memset(nextState,-1,sizeof nextState);nextState[1][1]=nextState[2][0]=q0;nextState[0][1]=nextState[3][0]=q1;nextState[0][0]=nextState[3][1]=q2;nextState[2][1]=nextState[1][0]=q3;
}void print(int nowflg){if(nowflg==-1){cout<<"字符串中的字符不在输入符号集中\n";}else if(nowflg==0||nowState!=q0){cout<<"字符串不可以被有限自动机接受\n";}else{cout<<"字符串可以被有限自动机接受，状态序列为：";for(int x=0;x<ans.size();x++){cout<<"q"<<ans[x];if(x!=ans.size()-1) cout<<"->";}cout<<endl;}
}int main() {init();t=3;cout<<"请输入字符串"<<endl;while(t--){cin>>str;nowState=q0;int flg= 1;ans.clear();ans.push_back(0);for(char i : str){if(i!='0'&&i!='1'){flg = -1;break;}if(flg==1){int next=nextState[nowState][i-'0'];if(next==-1){flg=0;}else{ans.push_back(next);nowState = (State)next;}}}print(flg);}return 0;
}