O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required