| Version 33 |
Version 32 |
|
An \emph{automaton} is a state machine with two types of special states: starting states, and final states. Specifically, an automaton $A$ is is a five-tuple $(S,\Sigma,\delta,I,F)$, where
|
An \emph{automaton} is a general term for any formal model of computation. Typically, an automaton $A$ is represented as a \emph{state machine}. Specifically, $A$ is a five-tuple $(S,\Sigma,\delta,I,F)$, consisting of
|
| \begin{enumerate} |
\begin{enumerate} |
| \item |
\item |
| a non-empty set $S$ of states, |
a non-empty set $S$ of states, |
| \item |
\item |
| a non-empty set $\Sigma$ of symbols; a pair $(s,\alpha)$ of a state $s\in S$ and a symbol $\alpha \in\Sigma$ is called a \emph{configuration}, |
a non-empty set $\Sigma$ of symbols; a pair $(s,\alpha)$ of a state $s\in S$ and a symbol $\alpha \in\Sigma$ is called a \emph{configuration}, |
| \item |
\item |
| a rule $\delta$ associating every configuration $(s,\alpha)$ a subset $\delta(s,\alpha)\subseteq S$ of states; $\delta$ is called a \emph{next-state relation}, or a \emph{transition relation}, |
a rule $\delta$ associating every configuration $(s,\alpha)$ a subset $\delta(s,\alpha)\subseteq S$ of states; $\delta$ is called a \emph{next-state relation}, or a \emph{transition relation}, |
| \item |
\item |
| a non-empty set $I\subseteq S$ of \emph{starting states}, and |
a non-empty set $I\subseteq S$ of \emph{starting states}, and |
| \item |
\item |
| a set $F\subseteq S$ of \emph{final states} or \emph{terminating states}. |
a set $F\subseteq S$ of \emph{final states} or \emph{terminating states}. |
| \end{enumerate} |
\end{enumerate} |
|
|
| The following terms are typically associated with an automaton $A$: |
\textbf{Remarks}. |
| \begin{itemize} |
\begin{itemize} |
| \item |
\item |
| A triple $(s,\alpha,t)$ is called a \emph{transition} if $t\in \delta(s,\alpha)$, and is written $s\stackrel{\alpha}{\longrightarrow} t$. |
A triple $(s,\alpha,t)$ is called a \emph{transition} if $t\in \delta(s,\alpha)$, and is written $s\stackrel{\alpha}{\longrightarrow} t$. |
| \item |
\item |
| The set $\delta(s,\alpha)$ of next states may contain one, more than one, or no elements. |
The set $\delta(s,\alpha)$ of next states may contain one, more than one, or no elements. |
| \item |
\item |
| If $\delta(s,\alpha)$ is a singleton for every configuration $(s,\alpha)$, then $\delta$ can be viewed as a function (called a \emph{transition function}) from the set of configurations $S\times \Sigma$ to $S$. |
If $\delta(s,\alpha)$ is a singleton for every configuration $(s,\alpha)$, then $\delta$ can be viewed as a function (called a \emph{transition function}) from the set of configurations $S\times \Sigma$ to $S$. |
| \item |
\item |
| If $\delta:S\times \Sigma \to S$ is a function, and in addition $I$ is a singleton, then the automaton $A$ is said to be \emph{deterministic}. Otherwise, $A$ is \emph{non-deterministic}. |
If $\delta:S\times \Sigma \to S$ is a function, and in addition $I$ is a singleton, then the automaton $A$ is said to be \emph{deterministic}. Otherwise, $A$ is \emph{non-deterministic}. |
| \item |
\item |
| If $S$ and $\Sigma$ are both finite, then $A$ is called a \emph{finite-state automaton}, or \emph{FSA} for short. |
If $S$ and $\Sigma$ are both finite, then $A$ is called a \emph{finite-state automaton}, or \emph{FSA} for short. |
| \end{itemize} |
\end{itemize} |
|
|
| A finite-state automaton $A$, like a semiautomaton, may be visualized with the help of a graph called the state diagram $G_A$. The construction of $G_A$ given $A$ is exactly the same as the state diagram of a semiautomaton. In addition, a vertex corresponding to a starting state has an incoming arrow without a source, and a vertex corresponding to a final state has an outgoing arrow without a destination (alternatively, it may be represented by a double circle). |
|
|
|
| For example, let $A$ be given by $S=\lbrace \sigma, s, t\rbrace$, where $\sigma$ is the starting state, and $t$ the final state, $\Sigma=\lbrace a,b\rbrace$, with the transition function given by the following table |
|
| \begin{center} |
|
| \begin{tabular}{|c||c|c|} |
|
| \hline |
|
| & $a$ & $b$ \\ |
|
| \hline\hline |
|
| $\sigma$ & $s$ & $t$ \\ |
|
| \hline |
|
| $s$ & $\varnothing$ & $t,s$ \\ |
|
| \hline |
|
| $t$ & $\sigma$ & $s$ \\ |
|
| \hline |
|
| \end{tabular} |
|
| \end{center} |
|
|
|
| Then the state diagram $G_A$ is given by |
|
| \begin{figure}[!ht] |
|
| \centering |
|
| \scalebox{0.7}{\includegraphics{automaton.eps}} |
|
| \end{figure} |
|
|
|
| Basically, an automaton $A$ works as follows: |
Basically, an automaton $A$ works as follows: |
|
|
|
when a symbol $\alpha$ is fed into $A$ with starting state $q$, a set $\delta(q,\alpha)$ of next states is reached. If one of the next states is a final state, then $a$ is said to be \emph{accepted} by $A$. More generally, $A$ can read strings of symbols, and the way for $A$ reads a string $a=\alpha_1\alpha_2\cdots \alpha_n$ of symbols works as follows: |
| \begin{quote} |
\begin{quote} |
| when a symbol $\alpha$ is fed into $A$ with starting state $q$, a set $\delta(q,\alpha)$ of next states is reached. If one of the next states is a final state, then $a$ is said to be \emph{accepted} by $A$. |
when $a$ is fed into $A$ with starting state $q$, $A$ reads the leftmost symbol $\alpha_1$ first and it reaches the set of next states $\delta(q,\alpha_1)$. Take any of the possible next states, say, $s\in \delta(q,\alpha_1)$, $A$ reads the next symbol $\alpha_2$, and reaches the set of next states $\delta(s,\alpha_2)$, and so on..., until the last symbol $\alpha_n$ has been read. |
| \end{quote} |
|
| More generally, $A$ can read strings of symbols, and the way for $A$ reads a string $u=\alpha_1\alpha_2\cdots \alpha_n$ of symbols works as follows: |
|
| \begin{quote} |
|
| when $u$ is fed into $A$ with starting state $q$, $A$ reads the leftmost symbol $\alpha_1$ first and it reaches the set of next states $\delta(q,\alpha_1)$. Take any of the possible next states, say, $s\in \delta(q,\alpha_1)$, $A$ reads the next symbol $\alpha_2$, and reaches the set of next states $\delta(s,\alpha_2)$, and so on..., until the last symbol $\alpha_n$ has been read. $u$ is accepted if, upon reading the last symbol $\alpha_n$, $A$ reaches a final state. |
|
| \end{quote} |
\end{quote} |
|
More formally, the set-valued function $\delta$ defined on $S\times \Sigma$ can be extended to a function $\delta^*$ defined on $P(S)\times \Sigma^*$, where $P(S)$ is the powerset of $S$ and $\Sigma^*$ is the Kleene star of $\Sigma$, as follows: for $u\in \Sigma^*$,
|
More formally, the set-valued function $\delta$ defined on $S\times \Sigma$ can be extended to a function $\delta^*$ defined on $P(S)\times \Sigma^*$, where $P(S)$ is the powerset of $S$ and $\Sigma^*$ is the Kleene star of $\Sigma$, as follows: for $a\in \Sigma^*$,
|
| \begin{itemize} |
\begin{itemize} |
|
\item $\delta^*(\varnothing,u):=\varnothing$
|
\item $\delta^*(\varnothing,a):=\varnothing$
|
|
\item for any non-empty subset $Q\subseteq S$, $$\delta^*(Q,u):=\bigcup_{s\in Q} \delta^*(\lbrace s\rbrace,u)$$
|
\item for any non-empty subset $Q\subseteq S$, $$\delta^*(Q,a):=\bigcup_{s\in Q} \delta^*(\lbrace s\rbrace,a)$$
|
| \item for a singleton $\lbrace s\rbrace$, $\delta^*$ is defined inductively: |
\item for a singleton $\lbrace s\rbrace$, $\delta^*$ is defined inductively: |
| \begin{displaymath} |
\begin{displaymath} |
|
\delta^*(\lbrace s\rbrace ,u):= \left\{
|
\delta^*(\lbrace s\rbrace ,a):= \left\{
|
| \begin{array}{ll} |
\begin{array}{ll} |
|
\lbrace s\rbrace & \textrm{if $u=\lambda$, the empty word,}\\
|
\lbrace s\rbrace & \textrm{if $a=\lambda$, the empty word,}\\
|
|
\delta(s,u) & \textrm{if $u\in \Sigma$,}\\
|
\delta(s,a) & \textrm{if $a\in \Sigma$,}\\
|
|
\delta^*(\delta^*(\lbrace s\rbrace,v),\alpha) & \textrm{if $u=v\alpha$, where $v\in \Sigma^*$ and $\alpha\in \Sigma$.}
|
\delta^*(\delta^*(\lbrace s\rbrace,b),\alpha) & \textrm{if $a=b\alpha$, where $b\in \Sigma^*$ and $\alpha\in \Sigma$.}
|
| \end{array} |
\end{array} |
| \right. |
\right. |
| \end{displaymath} |
\end{displaymath} |
| \end{itemize} |
\end{itemize} |
|
|
|
By abuse of language, we write $\delta$ for $\delta^*$ and $\delta(s,u)$ for $\delta(\lbrace s\rbrace,u)$.
|
By abuse of language, we write $\delta$ for $\delta^*$ and $\delta(s,a)$ for $\delta(\lbrace s\rbrace,a)$.
|
|
|
|
In essence, $\delta$ becomes a function from $P(S)\times \Sigma^*$ to $P(S)$. A string $u\in \Sigma^*$ is \emph{accepted} by $A$ if for some starting state $q$, $\delta(q,u)$ contains a final state. The ability to accept finite strings is the reason why an automaton is also referred to as a (string) \emph{acceptor}. The subset of $\Sigma^*$ of all string accepted by $A$ is called the \emph{language accepted by} the automaton $A$, and is denoted by $$L(A).$$
|
In essence, $\delta$ becomes a function from $P(S)\times \Sigma^*$ to $P(S)$. A string $a\in \Sigma^*$ is \emph{accepted} by $A$ if for some starting state $q$, $\delta(q,a)$ contains a final state. The ability to accept finite strings is the reason why an automaton is also referred to as a (string) \emph{acceptor}. The subset of $\Sigma^*$ of all string accepted by $A$ is called the \emph{language accepted by} the automaton $A$, and is denoted by $$L(A).$$
|
| Clearly, if $F=\varnothing$, then $L(A)=\varnothing$. Also, if $I\cap F\ne \varnothing$, then $\lambda \in L(A)$. |
Clearly, if $F=\varnothing$, then $L(A)=\varnothing$. Also, if $I\cap F\ne \varnothing$, then $\lambda \in L(A)$. |
|
|
| %A state transition usually has some rules associated with it that govern when the transition may occur, and are able to remove symbols from the input string. An automaton may even have some sort of data structure associated with it, besides the input string, with which it may interact. |
%A state transition usually has some rules associated with it that govern when the transition may occur, and are able to remove symbols from the input string. An automaton may even have some sort of data structure associated with it, besides the input string, with which it may interact. |
|
|
| \textbf{Remark}. The word ``automaton'' may be used in a context wider than the definition given above. It is customary to sometimes call an automaton any computing device capable of accepting strings of symbols. A famous example is the \PMlinkname{Turing machine}{TuringMachine2}, invented by Alan Turing in 1935. Languages accepted by Turing machines are exactly the recursively enumerable languages. |
A famous automaton is the \PMlinkname{Turing machine}{TuringMachine2}, invented by Alan Turing in 1935. |
|
It consists of a (usually infinitely long) tape, capable of holding symbols from some alphabet, and a pointer to the current location in the tape. There is also a finite set of states, and transitions between these states, that govern how the tape pointer is moved and how the tape is modified. Each state transition is labelled by a symbol in the tape's alphabet, and also has associated with it a replacement symbol and a direction to move the tape pointer (either left or right). |
| %It consists of a (usually infinitely long) tape, capable of holding symbols from some alphabet, and a pointer to the current location in the tape. There is also a finite set of states, and transitions between these states, that govern how the tape pointer is moved and how the tape is modified. Each state transition is labelled by a symbol in the tape's alphabet, and also has associated with it a replacement symbol and a direction to move the tape pointer (either left or right). |
|
|
|
|
%At each iteration, the machine reads the current symbol from the tape. If a transition can be found leading from the current state that is labelled by the current symbol, it is ``executed.'' Execution of the transition consists of writing the transition's replacement symbol to the tape, moving the tape pointer in the direction specified, and making the state pointed to by the transition the new current state.
|
At each iteration, the machine reads the current symbol from the tape. If a transition can be found leading from the current state that is labelled by the current symbol, it is ``executed.'' Execution of the transition consists of writing the transition's replacement symbol to the tape, moving the tape pointer in the direction specified, and making the state pointed to by the transition the new current state. |
|
|
| %There are many variations of this model that are all called Turing machines, but fundamentally they all model the same set of possible computations. This abstract construct is very useful in computability theory. |
%There are many variations of this model that are all called Turing machines, but fundamentally they all model the same set of possible computations. This abstract construct is very useful in computability theory. |
|
|
|
Other common examples of automata are: finite automaton, which accept regular languages; pushdown automata, which accept context-free languages; and linear bounded automata, which accept context-sensitive languages.
|
Other automata prove useful in the area of formal languages. Any context-free language may be represented by a pushdown automaton, and any regular language can be represented by a deterministic or non-deterministic finite automaton.
|
