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 ___________ . Theory of Computation gatecse-2017-set1 theory-of-computation finite-automata numerical-answers minimal-state-automata + – Arjun asked Feb 14, 2017 edited Feb 17, 2018 by kenzou Arjun 28.9k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Shaik Masthan commented Dec 6, 2019 reply Follow Share Check https://gateoverflow.in/blog/8795/minimal-deterministic-finite-automata 1 votes 1 votes nishant_magarde commented Jan 23, 2020 reply Follow Share @Asim Siddiqui 4 Make a NFA, convert it to DFA and then to minimal DFA. 0 votes 0 votes Ray Tomlinson commented Jan 15 reply Follow Share Very Good Question 0 votes 0 votes Please log in or register to add a comment.
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 Prateek Thakral answered Oct 16, 2017 Prateek Thakral comment Share Follow See all 0 reply Please log in or register to add a comment.
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) Gaurav nitkkriit answered Jun 4, 2021 Gaurav nitkkriit comment Share Follow See all 0 reply Please log in or register to add a comment.
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. imakash665 answered Nov 1, 2021 imakash665 comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Piyush 777 answered Dec 21, 2021 Piyush 777 comment Share Follow See all 0 reply Please log in or register to add a comment.