Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms

190

ELEMENTS

OF

MATHEMATICAL

LOGIC

sampling instants, starting from the instantinwhich thep row of such

a

tape begins to differ from the

p

rows of the tapes enumerated in the

specification. If the main tapes

are

those of Tables 8.1

-

8.4, then

this additional condition could, for example, lead to an s-machine

having tapes showninTables

8.5

-

8.7 (where the instants of genera-

tion of

ho

are

marked off with heavy lines).

Table

8.5

Table 8.7

Table 8.6

4

~ ~

PI

Because

we

stipulated that

all

the giventapesmust start with

lco,

our specification may prove to be an impossible one. For example,

consider Tables 8.8 and 8.9. Obviously, there

is

no s-machine which

has both these tapes: for thismachine wouldgenerate, from the same

initial state

xo

and the same input sequenceplpspo,

two

different outputs

(3.,

in the case of 8.8, and lb3in the

case

of 8.9). Suchanoperationcan-

not

be

expected of an s-machine, which by definition

is

a

determinate

device. The specification

is

thus

contvadictovy.

Now

it

is

clear thatbefore proceedingwith the synthesis, the de-

signer must check the specification for contradictions.

He

does this

by inspecting sections of the given tapes,

as

shown below. The speci-

fication

is

not contradictory

if,

and only

if,

no

two

sections show dif-

fering outputs at identical inputs.

THE

REQUI RED INPUT-OUTPUT CORRESPONDENCES

Table

8.8

Table

8.9

191

Thus, in

the

example

of

tapes

8.8

and

8.9,

the tapes

are

split up

as

follows:

for

p=

1

192

ELEMENTS

OF

MATHEMATICAL LOGIC

for

p

=:

LI

The contradiction becomes apparent after

p

=

3.

Assume

that

we

start with a noncontradictory specification

so

that we can immediately proceed with the synthesis, that is, develop

the tables of

the

finite automaton and of the converter

of

the

s-

machine.

If

we

are

given

all

the

x

rows on the given tapes, than

we

can pick out

the

triads

directlyfrom the tapes and write out at least

some of the squares of these tables. The other squares could be filled

out arbitrarily,

if

no additional conditions

are

imposed on the ma-

chine,

or

in some other way,if there

are

such

conditions. Thus the

synthesis of an s-machine reduces to filling out the

x

rows of the

tapes in

a

noncontradictory manner.

If the specification can

be

realized in some s-machine

A,

then

it

can also be realized in any s-machine

B

which can substitute

for

A.

If all

we

require

is

some machine realizing

the

specification, that

is,

if

we

impose

no

additional requirements on the s-machine, then the

solution

is

trivial, and may involve one of the following

two

methods:

a) The

x

rows may be filled

with

nonrecurring

xt,

the number of

the different states

xi

thus obtained being equal to the sum of lengths

of

the (given) tapes.

b)

We

can construct an automatonwith an output converter which

represents the specific events "recorded" on the (given) tapes. Thus,

we

extract from the tapes all those input sets

GI,

Gz,

and

so

on, which

generate outputs

I.,

,

k2,

and

so

on, respectively. Then, using methods

of Chapter

7,

we

synthesize automata

I,

11,

and

so

on, respectively

representing the specific events

GI,

G2,

and

so

on by outputs of

1.

We

THE REQUIRED INPUT-OUTPUT CORRESPONDENCES

193

now connect the outputs of

these

automata to

a

converter generating

an output of

iil

if

there

is

a

1

on the first converter input,

hZ

with

a

1

on the second input, and

so

on.

The s-machines synthesized by either of these methods usually

have anextremelylarge number of states. Therefore, quite often one

is

faced with

a

much more difficult problem, where one wants to syn-

thesize an s-machine conforming to

a

given specification but having

fewer states than any other machine also conforming to this

specifi-

cation.

The solution

is

usually divided into

two

phases:

1)

synthesis of

some (any) machine conforming to specifications; and 2) its minimi-

zation, that is, the derivation, from this preliminaryversion, of an-

other s-machine which

also

conforms to the specification but which

has the least possible number of

statesk.

The

minimization

problem

of

phase

2

is

discussed in Chapter

9.

However, the methods of that chapter

are

difficultto apply

if

the

s-

machine of phase

1

has many states,

a

condition produced by the use

of

the above trivial methods in phase

1.

For

this

reason one

re-

sorts,

if

possible, toother phase

1

