() (.. )
, .
3. , n-2 , , > 2, , = 0 = 1.
= {0,1}. . , , .. q1 .
, , , , . , , . , :
q11→ q20; q21→ q30.
q3 , ( ). , , .. q0, . :
q30→ q00; q31→ q01.
, . , ( q11→ q20) q2 , 0. , . , , :
q20→ q20,
, ( ). , , , , . q1 0, :
q10→ q10.
( )
:
A\Q | q1 | q2 | q3 |
0 | q10 | q20 | q00 |
1 | q10 | q20 | q01 |
. = {0, 1}, ( > 2). , , : 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 .. ( ). , (. . ) 1 , . ( ): 101, 1001, 11101, 101101, 1100101101 ..
|
|
1. , , , .. , , , , .
, .
-, , ( , . . ), .
-, , f(x1, x2,..., ), , , . , , . :
. :
; .
, : - ; 0, 1, 2, 3,... .
,
:
, , .. , q1 . f(x1, x2,..., ) , f(x1, x2,..., ) ;
.
, .
, 1 .
. , f(x)= /2. : . , 1 , , , .
() . : , ().
= {0, 1}. 11... 1, , , .
:
01 1q110 ( ).
: , , 0. :
(1): q11→ q21;
(2): q21→ q10;
|
|
(3): q20→ q20.
, , . . . , q10010101... 01010, /2.
, .
. , , . :
(4): q10→ q30;
(5): q30→ q30;
(6): q31→ q41.
001q4 010101... 010100. (*)
0, , 1
0:
(7): q40→ q51;
(8): q51→ q21.
00111q50101... 010100, 01,..., 01. , . 01. :
(9): q50→ q60;
(10): q61→ q21.
001110101...01010q600.
. 01 :
(11): q60→ q70;
(12): q70→ q70;
(13): q71→ q80.
001110101...01q800. x/2.
(14): q80→ q90.
001110101...010q9100.
:
(15): q91→ q100;
(16): q100→ q100.
001110101... 0q10100, (**)
10, 10,,10 ( ). , . . (/2) - 1. 10.
(17): q101→ q111;
(18): q110→ q100,
, : 001q11110101...0100.
(19): q111→ q121;
(20): q121→ q121;
(21): q120→ q131.
001111q13101... 0100, /2.
q4
(22): q131→ q41,
: 0011111q401... 0100, (*). ( ): 0 1, 1 0, , , ..
?
00111... 10q10100. (17), (18),
00111... 1q11 110100. (19),
(20), (21), : 00111... 111111q1300.
.
(23): q130→ q00.
: 00111... 1111q0100.
:
Q\A | 1 | |
q30 | q21 | |
q20 | q10 | |
q30 | q41 | |
q51 | ||
q60 | q51 | |
q70 | q51 | |
q70 | q80 | |
q90 | q21 | |
q100 | ||
q100 | q111 | |
q100 | q121 | |
q131 | q131 | |
q00 | q41 |