Exercise 1 (2 pts). Let M be the following Turing machine:

0 1 ?

q0 q1,0,R q2,1,R qr

q1 q1,0,R qr qa

q2 qr q2,1,R qa

Input alphabet: ? = {0, 1}

Tape alphabet: ? = {0, 1, ?}

Set of states: Q = {q0, q1, q2, qa, qr}

For each statement indicate whether it is true or false.

1. L(M) contains all binary strings beginning with a 0 (equivalently, M accepts every binary string beginning with a 0).

2. L(M) contains all binary strings ending with a 1 (equivalently, M accepts every binary string ending with a 1).