Finding the output string corresponding to an input string for a finite-state machine

Question

Working on:

Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 590)

I am studying finite-state machines, and I have the following definition in my book:

Definition 12.1.8

Let $M = (I, O, S, f , g, \sigma )$ be a finite-state machine. An input string for $M$ is a string over $I$.
The string

$$y_1 \cdots y_n$$

is the output string for $M$ corresponding to the input string
$$\alpha = x_1 \cdots x_n$$ if there exist states
$\sigma_0, \dots, \sigma_n \in S$ such that:

$\sigma_0 = \sigma$

$\sigma_i = f(\sigma_{i-1}, x_i)$ for $i = 1, \dots, n$

$y_i = g(\sigma_{i-1}, x_i)$ for $i = 1, \dots, n$

Then, I have to do the following exercise:

Example 12.1.9

Find the output string corresponding to the string:

$$aababba$$

I proceed as follows:

For $i = 1$, I get:

$\sigma_1 = f(\sigma_{0}, x_1)$

$y_1 = g(\sigma_{0}, x_1)$

So, $y_0 = 0$. T

hen for $i = 2$, I get

$\sigma_2 = f(\sigma_{1}, x_2)$

$y_2 = g(\sigma_{1}, x_2)$

So, $y_1 = 0$. But now for $i = 3$, I don't have a state $\sigma_2 \in S$. So, how can I proceed calculation from here ?

Answer 1

In the example, as stated, $\sigma_1 = f(\sigma_0, x_1)$. Since $x_1 = a$, we get $\sigma_1 = \sigma_0$, as $f(\sigma_0, a) = \sigma_0$, according to Table 12.1.1. To compute $\sigma_2$, we use $f(\sigma_1, x_2)$. Given that $\sigma_1 = \sigma_0$ and $x_2 = a$, we again use the value of $f(\sigma_0, a)$ from the table, concluding that $\sigma_2$ is also equal to $\sigma_0$.

The key point here is that in the equation $\sigma_i = f(\sigma_{i-1}, x_i)$, $\sigma_i$ represents the state you reach after processing the $i^{th}$ character of the input. $\sigma_i$ is always one of the finite possible states of the DFA. In this example, the set of possible states is ${\sigma_0, \sigma_1}$.

Hope this helps!
-- SG