edited by
28,944 views
54 votes
54 votes
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 ___________ .
edited by

15 Answers

Best answer
67 votes
67 votes
$\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.$

edited by
28 votes
28 votes

Solution......

8 votes
8 votes

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:

Related questions

65 votes
65 votes
12 answers
3
38 votes
38 votes
5 answers
4
Akash Kanase asked Feb 12, 2016
15,597 views
The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.