# Finite Automata

 Question 1
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 1 Explanation:
 Question 2
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 2 Explanation:
 Question 3
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 3 Explanation:
 Question 4
Minimum number of states required in DFA accepting binary strings not ending in "101" is
 A 3 B 4 C 5 D 6
ISRO CSE 2020   Theory of Computation
Question 4 Explanation:
 Question 5
Consider the following language.

L={$x \in \{a,b\}^*|$ number of a's in x divisible by 2 but not divisible by 3}

The minimum number of states in DFA that accepts L is _______
 A 4 B 5 C 6 D 7
GATE CSE 2020   Theory of Computation
Question 5 Explanation:
 Question 6
Let $\Sigma$ be the set of all bijections from {1,...,5} to {1,...,5}, where $id$ denotes the identity function, i.e. $id(j)=j,\forall j$. Let $\circ$ denote composition on functions. For a string $x = x_1x_2 ... x_n \in \Sigma ^n, n \geq 0$, let $\pi(x) = x_1\circ x_2\circ ... \circ x_n$. Consider the language $L = \{x \in \Sigma ^* | \pi(x) = id\}$. The minimum number of states in any DFA accepting L is _________ .
 A 25 B 125 C 120 D 150
GATE CSE 2019   Theory of Computation
Question 6 Explanation:
 Question 7

The FSM (Finite State Machine) machine pictured in the figure above
 A Complements a given bit pattern B Finds $2^{\prime} s$ complement of a given bit pattern C Increments a given bit pattern by 1 D Changes the sign bit
ISRO CSE 2018   Theory of Computation
Question 7 Explanation:
 Question 8
Given a language L, define $L^{i}$ as follows:
$L^{0}=\{\varepsilon \}$
$L^{i}=L^{i-1} \cdot L$ for all $i \gt 0$
The order of a language L is defined as the smallest k such that $L^{k}=L^{k+1}$. Consider the language L1 (over alphabet 0) accepted by the following automaton.
The order of L1 is ______
 A 1 B 2 C 3 D 4
GATE CSE 2018   Theory of Computation
Question 8 Explanation:
 Question 9
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
 A $k\geqslant 2^{n}$ B $k\geqslant n$ C $k\leqslant n^{2}$ D $k\leqslant 2^{n}$
GATE CSE 2018   Theory of Computation
Question 9 Explanation:
 Question 10
Let $\delta$ denote that transition function and $\hat{\delta}$ denote the extended transition function of the $\epsilon$- NFA whose transition table is given below:

Then $\hat{\delta}(q_{2},aba)$ is ____
 A $\varnothing$ B $\{q_{0},q_{1},q_{3}\}$ C $\{q_{0},q_{1},q_{2}\}$ D $\{q_{0},q_{2},q_{3}\}$
GATE CSE 2017 SET-2   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.

### 11 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.