# On the Theory of Stochastic Automata

Merve Nur Cakir, Mehwish Saleemi, Karl-Heinz Zimmermann111Email:
<EMAIL_ADDRESS>
Department of Computer Engineering
Hamburg University of Technology
21071 Hamburg, Germany

###### Contents

  1. 1 Introduction
  2. 2 Stochastic Automata
  3. 3 Equivalence
  4. 4 Reduction
  5. 5 Minimality
  6. 6 Coverings
  7. 7 Observability and Determinism
  8. 8 Stochastic Mealy and Moore Automata
  9. 9 Stochastic Acceptors
  10. Bibliography

##  Chapter 1 Introduction

The theory of discrete stochastic systems has been initiated by the work of
Shannon [8] and von Neumann [4]. While Shannon has considered memory-less
communication channels and their generalization by introducing states, von
Neumann has studied the synthesis of reliable systems from unreliable
components. The fundamental work of Rabin and Scott [6] about deterministic
finite-state automata has led to two generalizations. First, the
generalization of transition functions to conditional distributions studied by
Carlyle [2] and Starke [9]. This in turn has led to a generalization of
discrete-time Markov chains in which the chains are governed by more than one
transition probability matrix. Second, the generalization of regular sets by
introducing stochastic automata as described by Rabin [5]. Stochastic automata
are well-investigated [3].

This report provides a short introduction to stochastic automata based on the
valuable book of Claus [3]. This includes the basic topics of the theory of
stochastic automata: equivalence, minimalization, reduction, coverings,
observability, and determinism. Then stochastic versions of Mealy and Moore
automata are studied and finally stochastic language acceptors are considered
as a generalization of nondeterministic finite-state acceptors.

##  Chapter 2 Stochastic Automata

Stochastic automata are abstract machines with input and output behavior. Such
automata are also called transducers. A stochastic automaton can be viewed as
an extension of a nondeterministic automaton with probabilistic transitions.

A stochastic automaton (SA) is a quadruple $A=(S,\Sigma,\Omega,p)$, where

  * •

$S$ is a nonempty finite set of states,

  * •

$\Sigma$ is an alphabet of input symbols,

  * •

$\Omega$ is an alphabet of output symbols, and

  * •

for each pair $(a,s)\in\Sigma\times S$, $p(\cdot,\cdot\mid a,s)$ is a
conditional probability distribution on $\Omega\times S$.

Note that a conditional probability distribution $p(\cdot,\cdot\mid a,s)$ on
$\Omega\times S$ consists of nonnegative numbers $p(b,s^{\prime}\mid a,s)$ for
all $s^{\prime}\in S$ and $b\in\Omega$ such that

$\displaystyle\sum_{b\in\Omega}\sum_{s^{\prime}\in S}p(b,s^{\prime}\mid
a,s)=1,\quad a\in\Sigma,s\in S.$ (2.1)

Given a conditional probability distribution $p(\cdot,\cdot\mid a,s)$ on
$\Omega\times S$, we define a conditional probability distribution
$\hat{p}(\cdot,\cdot\mid x,s)$ with $x\in\Sigma^{*}$ and $s\in S$ on
$\Omega^{*}\times S$ recursively as follows.

  * •

For all $s,s^{\prime}\in S$,

