Follow the instructions and solve the problems
CSci 4011, Formal Languages and Automata Theory Homework 4, Fall 2020 Posted: Oct 26, 2020 Due: Nov 9, 2020 Reminder: Assignments are due by 11:59 p.m. on the indicated date. Please make sure to consult the guidelines for homework submissions posted at https://z.umn.edu/csci4011submissions before you start writing up your homework. In addition, make sure to read the part of the syllabus that discusses the requirements of homework submissions to understand the factors that will impact on the grading. Remember that communicating your approach to the solution of a problem—e.g. the key ideas underlying a proof or a construction—is as important as laying out the details, and sometimes may be more important. For this reason, you should typically begin your answer to each problem with a brief discussion of these key ideas before you go into the specific details. This is not a hard-and-fast rule—sometimes the essential idea may be so apparent as to not need any further explanation—but it is a yardstick for you to consider when writing your solutions. Remember that this is a math course and in accessing math work we must look at precision as well as clarity of thought. Problem 1 (5 points) Provide an implementation-level description of a Turing machine that recognizes the following language: {w ∈ {0, 1}∗ | w contains twice as many 0s as 1s}. Recall that by “implementation-level description” we mean the description of a plan that can be followed to construct an actual Turing machine, given concretely by a 7-tuple, for recognizing the language of interest. Another way to understand this is that the implementation-level description provides an algorithm for recognizing strings in the language that pays attention to the structure of Turing machines. We have considered examples of such descriptions in the pre-recorded lectures. You may also consult Examples 3.7, 3.11 and 3.12 for further illustrations. Pay careful attention to the need to translate the plan into the description of an actual Turing machine, you will have to do this in the next problem and credit in that problem will depend on your adhering closely to the plan you describe in this one. Problem 2 (8 points) Transform the implementation-level description of a Turing machine that you have provided in Problem 1 into a formal description of a Turing machine for the language in that problem. By a formal description is meant a description in the style of what you find in Example 3.9 in the book. Also, the connection between the implementation-level description in Problem 1 and the formal description in this problem should be like that between the two styles of description in Example 3.7 in the book. Note that the two descriptions must be related in this fashion for credit in this problem. 1 https://z.umn.edu/csci4011submissions Problem 3 (5 points) Do Exercise 3.7 from the book. See the scan of the page that contains this problem that has been uploaded to Canvas before you start working on it to be sure that you have the right problem. Problem 4 (3 + 6 points) A k-PDA, where k is a number, is like the pushdown automaton that we have seen in class, except that it has k stacks to work with. Thus, a 0-PDA has no stacks and hence is equivalent to a finite state machine, a 1-PDA is the pushdown automaton we have seen in class and a 2-PDA has two stacks to work with. When there are multiple stacks, a question to ask is if the transition to the next state depends on the top of stack symbol on just one stack or on all the stacks. Assume that it is the latter. In other words, the transition function of a k-PDA has the type Q×Σε×Γkε → P(Q×Γkε). 1. Show that a k-PDA can be simulated by a (single-tape, deterministic) Turing machine for any k. Hint: You may find it convenient to use a multitape Turing machine for the simulation and then invoke Theorem 3.13. 2. Show that a Turing machine can be simulated by a 2-PDA. Hint: We may think initially of capturing what is on the tape of the Turing machine between the stack of a 1-PDA and the input tape. However, we have difficulty in realizing a left movement of the head with such a machine. But perhaps the second stack will be helpful for this? More specifically, the contents of the tape of the Turing machine may be given by some combination of what is on the first stack, what is on the second stack and what is in the input of the 2-PDA. If you follow this line of thinking, you should first explain what exactly this mapping is and then describe a translation from the Turing machine transition function to one for a 2-PDA from which it should be clear that the two accept the same language. Problem 5 (5 points) Do Problem 3.13 from the book. Look at the scan of the page that is posted on Canvas to be sure that you are working on the correct problem. Note that although the problem seems to be asking two questions, I do not see a way to answer the first question, i.e. proving that this variant is not equivalent to the usual Turing machine version, without identifying the class of languages the variant recognizes. Some comments concerning this problem. There are several solutions to it floating around the internet. As noted several times already, you are not prohibited from looking at such solutions. However, I strongly recommend that you do not look at the solutions before you have given the problem enough thought yourself. Further, remember that there is a rule that governs what you submit for grade: it must acknowledge any sources that you might have consulted and it must not be a copy of what you have consulted. More specifically, you may look at such solutions but then must put them aside and do something else for a little while and only after that set about writing your answer so that it reflects your own understanding of the problem. I might also add that it is 2 easy to tell when something you submit is a copy versus when it reflects your own understanding so it is best not to venture into the territory of trying to palm off a copy as your own work. You might ask why I have used this problem despite knowing that there are solutions available on the web. My response: It is just too nice a problem to pass up and I think you will learn something useful from trying it. Problem 6 (9 points, 3 for each part) Do parts (b), (c) and (d) of Problem 3.16 in the book. Look at the scan of the page that is posted on Canvas to be sure that you are working on the correct problem. For some parts, you may find it useful to use the equivalence of nondeterministic and deterministic Turing machines. If you compare this with Problem 3.15, you see that complementation has been left out. Think about whether or not this is necessary. You do not need to turn in anything for this part, but thinking about this now should help with regard to the topics that follow on the ones covered by this homework. Problem 7 (5 points, 2.5 points for each direction) Do Problem 3.18 from the book. Look at the scan of the page that is posted on Canvas to be sure that you are working on the correct problem. 3