Is there any formal and elegant way of finding the language of a finite automaton?
For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is
$L(A) = (a \cup b)^* $
Since every input word over $\left\{a,b \right\}$ leads to the final(and only) state of the automaton.
How can we find the language accepted by an abstract automaton, with, for example, 20 states??
Best Answer
Indeed, there is an elegant way to compute this.
The process of finding the language accepted by an automaton $A = (Q,\Sigma, \delta, q_0, F)$ involves solving a system of equations over the monoid $(\Sigma, \circ, \epsilon)$ with $\epsilon$ denoting the empty word of the alphabet.
Denote as $\Xi_i$ the language recognized by the automaton $(Q, \Sigma, \delta, q_i, F)$ and $Q= \left\{q_0,..,q_n \right\}$. That is, create for each state of the initial automaton a new automaton with an initial state $q_i$, for $i=0,1,..,n$. Now denote $L_{ij}$ the language consisting of all the letters on the diagram of $A$ that start from $q_i$ and end at $q_j$. So from there there is the system
$$\Xi_i = \bigcup L_{ij} \Xi_j \cup Mi$$
where $M_i = \emptyset$ if state $i$ is not final, ${\epsilon}$ otherwise.
So to find the language of the automaton $A$ we got to solve the above system of equations and find $\Xi_0$ under the operations defined by the monoid.
To solve this system we can use the following lemma:
Lemma: Let $L.M \subset \Sigma^*$ languages. The smallest language satisfying the equation $$Z = LZ \cup M$$ is $L^* M$.
For example consider the automaton:
$A = (\left\{q_0,q_1,q_2\right\},\left\{a,b \right\},\delta, q_0,\left\{q_2 \right\})$ with the state diagram of $\delta$ as follows
The system of equations is
$$\begin{cases} \Xi_0 = a \Xi_0 \cup b \Xi_1 \\ \Xi_1 = b\Xi_0 \cup a \Xi_2 \\ \Xi_2 = (a \cup b) \Xi_0 \cup \left\{\epsilon \right\} \end{cases} $$
With substitution we obtain
$$\begin{cases} \Xi_0 = a \Xi_0 \cup b \Xi_1 \\ \Xi_1 = b \Xi_0 \cup a ((a \cup b) \Xi_0 \cup \left\{\epsilon \right\}) \end{cases} $$
$$\begin{cases} \Xi_0 = a \Xi_0 \cup b \Xi_1 \\ \Xi_1 = b \cup a ((a \cup b)) \Xi_0 \cup a) \end{cases} $$
Substituting to the first equation we get
$$ \Xi_0 = a \Xi_0 \cup b ((b \cup a ((a \cup b)) \Xi_0 \cup a) $$
$$ \Xi_0 = a \cup (b^2 \cup b a^2 \cup b a b) \Xi_0 \cup ba $$
Finally, applying our lemma
$$ \Xi_0 = (a \cup b^2 \cup b a^2 \cup b a b)^* ba $$
Thus the language accepted by the automaton is
$$L(A) = (a \cup b^2 \cup b a^2 \cup b a b)^* ba $$ as one can validate easily.