Introduction to Automata Theory, Formal Languages and Computation

4.11  Inverse Machine

An inverse machine Mⁱ is a machine which is developed from the given machine M with its output sequence and produces the input sequence given to machine M, after at most a finite delay.

A deterministic inverse machine can be constructed if and only if the given machine is lossless. The machine can produce the input sequence applied to the original machine after at most a finite delay if and only if M is lossless of a finite order.

Consider the following example.

Example 4.22

Construct an inverse machine of the following given machine:

Solution:

Present State	Next State, z
	X = 0	X = 1
A	B, 0	C, 1
B	C, 1	D, 0
C	A, 0	D, 1
D	A, 1	C, 0

We have to construct the inverse machine of this given machine.

Before constructing ...