自动机介绍(粗略参考)
有穷自动机(finite state automata)是一个识别器,它对每个输入的字符做识别和判断,以确定其能到达的最终状态或状态集和路径,有穷自动机分为两类,即不确定的有穷自动机NFA和确定的有穷自动机DFA.
DFA: Deterministic Finite State 确定的有穷自动机
-
第一种计算模型:用来解决对一个已知字符串,看它是否能被某个自动机所接受。
-
一个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 那么需要将计数器加一
代码:
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来表示
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; }