Question

Using the solution you gave to Exercise 1.25, give a formal description of the machines ${\mathbf{T}}_{\mathbf{1}}$and${\mathbf{T}}_{\mathbf{2}}$ depicted in Exercise 1.24

Short answer

The formal description is given below.

Step-by-step solution

Introduce FST

Some theoretical descriptions of$\mathrm{T}$during machines ${\mathrm{T}}_1$ and ${\mathrm{T}}_2$ must be defined at this point. The term "finite state transducer" (FST) is used to describe a device that has a finite number of states.$(\mathrm{Q},\sum ,\mathrm{r},\mathrm{\delta },{\mathrm{q}}_0)$ tuple, where

• The finite set of states is$\mathrm{Q}$.

• The input alphabet is$\sum$.

• The output alphabet is $\mathrm{r}$.

Explain the solution

Some theoretical descriptions of$\mathrm{T}$during the use of machines ${\mathrm{T}}_1$and ${\mathrm{T}}_2$must be defined at this point. The term

• The transition functiontakes a state and an input symbol and returns a state and an output symbol.

$\mathrm{\delta }:\mathrm{Qx}\sum \to \mathrm{Qxr}$

• The start state is${\mathrm{q}}_0$.

The finite state transducer ${\mathrm{T}}_1$ is formally defined by the $(\{{\mathrm{q}}_1,{\mathrm{q}}_2\},\{0,1,2\},\{0,1\},{\mathrm{\delta }}_{1,}{\mathrm{q}}_1)$., where the transition function ${\mathrm{\delta }}_1$ is as follows:

Input State	0	1	2
${\mathrm{q}}_1$	$\{{\mathrm{q}}_1,0\}$	$\{{\mathrm{q}}_1,0\}$	$\{{\mathrm{q}}_1,1\}$
${\mathrm{q}}_2$	$\{{\mathrm{q}}_2,0\}$	$\{{\mathrm{q}}_2,0\}$	$\{{\mathrm{q}}_2,1\}$

The second FST is defined as ${\mathrm{T}}_2=\left(\{\{{\mathrm{q}}_1,{\mathrm{q}}_2,{\mathrm{q}}_3\},\{\mathrm{a},\mathrm{b}\},\{0,1\},{\mathrm{\delta }}_{1,}{\mathrm{q}}_1\right)$. The transition function ${\mathrm{\delta }}_2$ is given by:

Input State	A	B
${\mathrm{q}}_1$	$\{{\mathrm{q}}_2,1\}$	$\{{\mathrm{q}}_3,1\}$
${\mathrm{q}}_2$	$\{{\mathrm{q}}_3,1\}$	$\{{\mathrm{q}}_1,0\}$
${\mathrm{q}}_3$	$\{q_1,0\}$	$\{{\mathrm{q}}_2,1\}$