计算理论作业答案(1).pdf-资料库

weixin_37904131-12734061-16359647506978176716.pdf-第1页.png

第1页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第2页.png

第2页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第3页.png

第3页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第4页.png

第4页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第5页.png

第5页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第6页.png

第6页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第7页.png

第7页 / 共25页

weixin_37904131-12734061-16359647506978176716.pdf-第8页.png

第8页 / 共25页

1.6 画出识别下述语言的 DFA 的状态图。 0 1 1 1 0 0 0,1 a){w | w 从 1 开始以 0 结束} b){w | w 至少有 3 个 1} c) {w | w 含有子串 0101} d) {w | w 的长度不小于 3，且第三个符号为 0} 0,1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0,1 e) {w | w 从 0 开始且为奇长度，或从 1 开始且为偶长度} 0,1 0 0,1 0,1 或 0 0,1 0,1 1 1 f) {w | w 不含子串 110} 0 0,1 1 0 1 0,1 1 0 1

0,1 0,1 0,1 1 1 0,1 0 0,1 0,1 1 0,1 1 1 1 0 0,1 0,1 0 0 0,1 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} 1 0,1 1 1 0 0 0 0 0 0 0,1 1 1 0 0 0 0 1 1 1 1 0 0 0 0,1 1 1 1 0 0 1 2

m) 空集 n) 除空串外的所有字符串 0,1 0,1 0,1 1.7 给出识别下述语言的 NFA，且要求符合规定的状态数。 0,1 a. {w | w 以 00 结束}，三个状态 b. 语言｛w | w 含有子串 0101，即对某个 x 和 y，w=x0101y｝，5 个状态. 0 0 0,1 0,1 0 1 0 1 c. 语言｛w | w 含有偶数个 0 或恰好两个 1｝，6 个状态。 1 0 1 0 0 0 1   0 1 d. 语言｛0｝，2 个状态。 0 e. 语言 0*1*0*0，3 个状态。 0 1 0  0 f. 语言{ε}，1 个状态。 g. 语言 0*，1 个状态。 0 1.19 对下述每一个语言，给出 4 个字符串，2 个是这个语言的成员，2 个不是这个语言的成员。这里假设字母表 Σ={a,b}. 3

此题为开放题，答案不唯一。 a. a*b* 成员：ab，aab 非成员：aba，ba b. a(ba)* 成员：ab，abab 非成员：abb，aa c. a*b* 成员：aaa，bbb 非成员：ab，ba d. (aaa)* 成员：aaa，aaaaaa 非成员：a，aa e.Σ*aΣ*bΣ*aΣ* 成员：aba，aaba 非成员：aa，abb f. ababab 成员：aba，bab 非成员：a，b g. (a)b 成员：b，ab 非成员：a，bb h. (ababb) Σ* 成员：a，bb 非成员：，b 1.29 利用泵引理证明下述语言不是正则的。 a. A1={0 n n n | n0}。 2 1 证明：假设 A1 是正则的。设 p 是泵引理给出的关于 A1 的泵长度。令 S=0 p p p 2 , 1 ∵S 是 A1 的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满足泵引理的 3 个条件。根据条件 3，y 中只含 0，xyyz 中，0 比 1、2 多，xyyz 不是 A1 的成员。违反泵引理的条件 1，矛盾。 ∴A1 不是正则的。 b. A2={www | w{a,b}*}. 证明：假设 A2 是正则的。设 p 是泵引理给出的关于 A2 的泵长度。 p 令 S=a p ba p ba b, ∵S 是 A2 的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满足泵引理的 3 个条件。根据条件 3，y 中只含 a，所以 xyyz 中第一个 a 的个数将比后两个 a 的个数多，故 xyyz 不是 A2 的成员。违反泵引理的条件 1，矛盾。 ∴A2 不是正则的。 c. A3={a2n | n0}.(在这里，a2n 表示一串 2 n 个 a .) 证明：假设 A3 是正则的。设 p 是泵引理给出的关于 A3 的泵长度。令 S= a2p， ∵S 是 A2 的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满足泵引理的 3 个条件。即对任意的 i0，xyiz 都应在 A3 中，且 xyiz 与 xyi+1z 的长度都应是 2 的幂. 而且 xyi+1z 的长度应是 xyiz 的长度的 2 n 倍 (n1) 。于是可以选择足够大的 i ，使得 |xyiz|=2 n >p. 但是 |xyi+1z|-|xyiz|=|y|p. 即|xyi+1z|<2 n+1 , 矛盾。 ∴A3 不是正则的。 4

