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 |