CS3331 – Assignment 3 due Dec. 1, 2020, (latest to submit: Dec. 4, 11:55pm) 1. (10pt) Consider the alphabet Σ = {a, b} and define the function d : Σ∗ → Σ∗ by d(w) = ww. Construct a deterministic...

I just need the question 3,4,5 to be done


CS3331 – Assignment 3 due Dec. 1, 2020, (latest to submit: Dec. 4, 11:55pm) 1. (10pt) Consider the alphabet Σ = {a, b} and define the function d : Σ∗ → Σ∗ by d(w) = ww. Construct a deterministic Turing machine M that computes the function d, that is, M starts with the initial configuration (s,�w) and halts with the configuration (h,�d(w)). Describe M in details using a directed graph whose edges are labelled by transitions (such as the one in Example 17.2, p. 268 of textbook). 2. (10pt) Construct a deterministic Turing machine M that counts the number of a’s in its input. M starts with the initial configuration (s,�w) and halts with the configuration (h,�#a(w)2), where #a(w)2 is the number of a’s in w written in base 2. Here are some examples of M ’s behaviour: (s,�) `∗ (h,�0) (s,�bb) `∗ (h,�0) (s,�abcaaaa) `∗ (h,�101) Describe M using the macro language (such as the one in Example 17.8, p. 275 of textbook). 3. (40pt) Prove that the following languages are in D: (a) L = {| | | < 10},="" (b)="" l="">| M is a TM and L(M) 6∈ SD}, (c) L = {| |w| is even and M halts on input w in at most 2|w| steps}, (d) L = {| the first move of M on w is to the right and then M ’s head never moves outside the |w| tape cells that initially contain w}. 4. (20pt) Assume we have a way to encode a given finite state machine into a binary string. Describe in clear English a Turing machine that semidecides this language: L = {| M accepts the binary encodings of at least 2 FSMs whose language is not empty} . (Clear English description of the Turing machines is sufficient. That is, you don’t have to effectively build the machine, instead explain how the machine behaves.) 5. (20pt) Given a language L that is not decidable and a regular language R, what can you say about the decidability of L ∩R? READ ME! Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be either typed or legibly handwritten. Make sure you submit everything as a single pdf file. Self-reported absences can be used to extend the deadline by 48h. In this case, you must label “SELF-REPORTED ABSENCE” clearly at the top of the assignment and submit it by email to [email protected] instead of OWL. Failure to submit in OWL by “Accept until” date or follow the above procedure for self-reported absences will result in your submission not being considered. Due to the very large class, I cannot consider special cases without good reason. JFLAP: You are allowed to use JFLAP to solve the assignment. Make sure you understand what it does. LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to all the other programs, it is free, and you can start using it in minutes; here is useful introduction: https://tobi.oetiker.ch/lshort/lshort.pdf 1