UGC NET CSE | June 2019 | Part 2 | Question: 75

Question

How many states are there in a minimum state automata equivalent to regular expression given below?

Regular expression is $a^*b(a+b)$

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Answer 1

The minimal automata for the regular expression : $a^*b(a+b)$ is as shown below

$\therefore$ Option $C.$  $3$ is the correct answer.

Comments

Can't there be 2 states possible as a,b be on Q(as self loop) as final state

---

No ...in that case the language will become $a^*b(a+b)^*$.

---

Yeah ,got it:)

---

How can this be a valid automaton?

There are no transitions in the final state. Why haven't you included a dead state?

---

It is a NFA not a DFA. (both DFA and NFA are automatas)

---

On wiki this has been written about minimum state automata( DFA Minimization):

For each regular language, there also exists a minimal automaton that accepts it, that is, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names).[2][3] The minimal DFA ensures minimal computational cost for tasks such as pattern matching.

My question is should we go for NFA whenever minimum states automation has been asked without any prior mention of the type of automata.

As this question hasn't mentioned anything about the type of automata.

---

in such questions, We should go with the one that has minimum number of states.

---

Roger That!

---

@Satbir

Where is the transition for $\mathbf{Dead\; State}$.

In Dfa you have to complete all the transitions.

So $\mathbf{4}$ states should be there.

It says minimum state automata not $\mathbf{NFA}$

---

@Arjun

Please verify this answer once.

---

DFA and NFA both are automatas

---

Yeah, that's ok but I think we need to draw DFA only.

NFA is the more simpler form.

I am not sure whether its correct drawing an NFA in place of DFA

Answer 2

I think answer is four. Because it also has to reject the strings like bab,abba,etc.