GATE CSE 2017 Set 2 | Question: 25

Question

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .

Comments

shivay khustak is already uploading set 2..avoid duplicate qs

Answer 1

Answer is 8 states included one trap state (8) and final state (7).

$3^{rd}$ symbol from the start is an $\textbf{a}$

Comments

yes you can

---

I think in such a type of question we can’t minimize, because each state has it’s own significance.

---

We know if we combine and non-final states acc. to algo It will not remain as same language DFA.But really why our minimization algo create this problem here??? or  something I missing here

Answer 2

(a+b)(a+b)a(a+b)(a+b)(a+b) min length string is 6 alphabet so we need atleast 7 state and one for dead state so tatal 8 state needed.

Comments

@praveen sir what if we minimize the obtained dfa ? Will number of states will reduce or it will be same coz it's asking minimum number of states ? Or I am just overthinking

---

How did you come to know about the one extra dead state?

---

Because there is a restriction on the third symbol.

Answer 3

The answer will be 8 here

|w1| =2 for this we need 4 states (One dead state also)

|w2| >=3 for this we need 3 states

and 1 state in the middle for a so total 8

Answer 4

8 states including 1 final state and 1 dead state