DFA

Question 1
Consider the following language.

A
2
Theory-of-ComputationDFAGATE 2021 CS-Set-1Video-Explanation
Question 1 Explanation: 

Option A accepts string “01111” which does not end with 011 hence wrong.

Option C accepts string “0111” which does not end with 011 hence wrong.

Option D accepts string “0110” which does not end with 011 hence wrong.

Option B is correct.

 

The NFA for language in which all strings ends with “011”

">
Question 2

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 3

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