Theory Of Computation (Toc) Quiz

20 Questions | By Sathyabama.s | Updated: Mar 22, 2022 | Attempts: 2648

Questions

Settings

Create your own Quiz

Questions and Answers

1.

The FSM (Finite State Machine) machine pictured in the figure below represents what language? (ISRO-2018)
- A.
  
  Complements a given bit pattern
- B.
  
  Finds 2’s complement of a given bit pattern
- C.
  
  Increments a given bit pattern by 1
- D.
  
  Changes the sign bit
2.

Let L = {w = (0+1)* | w has even number of 1’s}, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ? (ISRO-2016)
- A.
  
  (0*10*1)*
- B.
  
  0*(10*10*)*
- C.
  
  0*(10*1*)*0*
- D.
  
  0*1(10*1)10*
3.

S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of (ISRO 2016)
- A.
  
  All palindromes
- B.
  
  All odd length palindromes
- C.
  
  Strings that begin and end with the same symbol
- D.
  
  All even length palindromes
4.

The DFA generated from the following NFA? ISRO CS2013
- A.
  
  Q0, q1, q2
- B.
  
  [q0, q1], [q0, q2], [ ]
- C.
  
  Q0, [q1, q2]
- D.
  
  [q0, q1], q2
5.

The number of states required by a Finite State Machine, to simulate the behaviour of a computer with a memory capable of storing ‘m’ words, each of length ‘n’ bits is?
- A.
  
  M x 2^n
- B.
  
  2m+n
- C.
  
  2^mn
- D.
  
  M+n
6.

The given finite automata represent which of the languages?
- A.
  
  {1, 0}* {01}
- B.
  
  {1, 0}* {1}
- C.
  
  {1}{1, 0}* {1}
- D.
  
  1*0* {0, 1}
7.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is ( GATE-CS-2003)
- A.
  
  1
- B.
  
  5
- C.
  
  7
- D.
  
  8
8.

The finite state machine given in figure below recognizes : UGC-NET JUNE Paper-2
- A.
  
  Any string of odd number of a’s
- B.
  
  Any string of odd number of b’s
- C.
  
  Any string of even number of a’s and odd number of b’s
- D.
  
  Any string of odd number of a’s and odd number of b’s
9.

The automata represent which of the languages given below? Nielit Scentist-B [02-12-2018]
- A.
  
  Ab*b*
- B.
  
  A*b*
- C.
  
  B*b
- D.
  
  B*ab*
10.

Which of the following languages over the alphabet {0,1} is described by the given regular expression: (0+1)*1(0+1)*1? Nielit Scentist-B [02-12-2018]
- A.
  
  The set of all strings containing the substrings 11
- B.
  
  The set of all string containing at most two 1’s
- C.
  
  The set of all strings containing at least two 1’s
- D.
  
  The set of all strings that begins and ends with only 0.
11.

In the given language L={ab,aa,baa}, __ number of strings are in L* (1) baaaba (2) aabaaaa (3) baaabaaaabaa (4) baaabaaa (GATE CS 2012)
- A.
  
  1, 2 and 3
- B.
  
  2, 3 and 4
- C.
  
  1, 2 and 4
- D.
  
  1, 3 and 4
12.

Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2*U L1*
- A.
  
  A
- B.
  
  B
- C.
  
  C
- D.
  
  D
13.

Consider the DFA given. GATE CS 2013 Which of the following are FALSE? 1. Complement of L(A) is context-free. 2. L(A) = L((11*0+0)(0 + 1)*0*1*) 3. For the language accepted by A, A is the minimal DFA. 4. A accepts all strings over {0, 1} of length at least 2.
- A.
  
  1 and 3 only
- B.
  
  2 and 4 only
- C.
  
  2 and 3 only
- D.
  
  3 and 4 only
14.

A deterministic finite automation (DFA)D with alphabet {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
- A.
  
  Option 1
- B.
  
  Option 2
- C.
  
  Option 3
- D.
  
  Option 4
15.

Which of the following statements is false? GATE CS 2008
- A.
  
  Every NFA can be converted to an equivalent DFA
- B.
  
  Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
- C.
  
  Every regular language is also a context-free language
- D.
  
  Every subset of a recursively enumerable set is recursive
16.

The transition function for the language L = {w|na (w) and nb(w) are both odd} is given by: UGC NET CS 2015 Jun δ (q0, a) = q1 ; δ (q0, b) = q2 δ (q1, a) = q0 ; δ (q1, b) = q3 δ (q2, a) = q3 ; δ (q2, b) = q0 δ (q3, a) = q2 ; δ (q3, b) = q1 The initial and final states of the automata are:
- A.
  
  Q0 and q0 respectively
- B.
  
  Q0 and q1 respectively
- C.
  
  Q0 and q2 respectively
- D.
  
  Q0 and q3 respectively
17.

Which of the following are not regular? UGC NET CS 2017 Jan (A) Strings of even number of a’s. (B) Strings of a’s, whose length is a prime number. (C)Set of all palindromes made up of a’s and b’s. (D)Strings of a’s whose length is a perfect square.
- A.
  
  (A) and (B) only
- B.
  
  (A), (B) and (C) only
- C.
  
  (B), (C) and (D) only
- D.
  
  (B) and (D) only
18.

Which of the following are not regular? UGC NET CS 2017 Jan (A) Strings of even number of a’s. (B) Strings of a’s, whose length is a prime number. (C) Set of all palindromes made up of a’s and b’s. (D) Strings of a’s whose length is a perfect square.
- A.
  
  (A) and (B) only
- B.
  
  (A), (B) and (C) only
- C.
  
  (B), (C) and (D) only
- D.
  
  (B) and (D) only
19.

The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________
- A.
  
  2
- B.
  
  3
- C.
  
  4
- D.
  
  5
20.

How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
- A.
  
  7
- B.
  
  10
- C.
  
  12
- D.
  
  11