1. .
, , . . . .
2. .
, , .
.
. , , , . .
20 .
: .
( ) , , . . , . , , . , , , . , , . , .
. : , .
. : . , . . A1 , . . A1 , . 1 . . .
|
|
|
.
A, Q .
, . , .
.
, -. , A={0, 1, 0}, 0 . :
q1
q2 1, .
q0 .
:
| q1 | q2 | |
| 0 | 0 → q1 | 1. q0 |
| 1 | 1 → q1 | 0 ← q2 |
| a0 | a0 ←q2 | 1. q0 |
q1:
- 0 -
- 1 -
- q2
q2:
- 0 1
- 1 ( 0 )
- , 1 .
. . .
.
:
1)
2)
.
O(n) , f(n)=C*n, .
, :
O(n) ;
O(log(n)) ;
O(nd), d >1 ;
:
O(en) .
, .
NP , .
, .
