CurrentGK -> Papers -> GAT(Graduate Aptitude Test In Engineering) -> THEORY OF COMPUTATION

If you find this context important and usefull. We request to all visitors to sheare this with your friends on social networking channels.

THEORY OF COMPUTATION

THEORY OF COMPUTATION

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





Tags


#

24 May, 2019, 06:43:41 AM