Home › Quizzes › Test 2 - Theory of Computation | Computer Science(CS)

Test 2 - Theory of Computation | Computer Science(CS)

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

21 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the regular expression

  1. b* ab* ab* ab*
  2. (a + b)*
  3. ba (a + b)
  4. b* ab* ab*
Question 2 Multiple Choice (Single Answer)

The language {0i 21i | i $\ge$0} over the alphabet {0, 1, 2} is:

  1. not recursive
  2. is recursive and is a deterministic CFL.
  3. is a regular language.
  4. is not a deterministic CFL but a CFL.
Question 3 Multiple Choice (Single Answer)

A minimum state deterministic finite automaton accepting the language L = {w | w $\in${0, 1}*, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

  1. 15 states
  2. 11 states
  3. 10 states
  4. 9 states
Question 4 Multiple Choice (Single Answer)

Which of the following statements is false?

  1. Every NFA can be converted to an equivalent DFA
  2. Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
  3. Every regular language is also a context-free language
  4. Every subset of a recursively enumerable set is recursive
Question 5 Multiple Choice (Single Answer)

Which of the following is true for the language $\left\{ a^p \text{ | p is a prime} \right\} $?

  1. It is not accepted by a Turing Machine
  2. It is regular but not context-free
  3. It is context-free but not regular
  4. It is neither regular nor context-free, but accepted by a Turing machine
Question 6 Multiple Choice (Single Answer)

Consider the following Finite State Automaton:

The minimum state automaton equivalent to the above FSA has the following number of states

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

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

  1. I and II
  2. I and IV
  3. II and III
  4. II and IV
Question 8 Multiple Choice (Single Answer)

If L and $\bar L$ are recursively enumerable then L is

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

S $\rightarrow$ aSa | bSb | a | b; The language generated by the above grammar over the alphabet {a, b} is the set of

  1. All palindromes.
  2. All odd length palindromes.
  3. Strings that begin and end with the same symbol
  4. All even length palindromes.
Question 10 Multiple Choice (Single Answer)

Which one of the following languages over the alphabet {0, 1} is described by the regular expression:
(0 + 1)*0(0 + 1)0(0 + 1)?

  1. The set of all strings containing the substring 00.
  2. The set of all strings containing at most two 0's.
  3. The set of all strings containing at least two 0's.
  4. The set of all strings that begin and end with either 0 or 1.
Question 11 Multiple Choice (Single Answer)

Which of the following are regular sets?

I. $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$
II. $\left\{a^nb^m \mid n =2m \right\}$
III. $\left\{a^nb^m \mid n \neq m \right\}$
IV. $ \left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\} $

  1. I and IV only
  2. I and III only
  3. I only
  4. IV only
Question 12 Multiple Choice (Single Answer)

Which of the following statements are true?

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
II. All $\epsilon$ productions can be removed from any context-free grammar by suitable transformations
III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

  1. I, II, III and IV
  2. II, III and IV only
  3. I, III and IV only
  4. I, II and IV only
Question 13 Multiple Choice (Single Answer)

Which of the following languages is regular?

  1. $\left\\{ww^R \mid w \in \{0, 1\}^+\right\\}$
  2. $\left\\{ww^Rx \mid x,w \in \{0, 1\}^+\right\\}$
  3. $\left\\{wxw^R \mid x, w \in \{0, 1\}^+\right\\}$
  4. $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$
Question 14 Multiple Choice (Single Answer)

Which one of the following is FALSE?

  1. There is unique minimal DFA for every regular language
  2. Every NFA can be converted to an equivalent PDA.
  3. Complement of every context-free language is recursive.
  4. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Question 15 Multiple Choice (Single Answer)

The above DFA accepts the set of all strings over {0, 1} that

  1. begin either with 0 or 1
  2. end with 0
  3. end with 00
  4. contain the substring 00.
Question 16 Multiple Choice (Single Answer)

Match the following NFAs with the regular expressions they correspond to

NFA Diagram GATE 2008

  1. $ \epsilon + 0 \left(01^*1+00\right)^*01^*$
  2. $ \epsilon + 0 \left(10^*1+00\right)^*0$
  3. $ \epsilon + 0 \left(10^*1+10\right)^*1$
  4. $ \epsilon + 0 \left(10^*1+10\right)^*10^*$
  1. P −2, Q −1, R −3, S −4
  2. P −1, Q −3, R − 2, S − 4
  3. P − 1, Q − 2, R − 3, S − 4
  4. P − 3, Q − 2, R − 1, S − 4
Question 17 Multiple Choice (Single Answer)

Match all items in Group 1 with correct options from those given in Group 2.

Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
  1. P-4. Q-1, R-2, S-3
  2. P-3, Q-1, R-4, S-2
  3. P-3, Q-4, R-1, S-2
  4. P-2, Q-1, R-4, S-3
Question 18 Multiple Choice (Single Answer)

Let L = L1 $\cap$ L2, where L1 and L2 are languages as defined below:
L1 = $(a^m b^m\ ca^n b^m | m,n \ge 0)$
L2 = $(a^i b^j\ c^k | i,j \ge 0)$
Then L is

  1. Not recursive
  2. Regular
  3. Context free but not regular
  4. Recursively enumerable but not context free.
Question 19 Multiple Choice (Single Answer)

Match the following:
E. Checking that identifiers are declared before their use P. $L : = : \left\{a^nb^mc^nd^m \mid n: \geq1, m \geq 1\right\}$
F. Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function Q. $X: \rightarrow XbX \mid XcX \mid dXf \mid g$
G. Arithmetic expressions with matched pairs of parentheses R. $L: = \left\{wcw\mid w : \in \left(a\mid b\right)^* \right\}$
H. Palindromes S. $X : \rightarrow : bXb \mid :cXc : \mid \epsilon $
  1. E −P, F −R, G −Q, H −S
  2. E −R, F −P, G −S, H −Q
  3. E −R, F −P, G −Q, H −S
  4. E −P, F −R, G −S, H −Q
Question 20 Multiple Choice (Single Answer)

Given the following state table of an FSM with two states A and B, one input and one output:

Present State A Present State B Input Next State A Next State B Output
0 0 0 0 0 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1

If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?

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

Given below are two finite state automata (→ indicates the start state and F indicates a final state)

Y:

a b
$\rightarrow$ 1 1 2
2(F) 2 1

Z:

a b
$\rightarrow$ 1 2 2
2(F) 1 1

Which of the following represents the product automaton Z × Y?

  1. | | a | b | |-----------------|---|---| | $\rightarrow$ P | S | R | | Q | R | S | | R(F) | Q | P | | S | Q | P |
  2. || a | b | |-----------------|---|---| | $\rightarrow$ P | S | Q | | Q | R | S | | R(F) | Q | P | | S | P | Q |
  3. | | a | b | |-----------------|---|---| | $\rightarrow$ P | Q | S | | Q | R | S | | R(F) | Q | P | | S | Q | P |
  4. || a | b | |-----------------|---|---| | $\rightarrow$ P | S | Q | | Q | S | R | | R(F) | Q | P | | S | Q | P |
← Back to Quizzes