: , , , S - , - .
1) 0: L(G) = {a2 
| n >= 1}
G: S aaCFD
F AFB | AB
AB bBA
Ab bA
AD D
Cb bC
CB C
bCD e
2) 1: L(G) = { an bn cn, n >= 1}
G: S aSBC | abC
CB BC
bB bb
bC bc
cC cc
3) 2: L(G) = {(ac)n (cb)n | n > 0}
G: S aQb | accb
Q cSc
4) 3: L(G) = {w ^ | w Î {a,b}+, }
G: S A^ | B^
A a | Ba
B b | Bb | Ab
, , , . (, , ) .
- ( ) . , - .
, -.
: b Î (VT)* S Î VN -
G = (VT, VN, P, S), (), .
: b Î (VT)* S Î VN -
G = (VT, VN, P, S), (), .
, , , .
, a+b+a
G = ({a,b,+}, {S,T}, {S T | T+S; T a | b}, S)
:
(1) ST+ST+T+ST+T+Ta+T+Ta+b+Ta+b+a
(2) ST+Sa+Sa+T+Sa+b+Sa+b+Ta+b+a
(3) ST+ST+T+ST+T+TT+T+aT+b+aa+b+a
(2) - , (3) - , (1) , , .
- , , .
: ( ) - G = {VT, VN, P, S), :
(1) (VN È VT È e), S; - (VT È e);
|
|
|
(2) A Î VN, - a1, a2,..., an, ai Î (VT È VN), A a1a2...an - ;
(3) A Î VN, e, A e - .
a+b+a G:
: - G , a Î L(G), .
, a ( ) .
: .
: , , , .
:
G = ({if, then, else, a, b}, {S}, P, S),
P = {S if b then S else S | if b then S | a}.
if b then if b then a else a .
, L(G) . - , , .. .
, .
else then. , else then, G, :
S if b then S | if b then S else S | a
S if b then S else S | a
, - (.. ), .
, :
(1) A AA | a
(2) A AaA | b
(3) A aA | Ab | g
(4) A aA | aAbA | g
-:
L = {ai bj ck | i = j j = k}.
, i = j , , j = k. , , i = j = k , , . , - L , [3, . 235-236].
, L, :
S AB | DC
A aA | e
B bBc | e
C cC | e
D aDb | e
, .
.
; , , , .
, S; , - ; , .
|
|
|
, .
- , .
: x Î (VT È VN) G = (VT, VN, P, S), .
:
: - G = (VT, VN, P, S)
: - G = (VT, VN, P, S), , L(G) = L(G).
:
1. V0 = {S}; i = 1.
2. Vi = {x | x Î (VT È VN), P Aaxb AÎVi-1, a,bÎ(VTÈVN)*} È Vi-1.
3. Vi ¹ Vi-1, i = i + 1 2, VN = Vi Ç VN;
VT = Vi Ç VT; P P, Vi; G = (VT, VN, P, S).
: A Î VN
G = (VT, VN, P, S), { a Î VT* | A Þ a} .
:
: - G = (VT, VN, P, S).
: - G = (VT, VN, P, S), , L(G) = L(G).
:
N0, N1,...
1. N0 = Æ, i = 1.
2. Ni = {A | (A a) Î P a Î (Ni-1 È VT)*} È Ni-1.
3. Ni ¹ Ni-1, i = i + 1 2, VN = Ni; P P, VN È VT; G = (VT, VN, P, S).
: - G , .
:
(1) .
(2) .
, .
: (1) (2), .
-.
.
1. . .
a) S T | T+S | T-S b) S aSBC | abC
T F | F*T CB BC
F a | b bB bb
a-b*a+b bC bc
cC cc
aaabbbccc
2. :
S A+B | B+A
A a
B b
3. ? ? ?
a) S APA b) S aQb | e
P + | - Q cSc
A a | b
c) S 1B d) S A | SA | SB
B B0 | 1 A a
B b
4. , :
a) L = { an bm | n, m >= 1}
b) L = { acbcgc | a, b, g - a b}
c) L = { a1 a2... an an... a2 a1 | ai = 0 1, n >= 1}
d) L = { an bm | n ¹ m; n, m >= 0}
e) L = { 0 1 0 1}
f) L = { aa | a Î {a,b}+}
g) L = { w | w Î {0,1}+ 0 1, , , , }.
h) L = { (a2m bm)n | m >= 1, n >= 0}
i) L = { 
^ | n >= 1}
j) L = { 
| n >= 1}
k) L = { 
| n >= 1}
5. ? ? ?
a) S a | Ba b) S Ab
|
|
|
B Bb | b A Aa | ba
c) S 0A1 | 01 d) S AB
0A 00A1 AB BA
A 01 A a
B b
*e) S A | B *f) S 0A | 1S
A aAb | 0 A 0A | 1B
B aBbb | 1 B 0B | 1B | ^
*g) S 0S | S0 | D *h) S 0A | 1S | e
D DD | 1A | e A 1A | 0B
A 0B | e B 0S | 1B
B 0A | 0
*i) S SS | A *j) S AB^
A a | bb A a | cA
B bA
*k) S aBA | e *l) S Ab | c
B bSA A Ba
AA c B cS
6. :
) S AB S AS | SB | AB
A a | Aa A a
B b | Bb B b
b) S aSL | aL S aSBc | abc
L Kc cB Bc
cK Kc bB bb
K b
7. -, :
) S aAb b) S AB | ABS
aA aaAb AB BA
A e BA AB
A a
B b
8. , :
) S A | AS b) S A. A
A a | bb A B | BA
B 0 | 1
9. , :
S aSBC | abC
CB BC
bB bb
bC bc
cC cc
L = {an bn cn | n >= 1}. ,
1) an bn cn (n >= 1)
2) .
10. :
a) S S0 | S1 | D0 | D1 b) S if B then S | B = E
D H. E B | B + E
H 0 | 1 | H0 | H1 B a | b
:
a) 10.1001 b) if a then b = a+b+b
11. . , . -.
S P^
P 1P1 | 0P0 | T
T 021 | 120R
R1 0R
R0 1
R^ 1^
12. ,
{a, b}, a .
13. - L, aabbbcccc.
L = {a2n bm c2k | m=n+k, m>1}.
14. , { a, (,), ^ }. a : a ,
a) a ,
b) a = (a1) a= a1 a2, a1 a2 .
15. -, L, aacbbbcaa .
L = {an cbm can | n, m>0}.
16. -, L, 110000111 .
L = {1n 0m 1p | n+p>m; n, p, m>0}.
17. G. ; , ; .
G: S 0A1
0A 00A1
A e
18. L = {13n+2 0n | n>=0}. , , L. , 1111111100.
19. ,
A Bt, A tB, A t, .
20. - G1 G2, L1 L2, -
a) L1ÈL2
b) L1 * L2
c) L1*
: L =L1 * L2 - L1 L2, ..L = { ab | a Î L1, b Î L2}; L = L1* - L1, .. {e} È L1 È L1*L1 È L1*L1*L1 È...
21. - L={wi 2 wi+1R | i Î N, wi=(i)2 - i, wR - w}. - L* (. 20).
|
|
|
22. ,
E E+E | E*E | (E) | i
. ?
23. , -
a) A AA | a
b) A AaA | b
c) A aA | Ab | g
a, b, g Î (VTÈVN)*, A Î VN, . , ?
*24. , G . ? ?
G: S aAc | aB
B bc
A b
25. - G={VT, VN, P, S}.
X={A Î VN | A Þ e}.
26. - G , , L(G).
27. , .
a) S aABS | bCACd b) S aAB | E
A bAB | cSA | cCC A dDA | e
B bAB | cSB B bE | f
C cS | c C cAB | dSD | a
D eA
E fA | g
28. , , . , . , , , .
29. , , , .
30. , - .
: A Î VN - , A Þ x1Ax2. - , .
31. , (. 30) .
32. , , -, , .
: , A Þ aAb, |aAb| > 1; .
