- q- , :
1. e, .
2. .
, . . q- G9.4(S):
1. S → aAS
2. S → b
3. A → cAS
4. A → e
, S- 4, . , , S- .
, X ( (X)) , - , S┤, ┤.
. :
() = { a, b }
(S) = { a, b }
, A, , A S, a, b. , S, 1 3, , S S, a, b:
S Þ aAS Þ acASS.
, , A → e. Ti Ï { a, b }, , c ┤, a , A → e. , , c ┤ , . , , G9.4, , S-. , bb, . , .
Ñ S | aacbb┤ | |||
Ñ SA | acbb┤ | , | ||
Ñ S | acbb┤ | |||
Ñ SA | cbb┤ | |||
Ñ S | cbb┤ |
4 3, .
|
|
Ñ S | aacbb┤ | |||
Ñ SA | acbb┤ | , | ||
Ñ S | acbb┤ | |||
Ñ SA | cbb┤ | |||
Ñ SSA | bb┤ | , | ||
Ñ SS | bb┤ | |||
Ñ S | b┤ | |||
Ñ | ┤ |
, . , , q- , :
A → bα, A → e b Î (A).
. .
: A → bα, b , α , A → bα b. :
(A → bα) = b.
: A → e, :
(A → e) = (A).
p , (p) ()
(p) p.
G9.4.
(1) = (S → aAS) = { a }
(2) = (S → b) = { b }
(3) = (A → cAS) = { c }
(4) = (A → e) = (A) = { a, b }
, , q-, :
(1) È (2) = Æ,
(3) È (4) = Æ.