1
$\begingroup$

Every theory has axioms and theorems derived from axioms.

How many axioms are there for automata theory? What are the axioms of automata theory?

$\endgroup$
  • 7
    $\begingroup$ I'm not sure I agree with your premise. $\endgroup$ – Yuval Filmus Feb 16 at 18:33
  • 2
    $\begingroup$ "Theory" is an English word that has meaning far beyond its technical meaning in e.g. "first-order theory" or "logical theory". The word is not being used in this technical sense there, so there is no reason to believe that there is some list of axioms. When studied formally, automata are usually defined within, e.g., set theory. Properties of these constructions are then studied. This doesn't require any special axioms. You could argue that regular expressions, for example, are a theory (in the technical sense) for finite state automata. I'm sure someone has made some "theory of automata". $\endgroup$ – Derek Elkins Feb 16 at 21:44
2
$\begingroup$

Automata theory is a broad field and researchers keep inventing new types of automata. There is even a conference series on non-classical models of automata. So it is impossible to encompass all of automata theory. For classical models such as context-free grammars, recently formalized proofs of the most basic theorems have been carried out. These are derived from first principles (these are definitions in terms of set theory). See this example for an accessible account: https://www.react.uni-saarland.de/people/hofmann/jhofBA.pdf

$\endgroup$
1
$\begingroup$

Automata theory is built on set theory, so the underlying axioms are those of the Zermelo–Fraenkel set theory (ZFC) with the axiom of choice.

$\endgroup$
  • 1
    $\begingroup$ Perhaps technically they are, but I think that especially in elementary automata theory (as seen in introductory cs courses), this precise formalization is not that relevant. (no doubt that e.g. choice is necessary in some advanced automata, but I doubt this is common) And if these axioms become relevant, so become results that do not assume them or are in contradiction with them. $\endgroup$ – Discrete lizard Apr 22 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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