STA1610 Assignment 2 Solutions 2022 [Unique No.: 650587]

STA1610 Assignment 2 Solutions 2022 [Unique No.: 650587] COS3701 Assignment 4 2022 Unique No.: 830436 Due Date: 29 September 2022 In this document you will find 1. The complete suggested solutions to COS3701 Assignment 4 2022 2. As a bonus you will have access to download the COS3701 prescribed textbook(Introduction to computer theory 2nd edition Daniel I.A. Cohen) completely free of charge by clicking the google drive link on the last page of this document. Please note: This should only be used as a guide for your own assignment. Question 1 Chapter 23 – Problem 1(i), p. 562 Σ = {a, b}. EVEN-EVEN is defined on page 236 of Cohen: EVEN-EVEN = all strings x with an even number of as and an even number of bs. Note that TL101 refers to ODDPALINDROME but the language we are actually interested in is EVEN-EVEN. A TM that accepts this language is illustrated in Figure 1. This TM has essentially four states State 1 This represents the case where an odd number of as and an even number of bs have been read (OE). State 2 This represents the case where an even number of as and an odd number of bs have been read (EO). State 3 This represents the case where an even number of as and an even number of bs have been read (EE). State 4 This represents the case where an odd number of as and an odd number of bs have been read (OO). Consider the string aa. In this case the TM moves to state 1 after reading the first a (OE) and then to state 3 after reading the second a (EE). The TM will then go the halt state and even number of as (2) and an even number of bs (0) have been read. Consider a more complicated string abaabbba. In this case the word is in EVEN-EVEN so the TM should reach the halt state. What happens is: Read a go to state 1 – here we have 1 a and 0 bs so we have OE Read b go to state 4 – OO Read a go to state 2 – EO Read a go to state 4 – OO Read b go to state 1 – OE Read b go to state 4 – OO Read b go to state 1 – OE Read a go to state 3 –EE Read ∆ go to state halt The TM will reject any word that is not in EVEN-EVEN. Figure 1: Turing Machine (TM) for Question 1 Question 2 Let T be the Turing machine in problem 13(v), p. 562 - 563. What are the languages accept(T), reject(T) and loop(T)? Again, Σ = {a, b}. For the given TM T: Accept(T) = nothing Reject(T) = ∆ + a(a + b)∗ + ba(a + b)∗ + bb(a + b)∗ Loop(T) = b