4.11 Inverse Machine
An inverse machine Mi 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 ...
Get Introduction to Automata Theory, Formal Languages and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.