Identification of Language:


Power of Language and Machine:

We already discussed the classification of language and the power of language (See Language Section).


As we know the power of DFA, NFA, Mealy, and Moore machine is the same. The power of DFA and NFA is the same because every DFA there is NFA and every NFA can convert to DFA




If we convert one machine to another and vice versa, in that case, the power of both machines is equal. Let M1 can convert to M2 and M2 can convert to M1then M1 and M2 has the same power.


Power of a machine: It means a set of strings accepted by the machine or power of a machine means which type of language (L) accepted by this machine.


If we can design a DFA machine from a language, then we can design also an NFA, Mealy, and Moore machine from this language.


Here power is not measured by time. 


Let us have a language (L) and we can design two machines M1 and M2 from language L. Here M1 faster than M2. Still, we are saying M1 and M2 have the same power because it is from the same language L i.e. same set of strings.


So, power does not depend on time. Here power means how many strings this machine can accept.


The maximum no. of language processor accepted by Turing Machine than Halting Machine than Linear Bounded Automata and the minimum of language processor accepted by Finite Automata.


So, we can say if any language process by Finite Automata then it is also processed by Deterministic Push Down Automata (DPDA) rather all high power machine than Finite Automata. But reverse it is not possible.





Let L give CSL but not NCFL, but or REC, RE