计算理论习题解答及状态机描述

计算理论习题解答 本资源为计算理论习题解答，涵盖自动机理论、形式语言、计算能力等方面的知识点。 1.1 图给出的两台DFAM1和M2的状态图： * M1的起始状态是q1，接受状态集是{q2}。 * M2的起始状态是q1，接受状态集是{q1，q4}。 * 对输入aabb，M1经历的状态序列是q1,q2,q3,q1,q1。 * M1接受字符串aabb吗？否。 * M2接受字符串ε吗？是。 1.2 给出练习2.1中画出的机器M1和M2的形式描述： * M1=(Q1,Σ,δ1,q1,F1)，其中Q1={q1,q2,q3},Σ={a,b},δ1为： a b q1 q2 q3 q2 q1 q3 q3 q2 q1 * M2=(Q2,Σ,δ2,q2,F2)，其中Q2={q1,q2,q3,q4},Σ={a,b},δ2为： a b q1 q2 q3 q4 q2 q1 q3 q4 q3 q2 q3 q4 q4 q1 q2 q3 1.3 DFAM的形式描述为({q1,q2,q3,q4,q5},{u,d},δ,q3,{q3})： * δ在表2-3中给出。 * 画出此机器的状态图。 1.6 画出识别下述语言的DFA的状态图： * a) {w|w从1开始以0结束} * b) {w|w至少有3个1} * c) {w|w含有子串0101} * d) {w|w的长度不小于3，且第三个符号为0} * e) {w|w从0开始且为奇长度，或从1开始且为偶长度} * f) {w|w不含子串110} * g) {w|w的长度不超过5} * h) {w|w是除11和111以外的任何字符} * i) {w|w的奇位置均为1} * j) {w|w至少含有2个0，且至多含有1个1} * k) {ε,0} * l) {w|w含有偶数个0，或恰好两个1} * m) 空集 * n) 除空串外的所有字符串 知识点总结： * 自动机理论：有限自动机（FA）、确定性有限自动机（DFA）、非确定性有限自动机（NFA）等。 * 形式语言：正规语言、上下文无关语言、上下文相关语言等。 * 计算能力：自动机的计算能力，包括语言识别、字符串匹配等。 本资源涵盖了计算理论的基础知识点，包括自动机理论、形式语言和计算能力等方面的知识点，对于计算理论的学习和研究具有重要的参考价值。