有限自动机：
利用有限自动机解决识别单词的问题：
状态转移图如下：
A: 如果在2状态接收到非字母，并且检测出在2状态收入的字母串是关键词的话，转移到状态3
B: 如果不是关键词，转移状态到4
C: 如果在2状态接收到非字母，并且检测出2状态收入的字母串超过了规定长度，转移到初始状态
准备一个字符串为 待检测字符串SampleString，用来接受扫描提出关键词或者标识词；准备一个字符串为 字母串字符串String，用来存放扫描时不断获得的字母串；设置一个SamFlag，初始值为0，当作SampleString的下标；设置一个StateSign，用作状态标识。
步骤如下：
(1)向SampleString中输入待接受检测字符串
(2)设置状态为初始状态，状态标识StateSign为0
(3)从SampleString[SamFlag]中取出一个字符。
(4)按照状态标识进入状态
(5)初始状态(状态 0)：判断SampleString[SamFlag]字符为字母字符还是非字母字符：
①如果是字母字符，收入到String字符串中，SamFlag+1，状态标识改变为2，跳到(10)
②如果是非字母字符，什么都不操作，SamFlag+1，状态标识改变为1，跳到(10)
(6)状态 1：判断SampleString[SamFlag]字符为字母字符还是非字母字符：
①如果是字母字符，收入到String字符串中，SamFlag+1，状态标识改变为2，跳到(10)
②如果是非字母字符，什么都不操作，SamFlag+1，状态标识改变为1，跳到(10)
(7)状态 2：判断SampleString[SamFlag]字符为字母字符还是非字母字符：
①如果是字母字符，收入到String字符串中，SamFlag+1，状态标识改变为2(不改变状态标识)，跳到(10)
②如果是非字母字符，判断String中的字母串是否大于规定的长度：
1）如果没有超过长度，判断是否是关键词：
Ⅰ如果是关键词，状态标识改变为3，跳到(10)
Ⅱ 如果不是关键词，状态标识改变为4，跳到(10)
2）如果超过长度，清空String表，SamFlag+1，状态标识改变为0，跳到(10)
(8)状态 3：输出关键词，清空String，SamFlag+1，改变状态标识为0，跳到(10)
(9)状态 4：输出标识词，清空String，SamFlag+1，改变状态标识为0，跳到(10)
(10)判断SamFlag是否已经超过SampleString的总长度(即判断SampleString字符串是否已经被扫描完)：
①如果扫描完，退出程序
②如果没有扫描完，回到(4)
下附程序：
#include
#include
#include
#define KEY_WORD_MAX 32 //关键词总数 32
#define SIGN_WORD_MAX 31 //标识符长度 31
using namespace std;
const string KEY_WORD[]=
{
"auto",
"break",
"case",
"char",
"const",
"continue",
"default",
"do",
"double",
"else",
"enum",
"extern",
"float",
"for",
"goto",
"if",
"int",
"long",
"register",
"return",
"short",
"signed",
"sizeof",
"static",
"struct",
"switch",
"typedef",
"union",
"unsigned",
"void",
"volatile",
"while"
};
int StateChange(int,char,char*);
int CompareChar(char*);
void ClearWord(char*);
int Flag_Word=0,Flag_JUD=0;
int main()
{
string SAM_WORD; //JUD 存入的待检查字符串
char Word[999999]; //Word 临时存入字符串，存入表
int JudWordSize=0,StateSign=0;
//StateSign 状态标识，FlagWord Word数组目前下标，FlagJUD JUD数组目前下标，JudWordSize JUD总长度
getline(cin,SAM_WORD);
JudWordSize=SAM_WORD.size();
while(Flag_JUD<=JudWordSize)
{
StateSign=StateChange(StateSign,SAM_WORD[Flag_JUD],Word);
}
return 0;
}
int StateChange(int StateSign,char NowWord,char Word[])
{
switch(StateSign)
{
case 0: //初始状态
{
//初始状态获得字母，转移状态到 2
if('a'<=NowWord&&NowWord<='z')
{
Word[Flag_Word]=NowWord;
Flag_Word++;
Flag_JUD++;
return 2;
}
//初始状态获得非字母，转移状态到 1
else
{
Flag_JUD++;
return 1;
}
break;
}
case 1: //状态 1
{
//1 状态获得字母，转移状态到 2
if('a'<=NowWord&&NowWord<='z')
{
Word[Flag_Word]=NowWord;
Flag_JUD++;
Flag_Word++;
return 2;
}
//1 状态获得非字母，状态不转移
else
{
Flag_JUD++;
return 1;
}
break;
}
case 2: //状态 2
{
//2 状态获得字母，收入到收入表，保持状态
if('a'<=NowWord&&NowWord<='z')
{
Word[Flag_Word]=NowWord;
Flag_Word++;
Flag_JUD++;
return 2;
}
//2 状态获得非字母，判断长度，判断是否是关键词
else
{
if(Flag_Word<=SIGN_WORD_MAX)
{
if(CompareChar(Word))
{
return 3;
}
else
{
return 4;
}
}
//长度超过规定长度，清空收入表
else
{
ClearWord(Word);
Flag_Word=0;
Flag_JUD++;
return 0;
}
}
break;
}
//3 状态 输出关键词，转移状态到初始状态，清空收入表
case 3:
{
cout<<"关键词："<<Word<<endl;
ClearWord(Word);
Flag_Word=0;
Flag_JUD++;
return 0;
break;
}
//4 状态 输出标识符，转移状态到初始状态
case 4:
{
cout<<"标识符："<<Word<<endl;
ClearWord(Word);
Flag_Word=0;
Flag_JUD++;
return 0;
break;
}
}
}
int CompareChar(char Word[])
{
int i,a;
for(i=0;i
{
//compare函数，如果两个字符串相等返回 0，否则返回 -1，string类的函数
a=KEY_WORD[i].compare(Word);
if(a==0) return 1;
}
return 0;
}
void ClearWord(char Word[])
{
for(int i=0;i
}
