n Consider the deterministic Turing machine M on alphabet (a, b, x,} with return value set V

n

Transcribed Image Text:

Consider the deterministic Turing machine M on alphabet (a, b, x,} with return value set V = {True, False}. The tape initially contains a non-empty block of a's and b's on an otherwise blank tape, with the head on the leftmost non-blank character. The transition function is given by the diagram below Read a,x 0 Read 2. Read a Read X Right Read b 1 7 4 Write X Read Write X 2 8 5 12 Return True Right (a) Is abaa in the language of M? (b) Is abba in the language of M? (c) What is the language of M? Read a,b,x Left Read b,x Right 3 9 6 Read b W Write X Read a 10 Read Read Questions. 1. (a) Give the complete run of machine M on the word aa, with the head positioned on the first a. That is, the starting confiiguration of the tape is: a a At each step, indicate the tape contents, the position of the head, the current state and the instruction (including the result if it is a Read). [2 marks] (b) Give the first seven steps of the run of machine M on the word ab, with the head positioned on the a. That is, the starting configuration of the tape is: a b At each step, indicate the tape contents, the position of the head, the current state and the instruction (including the result if it is a Read). [2 marks] 11 Return False [1 mark] [1 mark] [2 marks] Consider the deterministic Turing machine M on alphabet (a, b, x,} with return value set V = {True, False}. The tape initially contains a non-empty block of a's and b's on an otherwise blank tape, with the head on the leftmost non-blank character. The transition function is given by the diagram below Read a,x 0 Read 2. Read a Read X Right Read b 1 7 4 Write X Read Write X 2 8 5 12 Return True Right (a) Is abaa in the language of M? (b) Is abba in the language of M? (c) What is the language of M? Read a,b,x Left Read b,x Right 3 9 6 Read b W Write X Read a 10 Read Read Questions. 1. (a) Give the complete run of machine M on the word aa, with the head positioned on the first a. That is, the starting confiiguration of the tape is: a a At each step, indicate the tape contents, the position of the head, the current state and the instruction (including the result if it is a Read). [2 marks] (b) Give the first seven steps of the run of machine M on the word ab, with the head positioned on the a. That is, the starting configuration of the tape is: a b At each step, indicate the tape contents, the position of the head, the current state and the instruction (including the result if it is a Read). [2 marks] 11 Return False [1 mark] [1 mark] [2 marks]