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

Input: bbb - is this accepted? @Priya_Samanta

---

Oo.. I got it now, thanks

---

 

it just popped up in my head that lang accepts string ending with ba or bb so i visualized it as sigma star b (dont care ) which then i recalled having studied similar lang from poonia sir xth symbol from right is b so we track about 2^x states in a minimal DFA.

 

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

---

Inspiration 🙏.

Answer 3

Solution......

Comments

your DFA will not accept string 'b' which is acceptable by the expression above.

---

@Sachi

(a+b)*b(a+b) : this is given regular expression, I assume u know that what are strings comes under this expression.

If U put (* =0) in regular expression then expression will become b(a+b). So either ba or bb should be accepted.

There are no chances in the regular expression that only string "b" could be accepted. String "b" is not coming under regular expression...

---

@akash.dinkar12 I found your solution as BEST ANSWER for me! Good work, mate!

---

thanx bro!!!

---

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.

Answer 5

Answer  : 4 states

Explanation :

the given regular expression is for the language "2nd symbol from the right is b"

in such cases where the kth symbol from the right is asked, the no. of states in the dfa will always be 2^k as we got to calculate/ keep memory of all possible strings ending combinations (2^k)

Thus in our question, all possible strings from the right will give the answer 2²=4 states

Answer 6

Answer : 4 States. 

Note: Here,

1)Delta(B,a)=C

2)Delta(C,b)=B