Theory Of Computation (Toc) Quiz

Complements a given bit pattern

Finds 2’s complement of a given bit pattern

Increments a given bit pattern by 1

Changes the sign bit

(0*10*1)*

0*(10*10*)*

0*(10*1*)*0*

0*1(10*1)10*

All palindromes

All odd length palindromes

Strings that begin and end with the same symbol

All even length palindromes

Q0, q1, q2

[q0, q1], [q0, q2], [ ]

Q0, [q1, q2]

[q0, q1], q2

M x 2^n

2m+n

2^mn

M+n

{1, 0}* {01}

{1, 0}* {1}

{1}{1, 0}* {1}

1*0* {0, 1}

1

5

7

8

Any string of odd number of a’s

Any string of odd number of b’s

Any string of even number of a’s and odd number of b’s

Any string of odd number of a’s and odd number of b’s

Ab*b*

A*b*

B*b

B*ab*

The set of all strings containing the substrings 11

The set of all string containing at most two 1’s

The set of all strings containing at least two 1’s

The set of all strings that begins and ends with only 0.

1, 2 and 3

2, 3 and 4

1, 2 and 4

1, 3 and 4

A

B

C

D

1 and 3 only

2 and 4 only

2 and 3 only

3 and 4 only

Option 1

Option 2

Option 3

Option 4

Every NFA can be converted to an equivalent DFA

Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

Every regular language is also a context-free language

Every subset of a recursively enumerable set is recursive

Q0 and q0 respectively

Q0 and q1 respectively

Q0 and q2 respectively

Q0 and q3 respectively

(A) and (B) only

(A), (B) and (C) only

(B), (C) and (D) only

(B) and (D) only

(A) and (B) only

(A), (B) and (C) only

(B), (C) and (D) only

(B) and (D) only

2

3

4

5

7

10

12

11