1.1.
() , , :
1. (), , 
;
2. , , 
;
3. , () ;
1
1.2.
( )
;
.
:
( ).
( ).
(R), (L), (E).
; , , , (R) (L) (E).
:
(1)
:
- 
;
-
;
, 
.
() P;
Q :
,
, 
; () 
.
, 
. .
A Q, .
() :
,
:
, ;
;
, , .
,
.. , a, .
:
|
|
|
,
( .. ). .
:
;
;
;
.
1.3.
- () .
( ) () , 3 :
1) , ;
2) ;
3) - .
:
M = <Q, A, K0 , P>,
Q = { q0, q1 , q2, q z },
A = {a, b, c, λ},
K0 = q0 a b c λ.
1) :
P = {q0 a → q1 λ R; q1 b → q2 λ R; q2 c → q z λ E }
2) :
3) :
1.4.
, .
(A)
,
A , ,
A (), ,
A , .
: , .
(K0) (Ki) . ( ) Ki+1 .
.
Ki, Kj
,
.
:
f-, 
. () f, :
1) f(V)=W 
, 
.
2) V , f(V) . , q0 V, .
:
f , (), f () .
: , M1 M2 , , .
1.5.
, .
a , , a, *.
1a * 1b 
1a+b.
, 
, 
, 
.
:
P = { 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
}.
1.6.
?
: һ. , , .
|
|
|
():
- ;
- .
, - , !
, :
..
-: 
,
:
- (?? α) , ?
- 0 , α
T0(T,α) = , .
T0(T,α) = , - .
