. , , .
, , , . , . .
; , , . ( ) , ( ).
( ) (α, β). , α β ( α::= β). α β β α.
: ( ) ; ( ) . ( ) : , . , , ; (, , , ). .
, , . , .
, G, L(G).
G G , : L(G) = L(G). G G , : L(G){}=L(G){}.
1.2.2. .
.
G G(VT,VN,P,S), :
VT ;
VN : VNVT = ;
|
|
() αβ, αV+, βV*;
S () SVN.
V = VNVT G.
VN VT. VT , , . , VT , , . VN , , , . , , . , .
: , . . .
, , : αβ1, αβ2,... αβn. : αβ1|β2||βn. n .
. , , , : < >. ::=, , .
:
G({0,1,2,3,4,5,6,7,8,9,,+},{<>,<>,<>},,<>)
:
<> <> | +<> | <>
<> <> | <><>
<> 0|1|2|3|4|5|6|7|8|9
G:
VT : ;
VN : <>, <> <>;
15 , ( );
<>.
, <> , , , . , . , , , , , Pascal , .
|
|
. , .
, , , ( ):
G({0,1,2,3,4,5,6,7,8,9,,+},{S,T,F},P,S)
:
S | + |
F | TF
F 0|1|2|3|4|5|6|7|8|9
. VN={S,T,F}. , , G G .