0 votes 0 votes Give an example of DFA minimization where the initial state is final state and there are one or more final states Theory of Computation finite-automata minimization + – ck asked Dec 22, 2018 ck 1.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes Any dfa which accepts epsilon will have initial state as final state. Coming to the second part of your doubt: More than 1 final states and initial state as final state. So suppose L= a language over {a,b} L= atmost 2 a's={epsilon,a,aa,ab,ba,aba,.......}=b*+b*ab*+b*ab*ab* So we have more than one final states here and initial state is also final. So see the following dfa: For further ref:https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/min-fa.html anjali007 answered Dec 22, 2018 • edited Dec 22, 2018 by Lakshman Bhaiya anjali007 comment Share Follow See all 8 Comments See all 8 8 Comments reply ck commented Dec 22, 2018 reply Follow Share I am not clear about minimisation method when initial state is same as final state so please elaborate with a DFA and equivalent sets procedure 0 votes 0 votes anjali007 commented Dec 22, 2018 reply Follow Share @ck I hope u get it now... In case of any doubt.. feel free to ask 0 votes 0 votes ck commented Dec 22, 2018 reply Follow Share My question was how to minimise a DFA which has Same initial and same final State 0 votes 0 votes Satbir commented Dec 22, 2018 reply Follow Share Same procedure will apply... states containing the initial state (of given DFA) will be final state in minimized DFA 0 votes 0 votes anjali007 commented Dec 22, 2018 reply Follow Share @ck we will treate initial state as final state that is why it would put with other final states in 0 equivalent. 0 votes 0 votes Shaik Masthan commented Dec 22, 2018 reply Follow Share @ck a simple example is generate the Minimized DFA for the Language L = {∈,ab} Note that, when your language contain ∈, then your DFA should contain initial state as one of the final state. 0 votes 0 votes ck commented Dec 22, 2018 reply Follow Share How to minimize a DFA with all states as the final states? I have obtained DFA with all final states by performing the following steps step 1. epsilon NFA is converted into NFA --M1 step 2. NFA obtained is converted into DFA --M2 M2 contains all final states now I am not understanding how do I minimize it? 0 votes 0 votes Satbir commented Dec 22, 2018 reply Follow Share in M2 if all states are final states => it accepts every input including epsilon =>the minimized dfa there will be only 1 state which is initial state as well as finite state. 0 votes 0 votes Please log in or register to add a comment.