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

STA1610 Assignment 2 Solutions 2022 [Unique No.: ] COS3701 Assignment 4 2022 Unique No.: 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. STA1610 Assignment 2 Solutions 2022 [Unique No.: ] COS3701 Assignment 4 2022 Unique No.: 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 Question 3 Problem 13(v) on page 562-563. The given TM is T in question 2, yields the following table: From To Read Write Move Code for each row 1 1 a b L ababaaaba 1 3 b a R abaaababaab 3 1 b a L aaabababaaa 3 3 ∆ ∆ R aaabaaabbabab The code word for the TM T is ababaaabaabaaababaabaaabababaaaaaabaaabbabab. Accept (T)= { nothing }. Question 4 Run the word in CWL which you found in Question 3 on its TM to determine whether or not it is a word of the language ALAN. The code word is not accepted by T (as T accepts nothing) and is therefore in ALAN. Question 5 Problem 15(ii) on page 564. The given code word is abaabaabba. This gives us the table shown below. Code From To Read Write Move abaabaabba 1 2 a # L If we assume that state 1 is the start state and state 2 is a halt state then the corresponding TM is shown in Figure 2. Figure 2: TM for Question 5 By the definition of a TM, execution is terminated when a halt state is entered. This means that all words starting with an a will be accepted. So, the code word is accepted by its TM, and is therefore in MATHISON. Question 6 Problem 8(iv) on page 591 The given word is abab. Using the grammar given on p. 591 of Cohen, 2nd ed. we obtain the production sequence: S ⇒ UVX PROD 1 ⇒ aUYX PROD 2 ⇒ aUVaX PROD 4 ⇒ abUZaX PROD 3 ⇒ abUaZX PROD 8 ⇒ abUaVbX PROD 5 ⇒ abUVabX PROD 12 ⇒ abΛabX PROD 10 ⇒ abΛabΛ PROD 11 abab Question 7 Build a TM that takes in three numbers in unary encoding and leaves only the smallest of them on the tape. A possible TM is given in Figure 3. We will not describe the operation of the TM in detail, but rather explain the underlying principle. The best way to understand how the TM works is to study the figure and to trace some words (representing the 3 input numbers in unary encoding) on it. We are given an input of three unary coded numbers in the form #anbambap∆∆ ..., where n, m, p ≥ 0 represent the magnitude of each number and b acts as a separator. The numbers 1, 4 and 3 would thus be represented as #abaaaabaaa. Please note the following important points: • The numbers do not have to be distinct. • Any of n, m or p may be zero. Hence inputs such as baaabaa or abbaa etc. are valid inputs in which one or more of the numbers is equal to zero. A TM which accepts the required language is provided in Figure 3. The general approach taken to solve this problem is to repeatedly match an a from the first number against an a from the second number and also an a from the third until this can no longer be done – one of the number has been reduced to no as. For example, suppose the given numbers are 3, 2 and 5. Here we know that the input should be ... ∆∆∆#aaabaabaaaaa∆∆∆ ... and the output (what is left on the tape) should be ... ∆∆∆#aa∆∆∆ At the start and the end of the execution of the programme the tape head should point at the #. The execution of the TM on this input is shown below. #AaabAabAaaaa 7 ∆ #AaabAabAaaaa# 8 ∆ #AaabAabAaaaa#a 9 # #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 A #AaabAabAaaaa#a 9 b #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 A #AaabAabAaaaa#a 9 b (A,A,R) (A,A,L) (b,b,L) (a,a,L) (A,∆,R) (b,∆,R) (a,∆,R) Word State Tape head points at #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 a #AaabAabAaaaa#a 9 A #AaabAabAaaaa#a 9 # #AaabAabAaaaa#a 9 ∆ (to the left of the first #) #AaabAabAaaaa#a 10 # (the first #) #AaabAabAaaaa#a 1 A #AaabAabAaaaa#a 1 a #AAabAabAaaaa#a 3 a #AAabAabAaaaa#a 3 b #AAabAabAaaaa#a 4 A #AAabAabAaaaa#a 4 a #AAabAAbAaaaa#a 5 b #AAabAAbAaaaa#a 6 A #AAabAAbAaaaa#a 6 a #AAabAAbAAaaa#a 7 a #AAabAAbAAaaa#a 7 a #AAabAAbAAaaa#a 7 a #AAabAAbAAaaa#a 7 a #AAabAAbAAaaa#a 7 # #AAabAAbAAaaa#a 8 a #AAabAAbAAaaa#aa 8 ∆ #AAabAAbAAaaa#aa 9 a #AAabAAbAAaaa#aa 9 a #AAabAAbAAaaa#aa 9 # ... 9 moving left to find a ∆ #AAabAAbAAaaa#aa 10 # #AAabAAbAAaaa#aa 1 A #AAabAAbAAaaa#aa 1 A #AAAbAAbAAaaa#aa 1 a #AAAbAAbAAaaa#aa 3 b #AAAbAAbAAaaa#aa 4 A #AAAbAAbAAaaa#aa 4 A #AAAbAAbAAaaa#aa 4 b #AAAbAAbAAaaa#aa 2 A (the second A of the AA between the two b’s) ... 2 move back to the start of the string, the first # #AAAbAAbAAaaa#aa 2 # ∆AAAbAAbAAaaa#aa 11 A ∆∆AAbAAbAAaaa#aa 11 A ldots 11 blank out all of the input string ∆∆∆ ... ∆#aa 11 # ∆∆∆ ... ∆#aa 12 ∆ ∆∆∆ ... ∆#aa halt # What is finally left on the TM is ∆∆∆∆#aa∆∆∆ or simply #aa. Make sure that you understand how this TM works. 12 Note that this construction proves that a function which calculates the smallest of three given integers is computable. Click here or copy and paste the link below in your browser