Lecture No. 22

Dated: 22-02-2025

Applications of Incrementing and Complementing Machines

Incrementing Machine

It can be used to make a machine capable of doing binary addition.

Complementing Machine

It can be used to make a machine capable of doing binary subtraction.

Subtracting a Binary Number from Another

Method

Imagine we need to subtract \(b\) from \(a\).
Following are the steps to do so

1. Take 1's complement of \(b\).
2. Add it to \(a\).
3. Increment the final result by \(1\).

Also, ignore any overflows which may happen.

Example

\[a = 1110\]

\[b = 0101\]

Taking 1's complement.

\[b^\prime = 1010\]

Adding it to \(a\).

\[a + b^\prime = 1110 + 1010 = 11000\]

Incrementing by \(1\).

\[11000 \rightarrow 11001\]

Ignoring the overflow

\[a - b = a + b^\prime = 1001\]

Equivalent Machines

Two machines are called equivalent if they output same string¹ when same input string¹ is passed through them.

Theorem

Statement

For every moore machine,² there is an equivalent mealy machine³ if we ignore the extra character printed by moore machine²

Proof

Let \(M\) be a moore machine² then shifting the output characters corresponding to each state to the labels of corresponding incoming transitions, results into an equivalent mealy machine.³

Note

While converting moore machine² into an equivalent mealy machine,³ the output character of a state will be ignored if there is no incoming transition at that state.
A loop is also supposed to be an incoming transition.

Example

Moore machine² to translate

converted mealy machine³

Input		a	b	b	a	b	b	b	a
States	\(q_0\)	\(q_1\)	\(q_2\)	\(q_3\)	\(q_3\)	\(q_3\)	\(q_3\)	\(q_3\)	\(q_3\)
Moore	0	1	0	1	1	1	1	1	1
Mealy		1	0	1	1	1	1	1	1

Theorem

Statement

For every mealy machine,³ there is an equivalent moore machine² ignoring the extra character printed.

Proof

There can be multiple incoming transitions and hence there are following possibilities which may occur.

Same Output Characters

If the transitions have same output character then shift that character to the corresponding state.

Different Output Characters

If the transitions have different output characters then divide the corresponding state into 2 states to make sure the incoming transitions are only one and unique.
Meaning, if \(q_i\) has 2 incoming transitions with character \(a\) and \(b\) then divide it into \(q_i^1\) for \(a\) and \(q_i^2\) for \(b\).
Though these new states should behave like \(q_i\).

Note

If there is no incoming transition for a state then any character can be associated with that state.
If the initial state is converted into multiple states then only one of these will be considered as initial state.

Example

Mealy machine³ to be converted

Shifting the output character \(1\) of transition \(b\) to state \(q_0\).

Shifting the output character \(0\) of transition \(a\) to state \(q_1\).

Shifting the output character \(1\) of transition \(b\) to state \(q_2\).

Splitting \(q_3\) into \(q_3^1\) and \(q_3^2\).

Input		a	b	b	a	b	b	b	a
States	\(q_0\)	\(q_1\)	\(q_2\)	\(q_3\)	\(q_3\)	\(q_0\)	\(q_3\)	\(q_0\)	\(q_1\)
Mealy		0	1	1	1	1	0	1	0
Moore	1	0	1	1	1	1	0	1	0

References

---

1. Read more about fundamentals. ↩↩

2. Read more about moore machines. ↩↩↩↩↩↩

3. Read more about mealy machines. ↩↩↩↩↩↩