# Finite Automata

 Question 1
Consider the language L over the alphabet {0, 1}, given below:

$L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}.$
The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.
 A 3 B 4 C 5 D 6
GATE CSE 2023   Theory of Computation
Question 1 Explanation:
 Question 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below? A ab*bab* + ba*aba* B (ab*b)*ab* + (ba*a)*ba* C (ab*b + ba*a)*(a* + b*) D (ba*a + ab*b)*(ab* + ba*)
GATE CSE 2022   Theory of Computation
Question 2 Explanation:

 Question 3
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?
 A t=s+by=sb B t=by=sb C t=by=s$\bar{b}$ D t=s+by=s$\bar{b}$
GATE CSE 2021 SET-2   Theory of Computation
Question 3 Explanation:
 Question 4
Consider the following deterministic finite automaton (DFA) The number of strings of length 8 accepted by the above automaton is _________
 A 32 B 256 C 64 D 512
GATE CSE 2021 SET-2   Theory of Computation
Question 4 Explanation:
 Question 5
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$? A A B B C C D D
GATE CSE 2021 SET-1   Theory of Computation
Question 5 Explanation:

There are 5 questions to complete.

### 12 thoughts on “Finite Automata”

1. question no 7’s Diagram is wrong

• Thank you Shivam,
We have updated the figure.

2. question no 49th question is wrong .second term will be only of 5 1’s not of 6 1s.

• Thank you shivam,
We have updated the question.

3. In Que.64 Option (A) is also False. (Correct answer in GateOverflow- False. Conversion from NPDA To DPDA is not always possible like in the case of wwR.)

• Thank You Rashmi,
We have updated the option.

4. In question, 66 state table is not containing all elements.

• Thank You Rashmi,
We have updated the figure in question.

5. In question, 64 Option (A) is also False. (Correct answer in GateOverflow- False. Conversion from NPDA To DPDA is not always possible like in the case of wwR.)

6. In question, 67 option (A) is (01) instead of (1).

• 7. 