Mid-1 (10 points + 2 bonus points) Exercise 1 (4 pts). Let M be the following Turing machine:

0

1

q0

q1,0,R

q1,1,R

q1

q1,0,R

q1,1,R

q2

qa

qr

Input alphabet: Tape alphabet: Set of states:

= {0, 1}

= {0, 1, }

Q = {q0, q1, q2, qa, qr}

For each statement indicate whether it is true or false.

1. M accepts infinitely many strings, i.e. L(M) is infinite. 2. M rejects infinitely many strings.

3. M loops on infinitely many strings.

4. M is a recognizer for some language.

ise 1 (4 pts). Let M be the following Turing machine: put alphabet: = {0,1} ape alphabet :=(0,1, ,et of states: Q=140, q.Q2,Ja, a. Ir ach statement indicate whether it is true or false. M accepts infinitely many strings, ie. L(M) is infinite. . M rejects infinitely many strings. . M loops on infinitely many strings. 4. M is a recognizer for sone laneuaoes