View more random threads:
- Assignment # 1 Computer Proficiency License (CS 001)...
- MKT501 Marketing Management Assignment Solution May 6, 2010
- All Past Assignments with Solutions Of MGT201 Financial...
- MGT402 Cost & Management Accounting Assignment No. 01...
- ISL201 Islamic Studies assignment No 01 Discussion and...
- CS504 Solution idea May 19,2010
- Bus Ticket Reservation System SRS CS619 Final Software...
- PSY403 Social Psychology Assignment No. 02 Due Date:...
- CS601 Data Communication Quiz No.2 Discussions and...
- isl201 assignment no 2 solution December fall 2010
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 }
Sponsored Links
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.
[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)