techniques: these give s-machines

which, even though not minimal,

are

apriori

known to have

a

small-

er

number of states.

We

shall describe one such method.

Let

us

begin with the following example. Suppose

we

want to syn-

thesize an s-machine which, startingfrom the same state

x0

=

xo,

will

realize

the

two

tapes of Tables 8.10 and 8.11. The tapes generated at

other input sequences can be arbitrary.

Let us prepare

a

blank form for the tables of the automaton and

the converter (Table 8.12 for the automaton and Table 8.13 for the

converter). Since the ultimate number of the states

is

still unknown,

the number of the rows in these tables

is

still

undetermined.

time being,

we

have only one line-for

xo.

Table 8.10 Table 8.11

For the

In further filling

out

thexrow

,

we

must

always

check whether the

new entry does not contradict the preceding one; that

is,

that

it does

194

ELEMENTS

OF

MATHEMATICAL LOGIC

Table 8.12

Automaton

Table 8.13

Converter

not produce contradictory triads in the automaton

or

impose incom-

patible requirements on the converter.

In the first square of row

II

of Table 8.10 we write

xo

(in accord-

ance with the specification). There

is

also no reason why

xo

cannot be

entered in the second square

of

this tape.

We

alsowritexoin thecor-

responding square of the basic table of the automaton (Table 8.12).

We

fill the corresponding squares

(XO,

PO)

and

(KO,

p3)

of

the converter

table with the symbol

hi

(from columns

0

and

1

of

Table

8.10).

Again

we observe that nothing prevents

us

from entering the same symbol

xo

into the column

2

of

Table 8.10 and into the corresponding squares

of

Tables 8.12 and8.13. This results in Tables 8.14

-

8.16.

Table 8.14

Tape

Table 8.15 Table 8.16

Basic Table

of

the Automaton Converter

Table

THE

REQUIRED

INPUT-OUTPUT

CORRESPONDENCES

195

So

far,

we

enteredxowithout producing contradictions. Let us try

to enter it in

the

next (fourth) square of

the

tape (Table

8.14).

This

produces no contradictions in the automaton table since

this

symbol

goes into

a

blank square, but an attempt to write in

h2

into the square

(p3,

xo)

of

the converter does lead to contradiction since

this

square

already contains

h,.

We

have no other alternative but to enter

a

new

symbol

xI

into the fourth square of the tape (Table

8.14).

This, of

course, gives new rows in the tables of

the

automaton and

the

con-

verter, where

we

enter the corresponding symbols.

Now

we

try to enter

xo

into the next

(fifth)

square

of the tape

:

there

is

no contradiction. Had there been one, then

we

would have had to

try

xl

and,

if

this led to

a

contradiction,

we

would have to introduce

x2

and start

a

new row in

the

tables.

We

repeat this procedure all

along the tape

of

Table

8.14

andwe thus complete

its

x

row. Now

we

turn to

the

second tape (Table

8.11)

and

fill

itsxrow in the same man-

ner.

Here

we

must make sure that the symbol being entered not only

does not contradict the previous entries on

this

tape, but that

it

does

not contradict those

of

the

first

tape.

We

then have complete tables

for the automaton and the converter (Tables

8.17

-

8.20).

Now

these

tables have blank squares which may be filledin any desired manner,

since

we

have stiuplated

at

the outset that the tapes obtained at input

sequence other than

the

given ones

are

arbitrary.

Table

8.17

First Tape

Table

8.19

Basic

Table

of

the Automaton

1

Table

8.18

Second Tape

Table

8.20

Converter Table

196

ELEMENTS

OF

MATHEMATICAL LOGIC

The above example

has

been chosen

so

as

to present no difficulties

in completing thexrows. However, consider the tapes

of

Tables

8.21

and

8.22.

We leave the intermediate details to the reader, and shall

discuss only the final results. Thus, in tape

1,

we

can enter

xo

into

the second and the third squares without raising any contradictions,

Table

8.21

First

Tape

Table

8.22

Second

Tape

but since

xo

in the fourth square produces

a

contradiction in the con-

verter table,

we

must

write

xi

in this square.

A

xo

in the fifth square

does not, in itself, lead to

a

contradiction, but

we

then must have

xo

in the sixth square to avoid

a

contradiction in the automaton table

