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

**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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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?

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?

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?

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?

## Related Posts

Current Affairs