# Theory Of Computation (Toc) Quiz

20 Questions | Attempts: 2648  Settings  .

• 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

## Related Topics Back to top
×

Wait!
Here's an interesting quiz for you.