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