CS and IT GATE 2021 SET-2 Questions with Answer

Ques 53 Theory of Computation

---

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.
Input sequence: 00100011000011100
Output sequence: 00000001000001100
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?

A

t = s + b, y = s b

B

t = b, y = s b

C

t = b, y = s b̄

D

t = s ⊕ b, y = s b̄

See Answer Video Solution

Ques 54 Theory of Computation

---

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?

A

{wxw^Rx^R | w,x ∈ {0,1}*}

B

{ww^Rxx^R | w,x ∈ {0,1}*}

C

{wxw^R | w,x ∈ {0,1}*}

D

{wxx^Rw^R | w,x ∈ {0,1}*}

See Answer Video Solution

Ques 55 Theory of Computation

---

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

A

(0 + 1(01*0)*1)*

B

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

C

((0*(1(01*0)*1))*

D

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

See Answer Video Solution

Ques 56 Theory of Computation

---

Consider the following augmented grammar with {#, ā, <, >, a, b, c} as the set of terminals.
S' → S
S → S # c S
S → SS
S → S ā
S → < S >
S → a
S → b
S → c
Let I₀ = CLOSURE({S' → • S}). The number of items in the set GOTO(GOTO(I₀, <), <) is _______.

See Answer Video Solution