() .
.
: Q - ().
( ) Q.
, .
: , , ,
f() .
, f() , . . , .
, , , .
, , .
1 2. , , , :
, . , 1 2.
- 1 , 2 .
( ).
2 . 1. . , , . 2 2. 2 , 1 һ. . .
, 1 , . , 2 . , , ,
.
.
A={a0,..,ai,} ( ).
Q={q0, q1, , qj,} ( ).
a0 , q0 , q1 .
{, , , a0, a1,, ai,, q0, q1, qj } :
0 | |||
1 | |||
ai | 100 | 2i+4 | |
. | |||
Q | q0 | ||
q1 | |||
. | |||
qj | 100 | 2j+5 | |
:
.
q1a0, q1a1,q2a0,. . . I1,In(m+1), n , m Q.
|
|
:
()=(I1)(I2) ..(In(m+1)).
.
A={a0,a1}
Q={q0,q1}
I1:q1a0→q0a0C
I2:q1a1→q0a1C
()=
. . . .
, 0,1 ( ). (), (0,1)-, q1(). (.. ) , , . , . , 1, qiaj→qiaj ( ), 1, qiaj→q0ajE ( ). , , . , , q1() q01,
, q00, .
1. , , .. .
( ).
, .. , . 0, q0* , q0, :
q01→q01 (1)
q00→q0* 0 (2).
0.
. , q1() q01, (1), 0 . , q1() q00, (2), 0 .
, 0 .
(0) 0 q1(0). 0 , . 0 , , q1(0), . 0 , , , q1(0), . , 0, , .
|
|
, , q1. , .. , , (), .