Finite Automata

Question 1
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
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+b
y=sb
B
t=b
y=sb
C
t=b
y=s\bar{b}
D
t=s+b
y=s\bar{b}
GATE CSE 2021 SET-2   Theory of Computation
Question 3
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
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
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 6
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 7
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 8


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 9
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 10
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
There are 10 questions to complete.

12 thoughts on “Finite Automata”

  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.)

    Reply

  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.)

    Reply

Leave a Comment