Question 1 |
Consider the following languages:
\begin{aligned} L_1&= \{ ww|w \in \{a,b \}^* \} \\ L_2&= \{a^nb^nc^m | m,n \geq 0 \} \\ L_3 &= \{a^mb^nc^n|m,n \geq 0 \} \end{aligned}
Which of the following statements is/are FALSE?
MSQ
\begin{aligned} L_1&= \{ ww|w \in \{a,b \}^* \} \\ L_2&= \{a^nb^nc^m | m,n \geq 0 \} \\ L_3 &= \{a^mb^nc^n|m,n \geq 0 \} \end{aligned}
Which of the following statements is/are FALSE?
MSQ
L_1 is not context-free but L_2 and L_3 are deterministic context-free. | |
Neither L_1 nor L_2 is context-free. | |
L_2,L_3 and L_2 \cap L_3 all are context-free. | |
Neither L_1 nor its complement is context-free. |
Question 1 Explanation:
Question 2 |
Consider the following languages:
\begin{aligned} L_1&= \{a^n wa^n|w \in \{a,b \}^* \} \\ L_2&= \{wxw^R | w,x \in \{a,b \}^*, |w|,|x| \gt 0 \} \end{aligned}
Note that w^R is the reversal of the string w. Which of the following is/are TRUE?
MSQ
\begin{aligned} L_1&= \{a^n wa^n|w \in \{a,b \}^* \} \\ L_2&= \{wxw^R | w,x \in \{a,b \}^*, |w|,|x| \gt 0 \} \end{aligned}
Note that w^R is the reversal of the string w. Which of the following is/are TRUE?
MSQ
L_1 and L_2 are regular. | |
L_1 and L_2 are context-free. | |
L_1 is regular and L_2 is context-free. | |
L_1 and L_2 are context-free but not regular. |
Question 2 Explanation:
Question 3 |
Which of the following is/are undecidable?
MSQ
MSQ
Given two Turing machines M1 and M2 , decide if L(M1 ) = L(M2 ). | |
Given a Turing machine M , decide if L(M ) is regular. | |
Given a Turing machine M , decide if M accepts all strings. | |
Given a Turing machine M , decide if M takes more than 1073 steps on every string. |
Question 3 Explanation:
Question 4 |
Which of the following statements is/are TRUE?
MSQ
MSQ
Every subset of a recursively enumerable language is recursive. | |
If a language L and its complement \bar{L} are both recursively enumerable, then L must be recursive. | |
Complement of a context-free language must be recursive. | |
If L_1 and L_2 are regular, then L_1 \cap L_2 must be deterministic context-free. |
Question 4 Explanation:
Question 5 |
Which one of the following regular expressions correctly represents the language of the finite automaton given below?


ab*bab* + ba*aba* | |
(ab*b)*ab* + (ba*a)*ba* | |
(ab*b + ba*a)*(a* + b*) | |
(ba*a + ab*b)*(ab* + ba*) |
Question 5 Explanation:
Question 6 |
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]
[MSQ]
(0+1(01^*0)^*1)^* | |
(0+11+10(1+00)^*01)^* | |
(0^*(1(01^*0)^*1)^*)^* | |
(0+11+11(1+00)^*00)^* |
Question 6 Explanation:
Question 7 |
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?
[MSQ]
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 7 Explanation:
Question 8 |
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 8 Explanation:
Question 9 |
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 9 Explanation:
Question 10 |
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 10 Explanation:
There are 10 questions to complete.
Two options of Q15 are the same.