Ülesanne 8

Algoritm 1.

N0={}
N1={C, A}
N2={C, A}
N1=N2  SÏN2  => keel on tühi

Algoritm 2.

V0={S}
V1={S, A, C}
V2={S, A, C, B, a, b}
V3={S, A, C, B, a, b}

N’ = V3ÇN = {S, A, B, C}
å’ = V3Çå = {a, b}
P’ = {(S->AC), (C->aCB), (C->b), (A->aA), (A->a)}
G’ = {å’ , N’ , P’ , S}

Algoritm 4 on valesti lahendatud

N0={}
N1={A, B, C}     N1¹N0
N2={A, B, C}È{A, B, C, S} = {A, B, C, S}  N2¹N1
N3={S, A, B, C}È{ S, A, B, C}   N3=N2 => Keel ei ole tühi

V0={S}
V1={S} È{A, B, C} V1¹V0
V2={S, A, B, C} È{S, A, B, C, e, a, b}  V2¹V1
V3={S, A, B, C, e, a, b } È{S, A, B, C, e, a, b} V3=V2

N’={S, A, B, C}
å’ ={e, a, b }
P’={(S->ABC), (A->BB), (B->CC), (C->AA), (A->e), (B->a), (C->b)}

Ne={S, A, B, C}
P’={(S->ABC), (A->BB), (B->CC), (C->AA), (B->a), (C->b)}

Algoritm 6.

N’={S, A, B, X11, X21, X42, X72}
P’={(S->X11B), (S->X21A), (A->X11S), (A->X21X42), (X42->AA), (A->a), (B->X21S), (B->X11X72),
(X72->BB), (B->b), (X11->a), (X21->b)}

Algoritm 7.

Lähtegrammatika G:  {S->SaA, S->AA, S->b, A->Asa, A->Ad, A->aS, A->c}

Valin A1=S ja A2=A
1. i:=1
2. S->SaA asendub S->AAS’
S->bS’
S’->aA
S’->aAS’
3. i:=2 ja j:=1
4. muutusi ei teki
2. A->ASa asendub  A->aSA’
A->cA’
A’->Sa
A’->SaA’
A->Ad asendub A->aSA'
A->cA'
A'->d
A'->dA'
3. i=3 s.t. oleme lõpetanud

N'={S,A,A',S'}
P'={S->AA, S->b, S->AAS’, S->bS’, S’->aA, S’->aAS’, A->aS, A->c, A->aSA’, A->cA’, A’->Sa, A’->SaA’, A'->d, A'->dA'}

Algoritm 8.

Lähtegrammatikaks on algoritmi 7 tulemus s.t.
G: {S->AA, S->b, S->AAS’, S->bS’, S’->aA, S’->aAS’, A->aS, A->c, A->aSA’, A->cA’, A’->Sa, A’->SaA’, A'->d, A'->dA'}
1. Järjestuse valin sellise: S'<A'<S<A
2. i:=3
3. S->AA asendub  S->aSA
S->cA
S->aSA'A
S->cA'A
S->AAS' asendub S->aSAS'
S->cAS'
S->aSA'AS'
S->cA'AS'
4. i:=2
3. A'->Sa asendub  A'->aSAa
A'->cAa
A'->aSA'Aa
A'->cA'Aa
A'->aSAS'a
A'->cAS'a
A'->aSA'AS'a
A'->cA'AS'a
 A'->SaA' asendub A'->aSAaA'
A'->cAaA'
A'->aSA'AaA'
A'->cA'AaA'
A'->aSAS'aA'
A'->cAS'aA'
A'->aSA'AS'aA'
A'->cA'AS'aA'
4. i:=1
3. ei juhtu midagi
4. i:=0
3. i=0
5. A'->aSAa  asendub A'-aSAa'
 A'->cAa asendub A'->cAa'
 A'->aSA'Aa asendub A'->aSA'Aa'
A'->cA'Aa asendub A'->cA'Aa'
A'->aSAS'a asendub A'->aSAS'a'
A'->cAS'a asendub A'->cAS'a'
A'->aSA'AS'a asendub A'->aSA'AS'a'
A'->cA'AS'a asendub A'->cA'AS'a'
A'->aSAaA' asendub A'->aSSa'A'
A'->cAaA' asendub A'->cAa'A'
A'->aSA'AaA' asendub A'->aSA'Aa'A'
A'->cA'AaA' asendub A'->cA'Aa'A'
A'->aSAS'aA' asendub A'->aSAS'a'A'
A'->cAS'aA' asendub A'->cAS'a'A'
A'->aSA'AS'aA' asendub A'->aSA'AS'a'A'
A'->cA'AS'aA' asendub A'->cA'AS'a'A'
6. a'->a

Tulemus
N'={S,S',A,A',a'}
P={ S->b, S->bS’, S->aSA, S->cA, S->aSA'A, }
S->cA'A, S->aSAS', S->cAS', S->aSA'AS', S->cA'AS',
S’->aA, S’->aAS’,
A->aS, A->c, A->aSA’, A->cA’,
A'-aSAa', A'->dA', A'->d, A'-aSAa', A'->cAa',
A'->aSA'Aa', A'->cA'Aa', A'->aSAS'a', A'->cAS'a', A'->aSA'AS'a',
A'->cA'AS'a', A'->aSSa'A', A'->cAa'A', A'->aSA'Aa'A', A'->cA'Aa'A',
A'->aSAS'a'A', A'->cAS'a'A', A'->aSA'AS'a'A', A'->cA'AS'a'A',
a'->a