Tuesday, November 18, 2008

GATEQUESTIONS

THEORY OF COMPUTATION





Q1. Choose the correct statement.

The set of all strings over an alphabet S ={0,1} with the concatenation operator for strings


a) does not form a group

b) forms a noncommutative group

c) does not have a right identity

d) forms a group if the empty string is removed from S *


Q2. Consider the set of all strings S * over an alphabet S ={a,b} with the concatenation operator for strings, and
a) the set does forms semigroup

b) the set does not form a group

c) the set has a left and right identity

d) the set forms a monoid


Q3. Consider the set of all strings S * over the alphabet S ={a,b,c,d,e} with the concatenation operator for strings.
a. the set has a right identity and forms a semigroup

b. the set has a left identity and forms a monoid

c. the set does not form a commutative group but has an identity

d. the set does not form a semigroup with identity



Q4. Nobody knows yet if P = NP. Consider the language L defined as follows:

L=()+1)* if P = NP

And

L=j otherwise

Which of the following statements is true?


a) L is recursive

b) L is recursively enumerable but not recursive

c) L is not recursively enumerable

d) Whether L is recursive or not will be known after we find out if P = NP



Q5. Consider the language defined as follows

L= {a^n b^n|n>=1} if P=NP

And

L={ww|w in (a+b)+} otherwise

Which of the following statements is true?


a) L is recursive but not context sensitive

b) L is context sensitive but not context free

c) L is context sensitive

d) What L is will be known after we resolve the P=NP question


Q6. Consider the language defined as follows

L=(0+1)* if the CSLs are closed under complement

And

L=(0*1)*0* if P=NP

And

L=(10*)1* if P is not the same as NP

Which of the following statements is true?


a) L is always a regular set

b) L does not exist

c) L is recursive but not a regular set

d) What L is will be known after the two open problems P = NP and the closure of CSLs under complement are resolved


Q7. Consider the language defined as follows

L=(0+1)* if man goes to Mars by 2020AD

And

L=0* if man never goes to the Mars

Which of the following is true?


a. L is context free language but not recursive

b. L is recursive

c. Whether L is recursive or not will be known in 2020AD

d. L is a r.e. set that is not regular

Q8. Given an arbitrary context free grammar G, we define L as below.

L=(0+1)* if G is ambiguous

And

L=j if G is not ambiguous



a. L is a context-free language

b. L is recursive but not r.e.

c. What L is depends on whether we can determine if G is ambiguous or not

d. What L is is undecidable


Q9. Given an arbitrary turing machine M and a string w we define L as below.

L=(0*1)*0* if M halts on w

And

L=(0*1*)* if M does not halt on w



a. The type of L is undecidable because of the halting problem

b. L is a context-sensitive language

c. L is recursively enumerable and not context-free

d. L is context sensitive and not regular


Q10. Consider the language L defined below

L=(0+1)* if P=NP

And

L=(a^nb^n|n>=1} otherwise



a. Whether L is a regular set that is not context-free will be known after we resolve the P=NP question.

b. Whether L is context-free but not regular will be known after we resolve the P=NP question

c. L is context-sensitive

d. L is not recursive


Q11. It is undecidable if two cfls L1 and L2 are equivalent. Consider two cfls L1 and L2 and a language defined as follows

L={a^nb^nc^n|n>=234} if L1=L2

And

L={a^nb^nc^nd^n|n>=678} otherwise



a. L is recursive

b. L is context-free

c. We can never say anything about L as it is undecidable

d. L is regular

Q12. At present it is not known if NP is closed under complementation.

Consider L defined as below

L={w wR w| w in (0+1+2)* and wR is the reverse of w} if NP is closed under complement

And

L = {a^nb^nc^nd^ne^n|n>=34567} otherwise



a) L is recursive

b) L is context-free and not context-sensitive

c) L is recursively enumerable but not recursive

