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

We don't need any dead state here. On state "A" just put the alphabet "a" loop.

3 should be the answer

---

In the STT for DFA given above there is no dead state.
The NFA is drawn.
NFA is converted to DFA.
The DFA is tried to be minimized but could not.
Hence ans is 4.
If you have any DFA having 3 states you can post the DFA image or STT.

---

Please check this. Here C is the final state and it is accepting the same language

---

Your DFA accepts baaa, which is not generated by the given regular expression. Watch this NPTEL video of Prof from IIT Kgp :

https://youtu.be/XxuH_K-wzpg

---

Many strings which does not belong to the language are accepted by your machine.
Ex:  baa
Many such strings possible.
A DFA should not only accept all the strings in the language, but also reject the strings which are not in the language.



The machine given below can accept all the languages in the world..  (a+b)*   So why the ans is not 1?
It does not reject the other strings which are not in the language...

---

Sorry for bringing repeated doubts. Please check this

---

In this machine "bbb"  "bba" & many such strings are not accepted which belongs to the language.

---

stirng 'b' is not accepted in your dfa but it is accepted in expression stated above.

---

Sachi Saxena  b is not accepted by above expression.

Expression accepts language : which have length at least 2 and second last symbol is b.

---

above 3 states is correct i guess it is accepting bbb and bba. so answer shoould be 3 states.

---

See if you have tried to build up from seeing the string in Lang then you should be get the graph you might get this : But see you don’t accept there baba which should be accepted so do this type of question by making NFA first as suggested above  

---

Answer is 4..

---

4 states is absolutely correct. You can't make a 3 state DFA for this language.

---

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.