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

This may help : https://youtu.be/hxUZRgARn-g?t=1994

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

What if we make transition of b from third state to first/second state instead of creating new trap state?
It would be still DFA!! Anyone please correct me

---

👻

---

If u make transition of b from third state to 1st or 2nd state then w1 length will no longer be 2 and will become atleast 2.

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

hey please explain for the dead state why we need it???????

---

Rajesh because it's written DETERMINISTIC automaton. In DFA, from each state we need one transition for each symbol

---

from each state in DFA we need transition for each input 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

Answer 5

8 States in which 1 state is dead state.

Answer 6

in this finite automata to accept given language is 8 state (7 transition state and 1 f trap state)