. :
Æ ,
{e} ,
Î, { } ,
P, Q , P È Q ,
P, Q , PQ ,
P , * ,
.
:
Æ , Æ,
e , {e},
Î, , { },
p q , P Q ,
) (p + q) , P È Q;
) (pq) , PQ;
) (p)* , P *;
.
G =(N, T, s, P) , P A xB A x, , Î N, x ÎF(T).
:
1) Æ ({ s }, X, s,Æ),
2) e ({ s }, X, s,{ s e}),
3) ( Î ) ({ s }, X, s,{ s a }),
4) G 1=(N 1, X, s 1, P 1) G 2=(N 2, X, s 2, P 2) , p q (N 1Ç N 2=Æ), :
) p + q (N 1È N 2È{ s }, X, s, P 1È P 2È{ s s 1, s s 2}), s Ï N 1È N 2,
) pq (N 1È N 2, X, s 1, P), :
A xB P 1, A xB P,
A x P 1, A xs 2 P,
P 2 P,
) p * (N 1È{ s }, X, s, P), s Ï N 1, P :
A xB P 1, A xB P,
A x P 1, A xs A x P,
s s 1 s e P.
00+1* ={0,1}. .
: 0, 00, 1, 1*, 00+1*.
0
G 1=({ s 1}, X, s 1,{ s 10}) ( 3).
|
|
|
00 G 1=({ s 1}, X, s 1,{ s 10}) G 2=({ s 2}, X, s 2,{ s 20})
G 3=({ s 1, s 2}, X, s 1, { s 10 s 2, s 20}) ( 4).
1
G 4=({ s 3}, X, s 3, { s 31}) ( 3).
1* G 4
G 5=({ s 3, s 4}, X, s 4, { s 4e, s 4 s 3, s 31, s 31 s 4}) ( 4).
00+1* G 3 G 5
G 6=({ s 1, s 2, s 3, s 4, s 5}, X, s 5, P)), ( 4)
={ s 5 s 1, s 5 s 4, s 10 s 2, s 20, s 4e, s 4 s 3, s 31, s 31 s 4}.
00+1* .
() :
1) Æ ,
2) e ({ a 0}, X, f, a 0, { a 0}), f (a 0, ) ( f =Æ),
3) ( Î ) ({ a 0, a 1}, X, f, a 0, { a 1}), f (a 0, x)={ a 1}, f ,
4) 1=(A 1, X, f 1, a 0, F 1) 2=(A 2, X, f 2, b 0, F 2) , p q ( 1Ç 2=Æ), :
) p + q (A 1È A 2È{ c 0}, X, f, c 0, F), c 0Ï A 1È A 2, F = F 1È F 2, 1, 2 e, F = F 1È F 2È{ c 0}, 1 2 e, f :
f (c 0, x)= f (a 0, x)È f (b 0, x) x X,
f (a, x)= f 1(a, x) 1 X,
f (a, x)= f 2(a, x) 2 X;
) pq (A 1È A 2, X, f, a 0, F), F = F 2, b 0Ï F 2, F = F 1È F 2, b 0Î F 2, f :
f (a, x)= f 1(a, x) 1\ F 1 X,
f (a, x)= f 1(a, x)È f 2(b 0, x) F 1 X,
f (a, x)= f 2(a, x) 2 X;
) p * (A1È{ c 0}, X, f, c 0, F 1È{ c 0}), c 0Ï A 1, f :
f (a, x)= f 1(a, x) 1\ F 1 X,
f (a, x)= f 1(a, x)È f 1(a 0, x) F 1 X,
f (c 0, x)= f 1(a 0, x) X.
