Automata

$ \def\Lang{\mathit{Lang}} \def\devers#1#2{\colon#1\to#2} $

A finite automaton $M$ on the finite alphabet $A$ is composed of a finite set $Q$ of states, of an initial state $q_0$, of a set $T\subseteq Q$ of terminal states and of a set $F\subseteq Q\times A\times Q$ of labelled edges or arcs corresponding to state transitions. We denote the automaton $M$ by the quadruplet $(Q,q_0,T,F)$ or sometimes by just $(Q,F)$ when, for example, $q_0$ is implicit and $T=Q$. We say of an arc $(p,a,q)$ that it leaves state $p$ and enters state $q$; state $p$ is the source of the arc, letter $a$ its label and state $q$ its target. A graphic representation of an automaton is displayed below.

The number of arcs exiting a given state is called the outgoing degree of the state. The incoming degree of a state is defined in a dual way. By analogy with graphs, the state $q$ is a successor by the letter $a$ of the state $p$ when $(p,a,q)\in F$; in the same case, we say that the pair $(a,q)$ is a labelled successor of state $p$.

A path of length $n$ in the automaton $M=(Q,q_0,T,F)$ is a sequence of $n$ consecutive arcs $\langle (p_0,a_0,p'_0),(p_1,a_1,p'_1),\dots,(p_{n-1},a_{n-1},p'_{n-1}) \rangle$ that satisfies $p'_k=p_{k+1}$ for $k=0,1,\dots,n-2$. The label of the path is the word $a_0a_1\dots a_{n-1}$, its origin the state $p_0$ and its end the state $p'_{n-1}$. A path in the automaton $M$ is successful if its origin is the initial state $q_0$ and if its end is in $T$. A word is recognised or accepted by the automaton if it is the label of a successful path. The language composed of the words recognised by the automaton $M$ is denoted by $\Lang(M)$.

An automaton $M=(Q,q_0,T,F)$ is deterministic if for every pair $(p,a)\in Q\times A$ there exists at most one state $q\in Q$ for which $(p,a,q)\in F$. In such a case, it is natural to consider the transition function $\delta\devers{Q\times A}{Q}$ of the automaton defined for every arc $(p,a,q)\in F$ by $\delta(p,a)=q$ and undefined elsewhere. The function $\delta$ merely extends to words.

It is known that any language accepted by an automaton is also accepted by a deterministic automaton and that there is a unique (up to state naming) minimal deterministic automaton accepting it.

125 Problems in Text Algorithms

Example

Automata