d) We will be able to say something about L only after we resolve the NP complementation issue

Q14. Nobody knows if P=NP at present. Consider a language L as defined below

L=(0+1)* if satisfiability is in P

L=(0*1)0* if satisfiability is not in P

L=(1*0)1* if 3-sat is in P

L=(0*1*)* if 3-sat is not in P

L=(0*1*0*1*)* if 0/1 knapsack problem is in P

L=(1*0*1*0*)* if 0/1 knapsack problem is not in P

L=(0*(00)*(1*11*)*) * if max-clique problem is in P

L=(0*(00)*(1*11*)*) * if node-cover problem is not in P

L=(0*1*)****(010)* if edge-cover problem is not in P

L=(0* + 1* + (00)* + (11)*)*(0100101010)* if the chromatic problem is not in P

What can we say about the string 0000111100001111=x


a) x is always in L

b) whether x is in L or not will be known after we resolve P=NP

c) the definition of L is contradictory

d) x can never be in L

Q15. An arbitrary turing machine M will be given to you and we define a language L as follows

L=(0+00)* if M accepts at least one string

L=(0+00+000)* if M accepts at least two strings

L=(0+00+000+0000)* if M accepts at least three strings

---------

---------

L=(0+00+000+---+0^n) *if M accepts at least n-1 strings

Choose the correct statement.


a) We cannot say anything about L as the question of whether a turing machine accepts a string is undecidable

b) L is context-sensitive but not regular

c) L is context-free but not regular

d) L is not a finite set

Q16. We are given two context-free languages L1 and L2 and L defined as below

a) L=(0+1)* if L1=L2

b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2

c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1

d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable



a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L

b) L is recursively enumerable

c) L is recursive but not context-sensitive

d) L is context-sensitive but not context-free

e) L is context-free but not regular

Q17. It is undecidable if an arbitrary cfl is inherently ambiguous. We are given a cfg G and the language L is defined as below

L= (0+1)*01(0+1)* U 1*0* if L(G) is inherently ambiguous

L=(0+1)*10(0+1)* U 0*1* if L(G) is not inherently ambiguous

Choose the incorrect statement


a) L is regular

b) L iscontext-free

c) L is context-sensitive

d) The above choices can be resolved only if we know if L(G) is inherently ambiguous or not

Q18. We are given an arbitrary turing machine M and define the language L as below

L=(0*+1*)* if M halts on blank tape

L=(0+1*)* if M ever prints a 1

L=(0*+1)* if M ever enters a designated state q

L=((0+1+00+11+000+111)+)* if M accepts an infinite set

L=0*(10*)* if M accepts a finite set

L=1*(01*)* if M accepts exactly 45 strings

Choose the correct statement with reference to the string x=00000111111000000111111


a) x is in L

b) x is not in L

c) we can never decide if x is in L as all the problems of the turing machine are undecidable

d) whether x is in L depends on the particular turing machine M

Q19. We are given a language L defined as follows

L=(0+1)* if the Hamiltonian circuit problem is in P

L=(0*1*+0)* if the Traveling salesman problem is not in P

L=(0*1*1)*0* if the bin packing problem is in P



a) the definition of L is contradictory

b) What L is will be known after we resolve the P=NP question

c) L if a finite set

d) The string 01010101001010110010101 is in L

Q20. The intersection of two cfls can simulate a turing machine computation. We are given two cfls L1 and L2 and define the language L as below

a) L=(00)* if the intersection of L1 and L2 is empty

b) L=((0(00)*)(0(00)*))* if L1 is regular

c) L=(00+0000+000000)* if L2 is not regular

d) L=(00)*+(0000)* if the complement of L1 is a cfl



a) L is a finite set

b) L is a regular set

c) L is undecidable

d) L is recursive but not context-free

Result Page:- 1-20 | 21-40 | 41-60 | 61-80 | 81-100 | 101-120 |

No comments:

adbrite

Your Ad Here