EXAM Preparation Phase VI + Feedback PDF

Preview

Summary

Question 1 What are Accept(T), Loop(T), and Reject(T) of the following TM T?Start(a,b,L) (b,a,R)(b,a,L)(/,/,R)Feedback on Question 1 Accept(T) = Φ Loop(T) = {b} Reject(T) = All words starting with the letter a, and all words starting with the letter b that have length > 1.Question 2What are A...

Description

Question 1 What are Accept(T), Loop(T), and Reject(T) of the following TM T? (a,b,L)

(b,a,R)

Start

(/\,/\,R)

(b,a,L)

Feedback on Question 1 Accept(T) = Φ Loop(T) = {b} Reject(T) = All words starting with the letter a, and all words starting with the letter b that have length > 1. Question 2 What are Accept(T), Loop(T), and Reject(T) of the following TM T? (b,b,R)

(a,a,R) (a,a,R) Start

(b,b,L)

(/\,/\,R)

Halt

Feedback on Question 2 Accept(T) = All words of the form aab*, i.e. all words that start on a double a and are followed by some or no b’s. Loop(T) = All words that start with ‘ab’. Reject(T) = /\, a, all words starting with b, and all words starting with aa that have more than two a’s.

Question 3 (a) What are Accept(T), Loop(T), and Reject(T) of the following TM T?

(b,b,R)

(a,a,L) (a,a,R)(b,b,R)

(/\,/\,R) Start

(a,b,R)(b,b,R)

Halt

Feedback on Question 3 Accept (T) = All words from (a + b)* of odd length, where every odd position (i.e. positions 1, 3, 5, etc) is occupied by the letter b. Loop (T) = All words that have the letter a in an odd position anywhere from the third position onwards (i.e. position 3, 5, 7, etc) Reject (T) = All words starting with the letter a, and all words of even length without the letter a in any odd position. When the TM is in the HALT state, the tape contains an odd number of b’s (and no a’s). Question 4 What are Accept(T), Loop(T), and Reject(T) of the following TM T?

(a,a,R) (/\,/\,R) Start

(b,b,L)(a,a,R)

Halt

Feedback on Question 4 Accept (T) = All words of odd length consisting entirely of a’s. Loop (T) = All words from (a + b)* with at least one ‘b’, the first of which occurs in an even position (i.e. position 2, 4, 6, etc). Reject (T) = All words from (a + b)* with at least one ‘b’, the first of which occurs in an odd position (i.e. position 1, 3, 5, etc)....