有穷自动机

自动机介绍（粗略参考）

有穷自动机(finite state automata)是一个识别器，它对每个输入的字符做识别和判断，以确定其能到达的最终状态或状态集和路径，有穷自动机分为两类，即不确定的有穷自动机NFA和确定的有穷自动机DFA.

DFA: Deterministic Finite State 确定的有穷自动机

1. 第一种计算模型：用来解决对一个已知字符串，看它是否能被某个自动机所接受。

2. 一个DFA有有穷个状态（state），主要分为三种状态：

• 初始状态（initial state）：自动机开始的状态；

• 终止状态（final state）：一个DFA至少有一个终止状态；

• 中间状态。

「状态间转换的公式： 状态 x 输入字符 –> 状态」

DFA的定义：

A = ( Σ, S, s0, F, N )

• Σ: 输入字母表（alphabet），是一个输入字符的集合。

• S：状态的集合

• s0： 初始状态

• F：终止状态集合 F ⊆ S

• N：转换公式 N:S×Σ → S

「“确定”意味着对于一个输入字符，只有唯一的可能状态」

如

我们可以得到：

N (S0, 0)： 是自动机从s0状态，读取符号0之后的状态。

N (N (S0, 0), 1) = S2.

对S中所有的状态s，所有 Σ*中的字符串 α,β， 有：

N*(s, αβ) = N*(N*(s, α), β)。

NFA(Non-Deterministic Finite State Automata)不确定的有穷自动机:

对一个输入符号，有两种或两种以上可能对状态，所以是不确定的。

解题的简单应用

例子1：红绿灯系统： G（绿灯亮了的状态）；R（红灯亮的状态）；Y（黄灯亮的状态）

例子2：零售机（vending machine）。它接受五角和一块的硬币，但是要至少积累到3元才能按下选择，并且只有作出选择才会执行。所以从初始state开始，每一个状态之后都有两种选择：要么投5角，要么投1元；每次投完都会到达一个新的状态（目前投入硬币总数）。

例子3

输入一个字符串，输入的只有两种字符，一种是字母，一种是空格。现在求一共有几个单词。注意，有可能有多个空格连在一起，开头和结尾都有可能有空格。

那么这是一道简单的有穷自动机，运行时分两种情况：

①是空格

②是字母

（当前状态就是上一个字符的状态）

在遍历数组的时候拿一个变量记录下来当前是什么状态，可以用0代表当前是空格状态，1代表是字母状态

当如果当前状态是1，而现在却遇到空格，那么就计数器加一，同时要将状态改为0，如果当前状态是0，现在的字符却是字母，就只将状态改为 1

值得注意的是 若在跳出循环的时候状态是1 那么需要将计数器加一

代码：

 #include <cstdio> ​
int main () {
 ​     char a[1001];
      int state, ans = 0;
      gets(a);      
 
    if(a[0] == ' ') 
        state = 0;//设置初始值  
    else state = 1;  
    for(int i = 1; a[i]; i ++ ) {
//要从一开始遍历，因为零已经遍历过了  
if(a[i] == ' ') {
//是空格  
   if(state == 1) {
   //当前状态（前一个）是字母，说明找到一个单词了
     ans ++ ;//答案加一  
     state = 0;//千万别忘了改状态  
   }  
} 
 else {//是字母 
  if(state == 0) {
   //当前状态（前一个）是空格  
     state = 1;//将状态改为1 
   }  
  }  
}  
if(state == 1)
//最后还要判断一下千万不要忘记 
ans ++ ;  
printf("%d", ans);     
return 0;

例4：

noip 2011普及 T 2

其实一样，就是注意字母状态分时要查找单词状态和不是要查找单词状态，而且单词第n个字母的状态就用n来表示

#include <cstdio>
#include <cctype>
#include <cstring>
 ​ const int SPACE = 0;//三种状态，这是空格状态 
const int LETTER = -1;//字母状态，但这表示不是要查找的单词的字母的状态 
const int WORD = 1;//而这种状态是要查找的单词的状态 
//当然了，如果状态时大于1的数，说明是要查找的单词的中间部分的状态，上文讲过了 
​ inline void strlower (char *a) {
//不解释，上面的代码有了     
for(int i = 0; a[i]; i ++ ) {    
     if(isupper(a[i])) a[i] = tolower(a[i]);   
 } 
} ​ 

int main () {
    char a[1000001], word[20]; 
    int ans = 0;     
    int ans2 = -1;     
    int state = 0;
//表状态，假设是空格，
//因为空格上来就判断是不是三种状态  
   int i; ​     
   gets(word);     
   gets(a);     
   strlower(a);     
   strlower(word);     
   int len = strlen( word );
              
for(i = 0; a[i]; i ++ ) {
//遍历数组         
    switch ( state ) 
      {             
         case SPACE : 
     //如果当前状态（上一个）是空格  
if(a[i] == word[0]) state = WORD;
     //变成单词第一个字母状态             
else if(a[i] == ' ') state = SPACE;
    //其实这句话可以省略
   //因为反正都是空格状态，改它是一样的
     else state = LETTER;
     //剩下的肯定是其他字母状态了          
     break;             
case LETTER : //是其他字母状态 
       if(a[i] == ' ') state = SPACE;
//空格状态                 
break;            
 default: //是要查找的单词状态 
                
if ( state < len ) {
//还不是最后一个字母  
                  
 if(a[i] == ' ') state = SPACE; 
                    
else if(a[i] == word[state])
state ++ ;//变成下一个字母状态   
                 
 else state = LETTER;//其他字母状态
                
}                
 else if (state == len )
//是最后一个字母               
 {                     
 if(a[i] == ' ') {
//如果下一个是空格，找到了！  
                       
state = SPACE;//状态不要忘记改变 
                           
 if(ans2 == -1)
//第一次找到，记录下来位置          
                       
ans2 = i - len;
//因为i是单词的尾，所以要减长度      
                  
ans ++ ;//个数加一             
       }                   
  else state = LETTER;
//可惜，最后跟着其他字母，不是单词     
           }     
   } ​   
 }    
  if(state == len) {        
  ans ++ ;         
  if(ans2 == -1) 
            
  ans2 = i - 1 - len;    }   
  if(ans2 == -1) printf("-1");  
  else printf("%d %d", ans, ans2);
          
return 0;
 }