** For Past Papers Just Follow The Download Buttons, We have a large data for revision of Virtual University courses. You can also join following ****groups**** for study discussion . ****The best is We Recommend you to study your handouts and lectures, then revise the past papers for your good grades.**

#### CS701 mid term paper shared by student

on December 12, 2017 at 1:33pm

Q.1. Can Turing Machine contain just single state?

Examine Formal Definition of a Truing Machine. Give Reasons.

Q.2. Collection of Turing Recognizable Languages is closed under the intersection operation.

Q.3. Prove that all the odd numbers have one to one correspondence.

Q.4. Universe is N (kuch iss tarah ka tha)

#### CS701 mid term paper shared by student

Reply by Waqas Afzal on December 14, 2017 at 10:11pm

1. Show that the collection of Turning-recognizable language is closed under start , complement , intersection operation.

2. Consider the sentence y x [R1 (x, x, y)]. Let’s assign PLUS to R1 where PLUS (a, b, c) is TRUE whenever a + b = c. If universe is N(Natural Numbers), is this sentence TRUE? Justify your answer.

3. Show that set of all odd integers has one-to-one correspondence with set of even integer.

4. Let B the set of all infinite sequence over {0,1} show B is uncountable using a proof by diagnolization.

5. suppose there is a language L and we know that L is Turing recognizable. We can say L is also Turing Recognisable. Why or why not?

1. Show that the collection of Turning-recognizable language is closed under start , complement , intersection operation.

2. Consider the sentence y x [R1 (x, x, y)]. Let’s assign PLUS to R1 where PLUS (a, b, c) is TRUE whenever a + b = c. If universe is N(Natural Numbers), is this sentence TRUE? Justify your answer.

3. Show that set of all odd integers has one-to-one correspondence with set of even integer.

4. Let B the set of all infinite sequence over {0,1} show B is uncountable using a proof by diagnolization.

5. suppose there is a language L and we know that L is Turing recognizable. We can say L is also Turing Recognisable. Why or why not?

#### CS701 mid term paper shared by student

on June 24, 2018 at 10:18pm

Cs701 paper 2 30

Q1 find pop match possible or not prove

Q2 all languages are closed under concatenation

Q3 Th(N,+,*) is Turing recognizable

Q4 L (0^n 1^n: n>1) m tape TM wala

#### CS701 mid term paper shared by student

CS701 24-06-2018: 5:30PM

Q.1:Show that the collection of decidable language is closed under operation of cancatenation? (10)

Q.2:Let LALL = {<M>|M is a TM with input alphabet Σ and L(M)=Σ*} prove that LALL is not Turing recognizable? (10)

Q.3: PCP (5)

Q.4: Informal & Highl level description of given string for Turing Machine? (5)

#### CS701 mid term paper shared by student

Mid Term Paper CS701 held on 29-05-2016

2 Qus 5 marks

2 Qus 10 marks

Let LALL = {<M>|M is a TM with input alphabet Σ and L(M)=Σ*} prove

that LALL is not Turing recognizable.

If A<=B & B is a regular language show that A is a regular language

[001/01].[10/00].[01/011] in PCP problem. Find is there any match? If yes

prove it.

Let B the set of all infinitely sequence over{0,1}, show that B is uncountable using a proof by diagonalization.

An Other Paper same day

[001/01].[10/00].[01/011] in PCP problem. Find is there any match? If yes

prove it.

In the silly Post Correspondence Problem, SPCP, in each pair the top

string has the same length as the bottom string. Show that the SPCP is

decidable.

Odd integer has 1-1 correspondence to even integer

ᗄy,ᣮx[Rz(x,x,y)] let assign plus to R2 where (a,b,c)is true where a+b=c if uviverse is Real number.

#### CS701 mid term paper shared by student

on December 18, 2016 at 4:36pm

My Questions:

2 question 5 marks (each)

2 Question 10 marks (each)

Total 30 Marks

(1) Can Turing Machines can perform 2 successive steps with moving it’s head? If yes explain. Also provide formal definition of Turing Machine. (5)

(2) Check that X and Y are one-to-one or not. (5)

(3) MORE = <A, B> are Turing machines Language of A is greater than B, is MORE <A, B> also decidable? explain for each case. (10)

(4) show that some true statements in TH(N,+,X) are not provable (10)

#### CS701 mid term paper shared by student

cs701 fall 2016 mid term paper

17 December cs701 paper

CS701

Q#1suppose there is a language L we know that L is Turing recognizable. Can we say that L is also Turing decidable? Why and why not.

Q#2 PCP matching.

Q#3 Let Alldfa={<A>/A is a DFA and L(A)=∑*}Show that AllDFA is decidable.

Q#4 Let LALL ={<M>/M is a TM with i/p ∑ and L(M =∑*} Prove that LALL is not a co Turing recognizable.

#### CS701 mid term paper shared by student

cs701 fall 2016 mid term paper

17 December cs701 paper

CS701

Q#1suppose there is a language L we know that L is Turing recognizable. Can we say that L is also Turing decidable? Why and why not.

Q#2 PCP matching.

Q#3 Let Alldfa={<A>/A is a DFA and L(A)=∑*}Show that AllDFA is decidable.

Q#4 Let LALL ={<M>/M is a TM with i/p ∑ and L(M =∑*} Prove that LALL is not a co Turing recognizable.

## Responses