1 votes 1 votes The minimum number of states required to construct a DFA that recognizes the language of string that recognizes the language of string over alphabet {0,1} whose 10th symbol from the right end is 1 is ____________ Theory of Computation theory-of-computation finite-automata + – srestha asked Dec 30, 2017 srestha 2.0k views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply Ajay Jadhav commented Dec 30, 2017 reply Follow Share $2^{10}$?? 0 votes 0 votes Ashwin Kulkarni commented Dec 30, 2017 reply Follow Share I think it is 210 0 votes 0 votes akash.dinkar12 commented Dec 30, 2017 reply Follow Share how?? 0 votes 0 votes Ajay Jadhav commented Dec 30, 2017 reply Follow Share Try for 2nd symbol 1 from right,first NFA and then convert to DFA DFA will not be minimized further. 0 votes 0 votes akash.dinkar12 commented Dec 30, 2017 reply Follow Share I know that!! Try to generalize it! 0 votes 0 votes srestha commented Dec 30, 2017 reply Follow Share @ Ajay Jadhav how do u know, it cannot be minimized further, without drawing DFA? 0 votes 0 votes Ajay Jadhav commented Dec 30, 2017 reply Follow Share I drew for 2nd from right and 3rd from right,half states are final and half are non-final Anyway what is the answer? 0 votes 0 votes srestha commented Dec 30, 2017 reply Follow Share ans given, that u told Can u show me the DFA ? 0 votes 0 votes Ajay Jadhav commented Dec 30, 2017 reply Follow Share See last two symbols will be 00,01,10,11 among these we only want 10 and 11 so these are final 000,001,010,011,100,101,110,111(for 3rd symbol from right) among these 100,101,110,111 are useful There is NPTEL lecture where this problem is discussed 0 votes 0 votes gauravkc commented Dec 30, 2017 reply Follow Share have a look at this https://gateoverflow.in/63063/dfa 0 votes 0 votes Mk Utkarsh commented Jan 1, 2018 reply Follow Share it cannot be minimized below 210 because its goal is to remember sequence of all those possible 10 bits so for remembering those 10 bits we need 210 states 0 votes 0 votes Mk Utkarsh commented Jan 1, 2018 reply Follow Share https://www.youtube.com/watch?v=XxuH_K-wzpg watch till 10 mins also it cannot be minimized because every state is used for a unique 10bits 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes it cannot be minimized below 210 because its goal is to remember sequence of all those possible 10 bits so for remembering those 10 bits we need 210 states Mk Utkarsh answered Jan 1, 2018 Mk Utkarsh comment Share Follow See all 0 reply Please log in or register to add a comment.