知识点：程序设计语言-编译程序基本原理

第3点词法分析。书上位于222章节，大概在page75。

每年必考。常考：两个自动机互相等价转换、可以识别哪些组合的二进制串。一般题目必给一个状态转换图，就像题目中的。偶尔也会考正规式。

---

书上面说的比较复杂，后面再说书上的例题，解题其实有更容易的解法。

---

先认识题目中的图：

图里面的圆圈里面的S表示状态；线上面的0和1还有空字的ε都是条件，我们要识别的就是这个条件。

两层圆圈表示最终态，最后的状态一定会到这里。如果这个两层圆圈的圈圈在第一个位置，那么就可以识别空串。

解题：

解题有三个简单的判断：1、哪一个条件是可以重复的。2、以哪一个条件开始或以哪一个条件结尾。3、能否识别空串。

但是本题可以更简单，那就是在每个选项中直接抽几个组成的条件，然后带入题目中的，试一下能不能通过。

题图中可以识别000，A选项不行。题图可以识别010(ε是书上写的是空字)，B选项不行，D也不行。只有C可以识别000还有010。

解题方法参考了2015年上半年的有关题目的解析。