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

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 6

THEORY OF COMPUTATION 6

THEORY OF COMPUTATION 6

Q101. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs that generate infinte languages}

And L1={<G,G’,1>|G,G’ are the encodings of cfgs that either one or both do not generate infinite sets}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable


Q102. Let L0={<G,G’,0>|G,G’ are the encodings of csgs that generate the same set}

And L1={<G,G’,1>|G,G’ are the encodings of csgs that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive
d) Neither L nor L’ is recursively enumerable

Q103. Let L0={<G,G’,0>|G,G’ are the encodings of unrestricted grammars that generate the same set}

And L1={<G,G’,1>|G,G’ are the encodings of unrestricted grammars that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q104. Let L0={<G,G’,0>|G,G’ are the encodings of linear bounded automata that generate the same set}

And L1={<G,G’,1>|G,G’ are the encodings of linear bounded automata that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q105. Let L0={<G,G’,0>|G,G’ are the encodings of unrestricted grammars such that they generate L and LR respectively with L=LR}

And L1={<G,G’,1>|G,G’ are the encodings of unrestricted grammars that generate languages L and LR with L not the same as LR respectively}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q106. Let L0={<G,G’,0>|G,G’ are the encodings of C programs that produce the same output for all inputs}

And L1={<G,G’,1>|G,G’ are the encodings of C programs that do not produce the same output for all inputs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q107. Let L0={<G,G’,0>|G,G’ are the encodings of C programs that produce some output for all inputs}

And L1={<G,G’,1>|G,G’ are the encodings of C programs that do not produce some output for all inputs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q108. Let L0={<G,G’,0>|G,G’ are the encodings of C programs that loop on some input}

And L1={<G,G’,1>|G,G’ are the encodings of C programs that do not loop on some input}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q109. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs where the intersection of the langugaes generated is a cfl}

And L1={<G,G’,1>|G,G’ are the encodings of cfgs where the intersection of the languages generated is not a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q110. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs that generate regular sets}

And L1={<G,G’,1>|G,G’ are the encodings of cfs that both or either does not generate a regular set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q111. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs such that L(G’) is contained in L(G)}

And L1={<G,G’,1>|G,G’ are the encodings of cfgs sucht that L(G’) is not contained in L(G)}. Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q112. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs which generate languages whose complement is also a cfl}

And L1={<G,G’,1>|G,G’ are the encodings of C programs that generate languages whose complement is not both a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q113. Let L0={<G,G’,0>|G,G’ are the encodings of ambiguous cfgs}

And L1={<G,G’,1>|G,G’ are the encodings of unambiguous cfgs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q114. Let L0={<G,G’,0>|G,G’ are the encodings of inherently ambiguous cflss}

And L1={<G,G’,1>|G,G’ are the encodings of cfls that are not inherently ambiguous}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement


a)L is recursively enumerable but not recursive and L’ is recursive

b) L is recursive and L’ is recursively enumerable

c) L is not recursively enumerable and L’ is recursive

d) Neither L nor L’ is recursively enumerable

Q115. Choose the false statement

a) PCP over a one symbol alphabet is decidable

b) It is undecidable if a csl is a cfl

c) It is undecidable if a turing machine accepts at least 10 inputs

d) It is undecidable if two regular grammars generate the same set


Q116. Define languages L0 and L1 as follows:

L0={<M,M1,0>|M is equivalent to M1}

L1={<M,M1,1>| M is not equivalent to M1}

Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a nondeterministic linear bounded automaton, and third component I is a bit.

Let L=L0 U L1. Which of the following is true?


(a) L is recursively enumerable but L’ is not

(b) L’ is recursively enumerable but L is not

(c) Both L and L’ are recursive

(d) Neither L nor L’ is recursively enumerable

Q117. Define languages L0 and L1 as follows:

L0={<M,M1,0>|M is equivalent to M1}

L1={<M,M1,1>| M is not equivalent to M1}

Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a 100 tape nondeterministic turing machine that halts on all inputs, and third component I is a bit.

Let L=L0 U L1. Which of the following is true?


(a) L is recursively enumerable but L’ is not

(b) L’ is recursively enumerable but L is not

(c) Both L and L’ are recursive

(d) Neither L nor L’ is recursively enumerable



Q118. Define languages L0 and L1 as follows:

L0={<M,w,0>|M in the course of its computation visits state w}

L1={<M,w,1>| M does not halt visit state w}

Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a state and third component I is a bit.

Let L=L0 U L1. Which of the following is true?


(a) L is recursively enumerable but L’ is not

(b) L’ is recursively enumerable but L is not

(c) Both L and L’ are recursive

(d)Neither L nor L’ is recursively enumerable

Q119. Define languages L0 and L1 as follows:

L0={<M,w,0>|M prints symbol w}

L1={<M,w,1>| M never prints symbol w}

Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a symbol and third component I is a bit.

Let L=L0 U L1. Which of the following is true?


(a) L is recursively enumerable but L’ is not

(b) L’ is recursively enumerable but L is not

(c) Both L and L’ are recursive

(d)Neither L nor L’ is recursively enumerable





Tags


#

23 Aug, 2019, 02:30:52 AM