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

1 votes
1 votes

Minimum no. of states required if nth symbol is fixed from right hand side is 2n

Here 2nd symbol from right hand side is fix

so answer will be 22 = 4

0 votes
0 votes
RE=(a+b)*b(a+b)

Here 2nd symbol from right is b  required 2^2 =4 state in Minimal DFA

(If  nth symbol from right is fixed then require k^n state in Minimal DFA where k is no. Of input alphabet in string)
0 votes
0 votes

the answer is following :-  a first we made a nfa using the given expression and then we converted it into dfa its simple.

0 votes
0 votes
By looking to expression  we can know 2 last  symbol is b and after a or b accepted .it is language which is 2 last symbol is b reading from rhs to LHS.
So here formula for this type of language 2^n
So here 2^2 =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,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 ________.