# what do we mean by saying that a particular computing machine is more powerful than another computing machine?

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 ?

• 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. – iostream007 Apr 21 '15 at 7:28

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.
• Ahh shame "Anything $M2$ can do $M1$ can do better.."\$:) – DRF Apr 21 '15 at 8:03