cs701 midterm solved papers by moaaz

cs701 midterm solved papers

cs701 midterm solved papers pdf

cs701 midterm solved papers

cs701 mid term past papers by moaaz

cs701 midterm past papers mega file

For Important Helping Material related to this subject cs701

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

CS701 mid term paper shared by student

on December 18, 2016 at 9:56am

Paper pattern of cs701

Total questions= 4

2 question = 5 marks

2x5= 10

CS701 mid term paper shared by student

Reply by + !AℓωιиαMαhαм(MS) on December 18, 2016 at 10:05am

My paper of cs701

5 marks

can we write blank symbol to input tape prove ur reasoning under formal description of TM

5 marks

all positive real number has a one-to-one correspondence with real numbers

10 marks

show that some true statements in TH(N,+,X) are not proveable.

10 marks

All decidable languages are closed under complementation operation

CS701 mid term paper shared by student

on December 18, 2016 at 10:42am

Cs701 today papers

1.Atm is not mapping reducable to etm

2.is all problems are turing decidable.are you agree or not.in both cases justify with examples

3.f(n) and g(n) ke two tables the btana tha ke kiss ma one to one correspondence ha.

4.pcp problems are undecidable

........

CS701 Mine Paper today

Time duration 1 Hour

Just 4 subjective questions,

2 questions (5 marks)

2 question (10 marks)

1. Every problem compute in Turing machine, if yes describe with reason if no then also describe with no justify your answer (5 Marks)

2. Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe the functions f: X - Y and g: X Y Correspondence in the following tables.(5 Marks)

3. Can every set provable in function Turing-recognizable (10 marks)

4. every statement decidable in Turing etc is trhn ka tha. (10 Marks)

…………

CS701 Paper

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.

…………………..

my today paper

cs701

total 4 questions.

1) Let LALL = {|M is a TM with input alphabet Σ and L(M)=Σ*} prove that LALL is not Turing recognizable

2) Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe the functions f: X - Y and g: X Y in the following tables. Is g a correspondence?

3) Let B be the set of all infinite sequences over {0,1}. Show that B is uncountable, using a proof by diagonalization?

CS701 mid term paper shared by student

on December 18, 2016 at 10:43am

CS 701

Show that if A is Turing-recognizable and A <=m A, then A is decidable.

2. for all x, y [ R1 (x, y) V R1 (y, x) ]. Let model M1 = (N, <=)

be the model whose universe is the natural numbers and which assigns the "less

than or equal" relation to the symbol R1.

3. Show that single-tape TMs that cannot write on the portion of the tape containing

the input string recognize only regular languages.

4. Explain why the following is not a description of a legitimate Turing machine.

Mbad = "The input is a polynomial p over variables x1, . . ., Xk.

1. Try all possible settings of x1 , ... , Xk to integer values.

2. Evaluate p on all of these settings.

3. If any of these settings evaluates to 0, accept; otherwise, reject."

-----------------------

CS701 Mine Paper today

Time duration 1 Hour

Just 4 subjective questions,

2 questions (5 marks)

2 question (10 marks)

1. Every problem compute in Turing machine, if yes describe with reason if no then also describe with no justify your answer (5 Marks)

2. Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe the functions f: X - Y and g: X Y Correspondence in the following tables.(5 Marks)

3. Can every set provable in function Turing-recognizable (10 marks)

4. every statement decidable in Turing etc

CS701 mid term paper shared by student

on December 18, 2016 at 8:34pm

    My today CS 701 paper
    1: PCP maching peoblem..pcp was not maching..cause of not maching was asked
    2:Prove by recursion That MIan TM is not Turing Recognizable
    3:Is A language A is Turing Recognizable is it necessary that it is Turing Decidable also .prove?
    4: If two languages are Decidable show that their union is closed under union.

CS701 mid term paper shared by student

on December 21, 2015 at 1:17pm

TodayCS701 Paper

Relative prime number question 64 and some other number

Decidable question

there were only 4 question

CS701 mid term paper shared by student

Reply by Shahid Safoori on December 22, 2015 at 2:44pm

AOA. my questions for cs701 20-12-2015 were these.

1. show that 234 and 399 are relatively prime or not.

2. show that Atm is not mapping reducible to Etm/

3. show that some true statements in TH(N,+,X) are not proveable.

4. in PCP find dominos of 1/0 101/1,1/001.

CS701 mid term paper shared by student

Reply by Naveed Awan on December 26, 2015 at 4:21am

        Two integers are relatively prime (or coprime) if there is no integer greater than one that divides them both (that is, their greatest common divisor is one). For example, 12 and 13 are relatively prime, but 12 and14 are not.
        12 and 13 are only divided by 1
        Here GCD of 12 and 13 is 1.

CS701 mid term paper shared by student

Reply by tam jee on December 26, 2015 at 6:13pm

1. show that 234 and 399 are relatively prime or not. (4)

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

4. in PCP find dominos of 1/0 101/1,1/001.

Q23. Is PCP decidable over unary alphabet?

Q1. { [1/0],[101/0],[0/001]} in PCP problem. Find is there any match? If yes

Prove it. (05)

q no 3: prove by contradiction that ATM IS NOT mapping reducible to ETM. 10 MARKS

q no 4: show that A≤TB and B≤TC than A≤TC .10

Q12. Show that A<= T B and B<= T C then A <= T C. (Exercise 6.3)

CS701 mid term paper shared by student

my paper of cs701 dated 31-12-2015

pscp ka question prove karna tha k decidable ha

aik question relatively prime no ka tha 234 and 399

aik question

let x be the set[1,2,3,4,5] and y be the set[6,7,8,9,10] we describe the function f:x--->y and g:x-->y in the following table

n fn n gn

1 6 1 10

2 7 2 9

3 6 3 8

4 7 4 7

5 6 5 6

cs701 midterm past papers

cs701 midterm solved papers by moaaz