” CS662编程设计 写作、 辅导Python程序PRACTICE FINAL EXAM CS662SOLUTION: Think in terms of a 4-tape Turing machine: first put all the as onto one tape, then all thebs onto the second tape, then all the cs onto the third tape. Then just loop through all 3 tapes atonce. Reject if there is an a without a b, or a b without a c. Otherwise once were at the end of thetape, accept.2) Let M be the Turing machine defined bya) Trace the computation for the input string aabca.b) Trace the computation for the input string bcbc.c) Describe the result of a computation in MSolutions:3) Design a TM for strings that have the same number of as and bs: Give an outline first.SOLUTIONS:A computation of the machine begins by finding the first a on the tape and replacing it with an X (state q1). Thetape head is then returned to position zero and a search is initiated for a corresponding b. If a b isencountered in state q3, an X is written and the tape head is repositioned to repeat the cycle q2, q3, q4, q5. If nomatching b is found, the Computation halts in state q3 rejecting the input. After all the as have beenprocessed, the entire string 4 is read in q5 and q6 is entered upon reading the trailing blank. The computationhalts in the accepting state qf if no bs remain on the tape.Transitions (in a tabular form, easier to read)4) If L is a recursively enumerable (RE) language, then the strings in L can be accepted by a:____________________.5) If L is a recursively enumerable (RE) language, then the strings in L can be generated by an_______________ grammar.6) If L is RE but not recursive, then its complement cannot be RE (true or false). ____________7) Give context-free grammars that generate the following languages.i) { w {0, 1}*| the length of w is odd and the middle symbol is 0 }Solutions:i) S 0 S 0 | 0 S 1 | 1 S 0 | 1 S 1 | 0ii) S aSc | A A bAc | iii) S AB | C A aAb | B cB | C aC c | DD bD | 8) Transform the grammar with productions S abAB A baB| B BAa|A| intoChomsky normal form.Solutions:Removing productions: Here A and B are nullable variables. Then following the second step ofconstruction in Theorem 6.3 in the textbook, we get:S abAB|abA|abB|ab A baB|ba B BAa|A|Ba|Aa|aRemoving unit-productions(by Theorem 6.4):S abAB|abA|abB|ab A baB|ba B BAa|baB|ba|Ba|Aa|a.There are no useless productions in the grammar. By step 1 of Theorem 6.6, we introduce variables Cand D to substitute terminals a and b.S CDAB|CDA|CDB|CD A DCB|DC B BAC|DCB|DC|BC|AC|aC a, D bBy step 2 of Theorem 6.6, we introduce variables to shorten the right sides of the production.S EF|EA|EB|CD A GB|DC, B BH|GB|DC|BC|AC|a,E CD, F AB G DC H AC C a D b9) Convert the Following grammar into Greibach form, then construct a corresponding NPDA:S aABB|aAA A aBB|a B bBB|A.Solutions:The grammar Does not have any productions. So we can convert it into Greibach normal form. Byapplying Theorem 6.1 on last production,S aABB|aAA A aBB|a B bBB|aBB|aBy applying construction in Theorem 7.1, Define M = ({q0, q1, qf }, , {S, A, B, z}, , q0, z, {qf}) with:(q0, , z) = {(q1, Sz)} (q1, a, S) = {(q1, ABB),(q1, AA)}(q1, a, A) = {(q1, BB),(q1, )} (q1, b, B) = {(q1, BB)}(q1, a, B) = {(q1, BB),(q1, )} (q1, , z) = {(qf , z)}10) Eliminate useless productions fromS a|aA|B|C A aB| B Aa C cCD D ddd.Solutions:Remove those variables that do not produce any strings then remove the unreachable variables.S a|aA|B A aB| B Aa,11) Construct an NPDA that accepts the following language on = {a, b}, L = {w | na(w) = nb(w) + 1}.Solutions:M = ({q0, q1, q2}, , {a, b, z}, , q0, z, {q2}) with(q0, , z) = {(q1, az)} (q1, a, z) = {(q1, az)} (q1, a, a) = {(q1, aa)}(q1, a, b) = {(q1, )} (q1, b, z) = {(q1, bz)} (q1, b, a) = {(q1, )}(q1, b, b) = {(q1, bb)} (q1, , z) = {(q2, )} (q1, c, z) = {(q1, c)}(q1, c, a) = {(qa, a)} (q1, c, b) = {(q1, b)}Then M accepts L since it starts with one extra a on the stack and then uses the machine given in Example 7.4to tell if the Number of as and bs are the same. If they are and we started with one more a on the stack, thenthe condition of L is met.12) Set of all strings that are at least of length 4 and contains even number of 1s.Solutions:如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
