## DFA

 Question 1

The minimum possible number of a deterministic finite automation that accepts the regular language L = {w1aw2 | w1, w2 ∈ {a,b}*, |w1| = 2,|w2| ≥ 3} is _________.

 A 8 B 9 C 10 D 11
Theory-of-Computation       DFA       GATE 2017(set-02)
Question 1 Explanation:
|w1 | = 2 means the length of w1 is two.
So we have four possibilities of w1 = {aa, ab, ba, bb}.
|w2 | ≥ 3 means the w2 will have at least three length string from {a,b}.
w2 will have {aaa, aab, aba, abb, baa, bab, bba, bbb, ……….}
So, the required DFA is
 Question 2

The number of states in the minimum sized DFA that accepts the language deﬁned by the regular expression

(0+1)*(0+1)(0+1)*
is_________.

 A 2 B 3 C 4 D 5
Theory-of-Computation       DFA       GATE 2016 set-2
Question 2 Explanation:
The regular expression generates the min string “0” or “1” and then any number of 0’s and 1’s .
So, the DFA has two states.
 Question 3
 A 1 B 2 C 3 D 4
Theory-of-Computation       DFA       GATE 2015 (Set-01)
Question 3 Explanation:
M accepts the strings which end with a and N accepts the strings which end with B. Their intersection should accept empty language.
 Question 4
The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________
 A 3 B 4 C 5 D 6
Theory-of-Computation       DFA       GATE 2015 -(Set-2)
Question 4 Explanation:

No. of states in minimal DFA is 3.
 Question 5

 A 2 B 3 C 4 D 5
Theory-of-Computation       DFA       Gate 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.