有限自动机
- 一般我们会用状态图来描述一个有限自动机。它有且只有一个起始状态（在状态图中，一个从不知道什么地方来的箭头指向的状态），有一些终止状态（状态图中的双圈节点）。
- 有限自动机的输出是接受或者拒绝。
例题
（2009年上半年软件设计师第48题）下图所示有限自动机的特点是（）。
A.识别的0、1串是以0开头且以1结尾 B.识别的0、1串中1的数目为偶数
C.识别的0、1串中0后面必须是1 ==D.识别的0、1串中1不能连续出现==
解析：采取排除法，枚举各种可到终态的方法，从而排除不符合的选项。
1，排除A、B。
001，排除C。
（2010年下半年软件设计师第22题）下图所示的有限自动机中，0是初始状态，3是终止状态，该自动机可以识别（）。
A.abab ==B.aaaa== C.bbbb D.abba
解析：将选项代入有限自动机中，看选项能否到达终态。
（2011年上半年软件设计师第49题）下图所示为一个有限自动机(其中，A是初态、C是终态)，该自动机可识别（）。
A.0000 B.1111 ==C.0101== D.1010
解析：将选项代入有限自动机中，看选项能否到达终态。
（2011年下半年软件设计师第48题）下图所示为一个有限自动机（其中，A是初态、C是终态)，该自动机识别的语言可用正规式（）表示。
==A.(0|1)*01== B.1*0*10*1 C.1*(0)*01 D.1*(0|10)*1*
解析：将*当作0次处理。
（2012年上半年软件设计师第48题）下图所示为一个有限自动机（其中，A是初态、C是终态），该自动机所识别的字符串的特点是（）。
A.必须以11结尾的0、1串 B.必须以00结尾的0、1串
==C.必须以01结尾的0、1串== D.必须以10结尾的0、1串
解析：采取排除法，枚举各种可到终态的方法，从而排除不符合的选项。
101，排除A、B、D
（2014年下半年软件设计师第49题）以下关于下图所示有限自动机的叙述中，不正确的是（）。
==A.该自动机识别的字符串中a不能连续出现==
B.该自动机识别的字符串中b不能连续出现
C.该自动机识别的非空字符串必须以a结尾
D.该自动机识别的字符串可以为空串
解析：采取排除法，枚举各种可到终态的方法，从而选择符合的选项。
aa，选择A
（2015年上半年软件设计师第49题）某非确定的有限自动机（NFA）的状态转换图如下图所示（q0既是初态也是终态），与该NFA等价的确定的有限自动机（DFA）是（）。
==A.== 
B. 
C. 
D. 
解析：采取排除法，枚举各种可到终态的方法，从而排除不符合的选项。
a，排除B、C
ba，排除D
（2015年下半年软件设计师第49题）某非确定的有限自动机（NFA）的状态转换图如下图所示（q0既是初态也是终态）。以下关于该NFA的叙述中，正确的是（）。
A.其可识别的0、1序列的长度为偶数
B.其可识别的0、1序列中0与1的个数相同
C.其可识别的非空0、1序列中开头和结尾字符都是0
==D.其可识别的非空0、1序列中结尾字符是1==
解析：采取排除法，枚举各种可到终态的方法，从而排除不符合的选项。
1，排除A、B、C
（2017年下半年软件设计师第49题）某确定的有限自动机（DFA）的状态转换图如下图所示（0是初态，4是终态），则该DFA能识别（）。
==A.aaab== B.abab C.bbba D.abba
解析：将选项代入有限自动机中，看选项能否到达终态。
（2018年上半年软件设计师第48题）下图所示为一个不确定有限自动机（NFA）的状态装换图。该NFA识别的字符串集合可用正规式（）描述。
==A.ab*a== B.(ab)*a C.a*ba D.a(ba)*
解析：将*当作0次处理。
（2018年下半年软件设计师第49题）下图所示为一个不确定有限自动机（NFA）的状态转换图。该NFA可识别字符串（）。
==A.0110== B.0101 C.1100 D.1010
解析：将选项代入有限自动机中，看选项能否到达终态。
（2019年上半年软件设计师第49题） 下图所示为一个不确定有限自动机（NFA）的状态转换图，与该NFA等价的DFA 是（）。
A.
B.
==C.==
D.
解析：采取排除法，枚举各种可到终态的方法，从而排除不符合的选项。
000，排除A
010，排除B、D
（2020年下半年软件设计师第50题）某有限自动机的状态转换图如下图所示，该自动机可识别 （ ）。
A.1001 ==B.1100== C.1010 D.0101
解析：将选项代入有限自动机中，看选项能否到达终态。