Theory Of Computation (Toc) Quiz
(103).jpg "Theory Of Computation (Toc) Quiz")
.
- 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
Back to top