Sprawdzenie czy baaba należy do języka

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

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

Pierwsza część algorytmu

V₁₁ = {A|A → x₁=b} = {B}
V₂₁ = {A|A → x₂=a} = {A,C}
V₃₁ = {A|A → x₃=a} = {A,C}
V₄₁ = {A|A → x₄=b} = {B}
V₅₁ = {A|A → x₅=a} = {A,C}

Druga część algorytmu

j=2, i=1,2,3,4, k=1
1. j=2, i=1, k=1
  
  V₁₂ = {A|A → BC, B ∈ V₁₁, C ∈ V₂₁}
  
  BC = {B}x{A,C}
  - A → BA
  - S → BC
  V₁₂ = {A,S}
2. j=2, i=2, k=1
  
  V₂₂ = {A|A → BC, B ∈ V₂₁, C ∈ V₃₁}
  
  BC = {A,C}x{A,C}
  - (-) → AA
  - (-) → AC
  - (-) → CA
  - B → CC
  V₂₂ = {B}
3. j=2, i=3, k=1
  
  V₃₂ = {A|A → BC, B ∈ V₃₁, C ∈ V₄₁}
  
  BC = {A,C}x{B}
  - S,C → AB
  - (-) → CB
  V₃₂ = {S,C}
4. j=2, i=4, k=1
  
  V₄₂ = {A|A → BC, B ∈ V₄₁, C ∈ V₅₁}
  
  BC = {B}x{A,C}
  - A → BA
  - S → BC
  V₄₂ = {A,S}
j=3, i=1,2,3, k=1,2
1. j=3, i=1, k=1,2
  
  V₁₃ = {A|A → BC, B ∈ V₁₁, C ∈ V₂₂;
  B ∈ V₁₂, C ∈ V₃₁}
  
  BC = {B}x{B} + {A,S}x{A,C}
  - (-) → BB
  - (-) → AA
  - (-) → AC
  - (-) → SA
  - (-) → SC
  V₁₃ = ∅
2. j=3, i=2, k=1,2
  
  V₂₃ = {A|A → BC, B ∈ V₂₁, C ∈ V₃₂;
  B ∈ V₂₂, C ∈ V₄₁}
  
  BC = {A,C}x{S,C} + {B}x{B}
  - (-) → AS
  - (-) → AC
  - (-) → CS
  - B → CC
  - (-) → BB
  V₂₃ = {B}
3. j=3, i=3, k=1,2
  
  V₃₃ = {A|A → BC, B ∈ V₃₁, C ∈ V₄₂;
  B ∈ V₃₂, C ∈ V₅₁}
  
  BC = {A,C}x{A,S} + {S,C}x{A,C}
  - (-) → AA
  - (-) → AS
  - (-) → CA
  - (-) → CS
  - (-) → SA
  - (-) → SC
  - (-) → CA
  - B → CC
  V₃₃ = {B}
j=4, i=1,2, k=1,2,3
1. j=4, i=1, k=1,2,3
  
  V₁₄ = {A|A → BC, B ∈ V₁₁, C ∈ V₂₃;
  B ∈ V₁₂, C ∈ V₃₂;
  B ∈ V₁₃, C ∈ V₄₁}
  
  BC = {B}x{B} + {A,S}x{S,C} + ∅x{B}
  - (-) → BB
  - (-) → AS
  - (-) → AC
  - (-) → SS
  - (-) → SC
  V₁₄ = ∅
2. j=4, i=2, k=1,2,3
  
  V₂₄ = {A|A → BC, B ∈ V₂₁, C ∈ V₃₃;
  B ∈ V₂₂, C ∈ V₄₂;
  B ∈ V₂₃, C ∈ V₅₁}
  
  BC = {A,C}x{B} + {B}x{A,S} + {B}x{A,C}
  - S,C → AB
  - (-) → CB
  - A → BA
  - (-) → BS
  - A → BA
  - S → BC
  V₂₄ = {A,S,C}
j=5, i=1, k=1,2,3,4
1. j=5, i=1, k=1,2,3,4
  
  V₁₅ = {A|A → BC, B ∈ V₁₁, C ∈ V₂₄;
  B ∈ V₁₂, C ∈ V₃₃;
  B ∈ V₁₃, C ∈ V₄₂;
  B ∈ V₁₄, C ∈ V₅₁}
  
  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
  V₁₅ = {A,S,C}

B	A,C	A,C	B	A,C
V₁₁	V₂₁	V₃₁	V₄₁	V₅₁
A,S	B	S,C	A,S
V₁₂	V₂₂	V₃₂	V₄₂
-	B	B
V₁₃	V₂₃	V₃₃
-	A,S,C
V₁₄	V₂₄
A,S,C
V₁₅

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

V₁₃ = {A\|A → BC,	B ∈ V₁₁, C ∈ V₂₂;
	B ∈ V₁₂, C ∈ V₃₁}

V₂₃ = {A\|A → BC,	B ∈ V₂₁, C ∈ V₃₂;
	B ∈ V₂₂, C ∈ V₄₁}

V₃₃ = {A\|A → BC,	B ∈ V₃₁, C ∈ V₄₂;
	B ∈ V₃₂, C ∈ V₅₁}

V₁₄ = {A\|A → BC,	B ∈ V₁₁, C ∈ V₂₃;
	B ∈ V₁₂, C ∈ V₃₂;
	B ∈ V₁₃, C ∈ V₄₁}

V₂₄ = {A\|A → BC,	B ∈ V₂₁, C ∈ V₃₃;
	B ∈ V₂₂, C ∈ V₄₂;
	B ∈ V₂₃, C ∈ V₅₁}

V₁₅ = {A\|A → BC,	B ∈ V₁₁, C ∈ V₂₄;
	B ∈ V₁₂, C ∈ V₃₃;
	B ∈ V₁₃, C ∈ V₄₂;
	B ∈ V₁₄, C ∈ V₅₁}