Editing Automata theory (section)

===Formal definition===

;Automaton

:An automaton can be represented formally by a [[N-tuple|quintuple]] <math>M = \langle \Sigma, \Gamma, Q, \delta, \lambda \rangle</math>, where:
:* <math>\Sigma</math> is a finite set of ''symbols'', called the ''input alphabet'' of the automaton,
:* <math>\Gamma</math> is another finite set of symbols, called the ''output alphabet'' of the automaton,
:* <math>Q</math> is a set of ''states'',
:* <math>\delta</math> is the ''next-state function'' or ''transition function'' <math>\delta : Q \times \Sigma \to Q</math> mapping state-input pairs to successor states,
:* <math>\lambda</math> is the ''next-output function'' <math>\lambda : Q \times \Sigma \to \Gamma</math> mapping state-input pairs to outputs.
:If <math>Q</math> is finite, then <math>M</math> is a [[finite automaton]].<ref name="Arbib 1969"/>

;Input word
:An automaton reads a finite [[Word (mathematics)|string]] of symbols <math>a_1a_2...a_n</math>, where <math>a_i \in \Sigma</math>, which is called an ''input word''. The set of all words is denoted by <math>\Sigma^*</math>.

;Run
:A sequence of states <math>q_0,q_1,...,q_n</math>, where <math>q_i \in Q</math> such that <math>q_i = \delta(q_{i-1}, a_i)</math> for <math>0 < i \le n</math>, is a ''run'' of the automaton on an input <math>a_1a_2...a_n \in \Sigma^*</math> starting from state <math>q_0</math>. In other words, at first the automaton is at the start state <math>q_0</math>, and receives input <math>a_1</math>. For <math>a_1</math> and every following <math>a_i</math> in the input string, the automaton picks the next state <math>q_i</math> according to the transition function <math>\delta(q_{i-1},a_i)</math>, until the last symbol <math>a_n</math> has been read, leaving the machine in the ''final state'' of the run, <math>q_n</math>. Similarly, at each step, the automaton emits an output symbol according to the output function <math>\lambda(q_{i-1},a_i)</math>.

:The transition function <math>\delta</math> is extended inductively into <math>\overline\delta: Q \times \Sigma^* \to Q</math> to describe the machine's behavior when fed whole input words. For the empty string <math>\varepsilon</math>, <math>\overline\delta(q, \varepsilon) = q</math> for all states <math>q</math>, and for strings <math>wa</math> where <math>a</math> is the last symbol and <math>w</math> is the (possibly empty) rest of the string, <math>\overline\delta(q, wa) = \delta(\overline\delta(q,w),a)</math>.<ref name="structure theory"/> The output function <math>\lambda</math> may be extended similarly into <math>\overline\lambda(q,w)</math>, which gives the complete output of the machine when run on word <math>w</math> from state <math>q</math>.
;Acceptor

:In order to study an automaton with the theory of [[formal languages]], an automaton may be considered as an ''acceptor'', replacing the output alphabet and function <math>\Gamma</math> and <math>\lambda</math> with 
:* <math>q_0 \in Q</math>, a designated ''start state'', and
:* <math>F</math>, a set of states of <math>Q</math> (i.e. <math>F \subseteq Q</math>) called ''accept states''. 
:This allows the following to be defined:

;Accepting word
:A word <math>w = a_1a_2...a_n \in \Sigma^*</math> is an ''accepting word'' for the automaton if <math>\overline\delta(q_0,w) \in F</math>, that is, if after consuming the whole string <math>w</math> the machine is in an accept state.

;Recognized language
:The language <math>L \subseteq \Sigma^*</math> ''recognized'' by an automaton is the set of all the words that are accepted by the automaton, <math>L = \{w \in \Sigma^* \ |\  \overline\delta(q_0,w) \in F\}</math>.<ref>{{cite arXiv
 | last       = Moore
 | first      = Cristopher
 | title      = Automata, languages, and grammars
 | class      = cs.CC
 | date       = July 31, 2019
 | eprint = 1907.12713
 }}</ref>

;Recognizable languages
:The [[recognizable language]]s are the set of languages that are recognized by some automaton. For ''finite automata'' the recognizable languages are [[regular language|regular languages]]. For different types of automata, the recognizable languages are different.