Editing Automata theory (section)

==Automata==

What follows is a general definition of an automaton, which restricts a broader definition of a [[system]] to one viewed as acting in discrete time-steps, with its state behavior and outputs defined at each step by unchanging functions of only its state and input.<ref name="Arbib 1969"/>

===Informal description===
An automaton ''runs'' when it is given some sequence of ''inputs'' in discrete (individual) ''time steps'' (or just ''steps''). An automaton processes one input picked from a set of ''[[Symbol (formal)|symbols]]'' or ''letters'', which is called an ''input [[alphabet (computer science)|alphabet]]''. The symbols received by the automaton as input at any step are a sequence of symbols called ''words''. An automaton has a set of ''states''. At each moment during a run of the automaton, the automaton is ''in'' one of its states. When the automaton receives new input, it moves to another state (or ''transitions'') based on a ''transition function'' that takes the previous state and current input symbol as parameters. At the same time, another function called the ''output function'' produces symbols from the ''output alphabet'', also according to the previous state and current input symbol. The automaton reads the symbols of the input word and transitions between states until the word is read completely, if it is finite in length, at which point the automaton ''halts''. A state at which the automaton halts is called the ''final state''.

To investigate the possible state/input/output sequences in an automaton using [[formal language]] theory, a machine can be assigned a ''starting state'' and a set of ''accepting states''. Then, depending on whether a run starting from the starting state ends in an accepting state, the automaton can be said to ''accept'' or ''reject'' an input sequence. The set of all the words accepted by an automaton is called the ''language recognized by the automaton''. A familiar example of a machine recognizing a language is an [[Electronic_lock#Numerical_codes,_passwords,_and_passphrases|electronic lock]], which accepts or rejects attempts to enter the correct code.

===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.