1.37 令 Cn={x | x 是一个二进制数，且是 n 的整数倍}。证明对于每一个 n1, Cn 是正则的。证明：下面的 DFA 识别 Cn：(正向读) M=( Q, {0,1} ,  , q0 , F ), 其中 Q＝{0,1,2,…，n-1}, ( i,1)=2i+1 mod n, ( i,0 )=( 2i mod n), i=0,1,2,…，n-1, 起始状态为 0, F＝{0}. 这里 i 表示当前数 mod n 余 i. 下面的 DFA 识别 Cn M=( Q, {0,1} ,  , q0 , F ), 其中 Q＝{(i,j)|i,j=0,1,2,…，n-1}, ((i,j),1)=( 2i mod n, (2i+j)mod n ), ((i,j),0)=( 2i mod n, j ), i,j=0,1,2,…，n-1 起始状态为(1,0), F＝{ (i,0) | i=0,1,…，n-1}. 这里(i,j)表示当前数 mod n 余 j, 而下一位所表示单位数 mod n 余 i(例如，若读下一位将达到 k 位，则下一位所表示单位数为 10k-1). R：(反向读) 5

2.3 a. R,X,S,T; b. a,b; c. R; d. aaba,abaa,bbaa; e. bbbbb,aaaaa,abbbb; f. 假; g. 真; h. 假; i. 假; j. 真; k. 假; l. 真; m. 真; n. 假; o. 在非首尾两位置，存在对称的两个位置字母不一致。 → → → 2.6 答案不唯一 a. S aR|Ra|aRab|baRa R aRb|bRa|aRa| ϵ → b. S aRb|bRb|aRa|bRa|bR|Ra R a|b → c. S R0|R1 → R 0R0|1R1|0T0|1T1 → T T0|T1|# d. S aS|bS|Sa|Sb|#S|S#|#R# → R aRa|bRb|#T# → T aT|bT|Ta|Tb|#T|T#| ϵ → 2.7 a. 1)将符号$和起始变元S压入栈中； → 2)如果栈顶是S，则非确定地从S aR|Ra|aRab|baRa中选择一个规则，并把S替换成右边的字符串； → 3)如果栈顶是R，则非确定地从R aRb|bRa|aRa| 中选择一个规则，并把S替换成右边的字符串； 4)如果栈顶是终结符，则读取下一个输入符号，并且把它与之比较，如果匹配则重复，反之则这个非确定性分支拒绝； 5)如果栈顶是$，则进入接收状态，如果此时全部读完，则接受这个字符串。 b. 1)将符号$和起始变元S压入栈中； ϵ

→ → 2)如果栈顶是S，则非确定地从S aRb|bRb|aRa|bRa|bR|Ra中选择一个规则，并把S替换成右边的字符串； 3)如果栈顶是R，则非确定地从R a|b中选择一个规则，并把S替换成右边的字符串； 4)如果栈顶是终结符，则读取下一个输入符号，并且把它与之比较，如果匹配则重复，反之则这个非确定性分支拒绝； 5)如果栈顶是$，则进入接收状态，如果此时全部读完，则接受这个字符串。 c. 1)将符号$和起始变元S压入栈中； → 2)如果栈顶是S，则非确定地从S R0|R1中选择一个规则，并把S替换成右边的字符串； → 3)如果栈顶是R，则非确定地从R 0R0|1R1|0T0|1T1中选择一个规则，并把S替换成右边的字符串； → 4)如果栈顶是R，则非确定地从T T0|T1|#中选择一个规则，并把S替换成右边的字符串； 5)如果栈顶是终结符，则读取下一个输入符号，并且把它与之比较，如果匹配则重复，反之则这个非确定性分支拒绝； 6)如果栈顶是$，则进入接收状态，如果此时全部读完，则接受这个字符串。 d. 1)将符号$和起始变元S压入栈中； → 2)如果栈顶是S，则非确定地从S aS|bS|Sa|Sb|#S|S#|#R#中选择一个规则，并把S替换成右边的字符串； 3)如果栈顶是R，则非确定地从R aRa|bRb|#T#中选择一个规则，并把S替换成右边的字符串； 4)如果栈顶是R，则非确定地从T aT|bT|Ta|Tb|#T|T#| 中选择一个规则，并把S替换成右边的字符串； 5)如果栈顶是终结符，则读取下一个输入符号，并且把它与之比较，如果匹配则重复，反之则这个非确定性分支拒绝； 6)如果栈顶是$，则进入接收状态，如果此时全部读完，则接受这个字符串。 → → ϵ 2.10 → S UV|RT → ϵ U aUb| → ϵ V cV| → ϵ R aR| → ϵ T bTc| S / \ U V /\ \ a b c S / \ U V

/ / \ a b c 2.23 → S 0R1|1R0|0R0|1R1 → R 0T1|1T0 → T 0T1|1T0|U| ϵ → U 0U1|1U0|1U1|0U0| ϵ

资料库

计算理论作业答案(1).pdf

相关推荐

考试认证

热门标签

最新资料