CrazyEngineers Logo

Doubt regarding DFA

We all know that DFA can be minimized. A DFA can have several final states. Can every DFA be minimized into a DFA with single final state?

Replies

  • sushant005
    sushant005
    Generally a DFA has one initial state and one final state, when we make the DFA eqivalent to given NFA then it has many final states.I think that can not be reduced but i am not sure.Let me clarify it clearly...
  • rishi0922
    rishi0922
    I think Sushant is right, DFA has only one final state.
    DFA can be converted into NFA which has several final states, when we convert DFA to NFA then all the possible states should come through transition equations, it my be more than one final state.
  • Pensu
    Pensu
    I think u people are getting me wrong. DFA may have more than one final state. But the question is "Is it a must condition that a DFA having more than one final state can be reduced to DFA having one final state"...
  • sushant005
    sushant005
    thats why i told, if you convert a NFA to its equivalent DFA then it must have more than one final state and i think we can not minimize that DFA...
    Do me correct if i am wrong.
  • Pensu
    Pensu
    well sushant actually we can minimize that DFA using a state minimization algorithm in which we make groups of states and replace them.....and ya i have got the answer its not mandatory...there are DFAs which cant be minimized....
  • sushant005
    sushant005
    Till now i read how to convert an NFA to its equivalent DFA where i found that there are more than one final sates in DFA and i don't know that there exist an algorithm which is used to minimize DFA . you got the solution please tell something about that minimization algorithm.
  • Pensu
    Pensu
    try this....

    Dfa Minimization

    i studied it in some...i forgot the name. I will tell you as soon as recall it.

You are reading an archived discussion.

Related Posts

India has given an ultimatum to Blackberry, Google and Skype are Next!

India has asked RIM to give security access failing to which may result in closing the BBM and email services off in India. Google and Skype are facing similar threats...

Computer hard disc

How long a computer hard disc can last ??

Corruption of hard disc

Some says that by keeping very less memory space in the partitioned drives of hard disc lasts in the logical break of hard disc.... Is it true ?? And why...

Come on CEans! let's speak Japanese;)

hey CEans😁 Nowadays we see that being able to speak a foreign language is an advantage anywhere. so here in this thread let's learn to speak Japanese. we can start...

need Industry Contacts in Mumbai

Hi I am a b.tech final year student (Electronics and telecom ) from Mumbai and need some industry contacts for my Final year Project! I will be highly Thankful.