$\displaystyle\hat{p}(\epsilon,s^{\prime}\mid\epsilon,s)=\left\\{\begin{array}[]{ll}1&\mbox{if
}s=s^{\prime},\\\ 0&\mbox{if }s\neq s^{\prime},\end{array}\right.$ (2.4)

where $\epsilon$ denotes both the empty word in $\Sigma^{*}$ and $\Omega^{*}$.

  * •

For all $s,s^{\prime}\in S$, $x\in\Sigma^{*}$, and $y\in\Omega^{*}$ with
$|x|\neq|y|$,

$\displaystyle\hat{p}(y,s^{\prime}\mid x,s)=0.$ (2.5)

  * •

For all $s,s^{\prime}\in S$, $a\in\Sigma$, $x\in\Sigma^{*}$, $b\in\Omega$, and
$y\in\Omega^{*}$,

$\displaystyle\hat{p}(yb,s^{\prime}\mid xa,s)=\sum_{t\in S}\hat{p}(y,t\mid
x,s)\cdot p(b,s^{\prime}\mid a,t).$ (2.6)

######  Proposition 2.1.

For each pair $(x,s)\in\Sigma^{*}\times S$, $\hat{p}(\cdot,\cdot\mid x,s)$ is
a conditional probability distribution on $\Omega^{*}\times S$.

Therefore, for each pair $(x,s)\in\Sigma^{*}\times S$,

$\displaystyle\sum_{y\in\Omega^{*}}\sum_{s^{\prime}\in S}p(y,s^{\prime}\mid
x,s)=1.$ (2.7)

A stochastic automaton works serially and synchronously. It reads an input
word symbol by symbol and after reading an input symbol it emits an output
symbol and transits into another state. More precisely, if the automaton
starts in state $s$ and reads the word $x$, then with probability
$\hat{p}(y,s^{\prime}\mid x,s)$ it will end in state $s^{\prime}$ emitting the
word $y$ by taking all intermediate states into account.

Note that the measures $p$ and $\hat{p}$ coincide on the set $\Omega\times
S\times\Sigma\times S$ if we put $x=y=\epsilon$ in (2.6). Therefore, we will
write $p$ instead of $\hat{p}$.

######  Proposition 2.2.

For all $x,x^{\prime}\in\Sigma^{*}$, $y,y^{\prime}\in\Omega^{*}$, and
$s,s^{\prime}\in S$ with $|x|=|y|$,

$p(yy^{\prime},s^{\prime}\mid xx^{\prime},s)=\sum_{t\in S}p(y,t\mid x,s)\cdot
p(y^{\prime},s^{\prime}\mid x^{\prime},t).$

###### Proof.

First, if $|x^{\prime}|\neq|y^{\prime}|$, then
$|xx^{\prime}|\neq|yy^{\prime}|$ and so both sides are zero by (2.5). Second,
if $x^{\prime}=\epsilon=y^{\prime}$, then both sides are equal to
$p(y,s^{\prime}\mid x,s)$ by (2.4).

Third, if $x^{\prime}\in\Sigma$ and $y^{\prime}\in\Omega$, then both sides are
equal by (2.6). Finally, suppose the assertion holds for words of length
$|x^{\prime}|=|y^{\prime}|\leq k$ for some $k\geq 1$. Then consider words
$x^{\prime}a$ and $y^{\prime}b$ of length $k+1$, where $a\in\Sigma$ and
$b\in\Omega$. We have

$\displaystyle p(yy^{\prime}b,s^{\prime}\mid xx^{\prime}a,s)$ $\displaystyle=$
$\displaystyle\sum_{t\in S}p(yy^{\prime},t\mid xx^{\prime},s)\cdot
p(b,s^{\prime}\mid a,t),\quad\mbox{by~{}(\ref{e-SA-phat3})},$ $\displaystyle=$
$\displaystyle\sum_{t\in S}\sum_{t^{\prime}\in S}p(y,t^{\prime}\mid
x,s)p(y^{\prime},t\mid x^{\prime},t^{\prime})\cdot p(b,s^{\prime}\mid
a,t),\;\mbox{by induction},$ $\displaystyle=$
$\displaystyle\sum_{t^{\prime}\in S}p(y,t^{\prime}\mid x,s)\sum_{t\in
S}p(y^{\prime},t\mid x^{\prime},t^{\prime})\cdot p(b,s^{\prime}\mid a,t)$
$\displaystyle=$ $\displaystyle\sum_{t^{\prime}\in S}p(y,t^{\prime}\mid
x,s)\cdot p(y^{\prime}b,s^{\prime}\mid
x^{\prime}a,t^{\prime}),\quad\mbox{by~{}(\ref{e-SA-phat3})}.$

∎

The behavior of a stochastic automaton can be described by probability
matrices. To see this, let $A$ be a stochastic automaton with state set
$S=\\{s_{1},\ldots,s_{n}\\}$. For each pair of input and output symbols
$a\in\Sigma$ and $b\in\Omega$, put

$\displaystyle p_{ij}(b\mid a)=p(b,s_{j}\mid a,s_{i}),\quad 1\leq i,j\leq n,$
(2.8)

and define the real-valued $n\times n$ matrix

$\displaystyle P(b\mid a)=(p_{ij}(b\mid a))_{1\leq i,j\leq n}.$ (2.9)

Note that the matrix $P(b\mid a)$ is substochastic, i.e., it is a square
matrix with nonnegative entries and by (2.7) each row adds up to at most 1.
The elements of $P(b\mid a)$ provide the transition probabilities between the
states if the symbol $a$ is read and the symbol $b$ is emitted. This
definition can be extended to strings of input and output symbols. For this,
note that by (2.4) we have

$\displaystyle P(\epsilon\mid\epsilon)=I_{n},$ (2.10)

where $I_{n}$ is the $n\times n$ unit matrix. Moreover, if $x\in\Sigma^{*}$
and $y\in\Omega^{*}$ with $|x|\neq|y|$, then by (2.5) we have

$\displaystyle P(x\mid y)=O_{n},$ (2.11)

where $O_{n}$ is the $n\times n$ zero matrix. Furthermore, if $a\in\Sigma$,
$x\in\Sigma^{*}$, $b\in\Omega$, and $y\in\Omega^{*}$, then by (2.6) we have

$\displaystyle P(yb\mid xa)=P(y\mid x)\cdot P(b\mid a).$ (2.12)

By Prop. 2.2 and the associativity of matrix multiplication, we obtain the
following.

######  Proposition 2.3.

For all $x,x^{\prime}\in\Sigma^{*}$ and $y,y^{\prime}\in\Omega^{*}$ with
$|x|=|y|$,

$P(yy^{\prime}\mid xx^{\prime})=P(y\mid x)\cdot P(y^{\prime}\mid x^{\prime}).$

It follows by induction that if $x=x_{1}\ldots x_{k}\in\Sigma^{*}$ and
$y=y_{1}\ldots y_{k}\in\Omega^{*}$, then

$\displaystyle P(y\mid x)=P(y_{1}\mid x_{1})\cdots P(y_{k}\mid x_{k}).$ (2.13)

######  Proposition 2.4.

Each stochastic automaton $A$ is uniquely characterized by the collection of
substochastic matrices

$\\{P(b\mid a)\mid a\in\Sigma,b\in\Omega\\}.$

For each input word $x\in\Sigma^{*}$, the matrix

$P(x)=\sum_{y\in\Omega^{*}}P(y\mid x)$

is (row) stochastic, i.e., each row sums up to $1$.

###### Proof.

The substochastic matrices $P(b\mid a)$ with $a\in\Sigma$ and $b\in\Omega$
describe the conditional probabilities of the automaton and so characterize
the automaton uniquely.

By (2.1), the matrix $P(a)=\sum_{b\in\Omega}P(b\mid a)$ is stochastic for each
input symbol $a\in\Sigma$. Moreover, the matrix
$P(\epsilon)=P(\epsilon\mid\epsilon)=I_{n}$ is stochastic. Since the
multiplication of stochastic matrices is again a stochastic matrix, by (2.13)
the matrix $P(x)$ is stochastic for each $x\in\Sigma^{*}$. ∎

  * Example 1.

Consider the stochastic automaton $A=(\\{s_{1},s_{2}\\},\\{a\\},\\{b\\},p)$
with conditional probabilities

$p(b,s_{1}\mid a,s_{1})=\frac{2}{3},\quad p(b,s_{2}\mid
a,s_{1})=\frac{1}{3},\quad\mbox{and}\quad p(b,s_{2}\mid a,s_{2})=1.$

The automaton is given by the state diagram in Fig. 2.1. The corresponding
(substochastic) matrix is

$P(a)=P(b\mid a)=\left(\begin{array}[]{cc}\frac{2}{3}&\frac{1}{3}\\\
0&1\end{array}\right).$

Thus for each integer $k\geq 1$,

$P(a^{k})=\left(\begin{array}[]{cc}\frac{2^{k}}{3^{k}}&\frac{3^{k}-2^{k}}{3^{k}}\\\
0&1\end{array}\right).$

$\diamondsuit$

$\textstyle{s_{1}}$$\scriptstyle{a,b:2/3}$$\scriptstyle{a,b:1/3}$$\textstyle{s_{2}}$$\scriptstyle{a,b:1}$

Figure 2.1: State diagram of $A$.

For each input word $x\in\Sigma^{*}$, the stochastic matrix $P(x)$ can be
viewed as generating a discrete-time Markov chain. Thus the behavior of a
stochastic automaton is an interleaving of Markov chains each of which
corresponding to a single input symbol.

  * Example 2.

(Communication channels) A binary symmetric channel (BSC) introduced by Claude
Shannon (1948) is a common communication channel in coding theory. A BSC with
crossover probability $p$ is a binary input, binary output channel that flips
the input bit with probability $p$. A BSC is memoryless and characterized by
the conditional probabilities

$\displaystyle{\mathbb{P}}(Y=0\mid X=0)$ $\displaystyle=$ $\displaystyle 1-p,$
$\displaystyle{\mathbb{P}}(Y=0\mid X=1)$ $\displaystyle=$ $\displaystyle p,$
$\displaystyle{\mathbb{P}}(Y=1\mid X=0)$ $\displaystyle=$ $\displaystyle p,$
$\displaystyle{\mathbb{P}}(Y=1\mid X=1)$ $\displaystyle=$ $\displaystyle 1-p,$

where the crossover probability lies between $0$ and $\frac{1}{2}$ (Fig. 2.2).

An alternative to the more idealized binary symmetric channel is the
arbitrarily varying channel (AVC) which is more realistic for network models.
An AVC has an input alphabet $\Sigma$, an output alphabet $\Omega$, and a
state set $S$. A symbol over the input alphabet is transmitted and at the
other end a symbol over the output alphabet is received. During transmission,
the state in the set $S$ can vary arbitrarily at each time step. The
conditional probabilities of an AVC are defined as

$p(b,s^{\prime}\mid a,s)=p^{\prime}(b\mid a,s)\cdot
p^{\prime\prime}(s^{\prime}\mid s).$

where $p^{\prime}(b\mid a,s)$ is the conditional probability of receiving the
symbol $b$ when the symbol $a$ has been transmitted in state $s$, and
$p^{\prime\prime}(s^{\prime}\mid s)$ is the conditional probability of moving
from state $s$ to state $s^{\prime}$. $\diamondsuit$

$\textstyle{0}$$\scriptstyle{1-p}$$\scriptstyle{p}$$\textstyle{0}$$\textstyle{1}$$\scriptstyle{1-p}$$\scriptstyle{p}$$\textstyle{1}$

Figure 2.2: Binary symmetric channel.

##  Chapter 3 Equivalence

In the following, the capabilities of stochastic automata will be compared.
Intuitively, two stochastic automata have the same performance if they exhibit
the same input-output behavior.

More concretely, let $A=(S,\Sigma,\Omega,p)$ be a stochastic automaton with
state set $S=\\{s_{1},\ldots,s_{n}\\}$. The output behavior of the automaton
being in state $s_{i}\in S$, reading the symbol $a\in\Sigma$ and emitting the
symbol $y\in\Omega$ is given by the marginal probability

$\displaystyle\eta_{i}(b\mid a)=\sum_{s\in S}p(b,s\mid a,s_{i}).$ (3.1)

Take the column vector of marginals

$\displaystyle\eta(b\mid a)=\left(\begin{array}[]{c}\eta_{1}(b\mid a)\\\
\vdots\\\ \eta_{n}(b\mid a)\end{array}\right).$ (3.5)

Thus $\eta(b\mid a)$ is the vector of row sums of the substochastic matrix
$P(b\mid a)$. Equivalently, if $\mbox{\boldmath$1$}_{n}$ denotes the all-one
vector of length $n$, we have

$\displaystyle\eta(b\mid a)=P(b\mid a)\cdot\mbox{\boldmath$1$}_{n}.$ (3.6)

This can be generalized to words $x\in\Sigma^{*}$ and $y\in\Omega^{*}$ by
setting

$\displaystyle\eta(y\mid x)=P(y\mid x)\cdot\mbox{\boldmath$1$}_{n}.$ (3.7)

The $i$th component $\eta_{i}(y\mid x)$ is the conditional probability of
transition from state $s_{i}$ to any state when the word $x$ is read and the
word $y$ is emitted, $1\leq i\leq n$. The vector $\eta(y\mid x)$ is the result
vector of the stochastic automaton reading $x\in\Sigma^{*}$ and emitting
$y\in\Omega^{*}$.

######  Proposition 3.1.

We have

  * •

$\eta(\epsilon\mid\epsilon)=\mbox{\boldmath$1$}_{n}.$

  * •

For all words $x\in\Sigma^{*}$,

$\sum_{y\in\Omega^{*}}\eta(y\mid x)=\mbox{\boldmath$1$}_{n}.$

  * •

For all words $x,x^{\prime}\in\Sigma^{*}$ and $y,y^{\prime}\in\Omega^{*}$ with
$|x|=|y|$,

$\eta(yy^{\prime}\mid xx^{\prime})=P(y\mid x)\cdot\eta(y^{\prime}\mid
x^{\prime}).$

###### Proof.

First, we have
$p(\epsilon\mid\epsilon)=P(\epsilon\mid\epsilon)\cdot\mbox{\boldmath$1$}_{n}=I_{n}\cdot\mbox{\boldmath$1$}_{n}=\mbox{\boldmath$1$}_{n}$.

Second, we have

$\sum_{y\in\Omega^{*}}\eta(y\mid x)=\sum_{y\in\Omega^{*}}P(y\mid
x)\cdot\mbox{\boldmath$1$}_{n}=P(x)\cdot\mbox{\boldmath$1$}_{n}=\mbox{\boldmath$1$}_{n},$

since the matrix $P(x)$ is stochastic.

Finally, by Prop. 2.3 and (3.7), we have

$\displaystyle\eta(yy^{\prime}\mid xx^{\prime})$ $\displaystyle=$
$\displaystyle P(yy^{\prime}\mid
xx^{\prime})\cdot\mbox{\boldmath$1$}_{n}=P(y\mid x)\cdot P(y^{\prime}\mid
x^{\prime})\cdot\mbox{\boldmath$1$}_{n}$ $\displaystyle=$ $\displaystyle
P(y\mid x)\cdot\eta(y^{\prime}\mid x^{\prime}).$

∎

A stochastic automaton can be thought of as an abstract machine which takes on
a well-defined state at each step. However, an external observer is unable to
determine this state with certainty. She can only consider the probability
that the automaton is in a certain state. Therefore, we introduce socalled
state distributions.

Let $A=(S,\Sigma,\Omega,p)$ be a stochastic automaton with state set
$S=\\{s_{1},\ldots,s_{n}\\}$. A row vector $\pi=(\pi_{1},\ldots,\pi_{n})$ is a
state distribution of $A$ if the entries of $\pi$ are nonnegative and add up
to 1. The $i$th component $\pi_{i}$ is the probability that the automaton $A$
is in state $s_{i}$, $1\leq i\leq n$.

By convention, a state distribution $\pi=(\pi_{1},\ldots,\pi_{n})$ of $A$ will
also be written as a formal linear combination of states,

$\displaystyle\pi=\pi_{1}s_{1}+\ldots+\pi_{n}s_{n}.$ (3.8)

In particular, $\pi=s_{i}$ is the state distribution given by the $i$th unit
vector $e_{i}$ which has 1 in position $i$ and 0’s elsewhere, $1\leq i\leq n$.

Take the probability of emitting the word $y\in\Omega^{*}$ if the automaton
$A$ is in state $s_{i}$ with probability $\pi_{i}$ and the word
$x\in\Sigma^{*}$ is read. This probability is given by the matrix product

$\displaystyle\pi\cdot\eta(y\mid x)=\sum_{i=1}^{n}\pi_{i}\cdot\eta_{i}(y\mid
x).$ (3.9)

For this, consider the mapping
$\eta^{\pi}:\Omega^{*}\times\Sigma^{*}\rightarrow[0,1]$ defined by

$\displaystyle\eta^{\pi}(y\mid x)=\pi\cdot\eta(y\mid x),\quad
x\in\Sigma^{*},y\in\Omega^{*}.$ (3.10)

This mapping is well-defined, since $\sum_{i}\pi_{i}=1$, $0\leq\eta_{i}(y\mid
x)\leq 1$ for each $1\leq i\leq n$ and so $0\leq\sum_{i}\pi_{i}\eta_{i}(y\mid
x)\leq 1$.

In view of the result vectors, define the sets

$\displaystyle\mbox{$\cal D$}_{A}=\\{\eta^{\pi}\mid\pi\mbox{ state
distribution of }A\\}$ (3.11)

and

$\displaystyle\mbox{$\cal S$}_{A}=\\{\eta^{s}\mid s\mbox{ state of }\;A\\}.$
(3.12)

We introduce several notions of equivalence of state distributions and
stochastic automata. For this, let $A=(S_{A},\Sigma,\Omega,p_{A})$ and
$B=(S_{B},\Sigma,\Omega,p_{B})$ be stochastic automata with the same input and
output alphabets.

  * •

$A$ and $B$ are equivalent, written $A\equiv B$, if $\mbox{$\cal
D$}_{A}=\mbox{$\cal D$}_{B}$.

  * •

$A$ and $B$ are S-equivalent, written $A\equiv_{S}B$, if $\mbox{$\cal
S$}_{A}=\mbox{$\cal S$}_{B}$.

  * •

$A$ covers $B$, written $A\geq B$, if $\mbox{$\cal D$}_{A}\supseteq\mbox{$\cal
D$}_{B}$.

  * •

A state distribution $\pi_{A}$ of $A$ is equivalent to a state distribution
$\pi_{B}$ of $B$, written $\pi_{A}\equiv\pi_{B}$, if

$\displaystyle\eta_{A}^{\pi_{A}}(y\mid x)=\eta_{B}^{\pi_{B}}(y\mid x)$ (3.13)

for all $x\in\Sigma^{*}$ and $y\in\Omega^{*}$.

  * •

Let $k\geq 0$. A state distribution $\pi_{A}$ of $A$ is $k$-equivalent to a
state distribution $\pi_{B}$ of $B$, written $\pi_{A}\equiv_{k}\pi_{B}$, if

$\displaystyle\eta_{A}^{\pi_{A}}(y\mid x)=\eta_{B}^{\pi_{B}}(y\mid x)$ (3.14)

for all $x\in\Sigma^{*}$ and $y\in\Omega^{*}$ with $|x|=|y|\leq k$.

These relations are equivalence relations on the class of stochastic automata
resp. the class of state distributions. The following result follows directly
from the definitions.

######  Lemma 3.2.

Let $A$ and $B$ be stochastic automata with the same input and output
alphabets. Then $A\equiv B$ if and only if $A\geq B$ and $B\geq A$.

######  Lemma 3.3.

Let $A$ and $B$ be stochastic automata. Then $A$ covers $B$ if and only if for
each state of $B$ there is an equivalent state distribution of $A$.

###### Proof.

Let $S_{A}=\\{s_{1},\ldots,s_{n}\\}$ and $S_{B}=\\{t_{1},\ldots,t_{m}\\}$.

First, suppose $A$ covers $B$. Then for each state $t\in S_{B}$ there is a
state distribution $\pi$ of $A$ such that $\eta_{B}^{t}=\eta^{\pi}$.

Conversely, suppose that for each state $t\in S_{B}$ there is an equivalent
state distribution $\pi(t)$ of $A$. Then the state distribution
$\pi^{\prime}=\sum_{j}\pi^{\prime}_{j}t_{j}$ of $B$ is equivalent to the state
distribution $\pi=\sum_{j}\pi^{\prime}_{j}\pi(t_{j})$ of $A$. Thus
$\mbox{$\cal D$}_{A}\supseteq\mbox{$\cal D$}_{B}$ and hence $A$ covers $B$. ∎

######  Proposition 3.4.

Let $A$ and $B$ be stochastic automata with the same input and output
alphabets. If $A$ and $B$ are S-equivalent, then $A$ and $B$ are equivalent.

###### Proof.

Let $A$ and $B$ be S-equivalent. Then for each state $s_{i}$ in $A$ there is
an equivalent state $t_{i}$ in $B$. Thus the state distribution
$\pi=\sum_{j}\pi_{j}s_{j}$ of $A$ is equivalent to the state distribution
$\pi^{\prime}=\sum_{j}\pi^{\prime}_{j}t_{j}$ of $B$. Thus $\mbox{$\cal
D$}_{A}\subseteq\mbox{$\cal D$}_{B}$ and similarly $\mbox{$\cal
D$}_{B}\subseteq\mbox{$\cal D$}_{A}$. Hence, $A\equiv B$. ∎

This assertion gives rise to a decision algorithm for the equivalence of
stochastic automata. Instead of considering all state distributions, it is
sufficient to take only the states (i.e., the state distributions of the
states) into account (Alg. 1).

Algorithm 1 Equivalence of stochastic automata.

0: Stochastic automata $A$ and $B$ with respective state sets
$S_{A}=\\{s_{1},\ldots,s_{m}\\}$ and $S_{B}=\\{t_{1},\ldots,t_{n}\\}$ and
common input and output alphabets

0: Output 1 if $A$ and $B$ are equivalent; otherwise, output 0

Compute $\mbox{$\cal S$}_{A}=\\{\eta_{A}^{s_{1}},\ldots,p_{A}^{s_{m}}\\}$

Compute $\mbox{$\cal S$}_{B}=\\{\eta_{B}^{t_{1}},\ldots,p_{B}^{t_{n}}\\}$

if $\mbox{$\cal S$}_{A}=\mbox{$\cal S$}_{B}$ then

return 1

else

return 0

end if

  * Example 3.

Consider the stochastic automaton
$A=(\\{s_{1},s_{2}\\},\\{a,b\\},\\{c,d\\},p)$ given by the substochastic
matrices

$\begin{array}[]{ll}P(c\mid
a)=\left(\begin{array}[]{cc}\frac{1}{4}&\frac{1}{8}\\\
0&\frac{1}{2}\end{array}\right),&P(d\mid
a)=\left(\begin{array}[]{cc}\frac{1}{8}&\frac{1}{2}\\\
0&\frac{1}{2}\end{array}\right),\\\ P(c\mid
b)=\left(\begin{array}[]{cc}\frac{1}{4}&\frac{1}{4}\\\
\frac{1}{4}&0\end{array}\right),&P(d\mid
b)=\left(\begin{array}[]{cc}\frac{3}{8}&\frac{1}{8}\\\
\frac{3}{4}&0\end{array}\right).\end{array}$

The corresponding stochastic matrices are

$P(a)=\left(\begin{array}[]{cc}\frac{3}{8}&\frac{5}{8}\\\
0&1\end{array}\right)\;\mbox{and}\;P(b)=\left(\begin{array}[]{cc}\frac{5}{8}&\frac{3}{8}\\\
1&0\end{array}\right).$

The result vectors for single in- and outputs are

$\begin{array}[]{ll}\eta(c\mid a)=\left(\begin{array}[]{c}\frac{3}{8}\\\
\frac{1}{2}\end{array}\right),&\eta(d\mid
a)=\left(\begin{array}[]{c}\frac{5}{8}\\\ \frac{1}{2}\end{array}\right),\\\
\eta(c\mid b)=\left(\begin{array}[]{c}\frac{1}{2}\\\
\frac{1}{4}\end{array}\right),&\eta(d\mid
b)=\left(\begin{array}[]{c}\frac{1}{2}\\\
\frac{3}{4}\end{array}\right).\end{array}$

For instance, the states $s_{1}$ and $s_{2}$ are not equivalent, since
$\eta^{s_{1}}(c\mid a)=\frac{3}{8}$ and $\eta^{s_{2}}(c\mid a)=\frac{1}{2}$.
$\diamondsuit$

##  Chapter 4 Reduction

The objective of reduction is to construct stochastic automata with the same
performance but a reduced number of states. For this, a stochastic automaton
$A$ is called reduced if $A$ has no two distinct states which are equivalent.

######  Proposition 4.1.

Let $A$ and $B$ be reduced and S-equivalent stochastic automata. Then the
state sets of $A$ and $B$ have the same cardinality.

###### Proof.

For each state $s\in S_{A}$ there is an equivalent state $s^{\prime}\in S_{B}$
in the sense that the induced state distributions are equivalent. Since the
automaton $B$ is reduced, the state $s$ cannot be equivalent to another state
$s^{\prime\prime}\in S_{B}$, since then the states $s^{\prime}$ and
$s^{\prime\prime}$ would be equivalent. This gives an injective mapping
$S_{A}\rightarrow S_{B}$. In the same way, we obtain an injective mapping
$S_{B}\rightarrow S_{A}$. But the state sets are finite and hence there is a
bijection between $S_{A}$ and $S_{B}$. ∎

For each stochastic automaton, there is an equivalent and reduced stochastic
automaton which can be constructed using the powerset construction.

######  Theorem 4.2.

Each stochastic automaton is S-equivalent to a reduced stochastic automaton.

###### Proof.

Let $A=(S,\Sigma,\Omega,p_{A})$ be a stochastic automaton with state set
$S=\\{s_{1},\ldots,s_{n}\\}$. Two states $s$ and $t$ of $A$ are equivalent if
$\eta^{s}(y\mid x)=\eta^{t}(y\mid x)$ for all $x\in\Sigma^{*}$ and
$y\in\Omega^{*}$. This relation is an equivalence relation on the state set
$S$ of $A$. Let $Z=\\{Z_{1},\ldots,Z_{r}\\}$ denote the corresponding set of
equivalence classes of the state set of $A$; in particular, the set $Z$ is a
partition of the state set $S$. For each class $Z_{i}$ choose a fixed
representative $z_{i}$, $1\leq i\leq r$.

Define the stochastic automaton $B=(Z,\Sigma,\Omega,p_{B})$ with conditional
probabilities

$\displaystyle p_{B}(b,Z_{j}\mid a,Z_{i})=\sum_{z\in Z_{j}}p_{A}(b,z\mid
a,z_{i}),\quad a\in\Sigma,\;b\in\Omega,\;1\leq i,j\leq r.$ (4.1)

The automaton $B$ is reduced, since if the states $Z_{i}$ and $Z_{j}$ are
equivalent, then $z_{i}=z_{j}$ and thus $i=j$ by definition.

Claim that the automata $A$ and $B$ are S-equivalent. Indeed, take the states
$z_{i}\in Z_{i}$ in $A$ and $Z_{i}$ in $B$, $1\leq i\leq r$. Then for all
$a\in\Sigma$ and $b\in\Omega$,

$\displaystyle\eta_{A}^{z_{i}}(b\mid a)$ $\displaystyle=$
$\displaystyle\sum_{s\in S_{A}}p_{A}(b,s\mid a,z_{i})$ $\displaystyle=$
$\displaystyle\sum_{Z_{j}\in Z}\sum_{z\in Z_{j}}p_{A}(b,z\mid a,z_{i})$
$\displaystyle=$ $\displaystyle\sum_{Z_{j}\in Z}p_{B}(b,Z_{j}\mid a,Z_{i})$
$\displaystyle=$ $\displaystyle\eta_{B}^{Z_{i}}(b\mid a).$

Thus the states $z_{i}$ and $Z_{i}$ are 1-equivalent. Suppose the states
$z_{i}$ and $Z_{i}$ are $k$-equivalent for some $k\geq 1$. Then for all
$x\in\Sigma^{*}$, $y\in\Omega^{*}$ with $|x|=|y|=k$, $a\in\Sigma$, and
$b\in\Omega$, we have

$\displaystyle\eta_{A}^{z_{i}}(by\mid ax)$ $\displaystyle=$
$\displaystyle\sum_{s\in S_{A}}p_{A}(b,s\mid a,z_{i})\eta_{A}^{s}(y\mid
x),\quad\mbox{by Prop.~{}\ref{p-omega}},$ $\displaystyle=$
$\displaystyle\sum_{Z_{j}\in Z}\sum_{s\in Z_{j}}p_{A}(b,s\mid
a,z_{i})\eta_{A}^{s}(y\mid x)$ $\displaystyle=$ $\displaystyle\sum_{Z_{j}\in
Z}p_{B}(b,Z_{j}\mid a,Z_{i})\eta_{A}^{z_{j}}(y\mid x)$ $\displaystyle=$
$\displaystyle\sum_{Z_{j}\in Z}p_{B}(b,Z_{j}\mid
a,Z_{i})\eta_{B}^{Z_{j}}(y\mid x),\quad\mbox{by induction},$ $\displaystyle=$
$\displaystyle\eta_{B}^{Z_{i}}(by\mid ax),\quad\mbox{by
Prop.~{}\ref{p-omega}}.$

Therefore, the states $z_{i}$ and $Z_{i}$ are $(k+1)$-equivalent. Thus the
states $z_{i}$ and $Z_{i}$ are equivalent, $1\leq i\leq r$, and hence the
automata $A$ and $B$ are S-equivalent. ∎

The equivalence of two state distributions can be decided by considering
inputs and outputs of restricted length.

######  Proposition 4.3.

Let $A$ be a stochastic automaton with $n$ states. Two state distributions of
$A$ are equivalent if and only if they are $(n-1)$-equivalent.

###### Proof.

Let $k\geq 0$. Two state distributions $\pi$ and $\pi^{\prime}$ of $A$ are
$k$-equivalent if and only if for all words $x\in\Sigma^{*}$ and
$y\in\Omega^{*}$ with $|x|=|y|\leq k$,

$\pi\cdot\eta(y\mid x)=\pi^{\prime}\cdot\eta(y\mid x).$

Equivalently,

$(\pi-\pi^{\prime})\cdot\eta(y\mid x)=0.$

Let $V_{k}$ be the vector subspace of ${\mathbb{R}}^{n}$ generated by the
result vectors $\eta(y\mid x)$, where $x\in\Sigma^{*}$ and $y\in\Omega^{*}$
with $|x|=|y|\leq k$. We have $V_{0}={\mathbb{R}}\cdot\mbox{\boldmath$1$}_{n}$
and $V_{k}\subseteq V_{k+1}$ for each $k\geq 0$. Thus $V_{k}$ is a subspace of
$V_{k+1}$ for all $k\geq 0$. Moreover, let $V_{A}$ be the vector subspace of
${\mathbb{R}}^{n}$ generated by all the result vectors $\eta(y\mid x)$, where
$x\in\Sigma^{*}$ and $y\in\Omega^{*}$. Then $V_{k}$ is a subspace of $V_{A}$
for each $k\geq 0$.

Consider the ascending chain of subspaces of ${\mathbb{R}}^{n}$:

$V_{0}\subseteq V_{1}\subseteq V_{2}\subseteq\ldots\subseteq
V_{A}\subseteq{\mathbb{R}}^{n}.$

Since the subspaces are of finite dimension, there exists a smallest number
$j\geq 0$ such that $V_{j}=V_{j+1}$. Then we have $V_{j}=V_{j+l}$ for each
$l\geq 0$, since by Prop. 3.1 the result vector $\eta(ay\mid bx)$ is the image
of the linear mapping $P(b\mid a)$ applied to the result vector $\eta(y\mid
x)$. By construction, $V_{j}=V_{A}$ and thus by considering dimensions,

$1=\dim V_{0}<\dim V_{1}<\dim V_{2}<\ldots<\dim V_{j}=\dim V_{A}\leq
n=\dim{\mathbb{R}}^{n},$

where $j\leq n-1$.

It follows that any two state distributions $\pi$ and $\pi^{\prime}$ of $A$
are equivalent if and only if $(\pi-\pi^{\prime})\cdot\eta(y\mid x)=0$ for all
$\eta(y\mid x)\in V_{j}$. Equivalently, the state distributions $\pi$ and
$\pi^{\prime}$ are $j$-equivalent with $j=n-1$. ∎

######  Corollary 4.4.

Let $A$ and $B$ be stochastic automata with the same input and output
alphabets as well as $m$ and $n$ states, respectively. A state distribution of
$A$ is equivalent to a state distribution of $B$ if and only if the state
distributions are $(m+n-1)$-equivalent.

###### Proof.

We may assume that the state sets of $A$ and $B$ are disjoint. Define the
stochastic automaton $C=(S,\Sigma,\Omega,p)$ with the same input and output
alphabets, state set $S_{C}=S_{A}\cup S_{B}$, and substochastic matrices

$P_{C}(b\mid a)=\left(\begin{array}[]{cc}P_{A}(b\mid a)&0\\\ 0&P_{B}(b\mid
a)\end{array}\right),\quad a\in\Sigma,\;b\in\Omega.$

Then state distribution $\pi_{A}=(\pi_{A,1},\ldots,\pi_{A,m})$ of $A$ is
equivalent to a state distribution $\pi_{B}=(\pi_{B,1},\ldots,\pi_{B,n})$ of
$B$ if and only if the length-$m+n$ state distributions
$(\pi_{A,1},\ldots,\pi_{A,m},0\ldots,0)$ and
$(0,\ldots,0,\pi_{B,1},\ldots,\pi_{B,n})$ of $C$ are equivalent. By Prop. 4.3,
the latter distributions are equivalent if and only if they are
$(m+n-1)$-equivalent, since the automaton $C$ has $m+n$ states. ∎

The bound $n-1$ given in Prop. 4.3 is tight as shown in the following.

  * Example 4.

Let $n\geq 1$. Consider the stochastic automaton

$A=(\\{s_{1},\ldots,s_{n}\\},\\{a,b\\},\\{c,d\\},p)$

with nonzero transition probabilities

$p(c,s_{i+1}\mid a,s_{i})=p(c,s_{i+1}\mid b,s_{i})=1,\quad 1\leq i\leq n-1,$

and

$p(c,s_{1}\mid a,s_{n})=p(d,s_{1}\mid b,s_{n})=1.$

Note that $A$ is a deterministic automaton (Fig. 4.1). If one starts in the
state $s_{1}$ or $s_{2}$ and reads a word of length $l\leq n-2$, the word
$c^{l}$ is emitted with certainty. Thus the states $s_{1}$ and $s_{2}$ are
$(n-2)$-equivalent. However, if one begins in the state $s_{1}$ and inputs a
word of length $n-1$, the word $c^{n-1}$ is emitted with certainty. On the
other hand, if one starts in the state $s_{2}$ and reads the word $b^{n-1}$,
the word $c^{n-1}d$ is emitted with certainty. Hence, the states $s_{1}$ and
$s_{2}$ are not $(n-1)$-equivalent. $\diamondsuit$

$\textstyle{s_{1}}$$\scriptstyle{a,c:1;\;b,c:1}$$\textstyle{s_{2}}$$\scriptstyle{a,c:1;\;b,c:1}$$\textstyle{s_{4}}$$\scriptstyle{a,c:1;\;b,d:1}$$\textstyle{s_{3}}$$\scriptstyle{a,c:1;\;b,c:1}$

Figure 4.1: State diagram of stochastic automaton $A$ with $n=4$.

  * Example 5.

Consider the stochastic automaton (Fig. 4.2)

$A=(\\{s_{1},s_{2},s_{3},s_{4}\\},\\{a\\},\\{b,c\\},p)$

with substochastic matrices

$P(b\mid a)=\left(\begin{array}[]{cccc}0&0&\frac{1}{6}&\frac{1}{6}\\\
0&0&\frac{1}{3}&\frac{1}{3}\\\ \frac{1}{4}&\frac{1}{4}&0&0\\\
0&0&0&\frac{1}{2}\end{array}\right)\quad\mbox{and}\quad P(c\mid
a)=\left(\begin{array}[]{cccc}0&0&\frac{1}{3}&\frac{1}{3}\\\
0&0&\frac{1}{6}&\frac{1}{6}\\\ \frac{1}{4}&\frac{1}{4}&0&0\\\
0&0&0&\frac{1}{2}\end{array}\right).$

Then we have

$\eta(b\mid a)=\left(\begin{array}[]{c}\frac{1}{3}\\\ \frac{2}{3}\\\
\frac{1}{2}\\\ \frac{1}{2}\\\ \end{array}\right)\quad\mbox{and}\quad\eta(c\mid
a)=\left(\begin{array}[]{c}\frac{2}{3}\\\ \frac{1}{3}\\\ \frac{1}{2}\\\
\frac{1}{2}\\\ \end{array}\right).$

By Prop. 3.1, we obtain

$\eta(bb\mid aa)=\eta(bc\mid aa)=\left(\begin{array}[]{c}\frac{1}{6}\\\
\frac{1}{3}\\\ \frac{1}{4}\\\ \frac{1}{4}\\\
\end{array}\right)=\frac{1}{2}\eta(b\mid a)$

and

$\eta(cb\mid aa)=\eta(cc\mid aa)=\left(\begin{array}[]{c}\frac{1}{3}\\\
\frac{1}{6}\\\ \frac{1}{4}\\\ \frac{1}{4}\\\
\end{array}\right)=\frac{1}{2}\eta(c\mid a).$

Thus by the proof of Prop. 4.3, we have $V_{0}={\mathbb{R}}$ and
$V_{1}=V_{2}=V_{A}$ with $\dim V_{A}=2$. By Prop. 4.3, two states of $A$ are
equivalent if and only if they are 1-equivalent. The states $s_{1}$, $s_{2}$,
and $s_{3}$ are pairwise non-equivalent, while the states $s_{3}$ and $s_{4}$
are 1-equivalent, since $\eta^{s_{3}}(b\mid a)=\eta^{s_{4}}(b\mid a)$ and
$\eta^{s_{3}}(c\mid a)=\eta^{s_{4}}(c\mid a)$. Thus the state set decomposed
into equivalence classes gives
$Z=\\{Z_{1}=\\{s_{1}\\},Z_{2}=\\{s_{2}\\},Z_{3}=\\{s_{3},s_{4}\\}\\}$.

|
---|---
$\textstyle{s_{1}}$$\scriptstyle{a,b:1/6;\;a,c:1/3}$$\scriptstyle{a,b:1/6;\;a,c:1/3}$$\textstyle{s_{3}}$$\scriptstyle{a,b:1/4;\;a,c:1/4}$$\scriptstyle{a,b:1/4;\;a,c:1/4}$$\textstyle{s_{4}}$$\scriptstyle{a,b:1/2;\;a:c:1/2}$$\textstyle{s_{2}}$$\scriptstyle{a,b:1/3;\;a,c:1/6}$$\scriptstyle{a,b:1/3;\;a,c:1/6}$

Figure 4.2: State diagram of stochastic automaton $A$.

By (4.1), the corresponding reduced stochastic automaton $B$ (Fig. 4.3) with
representative $s_{3}\in Z_{3}$ has the substochastic matrices

$P_{B}(b\mid a)=\left(\begin{array}[]{ccc}0&0&\frac{1}{3}\\\
0&0&\frac{2}{3}\\\
\frac{1}{4}&\frac{1}{4}&0\end{array}\right)\quad\mbox{and}\quad P_{B}(c\mid
a)=\left(\begin{array}[]{cccc}0&0&\frac{2}{3}\\\ 0&0&\frac{1}{3}\\\
\frac{1}{4}&\frac{1}{4}&0\end{array}\right),$

|
---|---
$\textstyle{Z_{1}}$$\scriptstyle{a,b:1/3;\;a,c:2/3}$$\textstyle{Z_{3}}$$\scriptstyle{a,b:1/4;\;a,c:1/4}$$\scriptstyle{a,b:1/4;\;a,c:1/4}$$\textstyle{Z_{2}}$$\scriptstyle{a,b:2/3;\;a,c:1/3}$

Figure 4.3: State diagram of stochastic automaton $B$.

On the other hand, the associated reduced stochastic automaton $B^{\prime}$
(Fig. 4.4) with representative $s_{4}\in Z_{3}$ has the substochastic matrices

$P_{B^{\prime}}(b\mid a)=\left(\begin{array}[]{ccc}0&0&\frac{1}{3}\\\
0&0&\frac{2}{3}\\\ 0&0&\frac{1}{2}\end{array}\right)\quad\mbox{and}\quad
P_{B^{\prime}}(c\mid a)=\left(\begin{array}[]{cccc}0&0&\frac{2}{3}\\\
0&0&\frac{1}{3}\\\ 0&0&\frac{1}{2}\end{array}\right).$

|
---|---
$\textstyle{Z_{1}}$$\scriptstyle{a,b:1/3;\;a,c:2/3}$$\textstyle{Z_{3}}$$\scriptstyle{a,b:1/2;\;a,c:1/2}$$\textstyle{Z_{2}}$$\scriptstyle{a,b:2/3;\;a,c:1/3}$

Figure 4.4: State diagram of stochastic automaton $B^{\prime}$.

$\diamondsuit$

Two stochastic automata $A=(S_{A},\Sigma,\Omega,p_{A})$ and
$B=(S_{B},\Sigma,\Omega,p_{B})$ are isomorphic if there is a bijective mapping
$\phi:S_{A}\mapsto S_{B}$ such that for all $s,s^{\prime}\in S_{A}$,
$a\in\Sigma$ and $b\in\Omega$,

$\displaystyle p_{B}(b,\phi(s^{\prime})\mid a,\phi(s))=p_{A}(b,s^{\prime}\mid
a,s).$ (4.2)

  * Example 6.

The reduced stochastic automata $B$ and $B^{\prime}$ in Ex. 4 are not
isomorphic. The only mapping that would make sense is
$\phi:\\{s_{1},s_{2},s_{3}\\}\rightarrow\\{s_{1},s_{2},s_{4}\\}$ with
$\phi(s_{1})=s_{1}$, $\phi(s_{2})=s_{2}$, and $\phi(s_{3})=s_{4}$.
$\diamondsuit$

The vector space $V_{A}$ associated with a stochastic automaton $A$ can be
used to further investigate the problem of equivalence of state distributions.
For this, we need a vector-space basis of the space $V_{A}$. To this end, let
$\Sigma$ and $\Omega$ be alphabets. The set

$\displaystyle M=\\{(y\mid x)\mid x\in\Sigma^{*},y\in\Omega^{*},|x|=|y|\\}$
(4.3)

together with the binary operation of concatenation,

$\displaystyle(y\mid x)(y^{\prime}\mid x^{\prime})=(yy^{\prime}\mid
xx^{\prime}),\quad x,x^{\prime}\in\Sigma^{*},\;y,y^{\prime}\in\Omega^{*},$
(4.4)

is a free monoid generated by the set $N=\\{(b\mid a)\mid
a\in\Sigma,b\in\Omega\\}$. Note that the monoids $M$ and
$(\Omega\times\Sigma)^{*}$ are isomorphic by the assignment

$\displaystyle(b_{1}\ldots b_{n}\mid a_{1}\ldots
a_{n})\mapsto(b_{1},a_{1})\ldots(b_{n},a_{n}).$ (4.5)

This isomorphism maps the generating set $N$ to the cartesian product
$\Omega\times\Sigma$. In this way, we may assume that the elements of $N$ are
lexicographically ordered. This ordering can be extended to the monoid $M$.

Let $A$ be a stochastic automaton with $n$ states. Consider the vector
subspace $V_{A}$ of ${\mathbb{R}}^{n}$ generated by the result vectors
$\eta(y\mid x)$, where $x\in\Sigma^{*}$ and $y\in\Omega^{*}$. Suppose the
space $V_{A}$ has ${\mathbb{R}}$-dimension $d$. Then define the $n\times d$
matrix

$\displaystyle H_{A}=\left(\begin{array}[]{ccc}\eta(y_{1}\mid
x_{1})&\ldots&\eta(y_{d}\mid x_{d})\end{array}\right),$ (4.7)

where $x_{1}=y_{1}=\epsilon$ and $(y_{i+1}\mid x_{i+1})\in M$ is the
lexicographically smallest element of $M$ that is linearly independent of the
previous vectors $\eta(y_{1}\mid x_{1}),\ldots,\eta(y_{i}\mid x_{i})$, $1\leq
i\leq d-1$. The columns of the matrix $H_{A}$ form a basis of the space
$V_{A}$. Since $d\leq n$, the matrix $H_{A}$ has rank $d$.

  * Example 7.

Reconsider the stochastic automaton $A$ in Ex. 4. The matrix $H_{A}$ has rank
2 and is given by

$H_{A}=\left(\eta(\epsilon,\epsilon)\;\eta(b\mid
a)\right)=\left(\begin{array}[]{cc}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\
1&\frac{1}{2}\\\ 1&\frac{1}{2}\end{array}\right).$

$\diamondsuit$

The matrix $H_{A}$ can be used to characterize equivalent state distributions.

######  Proposition 4.5.

Let $A$ be a stochastic automaton. Two state distributions $\pi$ and
$\pi^{\prime}$ of $A$ are equivalent if and only if $\pi
H_{A}=\pi^{\prime}H_{A}$.

In particular, two states $s_{i}$ and $s_{j}$ of $A$ are equivalent if and
only if the $i$th and $j$th rows of $H_{A}$ are equal.

###### Proof.

Let $\pi$ and $\pi^{\prime}$ be equivalent state distributions. Then
$\pi\cdot\eta(y\mid x)=\pi^{\prime}\cdot\eta(y\mid x)$ for all
$x\in\Sigma^{*}$ and $y\in\Omega^{*}$. This particularly holds for the columns
of the matrix $H_{A}$ and therefore $\pi H_{A}=\pi^{\prime}H_{A}$.

Conversely, let $\pi H_{A}=\pi^{\prime}H_{A}$ for state distributions $\pi$
and $\pi^{\prime}$. The columns of the matrix $H_{A}$ form a basis of the
space $V_{A}$ and so we have for each result vector $\eta(y\mid x)\in V_{A}$,

$\eta(y\mid x)=\sum_{i=1}^{d}\alpha_{i}\eta(y_{i}\mid
x_{i}),\quad\alpha_{i}\in{\mathbb{R}},\;1\leq i\leq d.$

By hypothesis, we have $\pi\cdot\eta(y_{i}\mid
x_{i})=\pi^{\prime}\cdot\eta(y_{i}\mid x_{i})$ for each $1\leq i\leq d$. Thus
$\pi\cdot\eta(y\mid x)=\pi^{\prime}\cdot\eta(y\mid x)$. Hence, $\pi$ and
$\pi^{\prime}$ are equivalent.

The second assertion is an immediate consequence of the first one. ∎

######  Proposition 4.6.

Let $A$ and $B$ be reduced stochastic automata. If $A$ and $B$ are
S-equivalent, then $H_{A}=H_{B}$ up to a permutation of matrix rows.

###### Proof.

Suppose $A$ and $B$ have the same state set. We may assume that the state $s$
in $A$ is equivalent to the state $s$ in $B$. Then $\eta_{A}(y\mid
x)=\eta_{B}(y\mid x)$ for all $x\in\Sigma^{*}$ and $y\in\Omega^{*}$ by the
ordering of these vectors. Therefore, $H_{A}=H_{B}$.

Suppose $A$ and $B$ have the different state sets. Then by Prop. 4.1, the
matrices can only differ by a row permutation. ∎

######  Theorem 4.7.

Let $A=(S,\Sigma,\Omega,p)$ be a stochastic automaton with $n$ states given by
the collection of matrices $\\{P_{A}(b\mid a)\mid a\in\Sigma,b\in\Omega\\}$.

Let $\\{P_{B}(b\mid a)\mid a\in\Sigma,b\in\Omega\\}$ be a collection of non-
negative $n\times n$ matrices such that

$P_{A}(b\mid a)H_{A}=P_{B}(b\mid a)H_{A}$

for all $a\in\Sigma$ and $b\in\Omega$. Then the collection $\\{P_{B}(b\mid
a)\mid a\in\Sigma,b\in\Omega\\}$ defines a stochastic automaton $B$ with $n$
states such that the state $s\in S_{A}$ is equivalent to the state $s\in
S_{B}$. In particular, the automata $A$ and $B$ are S-equivalent.

###### Proof.

Since $\mbox{\boldmath$1$}_{n}$ is the first column of $H_{A}$, we have
$P_{A}(b\mid a)\cdot\mbox{\boldmath$1$}_{n}=P_{B}(b\mid
a)\cdot\mbox{\boldmath$1$}_{n}$. Then

$\sum_{b}P_{B}(b\mid a)\cdot\mbox{\boldmath$1$}_{n}=\sum_{b}P_{A}(b\mid
a)\cdot\mbox{\boldmath$1$}_{n}=P_{A}(a)\cdot\mbox{\boldmath$1$}_{n}=\mbox{\boldmath$1$}_{n}.$

Thus the collection of matrices $\\{P_{B}(b\mid a)\mid
a\in\Sigma,b\in\Omega\\}$ defines a stochastic automaton $B$ with
$P_{B}(a)=\sum_{b}P_{B}(b\mid a)$.

Let $s\in S_{A}$. Since for all $a\in\Sigma$ and $b\in\Omega$,

$\eta_{A}(b\mid a)=P_{A}(b\mid a)\cdot\mbox{\boldmath$1$}_{n}=P_{B}(b\mid
a)\cdot\mbox{\boldmath$1$}_{n}=\eta_{B}(b\mid a),$

it follows that $s$ in $A$ is 1-equivalent to $s$ in $B$.

Suppose for some $k\geq 1$, $s$ in $A$ is $k$-equivalent to $s$ in $B$. Then
for all $x\in\Sigma^{k}$, $a\in\Sigma$, $y\in\Omega^{k}$ and $b\in\Omega$,

$\displaystyle\eta_{A}(by\mid ax)$ $\displaystyle=$ $\displaystyle P_{A}(b\mid
a)\eta_{A}(y\mid x),\quad\mbox{by Prop.~{}\ref{p-omega}},$ $\displaystyle=$
$\displaystyle P_{B}(b\mid a)\eta_{A}(y\mid x)$ $\displaystyle=$
$\displaystyle P_{B}(b\mid a)\eta_{B}(y\mid x),\quad\mbox{by induction},$
$\displaystyle=$ $\displaystyle\eta_{B}(by\mid ax),\quad\mbox{by
Prop.~{}\ref{p-omega}},$

where the second equation uses the fact that $\eta_{A}(y\mid x)$ is a linear
combination of the columns of $H_{A}$. Thus $s$ in $A$ is $k+1$-equivalent to
$s$ in $B$. Hence, $A$ and $B$ are S-equivalent. ∎

The following result provides the reverse statement.

######  Theorem 4.8.

Let $A$ and $B$ be stochastic automata with the same state set such that state
$s$ in $A$ is equivalent to state $s$ in $B$ and $B$ is defined by the
collection of matrices $\\{P_{B}(b\mid a)\mid a\in\Sigma,b\in\Omega\\}$. Then
for all $a\in\Sigma$ and $b\in\Omega$,

$P_{A}(b\mid a)H_{A}=P_{B}(b\mid a)H_{A}.$

###### Proof.

Since state $s$ in $A$ is equivalent to state $s$ in $B$, we have
$\eta_{A}(y\mid x)=\eta_{B}(y\mid x)$ for all $x\in\Sigma^{*}$ and
$y\in\Omega^{*}$. Then by Prop. 3.1,

$P_{A}(b\mid a)\eta_{A}(y\mid x)=\eta_{A}(by\mid ax)=\eta_{B}(by\mid
ax)=P_{B}(b\mid a)\eta_{B}(y\mid x).$

Since all columns of $H_{A}$ are of the form $\eta_{A}(y\mid x)$, it follows
that $P_{A}(b\mid a)H_{A}=P_{B}(b\mid a)H_{A}$ for all $a\in\Sigma$ and
$b\in\Omega$. ∎

######  Corollary 4.9.

Let $A$ be a stochastic automaton with $n$ states. If the vector space $V_{A}$
has dimension $d=n$, then $A$ is reduced.

###### Proof.

Let $d=n$. Then the $n\times d$ matrix $H_{A}$ which has independent columns
has full rank and therefore is invertible. However, by Prop. 4.5, two states
$s_{i}$ and $s_{j}$ are equivalent if and only if the $i$th and $j$th rows of
$H_{A}$ are equal. Therefore, $A$ is reduced. ∎

The converse of this result is not valid.

  * Example 8.

Take the stochastic automaton
$A=(\\{s_{1},s_{2},s_{3}\\},\\{a\\},\\{b,c\\},p)$, where

$P(b\mid a)=\left(\begin{array}[]{ccc}1&0&0\\\ 0&0&0\\\ \frac{1}{2}&0&0\\\
\end{array}\right)\quad\mbox{and}\quad P(c\mid
a)=\left(\begin{array}[]{ccc}0&0&0\\\ 0&1&0\\\ 0&\frac{1}{2}&0\\\
\end{array}\right).$

Then

$H_{A}=\left(\begin{array}[]{cc}1&1\\\ 1&0\\\ 1&\frac{1}{2}\\\
\end{array}\right).$

By Prop. 4.5, the automaton $A$ is reduced, but the matrix $H_{A}$ does not
have full rank. $\diamondsuit$

##  Chapter 5 Minimality

The objective is to further decrease the state set of a reduced stochastic
automaton. For this, a stochastic automaton $A$ is called minimal if no state
of $A$ is equivalent to another state distribution of $A$. That is, if
$S_{A}=\\{s_{1},\ldots,s_{n}\\}$, there is no state $s_{i}$ and no state
distribution $\pi$ different from $s_{i}$ such that $\eta^{s_{i}}=\eta^{\pi}$.

  * Example 9.

Reconsider the reduced stochastic automaton $B^{\prime}$ in Ex. 4. This
automaton is not minimal. To see this, note that

$H_{B^{\prime}}=\left(\eta(\epsilon\mid\epsilon)\;\eta(b\mid
a)\right)=\left(\begin{array}[]{cc}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\
1&\frac{1}{2}\end{array}\right).$

For the state distributions $e_{3}=(0,0,1)$ and
$\pi=(\frac{1}{2},\frac{1}{2},0)$, we have $e_{3}\cdot H_{A}=\pi\cdot H_{A}$.
Thus by Prop. 4.5, the state distributions $s_{3}$ and $\pi$ are equivalent.
$\diamondsuit$

A permutation matrix is a quadratic matrix with entries 0 and 1 which has
exactly one entry 1 in each row and each column. An $n\times n$ permutation
matrix represents a bijection of a set of $n$ elements.

######  Lemma 5.1.

Let $M$ be a stochastic $m\times n$ matrix and $N$ be a stochastic $n\times m$
matrix. If $M\cdot N=I_{m}$ and $N\cdot M=I_{n}$, then $m=n$ and the matrices
$M$ and $N$ are permutation matrices.

###### Proof.

Matrices can be viewed as linear mappings between vector spaces. If $M\cdot
N=I_{m}$, the linear mappings given by $M$ and $N$ are surjective and
injective, respectively. Similarly, if $N\cdot M=I_{n}$, the linear mappings
given by $M$ and $N$ are injective and surjective, respectively. Therefore,
the linear mappings determined by $M$ and $N$ are bijective; i.e., the
matrices $M$ and $N$ are invertible with $m=n$.

Let $M=(a_{ij})$ and $N=(b_{ij})$ be $n\times n$ matrices with $M\cdot
N=I_{n}$ and $N\cdot M=I_{n}$. Then for the $(i,i)$th diagonal element, $1\leq
i\leq n$, we have $\sum_{j=1}^{n}a_{ij}b_{ji}=1$. Since $M$ and $N$ are
nonnegative matrices, we have $a_{il}>0$ and $b_{li}>0$ for some $l$.
Moreover, for each $j\neq l$, we have $\sum_{k=1}^{n}b_{jk}a_{kl}=0$. Since
$a_{il}\neq 0$, we have $b_{ji}=0$. Thus
$1=\sum_{j=1}^{n}a_{ij}b_{ji}=a_{il}b_{lj}$. But $a_{il},b_{lj}\leq 1$ and so
$a_{il}=b_{lj}=1$. Therefore, each row of $M$ and each column of $N$ has
exactly one entry $1$ and the remaining entries are $0$. By exchanging the
roles of $M$ and $N$, each row of $N$ and each column of $M$ has exactly one
entry $1$ and the remaining entries are $0$. Hence, $M$ and $N$ are
permutation matrices. ∎

######  Proposition 5.2.

Let $A$ and $B$ be minimal stochastic automata with the same input and output
alphabets. Then $A$ and $B$ are equivalent if and only if $A$ and $B$ are
S-equivalent.

###### Proof.

By Prop. 3.4, $A$ and $B$ are equivalent if they are S-equivalent.

Conversely, let $A$ and $B$ be equivalent. Let
$S_{A}=\\{s_{1},\ldots,s_{m}\\}$ and $S_{B}=\\{t_{1},\ldots,t_{n}\\}$ be the
state sets of $A$ and $B$, respectively. Then for each state $s_{i}\in S_{A}$
there is an equivalent state distribution $\pi^{\prime}_{i}$ of $B$, and for
each state $t_{j}\in S_{B}$ there is an equivalent state distribution
$\pi_{j}$ of $A$. Write

$\pi^{\prime}_{i}=\sum_{k=1}^{n}c_{ik}t_{k}\quad\mbox{and}\quad\pi_{j}=\sum_{l=1}^{m}d_{jl}s_{l}.$

Thus the state $s_{i}$ is equivalent to the state distribution

$\sum_{k=1}^{n}\sum_{l=1}^{m}c_{ik}d_{kl}s_{l}=\sum_{l=1}^{m}s_{l}\sum_{k=1}^{n}c_{ik}d_{kl}.$

Since the automaton $A$ is minimal, the right-hand of the equation must be
equal to $s_{i}$; that is,

$\sum_{k=1}^{n}c_{ik}d_{kl}=\left\\{\begin{array}[]{ll}1&\mbox{if }i=l,\\\
0&\mbox{if }i\neq l.\end{array}\right.$

Take the $n\times m$ matrix $C=(c_{ij})$ and the $m\times n$ matrix
$D=(d_{jk})$. Both matrices are stochastic, since their rows are state
distributions. Moreover, the above equation shows that $C\cdot D=I_{n}$ and
$D\cdot C=I_{m}$. Therefore, by Lemma 5.1, we have $m=n$ and the matrices $C$
and $D$ are permutation matrices. In particular, the state distributions
$\pi_{j}$ and $\pi^{\prime}_{i}$ are unit vectors and therefore correspond to
the states of $A$ and $B$, respectively. Thus for each state in $A$ there is
an equivalent state in $S_{B}$, and vice versa. Hence, the automata $A$ and
$B$ are S-equivalent. ∎

The construction of minimal stochastic automata is sketched in the next
result.

######  Theorem 5.3.

Each reduced stochastic automaton $A$ is equivalent to a minimal stochastic
automaton.

###### Proof.

Consider the set $Z_{A}$ of all states $s\in S_{A}$ for which there is a state
distribution $\pi$ of $A$ such that $s$ and $\pi$ are distinct and equivalent.
After rearranging the state set, write $S_{A}=\\{s_{1},\ldots,s_{n}\\}$ and
$Z_{A}=\\{s_{1},\ldots,s_{k}\\}$ with $k\leq n$. If $Z_{A}$ is the empty set,
the automaton $A$ is already minimal.

Suppose $Z_{A}\neq\emptyset$. Consider the state $s_{1}\in Z_{A}$. There is a
state distribution $\pi^{\prime}_{1}$ of $A$ such that $s_{1}$ and
$\pi^{\prime}_{1}$ are distinct and equivalent. Write
$\pi^{\prime}_{1}=\sum_{i=1}^{n}\pi^{\prime}_{1i}s_{i}$. Since $s_{1}$ and
$\pi^{\prime}_{1}$ are different, we have $\pi^{\prime}_{11}\neq 1$. Then by
Prop. 4.5, the state $s_{1}$ is equivalent to the state distribution

$\pi_{1}=\sum_{i=2}^{n}\frac{\pi^{\prime}_{1i}}{1-\pi^{\prime}_{11}}s_{i},$

where $\pi_{11}=0$ and $\pi_{i}=\frac{\pi^{\prime}_{1i}}{1-\pi^{\prime}_{11}}$
for each $2\leq i\leq n$.

More generally, one can show by induction that for each $1\leq l\leq k$, the
following holds: For each state $s_{i}$, $1\leq i\leq l$, there is a state
distribution $\pi_{i}$ of $A$ which is equivalent to $s_{i}$ and has the
property that $\pi_{i1}=\ldots=\pi_{il}=0$. In particular, the case $l=k$
shows that for each state $s_{i}$, $1\leq i\leq k$, there is a state
distribution $\pi_{i}$ of $A$ which is equivalent to $s_{i}$ and has the
property that $\pi_{i1}=\ldots=\pi_{ik}=0$.

Take the stochastic automaton $B$ with state set $S_{B}=S_{A}\setminus
Z_{A}=\\{s_{k+1},\ldots,s_{n}\\}$ and conditional probabilities

$p_{B}(b,s_{j}\mid a,s)=p_{A}(b,s_{j}\mid a,s)+\sum_{i=1}^{k}\pi_{ij}\cdot
p_{A}(b,s_{i}\mid a,s)$

for all $a\in\Sigma$, $b\in\Omega$, and $s,s_{j}\in S_{B}$. By definition, the
automaton $B$ is minimal. Claim that the automata $A$ and $B$ are equivalent.
Indeed, define the $k\times(n-k)$ matrix

$\Pi=\left(\begin{array}[]{ccc}\pi_{1,k+1}&\ldots&\pi_{1,n}\\\
\vdots&\ddots&\vdots\\\ \pi_{k,k+1}&\ldots&\pi_{k,n}\\\ \end{array}\right),$

the $(n-k)\times n$ matrix

$R=\left(O_{n-k,k}\;I_{n-k}\right)$

where $O_{n-k,k}$ denotes $(n-k)\times k$ zero matrix and $I_{n-k}$ the
$(n-k)\times(n-k)$ unit matrix, and the $n\times(n-k)$ matrix

$S=\left(\begin{array}[]{c}\Pi\\\ I_{n-k}\end{array}\right).$

This gives the $n\times n$ matrix

$SR=\left(\begin{array}[]{cc}O_{k,k}&\Pi\\\
O_{n-k,k}&I_{n-k}\end{array}\right).$

Since the state $s_{i}$ is equivalent to the state distribution $\pi_{i}$ for
$1\leq i\leq k$, we obtain

$\displaystyle SR\cdot\eta_{A}(y\mid x)=\eta_{A}(y\mid x),\quad
x\in\Sigma^{*},\;y\in\Omega^{*}.$ (5.1)

Moreover, the substochastic matrices defining $A$ and $B$ satisfy

$\displaystyle R\cdot P_{A}(b\mid a)\cdot S=P_{B}(b\mid a),\quad
a\in\Sigma,\;b\in\Omega.$ (5.2)

Claim that for all $x\in\Sigma^{*}$ and $y\in\Omega^{*}$ with $|x|=|y|$,

$\eta_{B}(y\mid x)=R\cdot\eta_{A}(y\mid x).$

Indeed, the equation holds for $x=y=\epsilon$. Suppose the equation is valid
for all $x\in\Sigma^{*}$ and $y\in\Omega^{*}$ with $|x|=|y|\leq l$ for some
$l\geq 0$. Then we obtain for $a\in\Sigma$, $b\in\Omega$, $x\in\Sigma^{*}$,
and $y\in\Omega^{*}$ with $|x|=|y|=l$,

$\displaystyle\eta_{B}(by\mid ax)$ $\displaystyle=$ $\displaystyle P_{B}(b\mid
a)\cdot\eta_{B}(y\mid x),\quad\mbox{by Prop.~{}\ref{p-omega}},$
$\displaystyle=$ $\displaystyle R\cdot P_{A}(b\mid a)\cdot
S\cdot\eta_{B}(y\mid x),\quad\mbox{by~{}(\ref{e-RS})},$ $\displaystyle=$
$\displaystyle R\cdot P_{A}(b\mid a)\cdot SR\cdot\eta_{A}(y\mid
x),\quad\mbox{by induction},$ $\displaystyle=$ $\displaystyle R\cdot
P_{A}(b\mid a)\cdot\eta_{A}(y\mid x),\quad\mbox{by~{}(\ref{e-SR})},$
$\displaystyle=$ $\displaystyle R\cdot\eta_{A}(by\mid ax),\quad\mbox{by
Prop.~{}\ref{p-omega}}.$

By definition of the matrix $R$, the vector $\eta_{B}(y\mid
x)=R\cdot\eta_{A}(y\mid x)$ consists of the last $n-k$ components of the
vector $\eta_{A}(y\mid x)$. It follows that state $s_{i}$ of $A$ is equivalent
to the state $s_{i}$ of $B$ for each $k+1\leq i\leq n$. Moreover, for each
$1\leq i\leq k$, the state $s_{i}$ of $A$ is equivalent to the state
distribution $\pi_{i}$ of $B$. Thus for each state of $A$ there is an
equivalent state distribution of $B$ and for each state of $B$ there is an
equivalent state distribution of $A$. Hence, by the proof of Prop. 3.4, the
automata $A$ and $B$ are equivalent. ∎

Note that the minimal stochastic automaton $B$ can be successively constructed
from the given stochastic automaton $A$. Suppose the state $s_{1}\in S_{A}$ is
equivalent to the state distribution $\pi=(0,\pi_{2},\ldots,\pi_{n})$. Note
that this distribution can be obtained as in the above proof. Then take the
stochastic automaton $B_{1}$ with state set
$S_{B_{1}}=S_{A}\setminus\\{s_{1}\\}$ and conditional probabilities

$\displaystyle p_{B_{1}}(b,s_{j}\mid a,s)=p_{A}(b,s_{j}\mid a,s)+\pi_{j}\cdot
p_{A}(b,s_{1}\mid a,s)$ (5.3)

for all $a\in\Sigma$, $b\in\Omega$, and $s,s_{j}\in S_{B_{1}}$. The iteration
of this process leads to a minimal stochastic automaton equivalent to $A$.

  * Example 10.

Take the stochastic automaton
$A=(\\{s_{1},s_{2},s_{3}\\},\\{a\\},\\{b,c\\},p)$ with substochastic matrices

$P_{A}(b\mid a)=\left(\begin{array}[]{ccc}0&0&\frac{1}{2}\\\
0&0&\frac{1}{3}\\\ 0&0&\frac{2}{3}\end{array}\right)\quad\mbox{and}\quad
P_{A}(c\mid a)=\left(\begin{array}[]{ccc}0&0&\frac{1}{2}\\\ 0&0&\frac{2}{3}\\\
0&0&\frac{1}{3}\end{array}\right).$

This gives the matrix

$H_{A}=\begin{pmatrix}1&\frac{1}{2}\\\ 1&\frac{1}{3}\\\
1&\frac{2}{3}\end{pmatrix}.$

This automaton is reduced by Prop. 4.5 but not minimal, since the state
$s_{1}$ and the state distribution $\pi=(0,\frac{1}{2},\frac{1}{2})$ are
equivalent. Therefore, define the stochastic automaton $B_{1}$ with state set
$S_{B_{1}}=\\{s_{2},s_{3}\\}$ and substochastic matrices

$P_{B_{1}}(b\mid a)=\left(\begin{array}[]{cc}0&\frac{1}{3}\\\
0&\frac{2}{3}\end{array}\right)\quad\mbox{and}\quad P_{B_{1}}(c\mid
a)=\left(\begin{array}[]{cc}0&\frac{2}{3}\\\ 0&\frac{1}{3}\end{array}\right).$

This gives the matrix

$H_{B_{1}}=\begin{pmatrix}1&\frac{1}{3}\\\ 1&\frac{2}{3}\end{pmatrix}.$

This automaton is already minimal. $\diamondsuit$

A vector $u\in{\mathbb{R}}^{n}$ is a convex combination of vectors
$v_{1},\ldots,v_{k}\in{\mathbb{R}}^{n}$ if there are nonnegative real numbers
$\lambda_{1},\ldots,\lambda_{k}$ such that

$\sum_{i=1}^{k}\lambda_{i}v_{i}=u\quad\mbox{and}\quad\sum_{i=1}^{k}\lambda_{i}=1.$

The minimality of a stochastic automaton can be tested by using the
$H$-matrices.

######  Proposition 5.4.

A stochastic automaton $A$ is minimal if and only if no row of $H_{A}$ is a
convex combination of the other rows.

###### Proof.

Suppose the automaton $A$ is not minimal. Then there is a state $s_{i}$ and a
state distribution $\pi$ such that $s_{i}$ and $\pi$ are distinct and
equivalent. As in the proof of Thm. 5.3, the state distribution $\pi$ can be
chosen such that the $i$th component is $\pi_{i}=0$. By Prop. 4.5, we have
$s_{i}H_{A}=\pi H_{A}$. This equation says that the $i$th row of $H_{A}$ given
by $s_{i}H_{A}$ is a convex combination of the remaining rows of $H_{A}$ given
by $\pi H_{A}$. ∎

  * Example 11.

(Shimon Even, 1965) Let $\Sigma=\\{a,b\\}$, $\Omega=\\{c,d,e\\}$, and
$S=\\{s_{1},\ldots,s_{5}\\}$. Consider the stochastic automaton
$A=(S,\Sigma,\Omega,p_{A})$ with substochastic matrices

$\begin{array}[]{ll}P_{A}(c\mid
a)=\left(\begin{array}[]{ccccc}0&\frac{1}{2}&0&0&0\\\ 0&\frac{1}{2}&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\end{array}\right),&P_{A}(d\mid
a)=\left(\begin{array}[]{ccccc}0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&\frac{1}{2}&0\\\ 0&0&0&\frac{1}{2}&0\\\ 0&0&0&0&0\end{array}\right),\\\
P_{A}(e\mid a)=\left(\begin{array}[]{ccccc}0&0&0&0&\frac{1}{2}\\\
0&0&0&0&\frac{1}{2}\\\ 0&0&0&0&\frac{1}{2}\\\ 0&0&0&0&\frac{1}{2}\\\
\frac{1}{2}&0&\frac{1}{2}&0&0\end{array}\right),&P_{A}(c\mid
b)=\left(\begin{array}[]{ccccc}\frac{1}{2}&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\\\ \frac{1}{2}&0&0&0&0\\\ 0&0&0&0&0\\\ \end{array}\right),\\\
P_{A}(d\mid b)=\left(\begin{array}[]{ccccc}0&0&0&0&0\\\ 0&0&\frac{1}{2}&0&0\\\
0&0&\frac{1}{2}&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
\end{array}\right),&P_{A}(e\mid
b)=\left(\begin{array}[]{ccccc}0&0&0&0&\frac{1}{2}\\\ 0&0&0&0&\frac{1}{2}\\\
0&0&0&0&\frac{1}{2}\\\ 0&0&0&0&\frac{1}{2}\\\
\frac{1}{2}&0&\frac{1}{2}&0&0\end{array}\right),\end{array}$

and the stochastic automaton $B=(S,\Sigma,\Omega,p_{B})$ with substochastic
matrices $P_{B}(c\mid a)=P_{A}(c\mid a)$, $P_{B}(d\mid a)=P_{A}(d\mid a)$,
$P_{B}(c\mid b)=P_{A}(c\mid b)$, $P_{B}(d\mid b)=P_{A}(d\mid b)$, and

$P_{B}(e\mid a)=\left(\begin{array}[]{ccccc}0&0&0&0&\frac{1}{2}\\\
0&0&0&0&\frac{1}{2}\\\ 0&0&0&0&\frac{1}{2}\\\ 0&0&0&0&\frac{1}{2}\\\
\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&0\end{array}\right)=P_{B}(e\mid
b).$

The vector space $V_{A}$ has the basis elements
$\eta_{A}(\epsilon\mid\epsilon)$, $\eta_{A}(c\mid a)$, $\eta_{A}(c\mid b)$,
and $\eta_{A}(e\mid a)$; that is,

$H_{A}=\left(\begin{array}[]{cccc}1&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\\
1&\frac{1}{2}&0&\frac{1}{2}\\\ 1&0&0&\frac{1}{2}\\\
1&0&\frac{1}{2}&\frac{1}{2}\\\ 1&0&0&1\end{array}\right).$

Furthermore, we have $H_{A}=H_{B}$. It is easy to check that no row of $H_{A}$
is a convex combination of the other rows. Thus both automata are minimal by
Prop. 5.4 and both automata are S-equivalent by Thm. 4.7. Hence, the automata
are equivalent by Prop. 5.2. However, the automata $A$ and $B$ are not
isomorphic. $\diamondsuit$

This example shows that there are stochastic automata which are minimal and
equivalent, but not isomorphic.

Finally, the aim is to further reduce the state set of a minimal stochastic
automaton. For this, a stochastic automaton $A$ is called strongly reduced if
equivalent state distributions of $A$ are equal. By definition, each strongly
reduced stochastic automaton is minimal. However, not every minimal stochastic
automaton is strongly reduced.

  * Example 12.

In the example of Even, the state distributions
$\pi=(\frac{1}{2},0,\frac{1}{2},0,0)$ and
$\pi^{\prime}=(0,\frac{1}{2},0,\frac{1}{2},0)$ are equivalent, since $\pi
H_{A}=(1,\frac{1}{4},\frac{1}{4},\frac{1}{2})=\pi^{\prime}H_{A}$. It follows
that the minimal automaton $A$ is not strongly reduced. $\diamondsuit$

Strong reduction of a stochastic automaton can be tested by using the
$H$-matrices.

######  Proposition 5.5.

Let $A$ be a stochastic automaton with $n$ states. Then $A$ is strongly
reduced if and only if the matrix $H_{A}$ has rank $n$.

###### Proof.

Suppose the $n\times d$ matrix $H_{A}$ has rank $d=n$. Then $H_{A}$ is an
$n\times n$ matrix which determines a bijective linear mapping. Let $\pi$ and
$\pi^{\prime}$ be equivalent state distributions of $A$. Then by Prop. 4.5, we
have $\pi H_{A}=\pi^{\prime}H_{A}$; i.e., $(\pi-\pi^{\prime})H_{A}=0$. But the
kernel of the bijective linear mapping provided by $H_{A}$ is the zero space
$\\{0\\}$. Thus we have $\pi=\pi^{\prime}$ and hence the automaton $A$ is
strongly reduced.

Conversely, suppose the $n\times d$ matrix $H_{A}$ has rank $d<n$. Then the
kernel of the linear mapping given by $H_{A}$ has nonzero dimension. That is,
there is a nonzero vector $u\in{\mathbb{R}}^{n}$ such that $uH_{A}=0$. Since
the first column of the matrix $H_{A}$ is the all-one vector, we have
$\sum_{i=1}^{n}u_{i}=0$. Moreover, since the vector $u$ is nonzero and the
matrix $H_{A}$ is nonnegative, the vector $u$ must have nonzero positive and
nonzero negative components. Let $u^{+}$ be the vector, which results from $u$
by setting all negative entries to 0. Moreover, put $u^{-}=u^{+}-u$; i.e.,
$u^{-}$ results from $u$ by setting all positive entries to 0 and then
changing signs. Then the vectors $u^{+}$ and $u^{-}$ are nonnegative with
$u=u^{+}-u^{-}$. For instance, if $u=(1,-4,3,0)$, then $u^{+}=(1,0,3,0)$ and
$u^{-}=(0,4,0,0)$. Since $\sum_{i=1}^{n}u_{i}=0$, we have
$\alpha=\sum_{i}u_{i}^{+}=\sum_{i}u_{i}^{-}$ and so
$\pi^{+}=\frac{1}{\alpha}u^{+}$ and $\pi^{-}=\frac{1}{\alpha}u^{-}$ are state
distributions of $A$ with $(\pi^{+}-\pi^{-})H_{A}=0$; i.e.,
$\pi^{+}H_{A}=\pi^{-}H_{A}$. Thus by Prop. 4.5, the distributions $\pi^{+}$
and $\pi^{-}$ are equivalent and hence the automaton $A$ is not strongly
reduced. ∎

  * Example 13.

Each reduced stochastic automaton $A$ with two states is strongly reduced. To
see this, consider the corresponding matrix

$H_{A}=\begin{pmatrix}1&a_{1}\\\ 1&a_{2}\end{pmatrix}.$

Suppose the state distributions $(b,1-b)$ and $(c,1-c)$ are equivalent. Then
equivalently $(b,1-b)H_{A}=(c,1-c)H_{A}$ and so $a_{1}(b-c)=a_{2}(b-c)$. If
the distributions are distinct, then $b\neq c$ and thus $a_{1}=a_{2}$. It
follows that the matrix has rank $1$ and so $A$ is not reduced contradicting
the hypothesis. $\diamondsuit$

A geometric interpretation can help to tackle the question whether a
stochastic automaton $A$ is reduced, minimal or strongly reduced. These
properties only depend on the matrix $H_{A}$ and so its obvious to further
analyse the vectors of this matrix. For this, let $H_{A}$ be an $n\times d$
matrix with row vectors $h_{1},\ldots,h_{n}$. These vectors span an
$(n-1)$-dimensional simplex

$\displaystyle
C_{A}=\left\\{\sum_{i=1}^{n}c_{i}h_{i}\mid\sum_{i=1}^{n}c_{i}=1\mbox{ and
}c_{i}\geq 0\mbox{ for }1\leq i\leq n\right\\}.$ (5.4)

Note that an $(n-1)$-simplex is an $(n-1)$-dimensional polytope which is given
by the convex hull of its $n$ vertices.

######  Proposition 5.6.

Let $A$ be a stochastic automaton.

  * •

$A$ is not reduced if and only if two generating vectors of $C_{A}$ are equal.

  * •

$A$ is not minimal if and only if one of the generating vectors of $C_{A}$ is
not a vertex.

  * •

$A$ is not strongly reduced if and only if $C_{A}$ has dimension less than
$n-1$.

The proof follows from the Props. 4.5, 5.4, and 5.5.

  * Example 14.

The stochastic automaton $A$ in Fig. 4.2 has the matrix

$H_{A}=\begin{pmatrix}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\ 1&\frac{1}{2}\\\
1&\frac{1}{2}\\\ \end{pmatrix}$

and thus is not reduced. The stochastic automata $B$ in Fig. 4.3 has the
matrix

$H_{B}=\begin{pmatrix}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\ 1&\frac{1}{2}\\\
\end{pmatrix}.$

The vectors $h_{1}=(1,\frac{1}{3})$, $h_{2}=(1,\frac{2}{3})$, and
$h_{3}=(1,\frac{1}{2})$ span a line segment or $1$-simplex with vertices
$h_{1}$ and $h_{2}$, while $h_{3}$ lies in-between. Therefore, $B$ is not
minimal. $\diamondsuit$

  * Example 15.

The matrix $H_{A}$ of the stochastic automaton $A$ in Even’s example is
spanned by the vectors

$\displaystyle h_{1}$ $\displaystyle=$
$\displaystyle(1,\frac{1}{2},\frac{1}{2},\frac{1}{2}),$ $\displaystyle h_{2}$
$\displaystyle=$ $\displaystyle(1,\frac{1}{2},0,\frac{1}{2}),$ $\displaystyle
h_{3}$ $\displaystyle=$ $\displaystyle(1,0,0,\frac{1}{2}),$ $\displaystyle
h_{4}$ $\displaystyle=$ $\displaystyle(1,0,\frac{1}{2},\frac{1}{2}),$
$\displaystyle h_{5}$ $\displaystyle=$ $\displaystyle(1,0,0,1).$

These vectors span a pyramid with a quadratic base, where the apex is
perpendicular above one of the vertices. Therefore, the automaton $A$ is
minimal. Since the vectors span a $3$-dimensional simplex, the automaton is
not strongly reduced. $\diamondsuit$

##  Chapter 6 Coverings

The previous chapters have shown that the state set of a stochastic automaton
can eventually be decreased without diminishing its performance. Further
reductions are possible if coverings of stochastic automata are considered.

For this, let $A=(S_{A},\Sigma,\Omega,p_{A})$ and
$B=(S_{B},\Sigma,\Omega,p_{B})$ be stochastic automata, and let $S_{A}$ and
$S_{B}$ have $n$ and $m$ states, respectively. The automaton $B$ is a
stochastic image of automaton $A$, written $A\rightarrow_{s}B$, if there is a
stochastic $m\times n$ matrix $Q$ such that for all $x\in\Sigma^{*}$ and
$y\in\Omega^{*}$,

$\displaystyle\eta_{B}(y\mid x)=Q\cdot\eta_{A}(y\mid x).$ (6.1)

Note that the matrix $Q$ defines a linear mapping
$\phi:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{m}:v\mapsto Qv$ such that
$\phi$ maps the result vectors $\eta_{A}(y\mid x)$ to the result vectors
$\eta_{B}(y\mid x)$.

######  Proposition 6.1.

Let $A$ and $B$ be stochastic automata with the same input and output
alphabets. Then $A$ covers $B$ if and only if $B$ is a stochastic image of
$A$.

###### Proof.

Let $S_{A}=\\{s_{1},\ldots,s_{n}\\}$ and $S_{B}=\\{t_{1},\ldots,t_{m}\\}$.

Suppose $A$ covers $B$. Then by Lemma 3.3, for each state $t\in S_{B}$ there
is an equivalent state distribution $q_{j}$ of $A$. Let $Q$ be the matrix with
rows $q_{1},\ldots,q_{m}$. Then $\eta_{B}^{t_{j}}(y\mid
x)=q_{j}\cdot\eta_{A}(y\mid x)$ for all $x\in\Sigma^{*}$, $y\in\Omega^{*}$ and
$1\leq j\leq m$. Thus $\eta_{B}(y\mid x)=Q\cdot\eta_{A}(y\mid x)$ for all
$x\in\Sigma^{*}$, $y\in\Omega^{*}$. Hence, $B$ is a stochastic image of $A$.

Conversely, let $B$ be a stochastic image of $A$. The $j$th row $q_{i}$ of the
matrix $Q$ is a state distribution of $A$. Then $\eta_{B}^{t_{j}}(y\mid
x)=q_{j}\cdot\eta_{A}(y\mid x)$ for all $x\in\Sigma^{*}$, $y\in\Omega^{*}$ and
$1\leq j\leq m$. Thus the state $t_{j}$ is equivalent to the state
distribution $q_{j}$ of $A$. By Lemma 3.3, it follows that $A$ covers $B$. ∎

Stochastic homomorphy is reflected by the corresponding $H$-matrices.

######  Proposition 6.2.

Let $A$ and $B$ be stochastic automata with the same input and output
alphabets. If there is an $m\times n$ matrix $Q$ such that $B$ is a stochastic
image of $A$, then $H_{B}$ is obtained from $Q\cdot H_{A}$ by deleting
linearly dependent columns. If the columns of $Q\cdot H_{A}$ are linearly
independent, then $H_{B}=Q\cdot H_{A}$.

###### Proof.

Let $\eta_{1},\ldots,\eta_{d}$ be the columns of the $n\times d$ matrix
$H_{A}$. Then $\eta^{\prime}_{i}=Q\cdot\eta_{i}$ for $1\leq i\leq d$ are the
columns of the $m\times d$ matrix $Q\cdot H_{A}$. Since each result vector
$\eta_{A}(y\mid x)$ of $A$ is a linear combination of the vectors
$\eta_{1},\ldots,\eta_{d}$, the vector $\eta_{B}(y\mid x)=Q\cdot\eta_{A}(y\mid
x)$ is a linear combination of the vectors
$\eta^{\prime}_{1}=Q\cdot\eta_{1},\ldots,\eta^{\prime}_{d}=Q\cdot\eta_{d}$.

Put $C=QH_{A}$. We may assume that the columns of $C$ are totally ordered as
given by the set $M$ in (4.3). It is easy to check that the matrix $D$
obtained from $C$ by deleting in turn the columns which are linear
combinations of previous columns is exactly the matrix $H_{B}$. Moreover, if
the columns of $QH_{A}$ are linearly independent, then $C=D=QH_{A}$. ∎

  * Example 16.

The stochastic automata $A$ and $B^{\prime}$ in Figs. 4.2 and 4.4 have the
respective matrices

$H_{A}=\begin{pmatrix}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\ 1&\frac{1}{2}\\\
1&\frac{1}{2}\\\ \end{pmatrix}\quad\mbox{and}\quad
H_{B^{\prime}}=\begin{pmatrix}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\
1&\frac{1}{2}\\\ \end{pmatrix}.$

Then $B^{\prime}$ is a stochastic image of $A$ by using the matrix
$Q=\begin{pmatrix}&0\\\ I_{3}&0\\\ &0\end{pmatrix}$. $\diamondsuit$

######  Proposition 6.3.

Let $A$ and $B$ be stochastic automata with the same input and output
alphabets. Suppose $A$ and $B$ have $n$ and $m$ states, respectively. Then $B$
is a stochastic image of $A$ if and only if there exists a stochastic $m\times
n$ matrix $Q$ such that for all $a\in\Sigma$ and $b\in\Omega$,

$Q\cdot P_{A}(b\mid a)\cdot H_{A}=P_{B}(b\mid a)\cdot Q\cdot H_{A}.$

###### Proof.

Let $B$ be a stochastic image of $A$. That is, there is a stochastic $m\times
n$ matrix $Q$ such that $Q\cdot\eta_{A}(y\mid x)=\eta_{B}(y\mid x)$ for all
$x\in\Sigma^{*}$ and $y\in\Omega^{*}$.

Equivalently, $Q\cdot\eta_{A}(y\mid x)=\eta_{B}(y\mid x)$ for all
$x\in\Sigma^{+}$ and $y\in\Omega^{+}$, since
$Q\cdot\eta_{A}(\epsilon\mid\epsilon)=\eta_{B}(\epsilon\mid\epsilon)$.

Equivalently, $Q\cdot\eta_{A}(by\mid ax)=\eta_{B}(by\mid ax)$ for all
$a\in\Sigma$, $b\in\Omega$, $x\in\Sigma^{*}$ and $y\in\Omega^{*}$.

Equivalently, by Prop. 3.1, $Q\cdot P_{A}(b\mid a)\cdot\eta_{A}(y\mid
x)=P_{B}(b\mid a)\cdot\eta_{B}(y\mid x)$ for all $a\in\Sigma$, $b\in\Omega$,
$x\in\Sigma^{*}$ and $y\in\Omega^{*}$.

Equivalently, $Q\cdot P_{A}(b\mid a)\cdot\eta_{A}(y\mid x)=P_{B}(b\mid a)\cdot
Q\cdot\eta_{A}(y\mid x)$ for all $a\in\Sigma$, $b\in\Omega$, $x\in\Sigma^{*}$
and $y\in\Omega^{*}$.

Equivalently, $Q\cdot P_{A}(b\mid a)\cdot H_{A}=P_{B}(b\mid a)\cdot Q\cdot
H_{A}$ for all $a\in\Sigma$ and $b\in\Omega$, since the columns of $H_{A}$
form a basis of the set of result vectors in $A$. ∎

General homomorphisms between stochastic automata are introduced. For this,
let $A=(S_{A},\Sigma,\Omega,p_{A})$ and $B=(S_{B},\Sigma,\Omega,p_{B})$ be
stochastic automata. An S-homomorphism from $A$ to $B$ is given by a mapping
$\phi:S_{A}\rightarrow S_{B}$ such that for all $a\in\Sigma$, $b\in\Omega$ and
$s,s^{\prime}\in S_{A}$,

$\displaystyle p_{B}(b,\phi(s^{\prime})\mid a,\phi(s))$ $\displaystyle=$
$\displaystyle p_{A}(b,\phi^{-1}\phi(s^{\prime})\mid a,s)$ $\displaystyle=$
$\displaystyle\sum_{s^{\prime\prime}\in
S_{A}\atop\phi(s^{\prime\prime})=\phi(s^{\prime})}p_{A}(b,s^{\prime\prime}\mid
a,s),$

where $\phi^{-1}\phi(s^{\prime})=\\{s^{\prime\prime}\in
S_{A}\mid\phi(s^{\prime\prime})=\phi(s^{\prime})\\}$.

An S-homomorphism from $A$ to $B$ is also written as $\phi:A\rightarrow B$. In
particular, an S-homomorphism $\phi:A\rightarrow B$ is called S-epimorphism if
the mapping $\phi$ is surjective. Each stochastic automaton $A$ can be mapped
by an S-epimomorphism to the trivial stochastic automaton
$B=(\\{a\\},\\{b\\},\\{s_{0}\\},p)$ with $p(b,s_{0}\mid a,s_{0})=1$.

######  Proposition 6.4.

Let $A=(S_{A},\Sigma,\Omega,p_{A})$ and $B=(S_{B},\Sigma,\Omega,p_{B})$ be
stochastic automata. Each S-homomorphism $\phi:A\rightarrow B$ satisfies

$\displaystyle p_{B}(y,\phi(s^{\prime})\mid
x,\phi(s))=p_{A}(y,\phi^{-1}\phi(s^{\prime})\mid x,s),$ (6.3)

where $x\in\Sigma^{*}$, $y\in\Omega^{*}$ and $s,s^{\prime}\in S_{A}$.

This assertion can be proved by induction on the length of the input words.

######  Proposition 6.5.

Let $\phi:A\rightarrow B$ be an S-homomorphism. Then each state $s$ in $A$ is
equivalent to the state $\phi(s)$ in $B$. In particular, if $\phi$ is an
S-epimorphism, then $A$ and $B$ are S-equivalent.

###### Proof.

For all $x\in\Sigma^{*}$, $y\in\Omega^{*}$, and $s\in S_{A}$, we have by Prop.
6.4,

$\eta_{B}^{\phi(s)}(y\mid x)=\eta_{A}^{s}(y\mid x).$

The results follow. ∎

  * Example 17.

Consider the stochastic automaton (Fig. 6.1)

$A=(\\{a\\},\\{b,c\\},\\{s_{1},s_{2},s_{3},s_{4}\\},p_{A}),$

where

$P_{A}(b\mid a)=\left(\begin{array}[]{cccc}0&0&\frac{1}{6}&\frac{1}{6}\\\
0&0&\frac{2}{3}&0\\\ 0&0&0&\frac{1}{2}\\\ 0&0&0&\frac{1}{2}\\\
\end{array}\right)\quad\mbox{and}\quad P_{A}(c\mid
a)=\left(\begin{array}[]{cccc}0&0&\frac{1}{3}&\frac{1}{3}\\\
0&0&\frac{1}{3}&0\\\ 0&0&\frac{1}{2}&0\\\ 0&0&0&\frac{1}{2}\\\
\end{array}\right)$

and the stochastic automaton (Fig. 6.2)

$B=(\\{a\\},\\{b,c\\},\\{t_{1},t_{2},t_{3}\\},p_{B}),$

where

$P_{B}(b\mid a)=\left(\begin{array}[]{ccc}0&0&\frac{1}{3}\\\
0&0&\frac{2}{3}\\\ 0&0&\frac{1}{2}\\\ \end{array}\right)\quad\mbox{and}\quad
P_{B}(c\mid a)=\left(\begin{array}[]{ccc}0&0&\frac{2}{3}\\\ 0&0&\frac{1}{3}\\\
0&0&\frac{1}{2}\\\ \end{array}\right).$

The mapping $\phi:S_{A}\rightarrow S_{B}$ given by $\phi(s_{1})=t_{1}$,
$\phi(s_{2})=t_{2}$ and $\phi(s_{3})=\phi(s_{4})=t_{3}$ is an S-epimorphism.
For instance, $p_{B}(b,t_{3}\mid a,t_{1})=p_{A}(b,s_{3}\mid
a,s_{1})+p_{A}(b,s_{4}\mid a,s_{1})=\frac{1}{6}+\frac{1}{6}=\frac{1}{3}$ and
$p_{B}(b,t_{3}\mid a,t_{2})=p_{A}(b,s_{3}\mid a,s_{2})+p_{A}(b,s_{4}\mid
a,s_{2})=\frac{2}{3}$. $\diamondsuit$

|
---|---
$\textstyle{s_{1}}$$\scriptstyle{a,b:1/6;\;a,c:1/3}$$\scriptstyle{a,b:1/6;\;a,c:1/3}$$\textstyle{s_{3}}$$\scriptstyle{a,c:1/2}$$\scriptstyle{a,b:\;1/2}$$\textstyle{s_{3}}$$\scriptstyle{a,b:1/2;\;a,c:1/2}$$\textstyle{s_{2}}$$\scriptstyle{a,b:2/3;\;a,c:1/3}$

Figure 6.1: State diagram of stochastic automaton $A$.

|
---|---
$\textstyle{t_{1}}$$\scriptstyle{a,b:1/3;\;a,c:2/3}$$\textstyle{t_{3}}$$\scriptstyle{a,b:1/2;\;a,c:1/2}$$\textstyle{t_{2}}$$\scriptstyle{a,b:2/3;\;a,c:1/3}$

Figure 6.2: State diagram of stochastic automaton $B$.

##  Chapter 7 Observability and Determinism

This chapter considers stochastic automata with restricted transition
probability distributions.

A stochastic automaton $A=(S,\Sigma,\Omega,p)$ is called observable if there
is a (partial) mapping $\gamma:\Omega\times\Sigma\times S\rightarrow S$ such
that for all $a\in\Sigma$, $b\in\Omega$, and $s,s^{\prime}\in S$,

$\displaystyle p(b,s^{\prime}\mid a,s)\neq 0\quad\Rightarrow\quad
s^{\prime}=\gamma(b,a,s).$ (7.1)

If in an observable stochastic automaton the current state, the input and the
output are known, the next state is uniquely determined.

The (partial) mapping $\gamma:\Omega\times\Sigma\times S\rightarrow S$ can be
extended to the (partial) mapping $\gamma:\Omega^{*}\times\Sigma^{*}\times
S\rightarrow S$ such that for all $a\in\Sigma$, $x\in\Sigma^{*}$,
$b\in\Omega$, $y\in\Omega^{*}$, $s,s^{\prime}\in S$ with $|x|=|y|$,

$\displaystyle\gamma(\epsilon,\epsilon,s)$ $\displaystyle=$ $\displaystyle s,$
(7.2) $\displaystyle\gamma(by,ax,s)$ $\displaystyle=$
$\displaystyle\gamma(y,x,\gamma(b,a,s)).$ (7.3)

######  Lemma 7.1.

A stochastic automaton $A$ is observable if and only if for all $a\in\Sigma$
and $b\in\Omega$, the matrices $P(b\mid a)$ contain in each row at most one
nonzero entry.

###### Proof.

Let $A$ be observable and let $S=\\{s_{1},\ldots,s_{n}\\}$. Consider the
$s_{i}$th row of the matrix $P(b\mid a)$. Since $p(b,s_{j}\mid a,s_{i})\neq 0$
implies $s_{j}=\gamma(b,a,s_{i})$, the $s_{i}$th row contains $p(b,s_{j}\mid
a,s_{i})$ as the only nonzero element.

Let the matrices $P(b\mid a)$ with $a\in\Sigma$ and $b\in\Omega$ contain in
each row at most one nonzero entry, say $p(b,s_{j}\mid a,s_{i})$. Then put
$s_{j}=\gamma(b,a,s_{i})$. This defines a mapping
$\gamma:\Omega\times\Sigma\times S\rightarrow S$ such that $A$ is observable.
∎

######  Proposition 7.2.

Let $A$ be a stochastic automaton and $\gamma:\Omega^{*}\times\Sigma^{*}\times
S\rightarrow S$ be the mapping as above. Then for all $s,s^{\prime}\in S$,
$x\in\Sigma^{*}$ and $y\in\Omega^{*}$ with $|x|=|y|$,

$\displaystyle p(y,s^{\prime}\mid x,s)\neq 0\quad\Rightarrow\quad
s^{\prime}=\gamma(y,x,s).$ (7.4)

###### Proof.

Let $y=by^{\prime}$ and $x=ax^{\prime}$ with $a\in\Sigma$, $b\in\Omega$,
$x^{\prime}\in\Sigma^{*}$ and $y^{\prime}\in\Omega^{*}$ with
$k=|x^{\prime}|=|y^{\prime}|$.

For $k=0$ the assertion is clear. Let $k\geq 1$. Suppose
$p(by^{\prime},s^{\prime}\mid ax^{\prime},s)\neq 0$. Then there is a state
$s^{\prime\prime}\in S$ such that $p(b,s^{\prime\prime}\mid a,s)\neq 0$ and
$p(y^{\prime},s^{\prime}\mid x^{\prime},s^{\prime\prime})\neq 0$. By
induction, $s^{\prime\prime}=\gamma(b,a,s)$ and
$s^{\prime}=\gamma(y^{\prime},x^{\prime},s^{\prime\prime})$. Hence,
$s^{\prime}=\gamma(y^{\prime},x^{\prime},\gamma(b,a,s)))=\gamma(by^{\prime},ax^{\prime},s)$.
∎

######  Proposition 7.3.

Let $A$ and $B$ be observable stochastic automata with mappings $\gamma_{A}$
and $\gamma_{B}$, respectively. For all $s\in S_{A}$, $s^{\prime}\in S_{B}$,
$a\in\Sigma$, and $b\in\Omega$, if $p_{A}(b,s^{\prime}\mid a,s)\neq 0$ and the
states $s$ and $s^{\prime}$ are equivalent, the states $\gamma_{A}(b,a,s)$ and
$\gamma_{B}(b,a,s^{\prime})$ are also equivalent.

###### Proof.

Let $a\in\Sigma$ and $b\in\Omega$. By Lemma 7.1, the rows $s\cdot P_{A}(b\mid
a)$ and $s^{\prime}\cdot P_{B}(b\mid a)$ contain a single nonzero element
$p_{A}(b,\gamma_{A}(b,a,s)\mid a,s)$ and
$p_{B}(b,\gamma_{B}(b,a,s^{\prime})\mid a,s^{\prime})$, respectively. These
are exactly the entries of $s\cdot\eta_{A}(b\mid a)$ and
$s^{\prime}\cdot\eta_{B}(b\mid a)$, respectively. Thus by the convention that
single states represent unit vectors in the state space, we obtain

$\frac{1}{s\cdot\eta_{A}(b\mid a)}s\cdot P_{A}(b\mid a)=\gamma_{A}(b,a,s),$

where $s\cdot\eta_{A}(b\mid a)\neq 0$, and

$\frac{1}{s^{\prime}\cdot\eta_{B}(b\mid a)}s^{\prime}\cdot P_{B}(b\mid
a)=\gamma_{B}(b,a,s^{\prime}),$

where $s^{\prime}\cdot\eta_{B}(b\mid a)\neq 0$. Then for all $a\in\Sigma$,
$x\in\Sigma^{*}$, $b\in\Omega$, and $y\in\Omega^{*}$,

$\displaystyle\gamma_{A}(b,a,s)\cdot\eta_{A}(y\mid x)$ $\displaystyle=$
$\displaystyle\frac{1}{s\cdot\eta_{A}(b\mid a)}s\cdot P_{A}(b\mid
a)\cdot\eta_{A}(y\mid x)$ $\displaystyle=$
$\displaystyle\frac{1}{s\cdot\eta_{A}(b\mid a)}s\cdot\eta_{A}(by\mid
ax),\;\mbox{by Prop.~{}\ref{p-omega}},$ $\displaystyle=$
$\displaystyle\frac{1}{s^{\prime}\cdot\eta_{B}(b\mid
a)}s^{\prime}\cdot\eta_{B}(by\mid ax),\;\mbox{by equivalence of
$s,s^{\prime}$},$ $\displaystyle=$
$\displaystyle\frac{1}{s^{\prime}\cdot\eta_{B}(b\mid a)}s^{\prime}\cdot
P_{B}(b\mid a)\;\eta_{B}(y\mid x),\quad\mbox{by Prop.~{}\ref{p-omega}},$
$\displaystyle=$ $\displaystyle\gamma_{B}(b,a,s^{\prime})\cdot\eta_{B}(y\mid
x).$

Hence, $\gamma_{A}(b,a,s)$ and $\gamma_{B}(b,a,s^{\prime})$ are equivalent. ∎

  * Example 18.

Take the stochastic automaton
$A=(\\{s_{1},s_{2},s_{3}\\},\\{a\\},\\{b,c\\},p)$ in Fig. 7.1 with

$P(b\mid a)=\begin{pmatrix}0&\frac{1}{2}&0\\\ 0&\frac{1}{3}&0\\\
0&\frac{5}{12}&0\\\ \end{pmatrix}\quad\mbox{and}\quad P(c\mid
a)=\begin{pmatrix}0&\frac{1}{2}&0\\\ 0&\frac{2}{3}&0\\\ 0&\frac{7}{12}&0\\\
\end{pmatrix}.$

This automaton is observable with $\gamma(b,a,s)=\gamma(c,a,s)=s_{2}$ for all
$s\in S$. It is reduced, since the row vectors in the corresponding $H$-matrix
are distinct (Prop. 5.6),

$H_{A}=\begin{pmatrix}1&\frac{1}{2}\\\ 1&\frac{1}{3}\\\ 1&\frac{5}{12}\\\
\end{pmatrix}.$

However, the automaton is not minimal by Prop. 4.5, since the state $s_{3}$ is
equivalent to the state distribution $(\frac{1}{2},\frac{1}{2},0)$.
$\diamondsuit$

|
---|---
$\textstyle{s_{1}}$$\scriptstyle{a,b:1/2;\;a,c:1/2}$$\textstyle{s_{2}}$$\scriptstyle{a,b:1/3;\;a,c:2/3}$$\textstyle{s_{3}}$$\scriptstyle{a,b:5/12;\;a,c:7/12}$

Figure 7.1: State diagram of observable stochastic automaton $A$.

The last part of this chapter is devoted to deterministic automata.

A stochastic automaton $A$ is called state-determined if there is a mapping
$\delta:\Sigma\times S\rightarrow S$ such that for all $a\in\Sigma$ and $s\in
S$,

$\displaystyle\sum_{b\in\Omega}p(b,\delta(a,s)\mid a,s)=1.$ (7.5)

If a state-determined stochastic automaton $A$ is in state $s$ and $a$ is the
input, then $A$ transits into the state $\delta(a,s)$ with certainty.

######  Lemma 7.4.

A stochastic automaton $A$ is state-determined if and only if for each
$a\in\Sigma$, the matrix $P(a)=\sum_{b\in\Omega}P(b\mid a)$ contains in each
row exactly one entry $1$.

A state-determined stochastic automaton is a specialized observable stochastic
automaton in which the mapping $\gamma$ is independent of the output.

  * Example 19.

Consider the stochastic automaton $A=(\\{s_{1},s_{2}\\},\\{a\\},\\{b,c\\},p)$
in Fig. 7.2 with

$P(b\mid a)=\begin{pmatrix}0&\frac{1}{3}\\\ 0&\frac{2}{3}\\\
\end{pmatrix}\quad\mbox{and}\quad P(c\mid a)=\begin{pmatrix}0&\frac{2}{3}\\\
0&\frac{1}{3}\\\ \end{pmatrix}.$

This automaton is state-determined and strongly reduced by Prop. 5.5, since
the $H$-matrix has full rank,

$H_{A}=\begin{pmatrix}1&\frac{1}{3}\\\ 1&\frac{2}{3}\\\ \end{pmatrix}.$

$\diamondsuit$

$\textstyle{s_{1}}$$\scriptstyle{a,b:1/3;\;a,c:2/3}$$\textstyle{s_{2}}$$\scriptstyle{a,b:2/3;\;a,c:1/3}$

Figure 7.2: State diagram of state-determined stochastic automaton $A$.

A stochastic automaton $A$ is called output-determined if there is a mapping
$\lambda:\Sigma\times S\rightarrow\Omega$ such that for all $a\in\Sigma$ and
$s\in S$,

$\displaystyle\sum_{s^{\prime}\in S}p(\lambda(a,s),s^{\prime}\mid a,s)=1.$
(7.6)

If an output-determined stochastic automaton $A$ is in state $s$ and $a$ is
the input, then $A$ outputs $\lambda(a,s)$ with certainty.

######  Lemma 7.5.

A stochastic automaton $A$ is output-determined if and only if for all
$a\in\Sigma$ and $s\in S$, the matrix $P(\lambda(a,s)\mid a)$ contains a
nonzero row labeled by $s$ whose entries sum up to $1$.

######  Proposition 7.6.

For each output-determined stochastic automaton there exists an output-
determined reduced stochastic automaton.

###### Proof.

Construct for a given output-determined stochastic automaton $A$ a reduced
stochastic automaton $B$ by the powerset method described in the proof of Thm.
4.2.

Using the notation in the proof, two states $s$ and $t$ in $A$ are equivalent
if and only if they lie an a state $Z_{i}$ of $B$. In particular,
$s\cdot\eta_{A}(b\mid a)=t\cdot\eta_{A}(b\mid a)$. If this value is nonzero,
then the output is $b=\lambda_{A}(a,s)=\lambda_{A}(a,t)$, since $A$ is output-
determined. Therefore, the mapping $\lambda_{B}:\Sigma\times Z\rightarrow Z$
given by $\lambda_{B}(a,Z_{i})=b$ if $\lambda_{A}(a,s)=b$ for some $s\in
Z_{i}$ is well-defined. Moreover, $\sum_{Z_{j}\in
Z}p_{B}(\lambda(a,Z_{i}),Z_{j}\mid a,Z_{i})=1$ for all $a\in\Sigma$ and
$Z_{i}\in Z$. Hence, $B$ is also output-determined. ∎

  * Example 20.

Consider the stochastic automaton $A=(\\{s_{1},s_{2}\\},\\{a\\},\\{b,c\\},p)$
with $\lambda(a,s_{1})=b$, $\lambda(a,s_{2})=c$, and

$P(b\mid a)=\begin{pmatrix}\frac{1}{3}&\frac{2}{3}\\\ 0&0\\\
\end{pmatrix}\quad\mbox{and}\quad P(c\mid a)=\begin{pmatrix}0&0\\\
\frac{1}{2}&\frac{1}{2}\\\ \end{pmatrix}.$

This automaton is output-determined and strongly reduced by Prop. 5.5, since
the $H$-matrix has full rank,

$H_{A}=\begin{pmatrix}1&1\\\ 1&0\\\ \end{pmatrix}.$

$\diamondsuit$

A stochastic automaton $A$ is called determined if there are mappings
$\delta:\Sigma\times S\rightarrow S$ and $\lambda:\Sigma\times
S\rightarrow\Omega$ such that for all $a\in\Sigma$ and $s\in S$,

$\displaystyle p(\lambda(x,s),\delta(a,s)\mid a,s)=1.$ (7.7)

If a determined stochastic automaton $A$ is in state $s$ and $a$ is the input,
then $A$ enters state $\delta(a,s)$ and outputs $\lambda(a,s)$ with certainty.

######  Lemma 7.7.

A stochastic automaton $A$ is determined if and only if for all $a\in\Sigma$
and $b\in\Omega$, the matrix $P(b\mid a)$ has in each row at most one entry
$1$ and all other entries are $0$.

######  Proposition 7.8.

A stochastic automaton $A$ is determined if and only if $A$ is observable and
output-determined.

###### Proof.

The matrices $P(b\mid a)$ of a determined stochastic automaton have by Lemma
7.7 the same form as the matrices of an observable and output-determined
stochastic automaton by Lemmata 7.1 and 7.5. ∎

######  Proposition 7.9.

A determined stochastic automaton $A$ is reduced if and only if $A$ is
minimal.

###### Proof.

Let $A$ be determined and reduced and let $S=\\{s_{1},\ldots,s_{n}\\}$.
Suppose the state $s\in S$ and the state distribution $\pi$ are equivalent.
Since $A$ is determined, for each input $x\in\Sigma^{*}$ there is exactly one
state $s^{\prime}\in S$ and one output $y\in\Omega^{*}$ such that
$p(y,s^{\prime}\mid x,s)=1$. Moreover, since $s$ and $\pi$ are equivalent,
$1=p(y,s^{\prime}\mid x,s)=s\cdot\eta(y\mid x)=\pi\cdot\eta(y\mid x)$. But
$\pi\cdot\eta(y\mid x)=1$ only holds if all components $\eta_{i}(y\mid x)$ are
equal to $1$ if $\pi_{i}\neq 0$. Thus $\eta_{i}(y\mid x)=s_{i}\cdot\eta(y\mid
x)=1=s\cdot\eta(y\mid x)$ and hence $s_{i}$ and $s$ are equivalent. However,
$A$ is reduced and so $s$ and $s^{\prime}$ cannot be equivalent. Hence, $A$ is
minimal.

Conversely, each minimal stochastic automaton is also reduced. ∎

  * Example 21.

Take the stochastic automaton
$A=(\\{s_{1},s_{2},s_{3}\\},\\{a\\},\\{b,c\\},p)$ with

$P(b\mid a)=\begin{pmatrix}1&0&0\\\ 0&0&0\\\ \frac{1}{2}&0&0\\\
\end{pmatrix}\quad\mbox{and}\quad P(c\mid a)=\begin{pmatrix}0&0&0\\\ 0&1&0\\\
0&\frac{1}{2}&0\\\ \end{pmatrix}.$

This automaton is observable by Lemma 7.1. The associated reduced stochastic
automaton is $B=(\\{t_{1},t_{2}\\},\\{a\\},\\{b,c\\},p)$ with

$P(b\mid a)=\begin{pmatrix}1&0\\\ 0&0\\\ \end{pmatrix}\quad\mbox{and}\quad
P(c\mid a)=\begin{pmatrix}0&0\\\ 0&1\\\ \end{pmatrix}.$

Moreover, $B$ is determined and therefore minimal. $\diamondsuit$

##  Chapter 8 Stochastic Mealy and Moore Automata

Stochastic versions of the well-known Mealy and Moore automata are presented
and the generality of stochastic Moore automata is shown.

A stochastic automaton $A=(S,\Sigma,\Omega,p)$ is called stochastic Mealy
automaton if there are conditional probabilities $p_{1}(\cdot\mid a,s)$ and
$p_{2}(\cdot\mid a,s)$ over $\Omega$ and $S$, respectively, such that for all
$a\in\Sigma$, $b\in\Omega$ and $s,s^{\prime}\in S$,

$\displaystyle p(b,s^{\prime}\mid a,s)=p_{1}(b\mid a,s)\cdot
p_{2}(s^{\prime}\mid a,s).$ (8.1)

Stochastic independence of state transition and output emission makes
stochastic Mealy automata a restricted class of stochastic automata.

######  Proposition 8.1.

Each state-determined stochastic automaton $A$ is a stochastic Mealy
automaton. Each output-determined stochastic automaton $A$ is a stochastic
Mealy automaton.

###### Proof.

Let $A$ be state-determined. Define $p_{1}(b\mid a,s)=p(b,\delta(a,s)\mid
a,s)$ and $p_{2}(s^{\prime}\mid a,s)=1$ if $\delta(a,s)=s^{\prime}$ and $0$
otherwise. Then $p(b,s^{\prime}\mid a,s)=p_{1}(b\mid a,s)\cdot
p_{2}(s^{\prime}\mid a,s)$ as required.

Let $A$ be output-determined. Define $p_{1}(b\mid a,s)=1$ if $b=\lambda(a,s)$
and $0$ otherwise, and $p_{2}(s^{\prime}\mid
a,s)=p(\lambda(a,s),s^{\prime}\mid a,s)$. Then $p(b,s^{\prime}\mid
a,s)=p_{1}(b\mid a,s)\cdot p_{2}(s^{\prime}\mid a,s)$ as required. ∎

######  Proposition 8.2.

A stochastic Mealy automaton $A$ is observable if and only if $A$ is state-
determined.

###### Proof.

Let $A$ be observable. Then for all $a\in\Sigma$, $b\in\Omega$, and $s\in S$,

$p(b,\gamma(b,a,s)\mid a,s)=p_{1}(b\mid a,s)\cdot p_{2}(\gamma(b,a,s)\mid
a,s).$

Thus $\gamma(b,a,s)$ is independent of $b$ and therefore we put
$\delta(a,s)=\gamma(b,a,s)$. Then

$\displaystyle\sum_{b\in\Omega}p(b,\delta(a,s)\mid a,s)$ $\displaystyle=$
$\displaystyle\sum_{b\in\Omega}p_{1}(b\mid a,s)p_{2}(\delta(a,s)\mid a,s)$
$\displaystyle=$ $\displaystyle\sum_{b\in\Omega}p_{1}(b\mid a,s)=1.$

Hence, $A$ is state-determined. The converse is similar. ∎

######  Proposition 8.3.

For each stochastic Mealy automaton $A$ there is a reduced stochastic Mealy
automaton.

###### Proof.

Construct for a given stochastic Mealy automaton $A$ a reduced stochastic
automaton $B$ by the powerset method described in the proof of Thm. 4.2.

Using the notation in the proof, we obtain for all $a\in\Sigma$, $b\in\Omega$,
and $1\leq i,j\leq r$,

$\displaystyle p_{B}(b,Z_{j}\mid a,Z_{i})$ $\displaystyle=$
$\displaystyle\sum_{z\in Z_{j}}p_{A}(b,z,\mid a,z_{i})$ $\displaystyle=$
$\displaystyle\sum_{z\in Z_{j}}p_{1,A}(b\mid a,z_{i})p_{2,A}(z\mid a,z_{i}).$

Define

$p_{1,B}(b\mid y,Z_{i})=p_{1,A}(b\mid a,z_{i})$

and

$p_{2,B}(Z_{j}\mid y,Z_{i})=\sum_{z\in Z_{j}}p_{2,A}(z\mid a,z_{i}).$

These values are independent of the chosen representative state $z_{i}\in
Z_{i}$. Thus

$p_{B}(b,Z_{j}\mid a,Z_{i})=p_{1,B}(b\mid y,Z_{i})\cdot p_{2,B}(Z_{j}\mid
y,Z_{i})$

and hence $B$ is a stochastic Mealy automaton. ∎

  * Example 22.

Take the stochastic Mealy automaton
$A=(\\{s_{1},s_{2}\\},\\{a\\},\\{b,c\\},p)$ with probabilities

$\begin{array}[]{c|cccc}&p_{1}(b\mid a,\cdot)&p_{1}(c\mid
a,\cdot)&p_{2}(s_{1}\mid a,\cdot)&p_{2}(s_{2}\mid a,\cdot)\\\ \hline\cr
s_{1}&\frac{1}{2}&\frac{1}{2}&\frac{1}{3}&\frac{2}{3}\\\
s_{2}&\frac{1}{4}&\frac{3}{4}&\frac{1}{5}&\frac{4}{5}\\\ \end{array}$

Then we have

$P(b\mid a)=\begin{pmatrix}\frac{1}{6}&\frac{1}{3}\\\
\frac{1}{20}&\frac{1}{5}\\\ \end{pmatrix}\quad\mbox{and}\quad P(c\mid
a)=\begin{pmatrix}\frac{1}{6}&\frac{1}{3}\\\ \frac{3}{20}&\frac{3}{5}\\\
\end{pmatrix}.$

Therefore,

$P(a)=\begin{pmatrix}\frac{1}{3}&\frac{2}{3}\\\ \frac{1}{5}&\frac{4}{5}\\\
\end{pmatrix}.$

$\diamondsuit$

A stochastic automaton $A=(S,\Sigma,\Omega,p)$ is called stochastic Moore
automaton if there are conditional probabilities $\mu(\cdot\mid s)$ and
$p^{\prime}(\cdot\mid a,s)$ over $\Omega$ and $S$, respectively, such that for
all $a\in\Sigma$, $b\in\Omega$ and $s,s^{\prime}\in S$,

$\displaystyle p(b,s^{\prime}\mid a,s)=\mu(b\mid s^{\prime})\cdot
p^{\prime}(s^{\prime}\mid a,s).$ (8.2)

In a Moore automaton the output emission depends on the state transition.

######  Theorem 8.4.

For each stochastic automaton $A=(S_{A},\Sigma,\Omega,p_{A})$ there is a
stochastic Moore automaton $B=(S_{B},\Sigma,\Omega,p_{B})$ such that $A$ and
$B$ are S-equivalent.

###### Proof.

By Prop. 6.5, it is sufficient to construct an S-epimorphism
$\phi:B\rightarrow A$. For this, put $S_{B}=\Omega\times S_{A}$ and

$p_{B}(b_{2},(b_{1},s_{1})\mid
a,(b_{0},s_{0}))=\left\\{\begin{array}[]{ll}p_{A}(b_{1},s_{1}\mid
a,s_{0})&\mbox{if }b_{1}=b_{2},\\\ 0&\mbox{otherwise}\end{array}\right.$

for all $a\in\Sigma$, $b_{2}\in\Omega$, and $(b_{1},s_{1}),(b_{0},s_{0})\in
S_{B}$.

Moreover, for all $a\in\Sigma$ and $(b_{1},s_{1}),(b_{0},s_{0})\in S_{B}$ put

$p^{\prime}((b_{1},s_{1})\mid a,(b_{0},s_{0}))=p_{A}(b_{1},s_{1}\mid a,s_{0})$

and

$\mu(b_{2}\mid(b_{1},s_{1}))=\left\\{\begin{array}[]{ll}1&\mbox{if
}b_{1}=b_{2},\\\ 0&\mbox{otherwise.}\end{array}\right.$

Then we have for all $a\in\Sigma$, $b_{2}\in\Omega$, and
$(b_{1},s_{1}),(b_{0},s_{0})\in S_{B}$,

$p_{B}(b_{2},(b_{1},s_{1})\mid
a,(b_{0},s_{0}))=\mu(b_{2}\mid(b_{1},s_{1}))\cdot p^{\prime}((b_{1},s_{1})\mid
a,(b_{0},s_{0})).$

It is clear that $B$ is a stochastic Moore automaton. In particular, $\mu$ is
a mapping, i.e., the successor state determines uniquely the output symbol.

Finally, define the mapping $\phi:S_{B}\rightarrow S_{A}$ by $\phi((b,s))=s$
for all $(b,s)\in S_{B}$. Then we have

$\displaystyle p_{B}(b_{2},\phi^{-1}\phi(b_{1},s_{1})\mid a,(b_{0},s_{0}))$
$\displaystyle=$ $\displaystyle\sum_{b\in\Omega}p_{B}(b_{2},(b,s_{1})\mid
a,(b_{0},s_{0}))$ $\displaystyle=$ $\displaystyle
p_{B}(b_{2},(b_{2},s_{1})\mid a,(b_{0},s_{0}))$ $\displaystyle=$
$\displaystyle p_{A}(b_{2},s_{1}\mid a,s_{0})$ $\displaystyle=$ $\displaystyle
p_{A}(b_{2},\phi(b_{1},s_{1})\mid a,\phi(b_{0},s_{0})).$

Hence, $\phi$ is an S-epimorphism. ∎

The above result shows that stochastic Moore automata already provide the most
general type of stochastic automata. However, this is not true for stochastic
Mealy automata, since the transition probabilities for successor state and
output are independent of each other given input and state.

##  Chapter 9 Stochastic Acceptors

Stochastic acceptors are a generalization of the nondeterministic finite
automata. The languages recognized by stochastic acceptors are called
stochastic languages. We will see that the class of stochastic languages is
uncountable and includes the regular languages. For this, we assume
familiarity with the basic concepts of regular languages as well as
deterministic and nondeterministic finite acceptors [7].

A stochastic acceptor is a quintuple $A=(S,\Sigma,P,\pi,f)$, where

  * •

$S$ is a nonempty finite set of states,

  * •

$\Sigma$ is an alphabet of input symbols,

  * •

$P$ is a collection $\\{P(a)\mid a\in\Sigma\\}$ of stochastic $n\times n$
matrices, where $n$ is the number of states,

  * •

$\pi$ is an initial distribution of the states written as row vector,

  * •

$f$ is a binary column vector of length $n$ called final state vector.

Note that if the state set is $S=\\{s_{1},\ldots,s_{n}\\}$ and the final state
vector is $f=(f_{1},\ldots,f_{n})^{T}$, then $F=\\{s_{i}\mid f_{i}=1\\}$ is
the final state set.

The matrices $P(a)=(p_{ij}(a))$ with $a\in\Sigma$ are transition probability
matrices, where the $(i,j)$th entry $p_{ij}(a)=p(s_{j}\mid a,s_{i})$ is the
conditional probability of transition from state $s_{i}$ to state $s_{j}$ when
the symbol $a$ is read, $1\leq i,j\leq n$. A state change from one state to
another must take place with probability 1. Thus for each symbol $a\in\Sigma$
and each state $s_{i}\in S$, we have

$\displaystyle\sum_{j=1}^{n}p(s_{j}\mid a,s_{i})=1.$ (9.1)

Given the conditional probability distribution $p(\cdot\mid a,s)$ on $S$, we
define a conditional probability distribution $\hat{p}$ recursively as
follows:

  * •

For all states $s,s^{\prime}\in S$,

$\displaystyle\hat{p}(s^{\prime}\mid\epsilon,s)=\left\\{\begin{array}[]{ll}1&\mbox{if
}s=s^{\prime},\\\ 0&\mbox{if }s\neq s^{\prime},\end{array}\right.$ (9.4)

where $\epsilon$ denotes the empty word in $\Sigma^{*}$.

  * •

For all $s^{\prime}\in S$, $a\in\Sigma$, and $x\in\Sigma^{*}$,

$\displaystyle\hat{p}(s^{\prime}\mid ax,s)=\sum_{t\in S}p(t\mid
a,s)\cdot\hat{p}(s^{\prime}\mid x,t).$ (9.5)

Then $\hat{p}(\cdot\mid x,s)$ is a conditional probability distribution on $S$
and so we have

$\displaystyle\sum_{s^{\prime}\in S}\hat{p}(s^{\prime}\mid x,s)=1,\quad
x\in\Sigma^{*},\,s\in S.$ (9.6)

Note that the condititional probability distributions $p(\cdot\mid a,s)$ and
$\hat{p}(\cdot\mid a,s)$ coincide on $\Sigma\times S$ and therefore we write
$p$ instead of $\hat{p}$.

A stochastic acceptor works serially and synchronously. It reads an input word
symbol by symbol and after reading an input symbol it transits from one state
into another. In particular, if the automaton starts in state $s$ and reads
the word $x$, then with probability $p(s^{\prime}\mid x,s)$ it will end in
state $s^{\prime}$ taking all intermediate states into account.

######  Proposition 9.1.

For all $x,x^{\prime}\in\Sigma^{*}$, and $s,s^{\prime}\in S$,

$p(s^{\prime}\mid xx^{\prime},s)=\sum_{t\in S}p(t\mid x,s)\cdot
p(s^{\prime}\mid x^{\prime},t).$

This result is a special case of Prop. 2.2.

The behavior of a stochastic acceptor can be described by transition
probability matrices. To see this, let $A$ be a stochastic acceptor with state
set $S=\\{s_{1},\ldots,s_{n}\\}$. For the empty word, define by (9.4),

$\displaystyle P(\epsilon)=I_{n},$ (9.7)

where $I_{n}$ is the $n\times n$ unit matrix. Furthermore, if $a\in\Sigma$ and
$x\in\Sigma^{*}$, then by (9.5) we have

$\displaystyle P(ax)=P(a)\cdot P(x).$ (9.8)

By Prop. 9.1 and the associativity of matrix multiplication, we obtain the
following.

######  Proposition 9.2.

For all $x,x^{\prime}\in\Sigma^{*}$,

$P(xx^{\prime})=P(x)\cdot P(x^{\prime}).$

It follows by induction that if $x=x_{1}\ldots x_{k}\in\Sigma^{*}$, then

$\displaystyle P(x)=P(x_{1})\cdots P(x_{k}).$ (9.9)

The $(i,j)$-th element of the product matrix $P(x)$ is the probability of
transition from state $s_{i}$ to state $s_{j}$ when the word $x$ is read.
Moreover, if $\pi$ is the initial state distribution of the stochastic
acceptor, then after reading the word $x\in\Sigma^{*}$ the final state
distribution of the stochastic acceptor becomes $\pi P(x)$.

  * Example 23.

Take the stochastic acceptor $A=(\\{s_{1},s_{2}\\},\\{a,b\\},P,\pi,f)$ with

$P(a)=\left(\begin{array}[]{cc}\frac{1}{2}&\frac{1}{2}\\\
0&1\end{array}\right),\quad
P(b)=\left(\begin{array}[]{cc}\frac{1}{4}&\frac{3}{4}\\\
\frac{1}{8}&\frac{7}{8}\end{array}\right),\quad\pi=(1,0),\quad\mbox{and}\quad
f=\left(\begin{array}[]{l}0\\\ 1\end{array}\right).$

Then we have for all input words of length 3,

$\displaystyle\begin{array}[]{lll}\pi P(aaa)f=\frac{7}{8},&&\pi
P(baa)f=\frac{15}{16},\\\ \pi P(aab)f=\frac{27}{32},&&\pi
P(bab)f=\frac{55}{64},\\\ \pi P(aba)f=\frac{29}{32},&&\pi
P(bba)f=\frac{59}{64},\\\ \pi P(abb)f=\frac{109}{128},&&\pi
P(bbb)f=\frac{219}{256}.\end{array}$

$\diamondsuit$

A stochastic acceptor $A=(S,\Sigma,P,\pi,f)$ is deterministic if each matrix
$P(a)$, $a\in\Sigma$, has in each row exactly one entry 1. Note that a
deterministic stochastic acceptor is a nondeterministic acceptor in the usual
sense if the initial state distribution is a single state.

  * Example 24.

Take the deterministic acceptor $A=(\\{s_{1},s_{2}\\},\\{a,b\\},P,\pi,f)$ with

$P(a)=\left(\begin{array}[]{cc}1&0\\\ 0&1\end{array}\right),\quad
P(b)=\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right),\quad\pi=(1,0),\quad\mbox{and}\quad
f=\left(\begin{array}[]{l}0\\\ 1\end{array}\right).$

Then we have for all input words of length 3,

$\displaystyle\begin{array}[]{lll}\pi P(aaa)f=0,&&\pi P(baa)f=1,\\\ \pi
P(aab)f=1,&&\pi P(bab)f=0,\\\ \pi P(aba)f=1,&&\pi P(bba)f=0,\\\ \pi
P(abb)f=0,&&\pi P(bbb)f=1.\\\ \end{array}$

$\diamondsuit$

Let $A=(S,\Sigma,P,\pi,f)$ be a stochastic acceptor and let $\lambda$ be a
real number with $0\leq\lambda\leq 1$. The set

$\displaystyle L_{A,\lambda}=\\{x\in\Sigma^{*}\mid\pi P(x)f>\lambda\\}$ (9.12)

is the stochastic language of the acceptor and the number $\lambda$ is the cut
point of the language. Note that by definition $L_{A,1}=\emptyset$.

  * Example 25.

Consider the stochastic acceptor $A=(\\{s_{1},s_{2}\\},\\{a\\},P,\pi,f)$ with

$P(a)=\left(\begin{array}[]{cc}\frac{1}{2}&\frac{1}{2}\\\
0&1\end{array}\right),\quad\pi=(1,0),\quad\mbox{and}\quad
f=\left(\begin{array}[]{l}0\\\ 1\end{array}\right).$

Then for each integer $k\geq 0$,

$\pi P(a^{k})f=\pi
P(a)^{k}f=\pi\left(\begin{array}[]{cc}\frac{1}{2^{k}}&\frac{2^{k}-1}{2^{k}}\\\
0&1\end{array}\right)f=1-\frac{1}{2^{k}}.$

Given the cut point $\lambda$ with $1-\frac{1}{2^{l+1}}>\lambda\geq
1-\frac{1}{2^{l}}$ for some $l\geq 0$, the accepted language is

$L_{A,\lambda}=\\{a^{k}\mid 1-\frac{1}{2^{k}}>\lambda\\}=\\{a^{k}\mid k>l\\}.$

This language is regular for each cut point $\lambda$. $\diamondsuit$

A subset $L$ of $\Sigma^{*}$ is a $\lambda$-stochastic language with
$0\leq\lambda\leq 1$ if there is a stochastic acceptor $A$ such that
$L=L_{A,\lambda}$. A subset $L$ of $\Sigma^{*}$ is a stochastic language if
$L$ is $\lambda$-stochastic for some $0\leq\lambda\leq 1$. A language $L$ is
$\lambda$-regular with $0\leq\lambda\leq 1$ if there is a deterministic
acceptor $A$ such that $L=L_{A,\lambda}$. A language $L$ is regular if $L$ is
$\lambda$-regular for some $0\leq\lambda\leq 1$.

######  Proposition 9.3.

Each $0$-stochastic language is regular.

###### Proof.

Let $L$ be a $0$-stochastic language over $\Sigma$. Then there is a stochastic
acceptor

$A=(S_{A},\Sigma,P_{A},\pi_{A},f_{A})$

such that $L=L_{A,0}$. Consider the deterministic acceptor

$B=(S_{B},\Sigma,P_{B},\pi_{B},f_{B}),$

where

  * •

$S_{B}=2^{S_{A}}$ is the power set of $S_{A}$.

  * •

The transition probability matrices $P_{B}(a)$, $a\in\Sigma$, are defined by

$\displaystyle p_{B}(S_{j}\mid a,S_{i})$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\mbox{if }S_{j}=\\{s^{\prime}\in
S_{A}\mid p_{A}(s^{\prime}\mid a,s)\neq 0\mbox{ for some }s\in S_{i}\\},\\\
0&\mbox{otherwise,}\end{array}\right.$

for all $a\in\Sigma$ and $S_{i},S_{j}\in S_{B}$.

  * •

$\pi_{B}=(\pi_{B,1},\ldots,\pi_{B,2^{n}})$ with

$\pi_{B,i}=\left\\{\begin{array}[]{ll}1&\mbox{if }S_{i}=R,\\\
0&\mbox{otherwise,}\end{array}\right.$

where $S_{B}=\\{S_{1},\ldots,S_{2^{n}}\\}$,
$\pi_{A}=(\pi_{A,1},\ldots,\pi_{A,n})$, and

$R=\\{s_{i}\in S_{A}\mid\pi_{A,i}\neq 0\\}.$

  * •

$f_{B}$ is uniquely determined by the final state set

$F_{B}=\\{R\in S_{B}\mid R\cap F_{A}\neq\emptyset\\}.$

Clearly, the acceptor $B$ is deterministic. Moreover, for each
$x\in\Sigma^{*}$, the inequality $\pi_{A}P_{A}(x)f_{A}>0$ is equivalent to
$\pi_{B}P_{B}(x)f_{B}>0$. Hence, $L_{A,0}=L_{B,0}$. ∎

  * Example 26.

In view of the stochastic acceptor $A$ in Ex. 9, we have $L_{A,0}=\\{a^{k}\mid
k\geq 1\\}$. The corresponding deterministic acceptor $B$ has state set
$S_{B}=\\{\emptyset,\\{s_{1}\\},\\{s_{2}\\},\\{s_{1},s_{2}\\}\\}$, input
alphabet $\Sigma_{B}=\\{0,1\\}$, state transition matrix

$P_{B}(x)=\bordermatrix{~{}&\emptyset&\\{s_{1}\\}&\\{s_{2}\\}&\\{s_{1},s_{2}\\}\cr\emptyset&1&0&0&0\cr\\{s_{1}\\}&0&0&0&1\cr\\{s_{2}\\}&0&0&1&0\cr\\{s_{1},s_{2}\\}&0&0&0&1\cr}$

as well as initial state distribution $\pi_{B}=(0,1,0,0)$, and final state set
$F_{B}=\\{\\{s_{2}\\},\\{s_{1},s_{2}\\}\\}$. $\diamondsuit$

######  Proposition 9.4.

For each deterministic acceptor $A$ and each cut point $\lambda$, there is a
deterministic acceptor $B$ with initial state distribution given by a single
state such that $L_{A,\lambda}=L_{B,0}$.

###### Proof.

Let $A=(S_{A},\Sigma,P_{A},\pi_{A},f_{A})$ be a deterministic acceptor with
$S_{A}=\\{s_{1},\ldots,s_{n}\\}$ and $\pi_{A}=(\pi_{A,1},\ldots,\pi_{A,n})$.
Write $\pi=\sum_{i=1}^{n}\pi_{A,i}s_{i}$.

For each $1\leq i\leq n$, define the acceptor $A_{i}$ obtained from $A$ by
replacing the initial state distribution $\pi_{A}$ with the state (standard
basis vector) $s_{i}$. This acceptor is deterministic in the ordinary sense.

Let $x\in L_{A,\lambda}$. Then $\pi_{A}P_{A}(x)f_{A}>\lambda$ or equivalently

$\sum_{i=1}^{n}\pi_{A,i}s_{i}P_{A}(x)f_{A}>\lambda.$

That is, there are states $s_{i_{1}},\ldots,s_{i_{k}}$ such that
$\sum_{j=1}^{k}\pi_{A,i_{j}}>\lambda$ and $x\in L_{A_{i_{j}},0}$ for all
$1\leq j\leq k$. Equivalently, we have

$x\in\bigcup(L_{A_{i_{1}},0}\cap\ldots\cap L_{A_{i_{k}},0})=L^{\prime},$

where the union extends over all nonempty subsets
$\\{s_{i_{1}},\ldots,s_{i_{k}}\\}$ of $S_{A}$ such that
$\sum_{j=1}^{k}\pi_{A,i_{j}}>\lambda$. Thus the set $L^{\prime}=L_{A,\lambda}$
is a finite union of intersections of regular languages. But the class of
regular languages is closed under finite unions and intersections. Thus the
language $L^{\prime}$ is regular in the ordinary sense and hence there exists
a deterministic acceptor $B$ with the desired property. ∎

The $p$-adic languages provide an example of stochastic languages which are
not regular and also demonstrate that the class of stochastic languages is
uncountable. To see this, let $p\geq 2$ be an integer. The stochastic acceptor
$A=(\\{s_{1},s_{2}\\},\\{0,\ldots,p-1\\},P,\pi,f)$ with

$P(a)=\left(\begin{array}[]{cc}1-\frac{a}{p}&\frac{a}{p}\\\
1-\frac{a+1}{p}&\frac{a+1}{p}\end{array}\right),\quad 0\leq a\leq
p-1,\quad\pi=(1,0),\quad\mbox{and}\quad f=\left(\begin{array}[]{c}0\\\
1\end{array}\right)$

is called $p$-adic acceptor.

Each word $x=x_{1}\ldots x_{k}\in\\{0,\ldots,p-1\\}^{*}$ can be assigned the
real number whose $p$-adic representation is $0.x_{k}\ldots x_{1}$.

######  Proposition 9.5.

Let $A$ be an $p$-adic acceptor and let $\lambda$ be a cut point. Then

$L_{A,\lambda}=\\{x_{1}\ldots x_{k}\in\\{0,\ldots,p-1\\}^{*}\mid 0.x_{k}\ldots
x_{1}>\lambda\\}.$

###### Proof.

A word $x=x_{1}\ldots x_{k}\in\\{0,\ldots,p-1\\}^{*}$ lies in $L_{A,\lambda}$
if and only if $\pi P(x)f>\lambda$. Note that $\pi P(x)f$ is the upper right
entry of the matrix $P(x)$.

Claim that the matrix $P(x)$ has $0.x_{k}\ldots x_{1}$ as upper right entry.
Indeed, this is true for $k=1$. The matrix $P(x_{1}\ldots x_{k}a)$ with
$x_{1},\ldots,x_{k},a\in\\{0,\ldots,p-1\\}$ can be written as the product
matrix $P(x_{1}\ldots x_{k})P(a)$. By induction, the upper right entry of this
matrix is

$\displaystyle(1-0.x_{k}\ldots x_{1})\cdot\frac{a}{p}+0.x_{k}\ldots
x_{1}\cdot\frac{a+1}{p}$ $\displaystyle=$
$\displaystyle\frac{a}{p}+\frac{0.x_{k}\ldots x_{1}}{p}$ $\displaystyle=$
$\displaystyle 0.a+0.0x_{k}\ldots x_{1}$ $\displaystyle=$ $\displaystyle
0.ax_{k}\ldots x_{1}.$

This proves the claim. Hence, $x_{1}\ldots x_{k}\in L_{A,\lambda}$ if and only
if $0.x_{k}\ldots x_{1}>\lambda$. ∎

The following result makes use of the Nerode equivalence relation $\equiv_{L}$
of a language $L$ over $\Sigma$. Define for all words $x,y\in\Sigma^{*}$,

$\displaystyle x\equiv_{L}y\quad:\Longleftrightarrow\quad\forall
z\in\Sigma^{*}:xz\in L\Longleftrightarrow yz\in L.$ (9.14)

This is an equivalence relation on the set $\Sigma^{*}$. The theorem of
Nerode-Myhill says that a language $L\subseteq\Sigma^{*}$ is regular if and
only if the number of equivalence classes of the relation $\equiv_{L}$ is
finite.

For instance, the language $L=\\{a^{n}b^{n}\mid n\in{\mathbb{N}}\\}$ is not
regular, since the words $a^{i}b$ and $a^{j}b$ with $i\neq j$ are not
equivalent and so the equivalence classes of the words $a^{i}b$, $i\geq 1$,
are all distinct.

######  Proposition 9.6.

Let $A$ be an $p$-adic acceptor and $\lambda$ be a cut point. Then
$L_{A,\lambda}$ is regular if and only if $\lambda$ is rational.

###### Proof.

In view of the Nerode equivalence relation of the language $L=L_{A,\lambda}$,
two words $x,y\in\Sigma^{*}$ belong to different equivalence classes if and
only if there is a word $z\in\Sigma^{*}$ such that $xz\in L$ and $yz\not\in L$
or $xz\not\in L$ and $yz\in L$. That is,
$0.\mbox{$\mu$}(yz)\leq\lambda<0.\mbox{$\mu$}(xz)$ or
$0.\mbox{$\mu$}(xz)\leq\lambda<0.\mbox{$\mu$}(yz)$, where
$\mbox{$\mu$}(x_{1}\ldots x_{k})=x_{k}\ldots x_{1}$ denotes the mirror image
of the word $x=x_{1}\ldots x_{k}$.

Suppose without restriction that
$0.\mbox{$\mu$}(yz)\leq\lambda<0.\mbox{$\mu$}(xz)$. Since
$\mu(yz)=\mbox{$\mu$}(z)\mbox{$\mu$}(y)$ and
$\mu(xz)=\mbox{$\mu$}(z)\mbox{$\mu$}(x)$, we have
$0.\mbox{$\mu$}(z)\mbox{$\mu$}(y)\leq\lambda<0.\mbox{$\mu$}(z)\mbox{$\mu$}(x)$.
Thus the cut point must have the form
$\lambda=0.\mbox{$\mu$}(z)a_{1}a_{2}\ldots$. If we put
$\lambda_{z}=0.a_{1}a_{2}\ldots$, then
$0.\mbox{$\mu$}(y)\leq\lambda_{z}<0.\mbox{$\mu$}(x)$. With this kind of
numbers $\lambda_{z}$ it is possible to separate the equivalence classes. That
is, the relation $\equiv_{L}$ has the classes

$\\{y\in\Sigma^{*}\mid\lambda_{u}<0.\mbox{$\mu$}(y)\leq\lambda_{v}\mbox{ and
there is no $w\in\Sigma^{*}$ with }\lambda_{u}<\lambda_{w}<\lambda_{v}\\}.$

We have

$\lambda=0.\mbox{$\mu$}(z)+\frac{\lambda_{z}}{p^{l}},$

where $l$ is the length of the word $z$. Therefore, there are only finitely
many equivalence classes of $\equiv_{L}$ if and only if there are only
finitely many $\lambda_{z}$ with this property. In this case, the cut point
$\lambda$ is eventually periodic and hence a rational number. ∎

By definition, each regular language is stochastic. However, if the cut point
$\lambda$ is not rational, one obtains a stochastic language which is not
regular. For this, note that the set of algorithms written for a Turing
machine is countable, while the set of real numbers is uncountable. Moreover,
for distinct cut points $\lambda_{1}$ and $\lambda_{2}$, the corresponding
$p$-adic stochastic acceptors yield different stochastic languages. Thus the
number of stochastic languages is uncountable. Hence, there are stochastic
languages that cannot be accepted by a Turing machine.

  * Example 27.

Take the stochastic acceptor $A=(\\{s_{1},\ldots,s_{5}\\},\\{a,b\\},P,\pi,f)$,
where

$P(a)=\left(\begin{array}[]{ccccc}\frac{1}{2}&\frac{1}{2}&0&0&0\\\
0&1&0&0&0\\\ 0&0&0&0&1\\\ 0&0&0&0&1\\\ 0&0&0&0&1\end{array}\right),\quad
P(b)=\left(\begin{array}[]{ccccc}0&0&\frac{1}{2}&\frac{1}{2}&0\\\
0&0&\frac{1}{2}&0&\frac{1}{2}\\\ 0&0&\frac{1}{2}&\frac{1}{2}&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\end{array}\right),$

and

$\pi=\left(\begin{array}[]{ccccc}1&0&0&0&0\end{array}\right),\quad
f=\left(\begin{array}[]{c}0\\\ 0\\\ 0\\\ 1\\\ 0\end{array}\right).$

The state diagram of the acceptor is given in Fig. 9.1. For integers $i\geq 0$
and $j\geq 1$, we obtain

$P(a^{i})=\left(\begin{array}[]{ccccc}\frac{1}{2^{i}}&\frac{2^{i}-1}{2^{i}}&0&0&0\\\
0&1&0&0&0\\\ 0&0&0&0&1\\\ 0&0&0&0&1\\\ 0&0&0&0&1\end{array}\right),\quad
P(b^{j})=\left(\begin{array}[]{ccccc}0&0&\frac{1}{2^{j}}&\frac{2^{j}-1}{2^{j}}&0\\\
0&0&\frac{1}{2^{j}}&\frac{2^{j-1}-1}{2^{j}}&\frac{1}{2}\\\
0&0&\frac{1}{2^{j}}&\frac{2^{j}-1}{2^{j}}&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\end{array}\right).$

Thus

$\pi
P(a^{i}b^{j})=\left(\begin{array}[]{ccccc}0,&0,&\frac{1}{2^{j}},&\frac{(2^{j}-1)+(2^{i}-1)(2^{j-1}-1)}{2^{i+j}},&\frac{2^{i}-1}{2^{i+1}}\end{array}\right)$

and hence

$\pi
P(a^{i}b^{j})f=\frac{1}{2}+\left(\frac{1}{2}\right)^{i+1}-\left(\frac{1}{2}\right)^{j}.$

The state diagram shows that for each word $x$, which is not of the form
$a^{i}b^{j}$ with $i\geq 0$ and $j\geq 1$, we obtain $\pi P(x)f=0$. Therefore,
we obtain the language

$L_{A,\frac{1}{2}}=\\{a^{i}b^{j}\mid i\geq 0,j\geq i+2\\},$

which is not regular by the theorem of Nerode-Myhill. $\diamondsuit$

$\textstyle{s_{2}}$$\scriptstyle{a:1}$$\scriptstyle{b:1/2}$$\scriptstyle{b:1/2}$$\textstyle{s_{1}}$$\scriptstyle{a:1/2}$$\scriptstyle{a:1/2}$$\scriptstyle{b:1/2}$$\scriptstyle{b:1/2}$$\textstyle{s_{3}}$$\scriptstyle{b:1/2}$$\scriptstyle{a:1}$$\scriptstyle{b:1/2}$$\textstyle{s_{5}}$$\scriptstyle{a,b:1}$$\textstyle{s_{4}}$$\scriptstyle{b:1}$$\scriptstyle{a:1}$

Figure 9.1: State diagram of stochastic acceptor $A$.

This example demonstrates that there are stochastic acceptors $A$, whose
transition matrices and initial distributions are given by rational numbers,
and rational cut points $\lambda$ such the language $L_{A,\lambda}$ is not
regular.

Two normalization properties will come next. First, stochastic languages are
independent of the specific cut point.

######  Proposition 9.7.

Let $A$ be a stochastic acceptor and $\lambda$ be a cut point. Then for each
number $\mu$ with $0<\mu<1$, there is a stochastic acceptor $B$ such that
$L_{A,\lambda}=L_{B,\mu}$.

###### Proof.

Let $A=(S,\Sigma,P,\pi,f)$ be a stochastic acceptor with state set
$S_{A}=\\{s_{1},\ldots,s_{n}\\}$ and let $\lambda$ be a cut point.

Let $\lambda=0$. Then by Prop. 9.3, $L_{A,0}$ is regular and thus there is a
deterministic acceptor $B$ which accepts this language for each cut point
$\mu$ with $0<\mu<1$.

Let $\lambda=1$. Then we have $L_{A,1}=\emptyset$ and it is clear that there
is a stochastic acceptor $B$ with the required property.

Let $0<\lambda<1$. Define the stochastic acceptor $B$ with alphabet $\Sigma$,
state set $S_{B}=S_{A}\cup\\{s_{n+1}\\}$, and transition matrices

$P_{B}(a)=\left(\begin{array}[]{ccc|c}&&&0\\\ &P_{A}(a)&&\vdots\\\ &&&0\\\
\hline\cr 0&\ldots&0&1\end{array}\right),\quad a\in\Sigma.$

Then for each $x\in\Sigma^{*}$,

$P_{B}(x)=\left(\begin{array}[]{ccc|c}&&&0\\\ &P_{A}(x)&&\vdots\\\ &&&0\\\
\hline\cr 0&\ldots&0&1\end{array}\right).$

Consider a cut point $\mu$ with $0<\mu<1$. We will define a number $\nu$ with
$0\leq\nu<1$ corresponding to $\lambda$ and $\mu$. Put

$\pi_{B}=((1-\nu)\pi_{A,1},\ldots,(1-\nu)\pi_{A,n},\nu).$

First, let $0<\mu\leq\lambda$. Then put $\nu=1-\frac{\mu}{\lambda}$ and
$f_{B}=\left(\begin{array}[]{c}f_{A}\\\ 0\end{array}\right)$. This defines a
stochastic acceptor $B$ with the property that for each word $x\in\Sigma^{*}$,

$\pi_{B}P_{B}(x)f_{B}=(1-\nu)\pi_{A}P_{A}(x)f_{A}=\frac{\mu}{\lambda}\pi_{A}P_{A}f_{A}.$

Thus $\pi_{A}P_{A}(x)f_{A}>\lambda$ if and only if $\pi_{B}P_{B}(x)f_{B}>\mu$.
Hence, $L_{A,\lambda}=L_{B,\mu}$.

Second, let $\lambda<\mu<1$. Then put $\nu=\frac{\mu-\lambda}{1-\lambda}$ and
$f_{B}=\left(\begin{array}[]{c}f_{A}\\\ 1\end{array}\right)$. This defines a
stochastic acceptor $B$ with the property that for each word $x\in\Sigma^{*}$,

$\pi_{B}P_{B}(x)f_{B}=(1-\nu)\pi_{A}P_{A}(x)f_{A}+\nu.$

We have $(1-\nu)\lambda+\nu=\mu$. Thus $\pi_{A}P_{A}(x)f_{A}>\lambda$ if and
only if $\pi_{B}P_{B}(x)f_{B}>\mu$. Hence, $L_{A,\lambda}=L_{B,\mu}$. ∎

Second, stochastic languages are independent in some way of the initial state
distribution.

######  Proposition 9.8.

Let $A$ be a stochastic acceptor and $\lambda$ be a cut point. Then there is a
stochastic acceptor $B$, whose initial state distribution is given by a single
state, such that $L_{A,\lambda}=L_{B,\lambda}$.

###### Proof.

Let $A=(S,\Sigma,P,\pi,f)$ be a stochastic acceptor with state set
$S_{A}=\\{s_{1},\ldots,s_{n}\\}$ and let $\lambda$ be a cut point.

Define the stochastic acceptor $B$ with alphabet $\Sigma$, state set
$S_{B}=S_{A}\cup\\{s_{0}\\}$, transition matrices

$P_{B}(a)=\left(\begin{array}[]{c|c}0&\pi P_{A}(a)\\\ \hline\cr 0&\\\
\vdots&P_{A}(a)\\\ 0&\end{array}\right),\quad a\in\Sigma,$

and

$\pi_{B}=(1,0\ldots,0),\quad
f_{B}=\left\\{\begin{array}[]{ll}\left(\begin{array}[]{c}0\\\
f_{A}\end{array}\right)&\mbox{if }\pi_{A}f_{A}\leq\lambda,\\\
\left(\begin{array}[]{c}1\\\ f_{A}\end{array}\right)&\mbox{if
}\pi_{A}f_{A}>\lambda.\end{array}\right.$

Then for each $x\in\Sigma_{A}^{*}$,

$P_{B}(x)=\left(\begin{array}[]{c|c}0&\pi P_{A}(x)\\\ \hline\cr 0&\\\
\vdots&P_{A}(x)\\\ 0&\end{array}\right).$

In view of the empty word, we have $\pi_{A}f_{A}>\lambda$ if and only if
$\pi_{B}f_{B}=1>\lambda$. Thus $\epsilon\in L_{A,\lambda}$ if and only if
$\epsilon\in L_{B,\lambda}$.

Moreover, for each word $x\in\Sigma^{*}$, we have
$\pi_{A}P_{A}(x)f_{A}=\pi_{B}P_{B}(x)f_{B}$. Thus $x\in L_{A,\lambda}$ if and
only if $x\in L_{B,\lambda}$. ∎

Finally, the concept of isolated cut points is introduced. For this, let $A$
be a stochastic acceptor. A cut point $\lambda$ is called isolated for $A$ if
there is a number $\Delta>0$ such that for all words $x\in\Sigma_{A}^{*}$,

$\displaystyle|\pi_{A}P_{A}(x)f_{A}-\lambda|\geq\Delta.$ (9.15)

Isolated cut points have some meaning when conducting probabilistic
experiments with stochastic acceptors.

######  Theorem 9.9 (Rabin).

Let $A$ be a stochastic acceptor with isolated cut point $\lambda$. Then the
language $L_{A,\lambda}$ is regular.

###### Proof.

Let $A$ have state set $S_{A}=\\{s_{1},\ldots,s_{n}\\}$. Then by Prop. 9.8,
there is a stochastic acceptor $B$ with state set $S_{A}=\\{s_{0}\\}\cup
S_{A}$ such that $L_{A,\lambda}=L_{B,\lambda}$.

Let $\equiv_{L}$ be the Nerode equivalence relation of the language
$L=L_{A,\lambda}$. Suppose $x$ and $y$ are words in $\Sigma^{*}$ such that
$x\not\equiv_{L}y$. Then there exists a word $z\in\Sigma^{*}$ such that
without restriction $xz\in L_{A,\lambda}$ and $yz\not\in L_{A,\lambda}$. Thus
$\pi_{B}P_{B}(xz)f_{B}>\lambda$ and $\pi_{B}P_{B}(yz)f_{B}\leq\lambda$. Since
$\lambda$ is isolated, $\pi_{B}P_{B}(xz)f_{B}\geq\lambda+\Delta$ and
$\pi_{B}P_{B}(yz)f_{B}\leq\lambda-\Delta$. Therefore,

$\pi_{B}(P_{B}(x)-P_{B}(y))P_{B}(z)f_{B}\geq 2\Delta.$

The column vector $P_{B}(z)f_{B}$ has nonnegative entries and the initial
state vector is $\pi_{B}=(1,0,\ldots,0)$. Thus the above inequality remains
valid if the summation is restricted to the positive entries
$p_{0j}(x)-p_{0j}(y)$, i.e.

$\sum_{j}^{+}p_{0j}(x)-p_{0j}(y)\geq 2\Delta,$

where $\sum^{+}$ denotes the summation over the positive terms. Since the
matrices $P_{B}(x)$ and $P_{B}(y)$ are stochastic, we obtain
$\sum_{j=0}^{n}p_{0j}(x)=\sum_{j=0}^{n}p_{0j}(y)=1$ and thus
$\sum_{j=0}^{n}p_{0j}(x)-p_{0j}(y)=0$. Hence,

$\sum_{j}^{+}p_{0j}(x)-p_{0j}(y)=-\sum_{j}^{-}p_{0j}(x)-p_{0j}(y),$

where $\sum^{-}$ denotes the summation over the non-positive terms. Therefore,

$\sum_{j=0}^{n}|p_{0j}(x)-p_{0j}(y)|=2\sum_{j}^{+}p_{0j}(x)-p_{0j}(y).$

We may assume that $x,y$ are different from the empty word. Then
$p_{00}(x)=p_{00}(y)$ and so

$2\Delta\leq\frac{1}{2}\sum_{j=1}^{n}|p_{0j}(x)-p_{0j}(y)|.$

Thus in case of $x\not\equiv_{L}y$, the row vectors
$\gamma_{x}=(p_{01}(x),\ldots,p_{0n}(x))$ and
$\gamma_{y}=(p_{01}(y),\ldots,p_{0n}(y))$ have the $|\cdot|$ (absolute)
distance of at least $4\Delta$.

However, all vectors of length $n$ with row sum $1$ form a closed and limited
(and thus compact) subset of ${\mathbb{R}}^{n}$, which can be covered by
finitely many $n$-dimensional cubes of length $2\Delta$. The above
considerations show that each of these cubes can only contain those vectors
$\gamma_{x}$, which belong to the same equivalence class of the Nerode
equivalence relation. Thus there are only finitely many classes of the Nerode
equivalence. Hence, by the Nerode-Myhill theorem, the language $L_{B,\lambda}$
is regular. ∎

  * Example 28.

Consider the stochastic acceptor

$A=(\\{s_{1},s_{2}\\},\\{0,2\\},\\{P(0),P(2)\\},\pi,f)$

with

$P(0)=\begin{pmatrix}1&0\\\ \frac{2}{3}&\frac{1}{3}\end{pmatrix},\quad
P(2)=\begin{pmatrix}\frac{1}{3}&\frac{2}{3}\\\
0&1\end{pmatrix},\quad\pi=\begin{pmatrix}1&0\end{pmatrix},\quad
f=\begin{pmatrix}0\\\ 1\end{pmatrix},$

which is part of the 3-adic acceptor. For each word, $x=x_{1}\ldots
x_{n}\in\Sigma^{*}$, we have

$\pi P(x)f=\frac{x_{n}}{3}+\frac{x_{n-1}}{3^{2}}\ldots+\frac{x_{1}}{3^{n-1}}.$

It follows that the topological closure of the set $\\{\pi P(x)f\mid
x\in\Sigma^{*}\\}$ is precisely Cantor’s discontinuum. In particular, the set
of isolated cut points of $A$ lies dense in the interval $[0,1]$.
$\diamondsuit$

## Bibliography

  * [1] R.G. Bukharaev: Theorie der stochastischen Automaten, Teubner, Stuttgart, 1995.
  * [2] J. W. Carlyle: Reduced forms for stochastic sequential machines, Journal Mathematical Analysis and Applications, 7, No. 2 (1963), 167-165. doi: 10.1016/0022-247X(63)90045-3
  * [3] V. Claus: Stochastische Automaten, Teubner, Stuttgart, 1971.
  * [4] J. von Neumann: Probabilistic logic and the synthesis of reliable organisms from unreliable components, in: Automata Studies, C. Shannon and J. McCarthy (eds), Annals of Mathematical Studies, 34, Princeton Univ. Press, Princeton, NJ (1956). doi: 10.1515/9781400882618-003
  * [5] M. O. Rabin: Probabilistic automata, Information and Control, 6, No. 3 (1963), 230-245. doi: 10.1016/S0019-9958(63)90290-0
  * [6] M. O. Rabin, D. Scott: Finite automata and their decision problems, IBM Journal Research Development, 3, No. 3 (1959), 114-125. doi: 10.1147/rd.32.0114
  * [7] A. Salomaa: Theory of Automata, Pergamon Press, Oxford, 1969.
  * [8] C. E. Shannon: A mathematical theory of communication, Bell System Technical Journal, 5, No. 1 (1948), 379-423.
  * [9] P. H. Starke: Stochastische Ereignisse und Wortmengen, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 12 (1966), 61-68. doi: 10.1002/malq.19660120108
  * [10] P. Turakainen: Generalized automata and stochastic languages, Proc. Amer. Math. Soc., 21, 303-309, 1969.
  * [11] M.N. Cakir, K.-H. Zimmermann: On stochastic automata over monoids, TU Hamburg, arxiv:2002.01214, 2020.

## Index

  * acceptor
    * p-adic Chapter 9
  * arbitrarily varying channel Example 2.
  * AVC Example 2.
  * binary symmetric channel Example 2.
  * BSC Example 2.
  * convex combination Chapter 5
  * cut point Chapter 9
    * isolated Chapter 9
  * final state set Chapter 9
  * final state vector 5th item
  * initial distribution 4th item
  * input 2nd item
  * isomorphism Chapter 4
  * language
    * lambda-regular Chapter 9
    * lambda-stochastic Chapter 9
    * regular Chapter 9
    * stochastic Chapter 9, Chapter 9
  * matrix
    * stochastic Proposition 2.4
    * substochastic Chapter 2
  * mirror image Chapter 9
  * Nerode relation Chapter 9
  * output 3rd item
  * permutation matrix Chapter 5
  * result vector Chapter 3
  * S-homomorphism Chapter 6
  * simplex Chapter 5
  * state 1st item
  * state distribution Chapter 3
    * equivalence 4th item
    * k-equivalence 5th item
  * stochastic acceptor Chapter 9
    * deterministic Chapter 9
  * stochastic automaton Chapter 2
    * acceptor Chapter 9
    * covering 3rd item
    * determined Chapter 7
    * equivalence 1st item
    * minimal Chapter 5
    * observable Chapter 7
    * output-determined Chapter 7
    * reduced Chapter 4
    * S-equivalence 2nd item
    * state-determined Chapter 7
    * strongly reduced Chapter 5
    * trivial Chapter 6
  * stochastic image Chapter 6
  * stochastic Mealy automaton Chapter 8
  * stochastic Moore automaton Chapter 8
  * transducer Chapter 2