View more random threads:
- ISL201 Study of Quran and hadith Assignment 2 Solution...
- MTH202 Assignment No. 1 Spring 2012 Last Date 13 April
- MTH303 Mathematical Methods Assignment No 1 Fall Semester...
- CS302 Digital Logic Design Assignment 6 Deadline 22 July...
- CS201-Introduction to Programming Assignment No.2 Due Date...
- Assignment solution eng 301 due date 20 may 2015
- MTH001 - Elementary Mathematics first assignment fall 2010
- CS402 assignment-1 discussion and Solution fall 2014
- CS614 Assignment No. 04 Deadline 5 July 2010
- HRM624 Conflict Management Assignment No.1 Solution Fall...
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 }
CS701TheoryofComputationAssignmentNo.1MSCSFall2014.jpg
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.
Sponsored Links
[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.
There are currently 1 users browsing this thread. (0 members and 1 guests)