Question 1 |

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string \epsilon is divisible by three.

**[MSQ]**(0+1(01^*0)^*1)^* | |

(0+11+10(1+00)^*01)^* | |

(0^*(1(01^*0)^*1)^*)^* | |

(0+11+11(1+00)^*00)^* |

Question 1 Explanation:

Question 2 |

For a string w, we define w^R to be the reverse of w. For example, if w=01101 then w^R=10110.

Which of the following languages is/are context-free?

Which of the following languages is/are context-free?

**[MSQ]**\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \} | |

\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \} | |

\{ wxw^R \mid w,x \in \{0,1\} ^* \} | |

\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \} |

Question 2 Explanation:

Question 3 |

Consider the following two statements about regular languages:

S1: Every infinite regular language contains an undecidable language as a subset.

S2: Every finite language is regular.

Which one of the following choices is correct?

S1: Every infinite regular language contains an undecidable language as a subset.

S2: Every finite language is regular.

Which one of the following choices is correct?

Only S1 is true | |

Only S2 is true | |

Both S1 and S2 are true | |

Neither S1 nor S2 is true |

Question 3 Explanation:

Question 4 |

Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example.

\begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array}

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.

The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.

Assume the initial state of the Mealy machine is 0.

What are the Boolean expressions corresponding to t and y in terms of s and b?

\begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array}

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.

The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.

Assume the initial state of the Mealy machine is 0.

What are the Boolean expressions corresponding to t and y in terms of s and b?

t=s+b y=sb | |

t=b y=sb | |

t=b y=s\bar{b} | |

t=s+b y=s\bar{b} |

Question 4 Explanation:

Question 5 |

Consider the following deterministic finite automaton (DFA)

The number of strings of length 8 accepted by the above automaton is _________

The number of strings of length 8 accepted by the above automaton is _________

32 | |

256 | |

64 | |

512 |

Question 5 Explanation:

Question 6 |

Let L_1 be a regular language and L_2 be a context-free language. Which of the following languages is/are context-free?

**[MSQ]**L_1 \cap \overline{L_2} | |

\overline{\overline{L_1} \cup \overline{L_2}} | |

L_1 \cup (L_2 \cup \overline{L_2}) | |

(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2) |

Question 6 Explanation:

Question 7 |

Let L \subseteq \{0,1\}^* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?

L - \{01\} | |

L \cup \{01\} | |

\{0,1\}^* -L | |

L \cdot L |

Question 7 Explanation:

Question 8 |

In a pushdown automaton P=(Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form,

where p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}, represents

(q,Y) \in \delta(p,a,X)

Consider the following pushdown automaton over the input alphabet \Sigma = \{a,b\} and stack alphabet \Gamma = \{ \#, A\}.

The number of strings of length 100 accepted by the above pushdown automaton is ___________

where p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}, represents

(q,Y) \in \delta(p,a,X)

Consider the following pushdown automaton over the input alphabet \Sigma = \{a,b\} and stack alphabet \Gamma = \{ \#, A\}.

The number of strings of length 100 accepted by the above pushdown automaton is ___________

50 | |

49 | |

101 | |

100 |

Question 8 Explanation:

Question 9 |

For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages.

\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}

Which one of the following options is correct?

\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}

Which one of the following options is correct?

Both L1 and L2 are decidable. | |

L1 is decidable and L2 is undecidable. | |

L1 is undecidable and L2 is decidable. | |

Both L1 and L2 are undecidable. |

Question 9 Explanation:

Question 10 |

Consider the following language:

L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}

Which one of the following deterministic finite automata accepts L?

L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}

Which one of the following deterministic finite automata accepts L?

A | |

B | |

C | |

D |

Question 10 Explanation:

There are 10 questions to complete.