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 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 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+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 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 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




There are 5 questions to complete.

12 thoughts on “Finite Automata”

  1. 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
  2. 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