You are here
Homesemiautomaton
Primary tabs
semiautomaton
A semiautomaton is basically an automaton without designated sets of starting and final states. Formally, a semiautomaton $A$ is a triple $(S,\Sigma,\delta)$ where

$\Sigma$ is a nonempty set whose elements are called input symbols, and

$\delta$ is a transition function that assigns each pair $(s,a)$ of state $s$ and input symbol $a$ a subset $\delta(s,a)$ of states in $S$.
A semiautomaton $A$ is said to be deterministic if $\delta(s,a)$ is a singleton for each $(s,a)\in S\times\Sigma$. In otherwords, $\delta$ is a function from $S\times\Sigma$ to $S$. Otherwise, it is nondeterministic. A deterministic semiautomaton is also called a state machine. A semiautomaton is said to be finite if both $S$ and $\Sigma$ are finite. A finite state machine (fsm for short) is a state machine that is finite.
A finite semiautomaton $A$ can be visualized by what is known as the state diagram $G_{A}$ of $A$. Given $A$, the state diagram can be constructed as follows: the vertices of $G_{A}$ are the states of $A$. Given two vertices $s,t$, an edge from $s$ to $t$ is constructed iff $t\in\delta(s,a)$ for some $a\in\Sigma$. The edge is then labeled $a$.
For example, let $A$ be defined as follows: $S=\{r,s,t\}$, $\Sigma=\{a,b,c\}$, and the transition function $\delta$ is given by the following table:
$a$  $b$  $c$  

$r$  $s$  $r$  $t$ 
$s$  $\varnothing$  $t$  $r$ 
$t$  $t$  $s$  $r,s$ 
Then the state diagram $G_{A}$ is given by
What we would like to do is to extend the transition function $\delta$ so it is applicable to all finite strings over $\Sigma$. This is done in two steps:

extend $\delta$ to a function $\delta^{{\prime}}:P(S)\times\Sigma\to P(S)$ via the subset construction,

extend $\delta^{{\prime}}$ to a function $\delta_{1}:P(S)\times\Sigma^{*}\to P(S)$ recursively, given by
$\delta_{1}(Q,u):=\left\{\begin{array}[]{ll}Q&\textrm{if $u=\lambda$, the empty% word}\\ \delta^{{\prime}}(Q,u)&\textrm{if $u\in\Sigma$}\\ \delta^{{\prime}}(\delta^{{\prime}}(Q,v),a)&\textrm{if $u=va$ with $v\in\Sigma% ^{*},a\in\Sigma.$}\end{array}\right.$
Without causing any confusion, we may identify $\delta_{1}$ with $\delta$. Basically, when a string $u=a_{1}a_{2}\cdots a_{n}$ is fed into a semiautomaton $A$ in state $s$, $\delta$ takes the first symbol $a_{1}$ and computes the next states $\delta(s,a_{1})$. Then it takes the next symbol $a_{2}$ and computes the next states $\delta(\delta(s,a_{1}),a_{2})$, and so on. It continues to do this until the last symbol $a_{n}$ has been consumed, and the next states corresponding to $(s,u)$ is $\delta(s,u)$. From the recursive definition above, it is not hard to see that
$\delta(Q,uv)=\delta(\delta(Q,u),v)$ 
for any $u,v\in\Sigma^{*},$ as the concatenation operation is associative.
In the case of a deterministic semiautomaton, $\delta$ is just a function $S\times\Sigma^{*}$ to $S$.
Remark. Like groups and rings, semiautomata can be considered as algebraic objects, so that concepts such as subsemiautomata and homomorphisms between semiautomata may be defined. However, unlike groups and rings, which are defined based on a single set, semiautomata are twosorted, in that two sets are needed for the definition.
References
 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
 2 M. Ito, Algebraic Theory of Automata and Languages, World Scientific (2004).
Mathematics Subject Classification
68Q70 no label found20M35 no label found03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Harshad Number by pspss
Sep 14
new problem: Geometry by parag
Aug 24
new question: Scheduling Algorithm by ncovella
new question: Scheduling Algorithm by ncovella