DFA

Question 1

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}* | w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}

A
Theory Explanation.
Theory-of-ComputationDFAGATE 1998
Question 2

Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet {a,b}, such that no string has 3 consecutive occurrences of the letter b.

A
Theory Explanation.
Theory-of-ComputationDFAGATE 1993
Question 3
 Let L ⊆ {0, 1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?
A
L U {01}
B
L.L
C
{0,1}*-L
D
L-{01}
Theory-of-ComputationDFAGATE 2021 CS-Set-2Video-Explanation
Question 3 Explanation: 
Explanation:If L has a DFA with the number of states k then complement of L will also have a DFA with k states. Hence {0,1}* -L i.e, the complement of L will have k states DFA also.
Question 4
Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by the above automaton is __________.
A
256
Theory-of-ComputationDFAGATE 2021 CS-Set-2Video-Explanation
Question 4 Explanation: 
State q3 and q4 are equivalent so they can be merged and states q1 and q2 are also equivalent so they can also be merged hence the min DFA will be

So the DFA accepts all strings of length greater than equal to 3.

 

For 8 length strings we have 8 positions

 

_ _ _ _ _ _ _ _

 

For each position there are two possibilities 0 or 1.

So for 8 positions we have 28 possibilities = 256

Question 5

Consider the regular grammar:
S → Xa | Ya
X → Za Z → Sa | ϵ
Y → Wa W → Sa
where S is the starting symbol, the set of terminals is {a} and the set of non-terminals is {S, W, X, Y, Z}. We wish to construct a deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA?

A
2
B
3
C
4
D
5
Theory-of-ComputationDFAGATE 2005-IT
Question 5 Explanation: 
L = {aa, aaa, aaaaa, ...}
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
There are 5 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access