# Can a language be the one recognized by more than one automatons?

The language recognized by an automaton is defined as the set of strings that are accepted by the automaton.

I wonder if it is possible that the languages recognized by two automatons are the same? Note, if I am correct, the most general automatons are the Turing machines, and the languages recognized by an automaton are exactly the recursively enumerable languages.

The same question if restricted to the commonly-known subfamilies of languages and their corresponding automatons (e.g. regular languages, context-free languages, context-sensitive languages)?

Thanks.

• In what way should these automatons be different? It might be that two different FSMs recognize exactly the same language, for instance. In the same way that two differently designed programs can be semantically equivalent, so to speak. – Guildenstern Jun 2 '14 at 18:28
• Probably "different" in formal theory? For example, two Turing machines are different, according to the definition en.wikipedia.org/wiki/Turing_machine#Formal_definition. Two finite state machines are different, according to the definition en.wikipedia.org/wiki/Finite-state_machine#Mathematical_model – Tim Jun 2 '14 at 18:35
• In that case, I think that making an example of two differently designed TMs that behave the same way (recognize the same language, say) should be simple enough. – Guildenstern Jun 2 '14 at 18:37

Yes, of course, it is possible. For instance, the process of DFA minimization works as follows: given a DFA $M$, produce another DFA $M'$ that recognizes the same language but is as small as possible. That tells you that it is possible to have two DFAs (deterministic finite-state automata) that recognize the same language.
If you want an explicit example: Let $M_1$ be a DFA with a single state (which is accepting) and self-loops on inputs $0$ and $1$. Let $M_2$ be a DFA with two states (which are both accepting) and edges from state $s_0$ to $s_1$ on inputs $0$ and $1$, and edges from state $s_1$ to $s_0$ on inputs $0$ and $1$. They both recognize the language $\{0,1\}^*$, i.e., they are two different DFA that recognize the same language.