They're like computers with extemely limited memory
The formal language of an automaton is the set of words which are mapped to final states
A finite automaton is a tuple (A, Q, q0, F, φ )
We can think of the transition function as the data of a directed graph, labeled by the letters in the alphabet A
Implicitly, we're saying that you can recursively apply the transition function, to take us from some word in A to a sequence of states From a language perspective, we only care about what the ultimate state is, corresponding to a word w ∈ A*. So we can just define the transition function to be a map φ: A* → Q that has to satisfy certain composition conditions
Then the language corresponding to the automaton is the set L = φ-1(F)
That seems far nicer
A (deterministic) finite automaton is a tuple (A, Q, F, φ) where
Now the initial state is just the data of φ(1)
Lexical analyzers
For instance, consider a programming language where the syntax says that words must be finite sequences of lower case letters and numbers, starting with a letter
The language is recognized by the automaton A = {a,b,c …, z, 0, .. 9} Q = {0, 1} F = {1}
In this case, the transition function should really be a relation In our definition, we can just replace the transition function with a multi-output map, or equivalently, φ: A* → P(Q) such that if φ(x) ⊆ φ(y) then φ(xz) ⊆ φ(yz)
Honestly, I'm pretty impressed with myself for coming up with that
L = { w | φ(w) ∩ F ≠ ∅}
Used in parsing (the second phase of compilers and interpreters)
It's basically a finite automaton plus finite memory
Automata are equivalent to formal languages.
\begin{definition}{Accepted Strings of an Automaton}{•}
Let $\mathbb{M}$ be an automaton and $w = w_1 \ldots w_n \in F(A)$. Then $w$ is accepted by $\mathbb{M}$ if there is a sequence of states $\{ x_0, \ldots, x_n \}$, such that
\begin{enumerate}
\item $x_0$ is the start state
\item $f(x_i, w_{i+1}) = x_{i+1}$
\item $x_n \in F$
\end{enumerate}
\end{definition}
\begin{definition}{Language of an Automaton}{•}
Let $\mathbb{M}$ be an automaton. Then the language of \mathbb{M} is defined to be
\begin{equation}
L(\mathbb{M}) = \{ w \mid \mathbb{M} \text { accepts } w \}.
\end{equation}
\end{definition}
| Language | Automaton |
| Regular | Finite |