The Mathematics of Finite State Automata I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a brief look online, and might I emphasize the use of the word "brief" here, I am beginning to question the amount and depth of mathematics that I would cover if this were the context of my project; a point worth taking seriously, as the central aim of the project is to communicate mathematics.
At the time of writing this, my project plan seems fairly vague, detailing that I review the origins of this theory, as well as understand and investigate the properties of both finite state automata and regular languages, culminating in a consideration of Kleene's theorem. The plan is open to change at this point.
I have two questions:


*

*Can I be reassured in the weight and depth of mathematics that one could cover in this topic?

*(In relation to the "could" in the above) Are there any particular angles or avenues that one could approach the notions of finite state automata and regular languages that would be fairly/heavily grounded in mathematical theory (e.g. particular application(s) that one could build up to in the project)?
If I can add any more information/ context please ask.
 A: There is a large number of mathematical topics related to finite automata and regular languages, but to start with, I would suggest to write a clean mathematical approach to the basic notions and results, like the minimal automaton and Kleene's theorem. My first recommendation would be to avoid most of the classical books on automata theory, which are usually not written for mathematicians. 
Here is an outline of possible topics:


*

*Minimal deterministic automata
Definition of a finite deterministic automaton $(Q, A, ., q_0, F)$. I insist on using the notation $q.u$ (where $q$ is a state and $u$ is a word) instead of $\delta(q, u)$ used in most books. It leads to simple and natural formulas like $(q.u).v = q.uv$ instead of the heavy $\delta(\delta(q, u),v) = \delta(q, uv)$.$^{(1)}$.
Definition of an accessible automaton (each state can be reached form the initial state) and of a partial preorder on finite automata as follows.
Let $\mathcal{A} = (Q, A, ., q_{-}, F)$ and $\mathcal{A}' = (Q', A,
., q'_{-}, F')$ be two deterministic automata. Then $\mathcal{A}' \leqslant
\mathcal{A}$ if there is a surjective function $\varphi:Q\rightarrow
Q'$ such that $\varphi(q_{-})= q'_{-}$, $\varphi^{-1}(F')=F$ and, for
every $u\in A^*$ and $q\in Q$, $\varphi(q. u) = \varphi(q). u$. 
Given a language $L$ on the alphabet $A$ and a word $u$, let $u^{-1}L = \{v \in A^* \mid uv \in L\}$ be the right quotient of $L$ by $u$. Prove that if $L$ is regular, then $L$ has only finitely many right quotients (Nerode's lemma).
The Nerode automaton of $L$ is the deterministic automaton $\mathcal{A}(L) = (Q, A, ., L, F)$ where $Q = \{u^{-1}L \mid u \in A^*\}$, $F = \{u^{-1}L \mid u \in L\}$ and the transition function is defined, for each $a \in A$, by the formula
$$ 
  (u^{-1}L). a = a^{-1}(u^{-1}L)=(ua)^{-1}L
$$
Prove that $\mathcal{A}(L)$ recognizes $L$ and that, amongst the accessible deterministic automata recognising $L$, the Nerode automaton of $L$
is minimal for the partial order $\leqslant$. This property is much stronger than the property traditionally used to defined the minimal automaton.
If you want to go a little further, you can distinguish between complete automata ($q.a$ is always defined) and uncomplete automata $q \to q .a$ is only a partial function. There is still a mathematical definition of a minimal automaton in this case, but this is more involved. See [1, Chapter 3].
$\scriptsize ^{(1)}\text{ Just try for a minute to work on vector spaces by denoting $\delta(v,a)$ the product of a scalar $a$ by a vector $v$ ...}$


*One direction of Kleene's theorem.


From automata to regular expressions, you could use Brzozowski algebraic method using linear equations, which is based on Arden's lemma: If $K$ does not contain the empty word, then $X=K^*L$ is the unique solution of the equation $X = KX + L$ (here $+$ denotes union - again this is a more appropriate notation in a mathematical context-). 
Side remark. A physicist would write: $X = KX + L$ is equivalent to $L = X - KX = (1-K)X$ which yields $X = (1-K)^{-1}L$ and then would observe that $(1-K)^{-1} = 1 + K + K^2 + \cdots = K^*$ to conclude. Of course, neither subtractions nor inverses are defined over languages and it is a nontrivial mathematical task to justify this writing. Still, you can use this method to remember the solution...


*Replacing automata by monoids.


A monoid is a set equipped with an associative binary operation and an identity element.
A monoid $M$ recognizes a language $L$ over the alphabet $A$ if there is a monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $L = f^{-1}(P)$.
One can show that a language is regular if and only if it can be recognized by a finite monoid. Converting a deterministic finite automaton or even a nondeterministic finite automaton to a finite monoid recognizing the same language would be a possible topic.


*Syntactic monoid.


The syntactic monoid is the first step towards the algebraic theory of automata.
In the monoid approach outlined in 3, it plays the same role as the minimal automaton. The definition is not very difficult. However demonstrating the interest of this very powerful tool would require to at least state a strong result, like Schützenberger's theorem on star-free languages.


*Abstract definition of recognizable and rational subsets of a monoid.


Using the monoid approach, it is possible to extend the notion of recognizable sets to arbitrary monoids. It is also possible to extend the notion of regular expression, leading to the notion of rational set. But in general, Kleene's theorem does not extend to this setting, that is, rational and recognizable sets do not coincide in general. However, there is a nice mathematical theory around these notions.


*More advanced topics
Probably not for your project, but there are deep connections between automata and mathematics. This includes logic (more precisely finite model theory), algebra (usually noncommutative), and perhaps more surprinsingly, topology
(if you really want to impress your adviser, you may prove that the Stone dual of the set of regular languages on the alphabet $A$ is the free profinite monoid on $A$: the definitions are probably more difficult than the proof itself).
References
[1] S. Eilenberg. Automata, languages, and machines. Vol. A. Pure and Applied Mathematics, Vol. 58. Academic Press, New York, 1974. xvi+451 pp.
[2] J.-É. Pin, Finite semigroups and recognizable languages: an introduction, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), 1-32, Kluwer academic publishers, (1995). 
You can also look at Mathematical Foundations of Automata Theory, which covers most of these topics.
