Doubt regarding DFA

@pensu-8tNeGU • Oct 24, 2024

Oct 24, 2024

977

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?

Like 0 Replies 7

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

sushant005

@sushant005-tyt4WK • Aug 12, 2010

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...
0
rishi0922

@rishi0922-a2xTAa • Aug 12, 2010

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.
0
Pensu

@pensu-8tNeGU • Aug 13, 2010

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"...
0
sushant005

@sushant005-tyt4WK • Aug 13, 2010

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.
0
Pensu

@pensu-8tNeGU • Aug 13, 2010

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....
0
sushant005

@sushant005-tyt4WK • Aug 13, 2010

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.
0
Pensu

@pensu-8tNeGU • Aug 13, 2010

try this....

<a href="https://en.wikipedia.org/wiki/DFA_minimization" target="_blank" rel="nofollow noopener noreferrer">Dfa Minimization</a>

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

0