Introduction to Automata Theory

Here, we introduce the field of automata theory.

The most general notion of abstract automaton is called a state transition machine (STM), a formalism used to model machines or computations by a 3-tuple (L, S, T):

• L is a linguistic structure symbolising the input that will get manipulated by the machine as well as possible output.
• S is a state structure with a set of states Q, a single starting state in Q and a set of final states in Q.
• T is an action structure containing a set of labels and a transition function, modelling the behaviour of the machine. That is, given a state in Q and specific constraints from a label (input/output symbols, costs, capacities, probabilities, etc.), the function will derive which states the machine should switch to. 

  Note that there are countably many ways to define a STM, and the literature on STMs is relatively poor and inconsistent. Suffice to say that STMs are a blueprint for constructing any form of automata.

   On the other hand, there are uncountably many different types of automata and, much to our despair, there is no unifying classification for all of them...

   Automata can then be organised by which machinery or dynamic system they are defined to model (cells - cellular automata, neurons - neural nets, computation - Turing machines, stochastic languages - probabilistic automata, etc.); or by the extent of their computational power, which is reflected by how many algorithms they can simulate or, equivalently, how many languages they can accept:

• Finite State Machines/Automata (FSM/FSA) accept regular languages.
• Pushdown Automata (PDA) accept context-free languages.
• Linear Bounded Automata (LBA) accept context-sensitive languages.
• Turing Machines (TM), including quantum TMs, accept recursively enumerable languages.
• Stream Automata (\omega-Automata) accept \omega-languages.
• Inductive Turing Machines (ITM) accept super-recursive languages.

  In the following segment we will choose to focus on finite-state automata, that is: machines with string input, that will parse their input character by character by changing states depending on their transition functions and eventually (since strings are finite) halt; the string will be accepted if the automaton halts in an accepting state and rejected otherwise.

An FSA is a 5-tuple (Q, \Sigma, \delta, q_0, F), where:

• Q is a finite set of states
• \Sigma is a finite alphabet
• \delta is a transition function: Q x \Sigma -> Q or P(Q) (where P(Q) is the powerset of Q)
• q_0 is the start state
• F is the set of accepting states

FSAs are characterised by having finite memory that depends only on the finite number of states the automaton can reach. They differ on the form of their transition function:

• Deterministic FSA (DFSA): \delta : Q x \Sigma -> Q
• Moore machine: \delta : Q -> Q (next state depends only on current state)
• Mealy machine: \delta : Q x \Sigma -> Q (next state depends on input)
  
• Non-deterministic FSA (NFSA): \delta : Q x \Sigma -> P(Q)

  FSAs can only be in a single state at once (like most non-quantum automata): the state in which a DFSA is, is deterministic (we know which state it is in with a 1 probability), the state in which an NFSA is, is non-deterministic (we don't know which state it is in, it could be in any state within the element of P(Q) returned by \delta). An NFSA will accept an input if it could be in an accepting state.

  Notice that the transition function for NFSAs differs by the fact that its range is the powerset of the range for that of DFSAs; thus it is possible to model any NFSA with a DFSA (the reverse is trivial), but doing so requires a number of states bounded by the cardinality of the powerset of the states in the NFSA - recall that we proved it to be 2^{#states in NFSA}. Hence non-determinism can be advantageous for its complexity aspect (rather than its computability aspect).

  There is a one-to-one correspondence between all languages that can be formed from a regular expression and languages that can be accepted by an FSA, namely both these classes of languages are equivalent - they are the class of regular languages: 

•  prove L(R) C L(M), use the recursive definition of regular expressions to show that FSAs can be built to accept any language induced by the base cases and by construction.
•  prove L(M) C L(R), use state elimination on an arbitrary FSA: show how a regular expression can express any intermediary state of the FSA, thus how any FSA can be reduced to a single start state with regular expression transitions to accepting states. The union of all these REs is the regexp generating the laguage the FSA accepts.
•  conclude that L(M) = L(R), that is: REs and FSAs are equivalently suitable to generate/accept any regular language.

  We provided a small foundation in automata theory, which provides us with powerful formalisms to model computations. We also briefly had a glance at the standard formalism of Computation: Turing Machines, based on automata (using the same STM construct). We tentatively extrapolate our remark about FSAs being as powerful a formalism as REs, to TMs being as powerful a formalism as another formalism for Computation, the Lambda-Calculus.