Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v11(1-4)/kholodenko-721-730.pdf Дата изменения: Mon Feb 18 14:09:50 2008 Дата индексирования: Tue Oct 2 00:30:13 2012 Кодировка: Поисковые слова: uv

. .

n- , , () . , .

A = (A, Q, , QF , q0 ) , A , S , Q F Q , : A в Q Q , q0 . . LA = { A | (q0 , ) QF } , A. , , A . s N L(s) L s: L(s) = { L : || = s}. PL L, : PL = { A | A , L}, L PL. L L, , L = { A L | A , = }.


722

. .

|w| = n. lw (s) L, (s - n + 1)- s- w, lw (s) = |PLw (s)|. (. . 1), PLw (s) = w L, , A , | w| = s.

, ||=s-n

w, |w|=n



q0
. 1. PLw (s). Gw (s)

F

w s- Gw (s) = lw (s) . lw (s)
|w |=|w |

Gw = lim Gw (s) s w . w A a A , |wa| = n. w,a (s)
w ,a

(s) =

l

wa

(s) . lw (s)

|w |=|w |


w ,a

(s) =
w

Gwa (s) Gwa (s) = , Gw a (s) Ga (s)

, .




723

, s, u PL , v u, v . PLu (s) =
v ,|v u|=n

PLvu (s).

.
w ,a

(s) = lim
s

w ,a

(s),

, n- L. n = 1 ,a = Ga n = 2 b,a b a. . L n, n- w,a , |wa| = n Gv , |v | = n. n M(n). M , , n:


M=
n=1

M(n).

, , , A . , . , : 1. , A (. 2) 1. . : PL2 (s) = ({00, 01, 10, 11} 2)(s). l2 (s) = 2 0 0 2
s-1

s s s s

PL3 (s) = ({00, 01, 10, 11} {0, 1}3)(s). l3 (s) =
s-1


724

. .
3

*
0,1

2

0,1

3

2

. 2. , . PL0 (s) = ({0, 1} 0)(s). PL1 (s) = ({0, 1} 1)(s). l0 (s) = l1 (s) = 2 ,
,2 ,2 s-1

(s) = (s) =
,3

1 3

0 0
1 3

s s s s

,3



. .

1. n-
n-. 2 ( ). L M(n), w2 A , |w2 | = k < n : G
w1 ,|w1 |=n-k w1 w
2

= G w2 .

. , s > n lvu (s) = lu (s).
v ,|v u|=n

, s, u PL , v u, v . PLu (s) =
v ,|v u|=n

PLvu (s).

,1, 2,3
0

F

0,1,2,3

.




725

PLu (s), = 1 v u, |v u| = n, PLvu (s). PLvu (s), PLu (s). PLv1 u (s) PLv2 u (s) = . , G
v ,|v |=n-k vw

2

(s) =
v ,|v |=n-k

l

vw

2

(s) = lx (s)
y ,|y |=n-k

lw2 (s) ly z (s)
z ,|z |=k

=

x,|x|=n

=
z ,|z |=k

lw2 (s) ly z (s)
y ,|y |=n-k

=

lw2 (s) = Gw2 (s). lz (s)
z ,|x|=k

. 3 ( n- ).
v ,a

=
u,|uv |=n



uv ,a

.

, 2 |v | < n : Gv =
u,|uv |=n

Guv .

, (s) =
v

v ,a

lva (s) = lv a (s)

l
u uv

uv a

(s) (s) =
u uv

l l

uv a

(s) (s) =
u

l



uv ,a

(s).

xv a

uv a

. . . , , G
|w2 |=k w1 w
2

=G

w

1


726

. .

0

0,1 1

*

1

F
0

0,1

. 3. . , w 1 w1 w2 L, |w1 w2 | = n. . , (. 3) {0 n 11|n N}. G0 = 1 , G1 = 2 , G00 = 1 , G01 = 1 , G10 = 0, G11 = 1 . 3 3 3 3 3 , G10 + G00 = G0 G01 + G11 = G1 , G01 + G00 = G0 G10 + G11 = G1 .

2.
. 1. n, k < n. 2 3, , , n- n- . , . . , . , , . . (. 4). Xi (t) , xi (t) 0 i = 0, 1, 2, 3.




727

2

*
0

1

0
0

2 0 3

2
0

F

0,1,2,3

1

3

3
1

. 4. 1. . x x x x
0 1 2 3

(t (t (t (t

+ + + +

1) 1) 1) 1)

= = = =

x x x x

1 0 0 1

(t) (t) (t) (t)

+ + + +

x x x x

2 3 3 2

(t); (t); (t); (t),

, , x0 01 x1 1 0 x2 (t + 1) = 1 0 x3 01 0 1 A= 1 0 1 0 0 1
2k

1 0 0 1

0 x x 1 1 x x 0

0 1 2 3



(t). 0 2 2 0 2 0 0 2

1 0 0 1

A2k+1 = 22k A, A :

=2

2k -2

0 2 0 1 , A2 = 0 1 0 2 A2 .

0 2 2 0

x0 (t) = x3 (t)

0 2

t-1

t t


728

. .

x1 (t) = x2 (t) =

2 0

t-1

t t
t-1 t-1 t-1

l0 (t) = x0 (t) + x1 (t) + x2 (t) + x3 (t) = 2t ; l1 (t) = x2 (t) + x3 (t) = 2 l2 (t) = x0 (t) + x2 (t) = 2 l3 (t) = x1 (t) + x3 (t) = 2
,1 ,0

; ; ;

(t) =

2t 2t + 3 2
,1

t-1

=

2 2 =; 2+3 5
t-1

(t) =

,1

(t) =

(t) =

2t-1 2t + 3 2

=

1 1 =; 2+3 5

, 4 1. ,
2,1

(t) =

G21 (t) x0 (t) = = G1 (t) x2 (t) + x3 (t)

0 t 1 t

, 2,1 . . 4 n. : 2. n N L, , L Mn-1 , L Mn . , L N , L M(N ) , L M. , : 3. L M(2|Q| ), L M, Q , L.

3.
4. A .




729

. q1 q2 , q1 q2 , , (q1 , ) = q2 , , w A , a A, |wa| = n PL
wa

(s) = {wa| A

s-n

}.

: wa , A s-n . (q0 , wa) = q1 , L , q F Q , (q1 , ) = qF Q. , wa L. , lwa (s) = 2s-n , w a, Gv =
w ,a

=

1 = , |A|n-1 2s-n |A|n-1 lv (s) 2s-n 1 = = . n 2s-n lv (s) |A| |A|n

2

s-n

|v |=n

, . . M N , N . RN , N . : 4 ( ). N MN 1 . > 1- RN e

4.
L A. . A A,


730

. .

, . . A . : 5. A , . . , , . , A, . A , A. , , A A , . A A. , .


[1] . ., . ., A. C. . .: , 1985. [2] ., . , . . 1, 2. .: , 1978. [3] . . // . . 6. . 1­4. 2002. . 381­394.