1 votes 1 votes Consider the following input sequence $010101\dots$ ($01$ repeated one or more times). The minimum number of states required in a DFA to accept the strings following the above pattern is _________. Theory of Computation tbb-toc-2 numerical-answers theory-of-computation minimal-state-automata + – Bikram asked Aug 12, 2017 • retagged Sep 17, 2020 by ajaysoni1924 Bikram 622 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Hemant Parihar commented Aug 16, 2017 reply Follow Share I can be made many conclusion from the given sequence. (01)* Whose minimal DFA will have 3 states. (01)+ whose minimal DFA will have 4 states. 0(10)* whose minimal DFA will also have 4 states. Why is any one of them wrong? 1 votes 1 votes Bikram commented Aug 16, 2017 i edited by Bikram Aug 16, 2017 reply Follow Share @joshi and @hemanth It seems that (01)+ is only possible RE for 010101 ... with 4 min states in DFA. as 0(10)* , 0(01)* , (01)*0 all these have some extra 0's coming.. 0(10)* = 010 1010 101010 like that ( but we need 010101 so at end one extra 0 is coming ) 0(01)* = 001 0101 010101 .... ( 2 consecutive 0's are coming ) (01)*0 = 010101010 .. ( again one extra 0 is coming at last ) so that means only (01)+ is possible.. 1 votes 1 votes premu commented Jun 26, 2020 reply Follow Share Good question,but while solving it confused me. 0 votes 0 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes The given sequence 010101...... represent (01)+. It's minimized DFA will have 4 states. Ans: 4 states. Hemant Parihar answered Aug 16, 2017 • selected Aug 16, 2017 by Bikram Hemant Parihar comment Share Follow See all 0 reply Please log in or register to add a comment.
