1
$\begingroup$

I am having confusion in understanding the concept of the word "powerful" in automata theory.

Even the confusion arises that if I have a DFA with single final state ,so then is it more or less powerful than another DFA with more than one final states?

And can we make a similar argument for NFA ?

$\endgroup$
  • $\begingroup$ powerfulness in automata theory shows that if a machine accept large grammer set than other machine.like in decreasing order of powerfullness TM>LBA>PDA>FA.means TM can accept all grammers that can FA,PDA,LBA do and also some other grammers too. and as far as powerfulness concern with no. of final states in dfa i'm not sure that there can be any conclusion on it. $\endgroup$ – iostream007 Apr 21 '15 at 7:28
1
$\begingroup$

Machine $M1$ is more powerful than machine $M2$ if, intuitively, anything that $M2$ can do, $M1$ can do as well. Formally, $M1$ is more powerful than $M2$ if, given any specification of a problem and a solution of it on $M2$, there exists a solution of the same problem on $M1$. One may further demand that the complexity (either time or space) does not increase when implementing on $M1$, so things can become a bit more complicated. Typically, one shows that machine $M1$ is more powerful than machine $M2$ by showing that any $M2$ type machine can be converted to an $M1$ type machine, which solves the exact same problem. In the case of DFA with 1 final state vs. multiple final states, it is obvious then anything that can be done with 1 final state can also be done with multiple final states. However, it is very easy to convert any FDA with multiple final states into a DFA with 1 final state without altering the accepted language; indeed, simply add a new state, label it the unique final state, and link to it precisely from all the previously final states. So, DFA's with 1 final state is as powerful as DFA's with multiple final states.

$\endgroup$
  • $\begingroup$ Ahh shame "Anything $M2$ can do $M1$ can do better.."$:) $\endgroup$ – DRF Apr 21 '15 at 8:03
  • $\begingroup$ Sir,I understood your explanation but I am just stuck up over two doubts: $\endgroup$ – RADHA GOGIA Apr 22 '15 at 7:36
  • $\begingroup$ Firstly ,If I have a DFA with multiple final states ,then when I will convert it into a DFA with a single final state,then I will link all the previous final states to the new final state with epsilon move,so then it will become an epsilon NFA ,so then when I will convert it into DFA so then won't the number of final states increase? $\endgroup$ – RADHA GOGIA Apr 22 '15 at 7:45
  • $\begingroup$ Secondly ,You said that DFA's with 1 final state is as powerful as DFA's with multiple final states. ,So is it that both are equally powerful ? $\endgroup$ – RADHA GOGIA Apr 22 '15 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.