:

 

1

, , " .

:

( (q0, 1, q1, X,

( (q1, 1, q2, X,

( (q1, Δ, q7, $,

( (q2, 1, q3, X,

( (q2, Δ, q6, $,

( (q3, 1, q1, X,

( (q3, Δ, q4, $,

( (q4, Δ, q5, $,

( (q6, Δ, q7, 1,

( (q7, Δ, q4, 1,

q5 .

. .

. 5 -3.

. ? .

. -0?
-0.

 

.




. 3: 0.

 

. 5: 2.

 

 

. f(x)=xmod3 0x.

q3,q2,q1 -3 1 (q1 1, q2 2, q3 0).

, $ 1 , 2 1 0 1, (q2,q1 -q3 ).

$ .

. -q0 . " :

( (q0, Δ, q4, $,

 

2

- , , " .

:

( (q0, #, q9, $,

( (q0, 1, q1, X,

( (q1, 1, q1, 1,

( (q1, #, q2, #,

( (q2, 1, q2, 1,

( (q2, Y, q3, Y,

( Δ, ,(q2, Δ, q3

( (q3, 1, q4, Y,

( (q3, #, q5, 1,

( (q4, 1, q4, 1,

( (q4, #, q4, #,

( (q4, X, q0, X,

( (q5, Y, q6, $,

( $, ,(q5, Δ, q6

( (q6, 1, q7, 1,

( (q7, 1, q7, 1,

( (q7, X, q8, $,

( (q9, Y, q8, $,

( (q9, Δ, q8, $,

( (q9, 1, q9, 1,

q8.

. .

. : 1 , 3 .
3 , 2 .

. ? .

 

.




. 1 -3: 2.

 

. 3 -2: 1.

 

 

. f(x) = x-yç.

-X 1 -Y 1 . . $ $ . 1 ( ), $ $ .