Theory of Computation

CS 3810, Spring 2020

Name:

Quiz 08.1

1. (T1) For each of the given strings, give the halting configuration of the Turing machine shown below.

1. ab#aa

2. bb#

3. aba#aa

2. (T2) Give the formal definition of a Turing machine which recognizes the language given below.

L1 = {xi#xi#xi, i ≥ 0}

3. (T3) Define the difference between recognizable and decidable with respect to languages and Turing machines.