The language recognized by an automaton is defined as the set of strings that ar

Question

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)?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.