edited by
28,980 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

6 votes
6 votes

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 2k as we got to calculate/ keep memory of all possible strings ending combinations (2k)

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

4 votes
4 votes

The language given is tht 2nd character  from the right should be 'b' 

For such languages, the no. Of states in the dfa will always be 2k

Where k is the position of the symbol from right 

In our scenario

K=2 

Therefore the no of states in the dfa will be 22 = 4

​​​​

Answer:

Related questions

65 votes
65 votes
12 answers
3
38 votes
38 votes
5 answers
4
Akash Kanase asked Feb 12, 2016
15,611 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 ________.