《编译原理》 课后练习参考答案 第 03 章 词法分析 共 4 页，第 1 页 课后练习参考答案课后练习参考答案 第第 03 章章 词法分析词法分析 1. 写出正规式写出正规式 a(a|b)*(ε|((.|_)(a|b)(a|b)*))相应的正规文法相应的正规文法 【解】 引入开始符号 S，构造 S→a(a|b)*ε|((.|_)(a|b)(a|b)*), a(a|b)*ε|((.|_)(a|b)(a|b)*) = a(a|b)*|a(a|b)*.(a(a|b)*|b(a|b)*)|a(a|b)*_(a(a|b)*|b(a|b)*) =aA|aC 引入非终结符 A，B， C * A→(a|b)* →ε ε| | (a|b)+ →ε ε| | (a|b) (a|b)* →ε ε| | (a|b) A C→ (a|b)*.(a(a|b)*|b(a|b)*)| (a|b)*_(a(a|b)*|b(a|b)*) →(ε ε| | (a|b) (a|b)*).(a(a|b)*|b(a|b)*)|(ε ε| | (a|b) (a|b)*)_(a(a|b)*|b(a|b)*) →.(a(a|b)*|b(a|b)*)| | (a|b) (a|b)*.(a(a|b)*|b(a|b)*)|_(a(a|b)*|b(a|b)*)| | (a|b) (a|b)* _(a(a|b)*|b(a|b)*) →.B|_B |aC|bC B→(a|b) (a|b)* → aA|bA 得到正规文法 G[S]: S→aA|aC A→aA|bA|ε C→aC|bC|.B|_B B→aA|bA 2. 给定正规式：给定正规式：0(0|1)*1 (1) 写出相应的正规文法。
写出相应的正规文法 (2) 画出相应的状态转移图画出相应的状态转移图 【解】 (1) 引入非终结符 S， A S → 0(0|1)*1 →0A A →(0|1)*1→(ε ε| | (0|1)+)1→1| (0|1)+ 1→1| (0|1) (0|1)*1→1| 0A|1A 得到正规文法 G[S]: S 0A A 0A|1A|1 (2) 第一问中给出的 G[S]是一个右线性文法 按照由右线性正规文法构造状态转换图的方法构造相应的状态转移图如下： S A 0 Z 1 0|1 《编译原理》 课后练习参考答案 第 03 章 词法分析 共 4 页，第 2 页 3. 给定文法给定文法 G[Z]: S0U | 1V U 1S | 1 V 0S | 0 (1) 请构造该文法的状态转换图请构造该文法的状态转换图 (2) 利用所得的状态转换图判别符号串利用所得的状态转换图判别符号串 100101 和和 100111 是否该文法的句子是否该文法的句子。
【解】 (1) 增加一个终态 Z，得到该文法对应的状态转换图如下： S U 0 V 1 0 0 1 1 Z (2) 对符号串 100101 的识别过程经历了状态 S、V、S、U、S、U、Z，终止于终止状态 Z，所 以 100101 是此文法的句子 对符号串 100111 的识别过程经历了状态 S、V、S、U、S、V 识别出 10011 后，在状态 V 无法进一步识别，所以 100111 不是此文法的句子 4. 给出描述包含奇数个给出描述包含奇数个 1 或奇数个或奇数个 0 的二进制数串的正规表达式的二进制数串的正规表达式 【解】 本题求二进制串，并且要求包含奇数个 0 或奇数个 1，由于 0 和 1 都可以在二进制串中任何 地方出现，所以本题只需要考虑包含奇数个 0 的字符串，另外一种情况可以类似求得 由于只关心 0 的个数的奇偶数，我们可以把二进制串分成多段来考虑： 第 1 段为二进制串的开始到第 1 个0 为止， 这一段包含 1 个 0， 并且 0 的前面有 0 或多个 1 对于剩下的二进制串按照每段包含两个 0 的方式去划分，即以 0 开始，以 0 结尾，中间 可以有 0 个或多个 1。
如果一个二进制串被这样划分完后，剩下的部分如果全部是全 1 串（这些全 1 串在前面划分 的串之间或最后） ，则该二进制串就具有奇数个 0 所以包含奇数个 0 的二进制串可以这样描述： 以第 1 段(1＊)开始，后面由全 1 串(1＊)以及包含两个 0 的串(01＊0)组成， 其正规表达式为：1＊0 ( 1 | 01＊0 )＊，本题的解答则是：1＊0 (1 | 01＊0)＊ | 0＊1(0 | 10＊1)＊ 5. 请给出接受｛请给出接受｛0,1｝上不含子串｝上不含子串 010 的所有串的正规表达式和的所有串的正规表达式和 DFA 【解】 本题有两种解题思路，一种是直接构造一个满足条件的状态转换图，然后根据状态转换 图求正规表达式另一种方法是分析题意直接写出满足条件的正规表达式 《编译原理》 课后练习参考答案 第 03 章 词法分析 共 4 页，第 3 页 方法方法 1： 直接写出满足条件的状态转换图在状态转换图中引入 3 个状态，初始状态 S（也是终止状 态） ，表示当前读入的串中不包含子串 010，并且最后读入的字符是 1 或没读入任何字符。
初 始状态读入字符 0 后进入一个新的状态 A，状态 A 表示当前读入的串中不包含子串 010，并 且最后读入的字符是 0状态 A 如果读入字符 1 后进入新状态 B，状态 B 表示当前读入的串 中不包含子串 010，并且最后读入的字符是 01，状态 B 不接受字符 0然后用 0、1 连接各状 态就构造出了满足条件的状态转换图，如下所示然后根据状态转换图来求正规表达式，这 里就不详细说明了 方法方法 2： 直接写出满足条件的正规表达式考虑满足条件的字符串中的 1，在串的开始部分可以有 0 个或多个 1，串的尾部也可以有 0 个或多个 1，但串的之间只要出现 1，则至少在两个以上， 所以满足条件的正规表达式为：1＊（0｜111＊）＊1＊ 【解答】所求正规表达式为：1＊（0｜111＊）＊1＊，所求 DFA 如上图所示 6. 一个人带着狼、山羊和白菜在一条河的左岸，有一条船，大小正好能装下这个人和其它一个人带着狼、山羊和白菜在一条河的左岸，有一条船，大小正好能装下这个人和其它 3 件东西中的一件 人和他的随行物都要过到河的右岸 人每次只能将一件东西摆渡过河 但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉，类似的，羊也可能会吃掉 白菜。
请问是否有可能摆渡过河，并使得羊和白菜都不会被吃掉？如果可能，请用有限 自动机写出渡河的方法件东西中的一件 人和他的随行物都要过到河的右岸 人每次只能将一件东西摆渡过河 但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉，类似的，羊也可能会吃掉 白菜请问是否有可能摆渡过河，并使得羊和白菜都不会被吃掉？如果可能，请用有限 自动机写出渡河的方法 【解】 这是一道经典的智力题，很显然是有办法渡河的，关键是如何用有限自动机来求解渡河 的方法有限自动机描述的是状态和状态之间的转换，对于本题，可以把人、狼、山羊和白 菜都在左岸作为有限自动机的初始状态，而把他们都在右岸作为终止状态，只要构造一个自 动机使得存在一条从初始状态到终止状态的路径就可以了 首先构造有限自动机的状态集，可以用｛ ｛M，W，G，C｝,{}｝表示人、狼、山羊和白 菜都在左岸，用｛ ｛｝ ， ｛M，W，G，C｝ ｝表示人、狼、山羊和白菜都在右岸可能存在状态 共有 1(初态)＋4(4 选 1 过河)＋4×3(4 选 2 过河)＋4(4 选 1 留左岸)＋1(终态)＝22 个，但其中 有些状态是不安全的，如｛ ｛G，C｝ ， ｛M，W｝ ｝表示人和狼在右岸，山羊和白菜在左岸，山 羊会吃了白菜。
去掉不安全的状态， 剩下的状态就是要构造的有限自动状态集， 共 10 个状态： ｛ ｛M，W，G，C｝ ， ｛｝ ｝ ， ｛ ｛｝ ， ｛M，W，G，C｝ ｝ ， ｛ ｛M，W，G｝ ， ｛C｝ ｝ ， ｛ ｛M，W，C｝ ， ｛G｝ ｝ ， ｛ ｛M，G，C｝ ， ｛W｝ ｝ ， ｛ ｛C｝ ， ｛M，W，G｝ ｝ ， ｛ ｛G｝ ， ｛M，W，C｝ ｝ ， ｛ ｛W｝ ， ｛M，《编译原理》 课后练习参考答案 第 03 章 词法分析 共 4 页，第 4 页 G，C｝ ｝ ， ｛ ｛M，G｝ ， ｛W，C｝ ｝ ， ｛ ｛W，C｝ ， ｛M，G｝ ｝ 接下来为有限自动机添加箭弧，用＜M＞表示人独自过河，用＜MW＞表示人和狼一起过 河，用＜MG＞表示人和山羊一起过河，用＜MC＞表示人和白菜一起过河在状态之间只要 可以使用箭弧，则得到一个状态转换图，如下图所示 观察所求得的有限自动机的状态转换图，可以发现从初始状态到终止状态之间存在两条 较短的路径，它们分别为｛＜MG＞＜M＞＜MW＞＜MG＞＜MC＞＜M＞＜MG＞｝和｛＜ MG＞＜M＞＜MC＞＜MG＞＜MW＞＜M＞＜MG＞＝这两条路径就是两种正确的渡河方法。
【解答】 分析题意，求得相应有限自动机的状态转换图如下所示，从图中直接可以得到两种渡河 方法｛＜MG＞＜M＞＜MW＞＜MG＞＜MC＞＜M＞＜MG＞｝和｛＜MG＞＜M＞＜MC＞ ＜MG＞＜MW＞＜M＞＜MG＞｝ 路径｛＜MG＞＜M＞＜MW＞＜MG＞＜MC＞＜M＞＜MG＞｝的解释为： 第 1 步，人带山羊过河（到右岸） ； 第 2 步，人独自过河（到左岸） ； 第 3 步，人带狼过河（到右岸） ； 第 4 步，人带山羊过河（到左岸） ； 第 5 步，人带白菜过河（到右岸） ； 第 6 步，人独自过河（到左岸） ； 第 7 步，人带山羊过河（到右岸） 另一条路径的解释类似。