GATE CSE 2017 Set 1 | Question: 22

Question

Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .

Comments

Check https://gateoverflow.in/blog/8795/minimal-deterministic-finite-automata

---

@Asim Siddiqui 4 Make a NFA, convert it to DFA and then to minimal DFA.

 

---

Very Good Question

Answer 1

$\text{NFA}$

NFA to DFA Conversion:
In the State Transition Table below we can see 4 states $(\text{A}, \text{AB}, \text{*AC}, \text{*ABC},$ the $\text{*}$ ones being FINAL$)$ are there but before confirming the ans lets try to minimize. $\text{A}, \text{AB}$ cannot be minimized further because $A$ goes to non-final state on $a$ where as $\text{AB}$ goes to a final state.  Similarly $\text{*AC}$ goes to a non-final state on $\textbf{a}$ whereas $\text{*ABC}$ goes to a final state. Hence, none of the states can be merged.

$$\begin{array}{|c|c|c|} \hline \text{$\delta$} & \text{a} & \text{b} \\\hline \text{A} & \text{A} & \text{AB}\\ \text{AB} & \text{*AC} & \text{*ABC} \\ \text{*AC} & \text{A} & \text{AB}\\ \text{*ABC} & \text{*AC} & \text{*ABC} \\\hline \end{array}$$

Answer: $4.$

Comments

Yeah, I agree… The answer is right and is wrongly flagged.

---

@Ahwan @Kabir5454 @GateCse @Abhrajyoti00

Why this does not here 

“ DFA that contain substring having n length will have n+1 states and same with complement”

See the comment of  @Praveen Saini 

in (selected answer)

https://gateoverflow.in/8415/gate-cse-2015-set-3-question-18 

to get insite idea.

---

@GateOverflow04 Bro in that q, it is containing substring "x". This is not the same. 

Here it is "the second last letter is x". Carefully notice the ending in Both the qs. Here its only (a+b), not (a+b)*

Answer 2

Please correct me if i am wrong.

Comments

i also did it in the same way.My answer was also 4

---

Yup

U r correct

Answer 3

Solution......

Comments

Best explanation so far

---

What's the logic behind this?

---

Yes i got the same 4 states and in them 2 final states

Answer 4

Given Regular expression Accept all strings over alphabet {a,b} which end with either ba or bb.

Because,(a+b)*b(a+b)=(a+b)*(ba+bb).

So, to recognise this we have to see the strings which have ba or bb at end .

Below is the Required Dfa. and we can't further minimize it.

By equivalance theorem we have two sets of final and non-final states.

[a,b] [ba,bb]   

[a] [b] [ba] [bb]  //Because a,b goes to diffrent sets on a-transitions and  ba,bb also goes to diffrent sets on a-transitions.