( 3) , : - . , . . , , , . , .
3 () , , .
, , 3. - ( 2), , () . - .
- -, -, , .. , .
, (, ) .
(, ).
- , - (.. ), , , - (- ).
{ an bn | n ≥ 0 }
-, .
S → aSb | ε
,
{ an bn cn | n ≥ 0 }
-, -. - , .
1)
) - (.. ) , ..
A → BC | a
, .
) - , ..
|
|
A → bα
α (, ).
2)
G A,
A ⇒ α 1 A α 2
( α 1 α 2 / ), , . , :
1) G 1 = ({ S }, { a, b }, P, S), P:
S → aSb
S → ε
2) G 2 = ({ S, A }, {begin, end,[,]}, P, S), P:
S → begin A end
S → ε
A → [ S ]
A S , . -, , . , . () . , .. , . , , , ().