第3章 作业及参考答案

1 针对 DFA M1 1 请给出在处理字符串 1011001 的过程中经过的状态序列 解 经过的状态序列为 q0q3q1q3q2q3q1q3 2 请给出形式描述 争议 M1的形式化还是接受过程的形式化 解 M1的形式描述为 M1 q0 q1 q2 q3 0 1 q0 q3 其中 定义为 q0 0 q1 q0 1 q3 q1 0 q2 q1 1 q3 q2 0 q3 q2 1 q0 q3 0 q1 q3 1 q2 接受过程的形式化 q01011001 1q3011001 10q111001 101q31001 1011q2001 10110q301 101100q11 1011001q3 注意 谈及自动机形式化描述 一定是用五元组表示 将 函数直接写出来 2 构造识别下列语言的 DFA 要求写出形式化描述 另外 写出设计过程对理清你的思维更有益 要求写出形式化描述 另外 写出设计过程对理清你的思维更有益 3 x x 0 1 且 x 中不含形如 00 的子串 1 0 0 1 qt qs q1 S 1 0 1 q0 0 或 对 但稍嫌麻烦 05 级孙磊 0 1 0 0 1 qt qs q1 S 1 q0 0 q 错解 x 0 1 1 0 q0 S q1 q2 1 0 0 1 1 0 q0 S q1 q3 1 0 0 1 q2 0 1 0 不接受 1 可接受 000 1 0 q0 S q1 1 0 5 x x 0 1 且 x 中含形如 10110 的子串 1 1 1 q0 S q1 q2 q3q4q5 0 0 110 0 0 1 0 1 q0 起始状态 以及未读入 1 的状态 q1 读入了 10110 中第 1 个符号 1 的状态 q2 读入了 10110 中第 2 个符号 0 的状态 q3 读入了 10110 中第 3 个符号 1 的状态 q4 读入了 10110 中第 4 个符号 1 的状态 q5 读入了 10110 中第 5 个符号 0 的状态 易犯的错误易犯的错误 状态转移时状态转移时 不考虑已接受一些字符后所处状态不考虑已接受一些字符后所处状态 一味地转到开始状态 不利一味地转到开始状态 不利 用阶段性成果 狗熊掰棒子 用阶段性成果 狗熊掰棒子 1 1 q0 S q1 q2 q3q4q5 0 0 110 0 0 0 1 1 7 x x 0 1 且把 x 看成二进制数时 x 模 5 与 3 同余 要求中当 x 为 0 时 x 1 且 x 0 时 x 首字符是 1 提示提示 和和 P98 例例 3 5 属同一类型属同一类型 这种设计如不写清楚设计过程这种设计如不写清楚设计过程 不能服人不能服人 也不能反映你也不能反映你 的设计方法的设计方法 解 按题意 当 x 为 0 时 x 的长度为 1 即不能出现多于 1 个 0 的全 0 串 当 x 不为 0 时 必须以 1 开始 又由于 0 模 5 与 3 不同余 故在开始状态 qs读入 0 则直接进入陷阱状态 qt 即 qs 0 qt 其余状态为 q1 对应 x 模 5 与 1 同余的等价类 q2 对应 x 模 5 与 2 同余的等价类 q3 对应 x 模 5 与 3 同余的等价类 终止状态 q4 对应 x 模 5 与 4 同余的等价类 q5 对应 x 模 5 与 0 同余的等价类 x 0 所以 要构造的 DFA 为 M qs q1 q2 q3 q4 q5 qt 0 1 qs q3 状态转换函数 定义如下 0 在初始状态 qs qs 0 qt qs 1 q1 1 当处于 q1状态时 已读入的 x 5n 1 n 0 由 2x 0 5 2n 2 有 q1 0 q2 由 2x 1 5 2n 3 有 q1 1 q3 2 当处于 q2状态时 已读入的 x 5n 2 n 0 由 2x 0 5 2n 4 有 q2 0 q4 由 2x 1 5 2n 1 0 有 q2 1 q5 3 当处于 q3状态时 已读入的 x 5n 3 n 0 由 2x 0 5 2n 1 1 有 q3 0 q1 由 2x 1 5 2n 1 2 有 q3 1 q2 4 当处于 q4状态时 已读入的 x 5n 4 n 0 由 2x 0 5 2n 1 3 有 q4 0 q3 由 2x 1 5 2n 2 4 有 q4 1 q4 5 当处于 q5状态时 已读入的 x 5n n 1 由 2x 0 5 2n 0 有 q5 0 q5 由 2x 1 5 2n 1 有 q5 1 q1 6 在陷阱状态 qt 有 qt 0 qt qt 1 qt 1 q2 0 1 qs S q1 q4 q3 0 00 1 1 1 1 0 q5 qt0 1 0 10 x x 0 1 且 x 中至少含两个 1 0 1 q0 S q1 q2 0 1 0 1 或 05 级张士光 0 1 S 0 1 0 1 1 错解 错误原因 0 1 q0 S q1 q2 0 1 0 1 10 构造识别下列语言的 NFA 要求写出形式化描述要求写出形式化描述 2 x x 0 1 且 x 中含形如 10110 的子串 1 q0 S q1 q2 q3q4q5 0 1 01 10 0 1 错解 0 用的是 DFA 思维 1 q0 S q1 q2 q3q4q5 01 10 0 1 qt0 1 000 1 1 另一不能算错的错误 设计 DFA 形式化描述时易犯的错误 q3 1 q2 或 q3 1 q2 8 x x 0 1 且 x 的首字符和尾字符相同 1 1 q1 q0 S q2 q3 0 1 00 0 1 q4 或 1 1 q1 q0 S q2 q3 0 1 00 0 1 或 后面的这两个解更好 严格讲 前两解不全对 05 级孙亮波 1 1 q1 q0 S q2 q3 0 1 00 0 1 q4 0 1 或 05 级孙磊 1 1 q1 q0 S q2 q3 0 1 0 0 0 1 0 1 11 1 根据给定的 NFA 构造与之等价的 DFA 输入字符 状态说明状态 012 开始状态 q0 q0 q1 q0 q2 q0 q2 q0 q1 q0 q1 q3 q0 q2 q0 q2 q0 q2 q0 q1 q0 q1 q2 q3 q0 q1 q2 终止状态 q0 q1 q3 q0 q1 q2 q3 q0 q2 q3 q0 q2 q0 q1 q2 q0 q1 q3 q0 q1 q2 q3 q0 q1 q2 终止状态 q0 q2 q3 q0 q1 q2 q3 q0 q1 q2 q3 q0 q1 q2 终止状态 q0 q1 q2 q3 q0 q1 q2 q3 q0 q1 q2 q3 q0 q1 q2 形式化描述与状态转移图略 不合适的解法不合适的解法 1 专门列出一个产生式专门列出一个产生式 S q0 2 列出列出 2Q中所有状态组中所有状态组 没有必要没有必要 2 状态组不用状态组不用 括起来括起来 虽然本质上没有问题虽然本质上没有问题 但可能但可能 忽略忽略 状态集状态集 状态组状态组 单个状态单个状态 在思维上的转变在思维上的转变 20 构造图 3 20 所给 DFA 对应的右线性文法 做左图 解 q0 0q1 1q3 1 q1 0q0 1q3 1 q3 0q1 1q1 q2 0q3 1q1 0 补充 先将无用状态 q2去掉再做 05 级张志辉 岳宝提出 不合适的解法不合适的解法 把非终结符把非终结符 qi 原自动机中的状态原自动机中的状态 换为换为 S A B 等在文法中常见的符号等在文法中常见的符号 抽象抽象 是去除表面的现象是去除表面的现象 保留其实质所在保留其实质所在 如果在用的符号上都得费心思变一下才行如果在用的符号上都得费心思变一下才行 对抽象能对抽象能 力培养不利力培养不利 我以这个理由辩不该换符号我以这个理由辩不该换符号 其实你也可以同样的理由辩换了也无所谓其实你也可以同样的理由辩换了也无所谓 但我但我 觉得还是不换为好觉得还是不换为好 22 1 根据下列所给文法 构造相应的 FA G1 S a aA A a aA cA bB B a b c aB bB cB 解 FA M S A B Z a b c S Z 其中 为 S a Z A A