|
An automaton is a semiautomaton 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
- $(S,\Sigma,\delta)$ is a semiautomaton,
- a non-empty set $I\subseteq S$ of starting states, and
- a set $F\subseteq S$ of final states or terminating states.
A triple $(s,a,t)$ is called a transition if $t\in \delta(s,a)$ , and is written $s\stackrel{a}{\longrightarrow} t$ . The set $\delta(s,a)$ may contain more than one element (or none at all), which is why an automaton is also said to be non-deterministic. If on the other hand $\delta(s,a)$ is a singleton for every $(s,a)$ , and $I$ is a singleton, then $A$ is said to be deterministic. In a deterministic automaton, $\delta$ can be viewed as a function from $S\times \Sigma$ to $S$ .
If $S$ and $\Sigma$ are both finite, then $A$ is called a finite-state automaton, or FSA for short.
The state diagram $G_A$ of a finite-state automaton $A$ is constructed as if $A$ is being treated as 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). This is illustrated in the following 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
| |
$a$ |
$b$ |
| $\sigma$ |
$s$ |
$t$ |
| $s$ |
$\varnothing$ |
$t,s$ |
| $t$ |
$\sigma$ |
$s$ |
Then the state diagram $G_A$ is given by
An automaton works in exactly the same way as a semiautomaton in terms of reading an input word. Briefly:
when a word $u=a_1a_2 \cdots a_n$ is fed into $A$ with starting state $q$ , $A$ reads $u$ one symbol at a time from left to right, starting from $a_1$ . It reaches one of the of next states in $\delta(q,a_1)$ , say, $s$ . $A$ reads the next symbol $a_2$ , and reaches one of the next states $\delta(s,a_2)$ , and so on..., until the last symbol $a_n$ has been read. $u$ is accepted if, it is possible, upon reading the last symbol $a_n$ , a final state is reached.
Basically, this means that a word $u$ is accepted by $A$ iff $\delta(q,u)$ contains a final state. The language accepted by $A$ is the set of all words accepted by $A$ , and is denoted by $L(A)$ .
Clearly, if $F=\varnothing$ , then $L(A)=\varnothing$ .
Remark. The word ``automaton'' may be used in a context wider than the definition given above. Any computing device capable of accepting strings of symbols is termed an automaton in this wider context. The set of all accepted strings is called the language accepted by the automaton. The automata defined in this entry accept what are known as regular languages. A famous example is the Turing machine, invented by Alan Turing in 1935. Languages accepted by Turing machines are exactly the recursively enumerable languages. Other common examples of automata are: pushdown automata, which accept context-free languages; and linear bounded automata, which accept context-sensitive languages.
|
