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

• $S$ is a non-empty set whose elements are called states
• $\Sigma$ is a non-empty 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 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=\lbrace r,s,t\rbrace$ , $\Sigma = \lbrace a, b, c\rbrace$ , and the transition function $\delta$ is given by the following table:

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': P(S)\times \Sigma \to P(S)$ via the subset construction,
• extend $\delta'$ to a function $\delta_1: P(S)\times \Sigma^*\to P(S)$ recursively, given by
  

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 two-sorted, in that two sets are needed for the definition.

Bibliography

1

A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).

2

M. Ito, Algebraic Theory of Automata and Languages, World Scientific (2004).