0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Guildenstern
    Commented Jun 2, 2014 at 18:28
  • $\begingroup$ 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 $\endgroup$
    – Tim
    Commented Jun 2, 2014 at 18:35
  • $\begingroup$ 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. $\endgroup$
    – Guildenstern
    Commented Jun 2, 2014 at 18:37

2 Answers 2

Reset to default
3
$\begingroup$

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.

The same holds for other common families of languages, e.g., context-free languages and pushdown automata; context-sensitive languages and context-sensitive grammars.

Improve this answer
$\endgroup$
3
$\begingroup$

If there is one automaton of some particular type that accepts a given language, there are infinitely many: take any automaton and add any pattern of states that are unreachable from the start state. (In fact, you can do it by adding reachable states in all cases I can think of.)

I don't see how you can conclude from, for example, the existence of multiple pushdown automata accepting the same language, that Turing machines are the most powerful automata. In any case, it's not true: a Turing machine with an oracle for the halting problem is strictly more powerful than an ordinary Turing machine. But these oracle Turing machines cannot decide their own halting problem (same argument as for regular TMs) so Turing machines with an oracle for that halting problem are even more powerful (same argument again). And so on, ad infinitum. There is no "most powerful" class of automata.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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