G = <{S, A, B, C, a, b}, {a, b}, P, S>

P:

S → AB|BC
A → BA|a
B → CC|b
C → AB|a
x = baaba

## Pierwsza część algorytmu

• V11 = {A|A → x1=b} = {B}
• V21 = {A|A → x2=a} = {A,C}
• V31 = {A|A → x3=a} = {A,C}
• V41 = {A|A → x4=b} = {B}
• V51 = {A|A → x5=a} = {A,C}

## Druga część algorytmu

• j=2, i=1,2,3,4, k=1
1. j=2, i=1, k=1  V12 = {A|A → BC, B ∈ V11, C ∈ V21}

BC = {B}x{A,C}

• A → BA
• S → BC
V12 = {A,S}
2. j=2, i=2, k=1  V22 = {A|A → BC, B ∈ V21, C ∈ V31}

BC = {A,C}x{A,C}

• (-) → AA
• (-) → AC
• (-) → CA
• B → CC
V22 = {B}
3. j=2, i=3, k=1  V32 = {A|A → BC, B ∈ V31, C ∈ V41}

BC = {A,C}x{B}

• S,C → AB
• (-) → CB
V32 = {S,C}
4. j=2, i=4, k=1  V42 = {A|A → BC, B ∈ V41, C ∈ V51}

BC = {B}x{A,C}

• A → BA
• S → BC
V42 = {A,S}
• j=3, i=1,2,3, k=1,2
1. j=3, i=1, k=1,2  V13 = {A|A → BC, B ∈ V11, C ∈ V22; B ∈ V12, C ∈ V31}

BC = {B}x{B} + {A,S}x{A,C}

• (-) → BB
• (-) → AA
• (-) → AC
• (-) → SA
• (-) → SC
V13 = ∅
2. j=3, i=2, k=1,2  V23 = {A|A → BC, B ∈ V21, C ∈ V32; B ∈ V22, C ∈ V41}

BC = {A,C}x{S,C} + {B}x{B}

• (-) → AS
• (-) → AC
• (-) → CS
• B → CC
• (-) → BB
V23 = {B}
3. j=3, i=3, k=1,2  V33 = {A|A → BC, B ∈ V31, C ∈ V42; B ∈ V32, C ∈ V51}

BC = {A,C}x{A,S} + {S,C}x{A,C}

• (-) → AA
• (-) → AS
• (-) → CA
• (-) → CS
• (-) → SA
• (-) → SC
• (-) → CA
• B → CC
V33 = {B}
• j=4, i=1,2, k=1,2,3
1. j=4, i=1, k=1,2,3  V14 = {A|A → BC, B ∈ V11, C ∈ V23; B ∈ V12, C ∈ V32; B ∈ V13, C ∈ V41}

BC = {B}x{B} + {A,S}x{S,C} + ∅x{B}

• (-) → BB
• (-) → AS
• (-) → AC
• (-) → SS
• (-) → SC
V14 = ∅
2. j=4, i=2, k=1,2,3  V24 = {A|A → BC, B ∈ V21, C ∈ V33; B ∈ V22, C ∈ V42; B ∈ V23, C ∈ V51}

BC = {A,C}x{B} + {B}x{A,S} + {B}x{A,C}

• S,C → AB
• (-) → CB
• A → BA
• (-) → BS
• A → BA
• S → BC
V24 = {A,S,C}
• j=5, i=1, k=1,2,3,4
1. j=5, i=1, k=1,2,3,4  V15 = {A|A → BC, B ∈ V11, C ∈ V24; B ∈ V12, C ∈ V33; B ∈ V13, C ∈ V42; B ∈ V14, C ∈ V51}

BC = {B}x{A,S,C} + {A,S}x{B} + ∅x{A,S} + ∅x{A,C}

• A → BA
• (-) → BS
• S → BC
• S,C → AB
• (-) → SB
V15 = {A,S,C}
 B A,C A,C B A,C V11 V21 V31 V41 V51 A,S B S,C A,S V12 V22 V32 V42 - B B V13 V23 V33 - A,S,C V14 V24 A,S,C V15

Ponieważ S ∈ V15, zatem słowo baaba należy do języka L(G).