[since the

(xo.

"0)

combinationwas alreadyusedin the first column of

the

tape and required

a

xoin the following column]. But ?coin

the

sixth

square contradicts the converter table.

We

must, therefore, go back

to the

fifth

square and tryx,. This gives no contradiction, and

we

can

thus tryx, in the sixth square.

No(p2,

x,)combination has yet been en-

countered and, therefore, from the point of view of the table of the

automaton,

we

can use any symbol in the seventh tape square. How-

ever,

x0

and ~~cannotbeusedbecause combinations

(pl,x0)

and

(pl,zl)

already

specify entries other than in the converter table. There-

fore,

we

use

a

new symbol

x2

in the seventh square.

Now let

us

examine tape

2

(Table

8.22).

The

(p2,

x0)

combination

has already been encountered in the third column of tape

1;

there-

fore, to avoid contradictions in the automaton table,

we

can only use

xI

in the second square of tape

2.

But

this

causes a contradiction in

the converter table,

so

we

have no alternative but to go back to the

third square of the tape

1,

remove the

x0,

and

fill

inx3. Now

we

can

proceed with the completion of the tape

2

without altering tape

1,

re-

solving only contradictions that may

arise

in

the

same manner

as

when

completing tape

1.

No states other thanxo,

XI,

x2andxsneed tobe used

in this example,

which

finally results in Tables

8.23

-

8.26.

THE

REQUl

RED

INPUT-OUTPUT CORRESPONDENCES

197

Table

8.23

First

Tape

Table

8.25

Basic

Table

of

the Automaton

Table

8.24

Second Tape

Table

8.26

Converter Table

P2

Rather than replacing the

xo

in

the

third square of tape

1

with

a

new symbol

x3,

we

could have tried to

use

one of the old ones

(x,

or

x2),

altering,

if

necessary, the other squares of tape

1.

This would

have given other tables for the automaton and converter, and these

might have had

a

different number of rows (that

is,

states).

Themethod demonstrated aboveisnot a regular, straightforward

procedure, and shows

the

complexities which may

arise

in phase

1

of

the synthesis, where

we

are

merely trying to obtain

any

s-machine

satisfying .the stipulated conditions.

Let us now develop a regular method for uniform synthesis of

relatively economical s-machines realizing any given noncontradic-

tory finite set of finite tapes.

We

shall confine ourselves to the case

where

the

tapes generated at input sequences other than those stipu-

lated in the specification may be arbitrary. Againwe

shall

startwith

the blanks for the tables of

the

automaton and the converter, and

we

198

ELEMENTS

OF

MATHEMATICAL LOGIC

shall increase

the

number

of

rows in these tables

as

new

states

?t

are

introduced. Assume, however, that the given tapes and the two tables

are

already partly filled.

We

shall say that these already-present

entries

are

correct

if

they meet the following conditions:

1.

The entries in the tapes and the tables do not conflict; that

is,

the tapes contain no triads producing contradictions in the automaton

and the converter and, conversely, the only filled positions in the

automaton and converter tables

are

those which correspond to triads

already present on the tapes.

2.

The last column of each tape contains

a

(p,

x)

pair which de-

fines a still empty square

in

the automaton table.

3. If two

or

more of these last(@,

?c)

pairs contain identical sym-

bols

11,

and

if

the corresponding tapes show identical

p's

during one

or

more subsequent sampling instants, then these tapes must also

show identical symbols

1,

during these instants.

For

example, Tables 8.27

-

8.30

are

correctly filled.

Table

8.27

First

Tape

Table 8.29

Basic

Table

of

the Automaton

Table 8.28

Second Tape

Table 8.30

Converter Table

However, the tables of the following three examples

are

incorrectly

filled.

Example

I

(Tables 8.31

-

8.34) violates condition

1:

THE

REQUIRED INPUT-OUTPUT CORRESPONDENCES

199

Table 8.31

First Tape

Table 8.32

Second Tape

Table 8.33 Table 8.34

Basic Table

of

the

Automaton

Converter Table

Table 8.35

First

Tape

Example

2

(Tables 8.35

-

8.38) violates condition

2:

Table 8.36

Second Tape

__

Dis-

crete

mo-

ment

P

~

7.

Example

3

(Tables 8.39

-

8.41)

violates condition 3:

Provided the specification

is

not contradictory, the initial (given)

tapes which contain onlyxofor

t

=

0,

together with

a

completely blank

automaton table and a converter table withentries only in the squares

corresponding

to

t

=

0

for all the tapes, are one

case

of correct filling.

Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms

Подождите немного. Документ загружается.