CS701 Theory of Computation Assignment No. 1 Fall 2014 7th December 2014

[Vuhelper]

CS701 Theory of Computation Assignment No. 1 Fall 2014 last Date 7th December 2014

The purpose of assignments is to give you hands on practice. It is expected that students will solve the assignments themselves. Following rules will apply during the evaluation of assignment.


Cheating from any source will result in zero marks in the assignment.
Any student found cheating in any two of the assignments submitted will be awarded "F" grade in the course.
No assignment after due date will be accepted.
Question 1: Total Points (10)

Following is the Turing Machine M1 for the language A = { | n ≥ 0 }

[ATTACH=CONFIG]24262[/ATTACH]


For each of the following input strings, provide the sequence of configurations that M1 enters.

(a) 0000

(b)000000



Question 2: Total Points (10)

Suppose for a programming language, a valid variable name has the following properties:

Only Alphabets (a, b, c, ... , z, A, B, C, ... , Z) and Numerals (0, 1, 2, ... , 9) are allowed in variable name.
Variable name can only start with Alphabets.
Maximum length of variable name is 8.
The keywords defined for the language cannot be a variable name.


Let L be the set of all such valid variable names.

(a) Prove that L is finite.

(b) How many strings does L contain (excluding the keywords condition stated above)?



Question 3: Total Points (15)

For the language A = { 0i10j | 0 ≤ i < j }, provide implementation-level and Formal description of Turing Machine.


[Note: Formal description also includes transition diagram.]


Question 4: Total Points (15)

Read the research paper titled “Turing Machines with Two Letters and Two States”, and explain how it is possible to decide halting problem for this two letters and two states Turing machine.