Home › Quizzes › Test 3 - Theory of Computation | Computer Science

Test 3 - Theory of Computation | Computer Science

GATE Previous year Topic Wise Questions and Answers | Theory of Computation

22 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

The smallest finite automaton, which accepts the language { x | length of x is divisible by 3} has

  1. 2 states
  2. 3 states
  3. 4 states
  4. 5 states
Question 2 Multiple Choice (Single Answer)

Which of the following statements true?

  1. If a language is context free it can be always be accepted by a deterministic push-down automaton.
  2. The union of two context free language is context free.
  3. The intersection of two context free language is context free
  4. The complement of a context free language is context free
Question 3 Multiple Choice (Single Answer)

Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

  1. N2
  2. 2N
  3. 2N
  4. N!
Question 4 Multiple Choice (Single Answer)

The C language is

  1. a context free language
  2. a context sensitive language
  3. a regular language
  4. parsable fully only by a turing machine
Question 5 Multiple Choice (Single Answer)

Consider a DFA over $\sum$= {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

  1. 8
  2. 14
  3. 15
  4. 48
Question 6 Multiple Choice (Single Answer)

Consider the following languages:

Which of these languages is/are regular?

  1. Only L1 and L2
  2. Only L2, L3 and L4
  3. Only L3 and L4
  4. Only L3
Question 7 Multiple Choice (Single Answer)

Which of the following is true?

  1. The complement of a recursive language is recursive.
  2. The complement of a recursively enumerable language is recursively enumerable.
  3. The complement of a recursive language is either recursive or recursively enumerable.
  4. The complement of a context-free language is context-free.
Question 8 Multiple Choice (Single Answer)

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

  1. context free
  2. regular
  3. deterministic context free
  4. recursive
Question 9 Multiple Choice (Single Answer)

The problems 3-SAT and 2-SAT are

  1. both in P
  2. both NP-complete
  3. NP-complete and in P respectively
  4. undecidable and NP-complete respectively
Question 10 Multiple Choice (Single Answer)

Consider the two statements:
S1 : {02n |n $\ge$ 1| } is a regular language
S2 : {0m1n 0m+n | m $\ge$ 1 and n $\ge$ 1| } is a regular language

Which of the following statements is incorrect?

  1. Only S1 is correct
  2. Only S2 is correct
  3. Both S1 and S2 are correct
  4. Neither S1 nor S2 is correct
Question 11 Multiple Choice (Single Answer)

pts all those binary strings in which the number of 1's and 0's are respectively

  1. divisible by 3 and 2
  2. odd and even
  3. even and odd
  4. divisible by 2 and 3
Question 12 Multiple Choice (Single Answer)

Consider the following problem x:

Given a Turing machine M over the input alphabet $\sum$, any state q of M. A word w $\in\sum^*$ does the computation of M on w visit the state q.

Which of the following statements about x is correct?

  1. x is decidable.
  2. x is undecidable but partially decidable.
  3. x is undecidable and not even partially decidable.
  4. x is not a decision problem.
Question 13 Multiple Choice (Single Answer)

The language {ambm+n | m,n $\le$ 1} is

  1. regular
  2. context-free but not regular
  3. context sensitive but not context free
  4. type-0 but not context sensitive
Question 14 Multiple Choice (Single Answer)

Consider the flowing grammar C
S $\rightarrow$ bS |aA| b
A$\rightarrow$ bA | aB
B bB |aS| a
Let Na (W) and Nb (W) denote the number of a's and b's in a string W respectively. The language L(G)
{a,b}+ generated by G is

  1. {W| Na (W) > 3Nb (W)}
  2. {W| Nb (W) > 3Na (W)}
  3. {W| Na (W) = 3k,k $\in$ {0,1,2,...}}
  4. {W| Nb (W) = 3k,k $\in$ {0,1,2,...}}
Question 15 Multiple Choice (Single Answer)

L1 is a recursively enumerable language over$\sum$. An algorithm A effectively enumerates its words as w1,w2,w3,.... Define another language L2 over $\sum \cup$ {#} as {wi # wj: wi, wj $\in$ L1, i < j}. Here # is a new symbol. Consider the following assertion.
S1:L1 is recursive implies L2 is recursive
S2:L2 is recursive implies L1 is recursive

Which of the following statements is true?

  1. Both S1 and S2 are true
  2. S1 is true but S2 is not necessarily true
  3. S2 is true but S1 ins necessarily true
  4. Neither is necessarily true
Question 16 Multiple Choice (Single Answer)

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is true?

  1. $\bar L_1$ is recursive and $\bar L_2$ is recursively enumerable
  2. $\bar L_1$ is recursive and $\bar L_2$ is not recursively enumerable
  3. $\bar L_1$ and L2 are recursively enumerable
  4. $\bar L_1$ is recursively enumerable and $\bar L_2$ is recursive
Question 17 Multiple Choice (Single Answer)

Consider the machine M

The language recognized by M is

  1. {W $\in$ {a,b}*/ every a in w is followed by exactly two b's}
  2. {W $\in$ {a,b}*/ every a in w is followed by at least two b's}
  3. {W $\in$ {a,b}*/ w contains the substring 'abb'
  4. {W $\in$ {a,b}*/ w does not contain 'aa' as a substring}
Question 18 Multiple Choice (Single Answer)

Let Nf and Np denote the classes of languages accepted by nondeterministic finite automata and non-deterministic push-down automata, respectively. let Df and DP denote the classes of languages accepted by deterministic finite automata and deterministic push down automata, respectively. Which one of the following is true?

  1. Df $\subset$ Nf and DP $\subset$ NP
  2. Df $\subset$ Nf and DP = NP
  3. Df = Nf and DP = NP
  4. Df = Nf and DP $\subset$ NP
Question 19 Multiple Choice (Single Answer)

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which of the following statements is true?

  1. P3 is decidable if P1 is reducible to P3.
  2. P3 is undecidable if P3 is reducible to P2.
  3. P3 is undecidable if P2 is reducible to P3.
  4. P3 is decidable if P3 is reducible to P2’s complement.
Question 20 Multiple Choice (Single Answer)

Consider the languages
L1 {an bn cm | n, m > 0} and L2 {an bm cm | n, m > 0}

  1. L1 $\cap$ L2 is a context-free language
  2. L1 $\cup$ L2 is a context-free language
  3. L1 and L2 are context-free language
  4. L1 $\cap$ L2 is a context sensitive language
Question 21 Multiple Choice (Single Answer)

Consider the following languages:

L1 = {WWR | W$\in$ {0, 1}}
L2 = {W # WR |W$\in$ {0, 1}} where # is a special symbol
L3 = {WW | W$\in$ {0, 1}*}

Which of the following statements is true?

  1. L1 is a deterministic CFL.
  2. L2 is a deterministic CFL.
  3. L3 is a CFL, but not a deterministic CFL.
  4. L3 is a deterministic CFL.
Question 22 Multiple Choice (Single Answer)

Consider the following two problems on undirected graphs
$\alpha$: Given G(V,E), does G have an independent set of size |V |− 4?
$\beta$: Given G(V,E), does G have an independent set of size 5?

Which one of the following is true?

  1. $\alpha$ is in the P and $\beta$ is NP-complete
  2. $\alpha$ is NP-complete and $\beta$ is P
  3. Both $\alpha$ and $\beta$ are NP-complete
  4. Both $\alpha$ and $\beta$ are in P
← Back to Quizzes