# VU HELP

Virtual University of Pakistan Study forum !

# CS701 Theory of Computation Assignment 1 Solution & Discussion Fall 2017 Due Date 9 Nov 2017

CS701 – Theory of Computation
Assignment No.1
Maximum marks: 50
Due Date: 9 November, 2017
Instructions
The purpose of this assignment is to give you hands on practice. It is expected that students will solve the assignment themselves. The 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 of the two assignments submitted will be awarded "F" grade in the course.
 No assignment after due date will be accepted through email
Question No. 1 (Part1 = 5 + Part2 = 15+ snapshots=5) =25 marks)
Part 1.) Suppose we will take a following Diophantine equation as an input, show that given equation has solution in positive integers.
33x + 15y = 14.
Part 2.) Design a Turing machine in the following three ways of descriptions that decide the language L = {03n+1 : n ≥ 0}, the language consisting of all strings of 0s in given exponential function.
1. The Formal description of Turing machine
2. Implementation level descriptions of the Turing machine
3. High level description of the Turing machine
Note: Turing Machine must be creating in JFLAP software. The tutorial link of JFLAP has already been sent via course announcement. The snapshots of Turing machine diagram and testing accepting/rejecting strings must be pasted in assignment.
Virtual University of Pakistan MS (CS), Fall 2017
Question No. 2 (15+10=25 marks)
Read the research paper entitled “Comments on some theories of fuzzy computation”
1) How can you differentiate and analysis between Turing Machine and Fuzzy
Turing Machine as discussed in the paper? Elaborate it critically in your own
words.
2) What functionalities have been expressed in extended Church thesis?
Elaborate it critically in your own words.
Note:
words and marks will be awarded on the basis of your answer and plagiarism report.
For any query about the assignment, contact at CS701@vu.edu.pk

Views: 1706

## CS701 Assignment No 1 Solution Idea

Describe and Design a Turing machine in following three ways description that decide the following language

1. Formal description of Turing machine
2. Implementation level descriptions of Turing machine
3. High level description of Turing machine

1. a) L = {13n+1 : n≥0}, the language consisting of all strings of 1s in given exponential function. Some example words of the language are as follows:

Solution

if we put n=0 then  in put string will be

1. 000

if we put n= 2 then the input string will be

2. 000000000

if we put n= 3 then the input string will be

3. 000000000000000000000000000

Formal Description of Turing Machine 0^3^n+1

1.

A Turing machine M1 that decides the language given in question above is defined by the following 7-Tuple.

M = (Q, Σ, Γ, δ, q­1, q­accept , qreject)

Q = (q1, ­q2, q3 … q7,  q­accept , qreject)

qis start state, q­accept is the accept state and  qreject  is the reject state.

Σ = {0} // Input alphabet

Γ = {0, x, []} // tape or work alphabet where Σ⊆Γ and     ∈ Γ.

δ : (Q × Γ) → (Q × Γ × {L, R}) // The transition function is described by the following state diagram.

1. Implementation level description of Turing Machine(0^3^n+1) 03n+1
• A Turing machine M1 that decides L = {03n+1: n≥0}
• M1 = on input string w
1. Sweep left to right across the tape, crossing of every other 0.
2. If in stage 1 the tape contained a single 0, accept.
3. If in stage 1 the tape contained more than single 0 and the number of 0’s are even, reject.
4. Return the head to the left-hand end of the tape.
5. Go to stage 1.
• Basically every sweep cuts the number of 0’s by three.
• At the end only one should remain and if so the original number of zeroes was a power of three.
1. High Level Description
2. Sweep from left to right across the tape, crossing of every other 0.
3. If there is a single 0 on the tape, accept.
4. If there are more than one 0’s and the number of 0’s is even, reject.
5. Return the head to the left end and repeat.

Note: You may verify.. up to me its correct version

Question No 2

CS701 Assignment Qustion No 1 Solution – by- Ghulam Shabbir
Sol.
Ax+By=C
Coefficient ko comapre karain with given equation 33x+15y=14

A=33
B=15
C=14
The greatest common factor (GCR) of A and B must be divisible by C
GCF of A and B is 3
33/3=11
And
15/3=5

But this 3 is not not divisible by 14
As
14/3===not divisible
hence the given statement has no integer solution

Why you have put Q value till Q7 why not till Q5? Can you explain this point?

Secondly in state diagram why not you have put zero instead of 1? as main language has 0^3^n+1 so untimate Q1 will be zero not 1? Please explain to clarify my concept.

plz Q2 part one plzzzzzzzzzz

Question No 2

CS701 Assignment Qustion No 1 Solution
Sol.
Ax+By=C
Coefficient ko comapre karain with given equation 33x+15y=14

A=33
B=15
C=14
The greatest common factor (GCR) of A and B must be divisible by C
GCF of A and B is 3
33/3=11
And
15/3=5

But this 3 is not not divisible by 14
As
14/3===not divisible
hence the given statement has no integer solution

check video also

## Videos

• ### Imtehan Hai Imtehan - Faseel-e-Jaan Se Aaagay

Added by +" Heaven Scent "+

• View All