automata

References

Summary

They're like computers with extemely limited memory

Types

The formal language of an automaton is the set of words which are mapped to final states

Finite Automata

Definition

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

My Definition

A (deterministic) finite automaton is a tuple (A, Q, F, φ) where

Now the initial state is just the data of φ(1)

Examples

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}

Non-Deterministic

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 ≠ ∅}

Push-Down Automata

Used in parsing (the second phase of compilers and interpreters)

It's basically a finite automaton plus finite memory

Language of an Automaton

Automata are equivalent to formal languages.

Definitions

Accepted Language

\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}

Language of an Automaton

\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}

Types of Languages

Language Automaton
Regular Finite

context-free grammar