Finite-State Machines and Pushdown Automata - Models of Computation: Exploring the Power of Computing - page 167

r ( k ) let T ( k ) denote the table of values of . Table T ( 0 ) in Fig. 4.16 describes

thenext-statefunctionofthisDFSM.Theremaining tables are constructed by invoking the
definition of r ( k )

{

i , j |

1 ≤ i , j ≤ 6 }

in ( 4.1 ). Entries in table T ( 1 ) are formed using the following facts:

i , j

i ,1 r ( 0 ) 1,1 ∗ r ( 0 )

1, j ; r ( 0 )

1,1 ∗ = ∗ = ;

r ( 1 )

i , j = r ( 0 ) i , j + r ( 0 )

r ( 0 )

i ,1 =

∅ for i ≥ 2

It follows that r ( 1 )

i , j = r ( 0 )

is identical to T ( 0 ) . Invoking the identity r ( 2 )

or that T ( 1 )

i , j = i , j

i ,2 r ( 1 ) 2,2 ∗ r ( 1 )

and using r ( 1 )

2,2 ∗ = ,weconstructthetable T ( 2 ) below:

r ( 1 )
i , j

+ r ( 1 )

2, j

r ( 2 ) T ( 2 ) = {

i , j }

i \ j

1 2 3 4 5

1 + 00

∅

1 0 01

∅ ∅

2 0 1

3 ∅ ∅ +0+1 ∅ ∅

∅ ∅

4 1 0

∅

1 + 01 5 0 00

is shown below. It is constructed using the identity r ( 3 )

i , j = r ( 2 )

The fourth table T ( 3 )

i , j +

i ,3 r ( 2 )

3,3 ∗ r ( 2 )

and the fact that r ( 2 )

3,3 ∗ =( 0 + 1 ) ∗ .

r ( 2 )

3, j

r ( 3 )

T ( 3 ) = {

i , j }

i \ j

1 2 3 4 5

( 1 + 00 )( 0 + 1 ) ∗ 1 0 01 ∅

0 ( 0 + 1 ) ∗

∅ ∅

2 1

∅ ∅ ( 0 + 1 ) ∗ ∅ ∅

3

1 ( 0 + 1 ) ∗ 4 ∅ ∅ 0

00 ( 0 + 1 ) ∗

∅

1 + 01 5 0

is shown below. It is constructed using the identity r ( 4 )

i , j = r ( 3 )

The fifth table T ( 4 )

i , j +

i ,4 r ( 3 ) 4,4 ∗ r ( 3 )

and the fact that r ( 3 )

4,4 ∗ = .

r ( 3 )

4, j

r ( 4 )

T ( 4 ) = {

i , j }

i \ j 1 2 3 4 5

( 1 + 00 + 011 )( 0 + 1 ) ∗ 1 0 01 010

( 0 + 11 )( 0 + 1 ) ∗ 2 ∅ 1 10

( 0 + 1 ) ∗ ∅ ∅ ∅ ∅

3

1 ( 0 + 1 ) ∗

4 ∅ ∅ 0

( 00 + 11 + 011 )( 0 + 1 ) ∗ 5 ∅ 0 1 + 01 + 10 + 010