Automata theory

Automata theory is the study of <a href="/facts/Abstract_machine/zuC4RKLn">abstract machines</a> and <a href="/facts/Automaton/SXtErQr2">automata</a>, as well as the <a href="/facts/Computational_problem/jQ7bYUVh">computational problems</a> that can be solved using them. It is a theory in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a> with close connections to <a href="/facts/Cognitive_science/8qoggl7r">cognitive science</a> and <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>. The word automata comes from the <a href="/facts/Greek_language/pzDd6eIz">Greek</a> word αὐτόματος, which means "self-acting, self-willed, self-moving". An <a href="/facts/Automaton/SXtErQr2">automaton</a> (automata in plural) is an abstract self-propelled <a href="/facts/Computing_device/SQe1aK05">computing device</a> which follows a predetermined sequence of operations automatically. An automaton with a finite number of <a href="/facts/State_(computer_science)/4Yu8xXHS">states</a> is called a finite automaton (FA) or <a href="/facts/Finite-state_machine/GMusWd0a">finite-state machine</a> (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of <a href="/facts/State_(computer_science)/4Yu8xXHS">states</a> (represented in the figure by circles) and <a href="/facts/Transition_(computer_science)/sgSMeVDd">transitions</a> (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its <a href="/facts/Transition_table/eK0E4j8R">transition function</a>, which takes the previous state and current input symbol as its <a href="/facts/Parameter_(computer_programming)/LcuLbbSq">arguments</a>.
Automata theory is closely related to <a href="/facts/Formal_language/crDTyP8q">formal language</a> theory. In this context, automata are used as finite representations of formal languages that may be infinite. Automata are often classified by the class of formal languages they can recognize, as in the <a href="/facts/Chomsky_hierarchy/tUYCL00R">Chomsky hierarchy</a>, which describes a nesting relationship between major classes of automata. Automata play a major role in the <a href="/facts/Theory_of_computation/xYJd2YeI">theory of computation</a>, <a href="/facts/Compiler_construction/WNfCDFJe">compiler construction</a>, <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a>, <a href="/facts/Parsing/nRKB01S3">parsing</a> and <a href="/facts/Formal_verification/BYD4GnJR">formal verification</a>.

Automata theory open-in-new

Automata theory