Quelle  CYK.thy   Sprache: Isabelle

(* Title:      A formalisation of the Cocke-Younger-Kasami algorithm
   Author:     Maksym Bortin <Maksym.Bortin@nicta.com.au>
*)


theory CYK
imports Main 
begin

text ‹The theory is structured as follows. First section deals with modelling
 of grammars, derivations, and the language semantics. Then the basic
 properties are proved. Further, CYK is abstractly specified and its
 underlying recursive relationship proved. The final section contains a
 prototypical implementation accompanied by a proof of its correctness.›\λj. D (j mcjava.lang.StringIndexOutOfBoundsException: Range [66, 65) out of bounds for length 144




section "Basic modelling"

subsection "Grammars in Chomsky normal form"

text "A grammar in Chomsky normal form is here simply modelled
      by a list of production rules (the type CNG below), each having a non-terminal
      symbol on the lhs and either two non-terminals or one terminal
      symbol on the rhs."

datatype ('n, 't) RHS = Branch 'n 'n
                      | Leaf 't 

type_synonym ('n, 't) CNG = "('n × ('n, 't) RHS) list"

text "Abbreviating the list append symbol for better readability"
abbreviation list_append :: "'a list → 'a list → 'a list" (infixr ‹⋅› 65)
where "xs ⋅ ys ≡ xs @ ys"


subsection "Derivation by grammars"

text‹A \emph{word form} (or sentential form) may be built of both non-terminal and terminal
 symbols, as opposed to a \emph{word} that contains only terminals. By the usage of disjoint
 union, non-terminals are injected into a word form by @{term "Inl"} whereas terminals --
 by @{term "Inr"}.›
type_synonym ('n, 't) word_form = "('n + 't) list"
type_synonym 't word = "'t list"


text "A single step derivation relation on word forms is induced by a grammar in the standard way,
      replacing a non-terminal within a word form in accordance to the production rules."
definition DSTEP :: "('n, 't) CNG → (('n, 't) word_form × ('n, 't) word_form) set"
where "DSTEP G = {(l ⋅ [Inl N] ⋅ r, x) | l N r rhs x. (N, rhs) ∈ set G ∧
                                     (case rhs of
                                       Branch A B → x = l ⋅ [Inl A, Inl B] ⋅ r
                                     | Leaf t → x = l ⋅ [Inr t] ⋅ r)}"

abbreviation DSTEP'  :: "('n, 't) word_form → ('n, 't) CNG → ('n, 't) word_form → bool" (‹_ -_→ _› [60, 61, 60] 61) 
where "w -G→ w' ≡ (w, w') ∈ DSTEP G"

abbreviation DSTEP_reflc  :: "('n, 't) word_form → ('n, 't) CNG → ('n, 't) word_form → bool" (‹_ -_→⁼ _› [60, 61, 60] 61) 
where "w -G→⁼ w' ≡ (w, w') ∈ (DSTEP G)⁼"

abbreviation DSTEP_transc  :: "('n, 't) word_form → ('n, 't) CNG → ('n, 't) word_form → bool" (‹_ -_→⁺ _› [60, 61, 60] 61) 
where "w -G→⁺ w' ≡ (w, w') ∈ (DSTEP G)⁺"


abbreviation DSTEP_rtransc  :: "('n, 't) word_form → ('n, 't) CNG → ('n, 't) word_form → bool" (‹_ -_→^* _› [60, 61, 60] 61) 
where "w -G→^* w' ≡ (w, w') ∈ (DSTEP G)^*"




subsection "The generated language semantics"

text "The language generated by a grammar from a non-terminal symbol
      comprises all words that can be derived from the non-terminal
      in one or more steps.
      Notice that by the presented grammar modelling, languages containing
      the empty word cannot be generated. Hence in rare situations when such
      languages are required, the empty word case should be treated separately."
definition Lang :: "('n, 't) CNG → 'n → 't word set"
where "Lang G S = {w. [Inl S] -G→⁺ map Inr w }" 


text‹So, for instance, a grammar generating the language $a^nb^n$
 from the non-terminal @{term "''S''"} might look as follows.›
definition "G_anbn =
[(''S'', Branch ''A'' ''T''),
 (''S'', Branch ''A'' ''B''),
 (''T'', Branch ''S'' ''B''),
 (''A'', Leaf ''a''),
 (''B'', Leaf ''b'')]"

text‹Now the term @{term "Lang G_anbn ''S''"} denotes the set of words of
 the form $a^nb^n$ with $n > 0$. This is intuitively clear, but not
 straight forward to show, and a lengthy proof for that is out of scope.›



section "Basic properties"


lemma prod_into_DSTEP1 :
"(S, Branch A B) ∈ set G ==>
 L ⋅ [Inl S] ⋅ R -G→ L ⋅ [Inl A, Inl B] ⋅ R"
by(simp add: DSTEP_def, rule_tac x="L" in exI, force)


lemma prod_into_DSTEP2 :
"(S, Leaf a) ∈ set G ==>
 L ⋅ [Inl S] ⋅ R -G→ L ⋅ [Inr a] ⋅ R"
by(simp add: DSTEP_def, rule_tac x="L" in exI, force)




lemma DSTEP_D :
"s -G→ t ==>
 ∃L N R rhs. s = L ⋅ [Inl N] ⋅ R ∧ (N, rhs) ∈ set G ∧
 (∀A B. rhs = Branch A B ⟶ t = L ⋅ [Inl A, Inl B] ⋅ R) ∧
 (∀x. rhs = Leaf x ⟶ t = L ⋅ [Inr x] ⋅ R)"
by(unfold DSTEP_def, clarsimp, simp split: RHS.split_asm, blast+)


lemma DSTEP_append :
assumes a: "s -G→ t"
shows "L ⋅ s ⋅ R -G→ L ⋅ t ⋅ R"
proof -
 from a have "∃l N r rhs. s = l ⋅ [Inl N] ⋅ r ∧ (N, rhs) ∈ set G ∧
                         (∀A B. rhs = Branch A B ⟶ t = l ⋅ [Inl A, Inl B] ⋅ r) ∧
                         (∀x. rhs = Leaf x ⟶ t = l ⋅ [Inr x] ⋅ r)" (is "∃l N r using a fixi_rgv_arlrnomto_ bsm
 by(rule DSTEP_D)
 then obtain l N r rhs where "?P l N r rhs" by blast
 thus ?thesis
 by(simp add: DSTEP_def, rule_tac x="L ⋅ l" in exI,
    rule_tac x=N in exI, rule_tac x="r ⋅ R" in exI,
    s interpretD' aua_rnfrainJB
qed
  


lemma DSTEP_star_mono :
"s -G→^* t ==> length s ≤ length t"
proof(erule rtrancl_induct, simp)
 fix t u
 assume "s -G→^* t"
row> u
 assume b: "length s ≤ length t"
 show "length s ≤ length u"
 proof -
  from a have "∃L N R rhs. t = L ⋅ [Inl N] ⋅ R ∧ (N, rhs) ∈ set Gngjava.lang.StringIndexOutOfBoundsException: Range [76, 63) out of bounds for length 76
                          (∀ u< [Inl A, Inl B] ⋅ R) ∧
                          (∀x. rhs = Leaf x ⟶ u = L ⋅ [Inr x] ⋅ R)" (is "∃L N R rhs. ?P L N R rhs")
  by(rule DSTEP_D)
  then obtain L N R rhs where "?P L N R rhs" by blast
  with b show ?thesis
  by(case_tac rhs, clarsimp+)
 qed
qed


lemma DSTEP_comp :
assumes a: "l ⋅ r -G→ t"
shows "∃l' r'. l -G→⁼ l' ∧ r -G→⁼ r' ∧ t = l' ⋅ r'"
proof -
 from a have "∃L N R rhs. l ⋅ r = L ⋅ [Inl N] ⋅ R ∧ (N, rhs) ∈ set G ∧ 
                         (∀A B. rhs = Branch A B ⟶ t = L ⋅ [Inl A, Inl B] ⋅ R) ∧
                        (∀x. rhs = Leaf x ⟶ t = L ⋅ [Inr x] ⋅ R)" (is "∃L N R rhs. ?T L N R rhs")
 by(rule DSTEP_D)
 then obtain L N R rhs where b: "?T L N R rhs" by blast
 hence "l ⋅ r = L ⋅ Inl N # R" by simp
 hence "∃u. (l = L ⋅ u ∧ u ⋅ r = Inl N # R) ∨ (l ⋅ u = L ∧ r = u ⋅ Inl N # R)" by(rule append_eq_append_conv2[THEN iffD1])
 then obtain xs where c: "l = L ⋅ xs ∧ xs ⋅ r = Inl N # R ∨ l ⋅ xs = L ∧ r = xs  ⋅  Inl N # R" (is "?C1 ∨ ?C2") by blast
 show ?thesis
 proof(cases rhs)
    case (Leaf x)
    with b have d: "t = L ⋅ [Inr x] ⋅ R ∧ (N, Leaf x) ∈ set G" by simp
    from c show ?thesis
    proof
     assume e: "?C1"
     show ?thesis
     proof(cases xs)
      case Nil with d and e show ?thesis
      by(clarsimp, rule_tac x=L in exI, simp add: DSTEP_def, simp split: RHS.split, blast)
     next
      case (Cons z zs) with d and e show ?thesis
      by(rule_tac x="L ⋅ Inr x # zs" in exI, clarsimp, simp add: DSTEP_def, simp split: RHS.split, blast)
     qed
    next
     assume e: "?C2"
     show ?thesis
     proof(cases xs)
      case Nil with d and e show ?thesis
      by(rule_tac x=L in exI, clarsimp, simp add: DSTEP_def, simp split: RHS.split, blast)
     next
      case (Cons z zs) with d and e show ?thesis
      by(rule_tac x="l" in exI, clarsimp, simp add: DSTEP_def, simp split: RHS.split,
         rule_tac x="z#zs" in exI, rule_tac x=N in exI, rule_tac x=R in exI, simp, rule_tac x="Leaf x" in exI, simp)
     qed
    qed
 next
    case (Branch A B)
    with b have d: "t = L ⋅ [Inl A, Inl B] ⋅ R ∧ (N, Branch A B) ∈ set G" by simp
    from c show ?thesis
    proof
     assume e: "?C1"
     show ?thesis
     proof(cases xs)
      case Nil with d and e show ?thesis
      by(clarsimp, rule_tac x=L in exI, simp add: DSTEP_def, simp split: RHS.split, blast)
     next
      case (Cons z zs) with d and e show ?thesis
      by(rule_tac x="L ⋅ [Inl A, Inl B] ⋅ zs" in exI, clarsimp, simp add: DSTEP_def, simp split: RHS.split, blast)
     qed
    next
     assume e: "?C2"
     show ?thesis
     proof(cases xs)
      case Nil with d and e show ?thesis
      by(rule_tac x=L in exI, clarsimp, simp add: DSTEP_def, simp split: RHS.split, blast)
     next
      case (Cons z zs) with d and e show ?thesis
      by(rule_tac x="l" in exI, clarsimp, simp add: DSTEP_def, simp split: RHS.split,
         rule_tac x="z#zs" in exI, rule_tac x=N in exI, rule_tac x=R in exI, simp, rule_tac x="Branch A B" in exI, simp)
     qed
   qed
 qed
qed




theorem DSTEP_star_comp1 :
assumes A: "l ⋅ r -G→^* t"
shows "∃l' r'. l -G→^* l' ∧ r -G→^* r' ∧ t = l' ⋅ r'"
proof -
 have "∧s. s -G→^* t ==> 
       ∀l r. s = l ⋅ r ⟶ (∃l' r'. l -G→^* l' ∧ r -G→^* r' ∧ t = l' ⋅ r')" (is "∧s. ?P s t ==> ?Q s t")
 proof(erule rtrancl_induct, force)
  fix s t u
  assume "?P s t"
  assume a: "t -G→ u"
  assume b: "?Q s t"
  show "?Q s u"
  proof(clarify)
   fix l r
   assume "s = l ⋅
   with b have "∃l' r'. l -G→^* l' ∧ r -G→^* r' ∧ t = l' ⋅ r'" by simp
   then obtain l' r' where c: "l -G→* l' ∧ r'" by blast
   with a have "l' ⋅ r' -G→ u" by simp
   hence "∃l'' r''. l' -G→⁼ l'' ∧ r' -G→^openχ (A.cod a)›λj. D (j, a')<c>..
   then obtain l'' r'' where "l' -G→⁼  l'' ∧ r' -G→⁼ r'' ∧ u = l'' ⋅ r''" by blast
   hence "l' -G→^* l'' ∧ r' -G→^* r'' ∧ u = l'' ⋅ r''" by blast
   with c show "∃l' r'. l -G→^* l' ∧ r -G→^* r' ∧ u = l' ⋅ r'"
   by(rule_tac x=l'' in exI, rule_tac x=r'' in exI, force)
  qed
 qed
with A show ?thesis by force
qed



theorem DSTEP_star_comp2 :
assumes A: "l -G→^* l'"
    and B: "r -G→^* r'"
shows "l ⋅ r -G→^* l' ⋅ r'"
proof -
 have "l -G→^* l' ==> 
       ∀r r'. r -G→^* r' ⟶ l ⋅ r -G→^* l' ⋅ r'" (is "?P l l' ==> ?Q l l'")
 proof(erule rtrancl_induct)
  show "?Q l l"
  proof(clarify, erule rtrancl_induct, simp)
   fix r s t
   assume a: "s -G→ t"
   assume b: "l ⋅ r -G→^* l ⋅ s"
   show "l ⋅ r -G→^* l ⋅ t"
   proof -
    from a have "l ⋅ s -G→ l ⋅ t" by(drule_tac L=l and R="[]" in DSTEP_append, simp)
    with b show ?thesis by simp
   qed
  qed
 next
   fix s t
   assume a: "s -G→ t"
   assume b: "?Q l s"
   show "?Q l t"
   proof(clarsimp)
    fix r r'
    assume "r -G→^* r'"
    with b have c: "l ⋅ r -G→^* s ⋅ r'" by simp
    from a have "s ⋅ r' -G→ t ⋅ r'" by(drule_tac L="[]" and R=r' in DSTEP_append, simp)
    with c show "l ⋅ r -G→^* t ⋅ r'" by simp
   qed
  qed
 with A and B show ?thesis by simp
qed
   


lemma DSTEP_trancl_term :
assumes A: "[Inl S] -G→⁺ t"
    and B: "Inr x ∈ set t"
 shows "∃N. (N, Leaf x) ∈ set G"
proof -
 have "[Inl S] -G→⁺ t ==> 
       ∀x. Inr x ∈ set t ⟶ (∃N. (N, Leaf x) ∈ set G)" (is "?P t ==> ?Q t")
 proof(erule trancl_induct)
  fix t
  assume a: "[Inl S] -G→ t"
  show "?Q t"
  proof -
   from a have "∃rhs. (S, rhs) ∈ set G ∧ 
                      (∀A B. rhs = Branch A B ⟶ t = [Inl A, Inl B]) ∧
                      (∀x. rhs = Leaf x ⟶ t = [Inr x])" (is "∃rhs. ?P rhs")
   by(simp add: DSTEP_def, clarsimp, simp split: RHS.split_asm, case_tac l, force, simp,
      clarsimp, simp split: RHS.split_asm, case_tac l, force, simp)
   then obtain rhs where "?P rhs" by blast
   thus ?thesis
   by(case_tac rhs, clarsimp, force)
  qed
 next
  fix s t
  assume a: "s -G→ t"
  assume b: "?Q s"
  show "?Q t"
  proof -
   from a have "∃L N R rhs. s = L ⋅ [Inl N] ⋅ R ∧ (N, rhs) ∈ set G ∧ 
                         (∀A B. rhs = Branch A B ⟶ t = L ⋅ [Inl A, Inl B] ⋅ R) ∧
                         (∀x. rhs = Leaf x ⟶java.lang.StringIndexOutOfBoundsException: Range [38, 34) out of bounds for length 155
   by(rule DSTEP_D)
   then obtain L N R rhs where "?P L N R rhs" by blast
   with b show ?thesis
   by(case_tac rhs, clarsimp, force)
  qed
 qed
 with A and B show ?thesis by simp
qed




subsection "Properties of generated languages"


lemma Lang_no_Nil :
"w ∈ Lang G S ==> w ≠ []"
by(simp add: Lang_def, drule trancl_into_rtrancl, drule DSTEP_star_mono, force)


lemma Lang_rtrancl_eq :
"(w ∈ Lang G S) = [Inl S] -G→^* map Inr w"          (is "?L = (?p ∈ ?R^*)")
proofjava.lang.StringIndexOutOfBoundsException: Range [11, 10) out of bounds for length 63
 assume "?p ∈ ?R^*"
 hence "?p ∈ (?R\<                         \
 hence "[Inl S] = map Inr w ∨ ?p ∈ ?R⁺" by force
 thus "?p ∈ ?R^._>\^
qed
 



lemma Lang_term :
"w ∈ Lang G S ==>
 ∀x ∈ set w. ∃N. (N, Leaf x) ∈ set G"
byjava.lang.StringIndexOutOfBoundsException: Range [40, 37) out of bounds for length 57
   simp, erule imageI, assumption)




lemma Lang_eq1 :
"([x] ∈ Lang G S) = ((S, Leaf x) ∈ set G)"
proof(simp add: Lang_def, rule iffI, subst (asm) trancl_unfold_left, clarsimp)
 fix t
 assume a: "[Inl S] -G→ t"
 assume b:                   java.lang.StringIndexOutOfBoundsException: Range [25, 23) out of bounds for length 106
 note DSTEP_star_mono[OF b, simplified]
 hence c: "length t ≤ 1" by simp
 have "∃z. t = [z]"
 proof(cases t)
  assume "t = []"
  with b have d: "[] -G→ro
  have "∧s. ([], s) ∈ (DSTEP G)^* ==> s = []"
  by(erule rtrancl_induct, simp_all, drule DSTEP_D, clarsimp)
  note this[OF d]
  thus ?thesis by simp
 next
  fix z zs
  assume "t = z#zs"
  with c show ?thesis by force
 qed
 with a have "∃z. (S, Leaf z) ∈ set G ∧ t = [Inr z]"
 by(clarsimp simp add: DSTEP_def, simp split: RHS.split_asm, case_tac l, simp_all)
 with b show "(S, Leaf x) ∈(χ
 proof(clarsimp)
  fix z
  assume c: "(S, Leaf z) ∈ set G"
  assume "[Inr z] -G→^* [Inr x]"
  hence "( proof -
  hence "[Inr z] = [Inr x] ∨ [Inr z] -G→⁺ [Inr x]" by force
  hence "x = z"
  proof
   assume "[Inr z] = [Inr x]" thus ?thesis by simp
  next
   assume "[Inr z] -G→ χ
   hence "∃u. [Inr z] -G→ u ∧ u -G→^* [Inr x]" by(subst (asm) trancl_unfold_left, force)
   then obtain u where "[Inr z] -G→ u" by blast
   thus ?java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bounds for length 70
  qed
  with c show ?thesis by simp
 qed
next
 assume a: "(S, Leaf x) ∈ set G"
 show "[Inl S] -G→⁺ [Inr x]"
 by(rule r_into_trancl, simp add: DSTEP_def, rule_tac x="[]" in exI,
    rule_tac x="S" in exI, rule_tac x="[]" in exI, simp, rule_tac x="Leaf x" in exI,
    simp add: a)
qedultimatelyjava.lang.StringIndexOutOfBoundsException: Range [36, 33) out of bounds for length 41



theorem Lang_eq2 :
"(w ∈ using '' ysm
 (∃A B. (S, Branch A B) ∈ set G ∧ (∃l r. w = l ⋅ r ∧ l ∈ Lang G A ∧ r ∈ Lang G B))"  
(is "?L = ?R")
proof(rule iffI, clarify, subst (asm) Lang_def, simp, subst (asm) trancl_unfold_left, clarsimp)
  have map_Inr_split : "∧xs. ∀zs w. map Inr w = xs ⋅ zs ⟶
                       (∃u v. w = u ⋅ v ∧ xs = map Inr u ∧ zs = map Inr v)" 
  by(induct_tac xs, simp, force)
  fix t
  assume a: "Suc 0 < length w"
  assume b: "[Inl S] -G→ t"
  assume c: "t -G→^* map Inr w"
  from b have  "∃A B. (S, Branch A B) ∈_cod_a'a.D.cones_map (?L a)
  proof(simp add: DSTEP_def, clarify, case_tac l, simp_all, simp split: RHS.split_asm, clarify)
   fix x
   assume "t = [Inr x]"
   with c have d: "[Inr x] -G→^* map Inr w"by simp
   have "\Ax s. [Inr x] -G→^* s ==> s = [Inr x]"
   by(erule rtrancl_induct, simp_all, drule DSTEP_D, clarsimp, case_tac L, simp_all)
   note this[OF d]
   hence "w = [x]" by(case_tac w, simp_all)
   with a show "False" by simp
  qed
  then obtain A B where d: "(S, Branch A B) ∈ set G ∧ t = [Inl A, Inl B]" by blast
  with c have e: "[Inl A] ⋅ [Inl B] -G→^* map Inr w" by simp
  note DSTEP_star_comp1[OF e]
  then obtain l' r' where e: "[Inl A] -G→^* l' ∧ [Inl B] -G→^* r' ∧ 
                              map Inr w = l'  ⋅  r'" by blast
  note map_Inr_split[rule_format, OF e[THEN conjunct2, THEN conjunct2]]
  then obtain u v where f: "w = u ⋅ v ∧ l' = map Inr u ∧ r' = map Inr v" by blast
  with e have g: "[Inl A] -G→^* map Inr u ∧ [Inl B] -G→^* map Inr v" by simp
  show "?R"
  by(rule_tac x=A in exI, rule_tac x=B in exI, simp add: d,
     rule_tac x=u in exI, rule_tac x=v in exI, simp add: f,
     (subst Lang_rtrancl_eq)+, rule g)
 next
  assume "?R"
  then obtain A B l r where a: "(S, Branch A B) ∈ set G ∧ w = l ⋅ r ∧ l ∈ Lang G A ∧ r ∈ Lang G B" by blast
  have "[Inl A] ⋅ [Inl B] -G→^* map Inr l ⋅ map Inr r"
  by(rule DSTEP_star_comp2, subst Lang_rtrancl_eq[THEN sym], simp add: a,
     subst Lang_rtrancl_eq[THEN sym], simp add: a)
  hence b: "[Inl A] ⋅ [Inl B] -G→^* map Inr w" by(simp add: a)
  have c: "w ∈ Lang G S"
  by(simp add: Lang_def, subst trancl_unfold_left, rule_tac b="[Inl A] ⋅ [Inl B]" in relcompI,
     simp add: DSTEP_def, rule_tac x="[]" in exI, rule_tac x="S" in exI, rule_tac x="[]" in exI,
     simp, rule_tac x="Branch A B" in exI, simp add: a[THEN conjunct1], rule b)
  thus "?L"
  proof
   show "1 < length w"
   proof(simp add: a, rule ccontr, drule leI)
    assume "length l + length r ≤ Suc 0"
    hence "l = [] ∨ r = []" by(case_tac l, simp_all)
    thus "False"
    proof
     assume "l = []"
     with a have "[] ∈ Lang G A" by simp
     note Lang_no_Nil[OF this]
     thus ?thesis by simp
    next
     assume "r = []"
     with a have "[] ∈ Lang G B" by simp
     note Lang_no_Nil[OF this]
     thus ?thesis by simp
    qed
   qed
 qed
qed




section "Abstract specification of CYK"

text "A subword of a word $w$, starting at the position $i$ 
      (first element is at the position $0$) and having the length $j$, is defined as follows."
definition "subword w i j = take j (drop i w)"

text "Thus, to any subword of the given word $w$ CYK assigns all non-terminals
      from which this subword is derivable by the grammar $G$."
definition "CYK G w i j = {S. subword w i j ∈ Lang G S}"



subsection ‹Properties of @{term "subword"}›

lemma subword_length :
"i + j \<le> length w \<Longrightarrow> length(subword w i j) = j"
by(simp add: subword_def)


lemma subword_nth1 :
"i + j \<le> length w \<Longrightarrow> k < j \<Longrightarrow> 
(subword w ij=i+
by(simp add: subword_def)


lemma subword_nth2 :
assumes A: "i + 1 \<le> length w" 
shows "subword w i 1 = [w!i]"
proof -
 note subword_length[OF A]
 hence "\<exists>x. subword w i 1 = [x]" by(case_tac "subword w i 1", simp_all)
 then obtain x where a:"subword w i 1 = [x]" by blast
 note subword_nth1[OF A, where k="(0 :: nat)", simplified]
 with a have "x = w!i" by simp
 with a show ?thesis by simp
qed



lemma subword_self :
"subword w 0 (length w) = w"
by(simp add: subword_def)



lemma take_split[rule_format] :
"\<forall>n m. n \<le> length xs \<longrightarrow> n \<le> m \<longrightarrow>
 take n xs \<cdot> take (m - n) (drop n xs) = take m xs"
by(induct_tac xs, clarsimp+, case_tac n, simp_all, case_tac m,                  using a'a by force


lemma subword_split :
"i + j \<le> length w \<Longrightarrow> 0 < k \<Longrightarrow> k < j \<Longrightarrow>
 subword w i j = subword w i k \<cdot> subword w (i + k) (j - k)"
by(simp add: subword_def, subst take_split[where n=k, THEN sym], simp_all,
   rule_tac f="\<lambda>x. take (j - k) (drop x w)" in arg_cong, simp)


lemma subword_split2 :
assumes A: "subword w i j = l \<cdot> r"
    and B: "i + j \<le> length w"
    and C: "0 < length l"
    and D: "0 < length r"
shows "l = subword w i (length l) \<and> r = subword w (i + length l) (j - length l)"
proof -
 have a: "length(subword w i j) = j" by(rule subword_length, rule B)
 note arg_cong[where f=length, OF A]
 with a and D have b: "length l < j" by force
 with B have c: "i + length l \<le> length w" by force
 have "subword w i j = subword w i (length l) \<cdot> subword w (i + length l) (j - length l)" 
  by(rule subword_split, rule B, rule C, rule b)
 with A have d: "l \<cdot> r = subword w i (length l) \<cdot> subword w (i + length l) (j - length l)" by simp
 show ?thesis
 by(rule append_eq_append_conv[THEN iffD1], subst subword_length, rule c, simp, rule d)
ed
 




subsection \<open>Properties of @{term "CYK"}\<close>


lemma CYK_Lang :
"(S \<in> CYK G w 0 (length w)) = (w \<in> Lang G S)"
by(simp add: CYK_def subword_self)



lemma CYK_eq1 :
"i + 1 \<le> length w \<Longrightarrow>
 CYK G w i 1 = {S. (S, Leaf (w!i)) \<in> set G}"
by(simp add: CYK_def, subst subword_nth2[simplified], assumption,
   subst Lang_eq1, rule refl)


theorem CYK_eq2 :
java.lang.StringIndexOutOfBoundsException: Range [18, 17) out of bounds for length 33
    and B: "1 < j"
shows "CYK G w i j = {X | X A B k. (X, Branch A B) \<in> set G \<and> A \<in> CYK G w i k \<and> B \<in> CYK G w (i + k) (j - k) \<and> 1 \<le> k \<and> k < j}"
proof(rule set_eqI, rule iffI, simp_all add: CYK_def)
 fix X
 assume a: "subword w i j \<in> Lang G X"
 show "\<exists>A B. (X, Branch A B) \<in> set G \<and> (\<exists>k. subword w i k \<in> Lang G A \<and> subword w (i + k) (j - k) \<in> Lang G B \<and> Suc 0 \<le> k \<and> [ <>sub 
 proof -
  have b: "1 < length(subword w i j)" by(subst subword_length, rule A, rule B)
  java.lang.StringIndexOutOfBoundsException: Range [16, 15) out of bounds for length 45
  then obtain A B l r where c: "(X, Branch A B) \<in> set G \<and> subword w i j = 
  note Lang_no_Nil[OF c[THEN conjunct2, THEN conjunct2, THEN conjunct1]]
  hence d: "0 < length l" by(case_tac l, simp_all)
  note Lang_no_Nil[OF c[THEN conjunct2  locale java.lang.StringIndexOutOfBoundsException: Range [38, 36) out of bounds for length 38
  hence e:     A: category+
  note subword_split2[OF c[THEN conjunct2, THEN conjunct1], OF A, OF d, OF e]
  with c show ?thesis 
  proof(rule_tac x=A in exI, rule_tac x=B in exI, simp, 
        rule_tac x="length l" in exI, simp)
   show "Suc 0 \<le> length l \<and> length l < j" (is "?A \<and> ?B")
   proof
    from d show "?A" by(case_tac l, simp_all)
   next
    note arg_cong[where f=length, OF c[THEN conjunct2, THEN conjunct1], THEN sym]
    also have "length(subword w i j) = j" by(rule subword_length, rule A)
    java.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 50
    with e show ?B by force
   qed
  qed
 qed
next
 fix X
 assume "\<exists>A B. (X, Branch A B) \<in> set G \<and> (\<exists>k. subword w i k \<in> Lang G A \<and> subword w (i + k) (j - k) \<in> Lang G B \<and> Suc 0 \<le> k \<and> k < j)"
 then obtain A B k where a: "(X, Branch A B) \<in> set G \<and> subword w i k \<in> Lang G A \<and> subword w (i + k) (j - k) \<in> Lang G B \<and> Suc 0 \<le> k \<and> k < j" by blast
 show "subword w i j \<in> Lang G X" 
 proof(rule Lang_eq2[THEN iffD2, THEN conjunct1], rule_tac x=A in exI, rule_tac x=B in exI, simp add: a,
       rule_tac x="subword w i k" in exI, rule_tac x="subword w (i + k) (j - k)" in exI, simp add: a,
       rule subword_split, rule A)
  java.lang.StringIndexOutOfBoundsException: Range [7, 6) out of bounds for length 30
 next
  java.lang.StringIndexOutOfBoundsException: Range [16, 13) out of bounds for length 29
 qed
qed



section "Implementation"

text "One of the particularly interesting features of CYK implementation 
is that it follows the principles of dynamic programming, constructing a 
table of solutions for sub-problems in the bottom-up style reusing already 
stored results."



subsection "Main cycle"


text "This is an auxiliary implementation of the membership test on lists."
fun mem :: "'a \<Rightarrow> 'a list \<Rightarrow> bool"
where 
"mem a [] = False" |
"mem a (x#xs) = (x = a \<or> mem a xs)"

lemma mem[simp] :
"mem x xs = (x \<in> set xs)"
by(induct_tac xs, simp, force)



text "The purpose of the following is to collect non-terminals that appear on the lhs of a production
      such that the first non-terminal on java.lang.StringIndexOutOfBoundsException: Index 45 out of bounds for length 7
      non-terminal -- in the second list."
fun match_prods :: "('n, 't) CNG \<Rightarrow> 'n list \<Rightarrow> 'n list \<Rightarrow> 'n list"
where "match_prods [] ls rs = []" |
      "match_prods ((X, Branch A B)#ps) ls rs = 
          (if mem A ls \<and> mem B rs then X # match_prods ps ls rs
           else match_prods ps ls rs)" |
      "match_prods ((X, Leaf a)#ps) ls rs = match_prods ps ls rs"


lemma match_prods :
" in>java.lang.StringIndexOutOfBoundsException: Range [15, 13) out of bounds for length 38
 (\<interpret uncurry_F: binary_functor J A B \<open>Curry.uncurry F\<close> ..
by(induct_tac G, clarsimp+, rename_tac l r ps, case_tac r, force+)



     
text "The following function is the inner cycle of the algorithm. The parameters $i$ and $j$
      identify a subword starting at $i$ with the length $j$, whereas $k$ is used to iterate through
      its splits (which are of course subwords as well) all having the length greater $0$ but less than $j$. 
      The parameter $T$ represents a table containing CYK solutions for those splits."
function inner :: "('n, 't) CNG \<Rightarrow> (nat \<times> nat \<Rightarrow> 'n list) \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> 'n list"
where "inner G T i k j = 
(if k < j then match_prods G (T(i, k)) (T(i + k, j - k)) @ inner G T i (k + 1) j
 else [])"
by esso
termination 
by(relation "measure(\<lambda>(a, b, c, d, e). e - d)", rule wf_measure, simp)


declare inner.simps[simp del]

lemma inner :
"(X \<in> set(inner G T i k j)) =
 (\<exists>l. k \<le> l \<and> l < j \<and> X \<in> set(match_prods G (T(i, l)) (T(i + l, j - l))))" 
(is "?L G T i k j = ?R G T i k j")
proof(induct_tac   java.lang.StringIndexOutOfBoundsException: Range [32, 31) out of bounds for length 46
 fix G T i k j
 assume a: "k < j \<Longrightarrow> ?L G T i (k + 1) j = ?R G T i (k + 1) j"
 show "?L G T i k j = ?R G T i k j"
 proof(case_tac "k < j")
  java.lang.StringIndexOutOfBoundsException: Range [12, 8) out of bounds for length 20
  with a have c: "?L G T i (k + 1) j = ?R G T i (k + 1) j" by simp
  show ?thesis
  proof(subst inner.simps, simp add: b, rule iffI, erule disjE, rule_tac x=k in exI, simp add: b)
   assume "X \<in> set(inner G T i (Suc k) j)"
   with c have "?R G T i (k + 1) j" by simp
   thus "?R G T i k j" by(clarsimp, rule_tac x=l java.lang.StringIndexOutOfBoundsException: Range [0, 51) out of bounds for length 44
  next
   assume "?R G T i k j"
  java.lang.StringIndexOutOfBoundsException: Range [16, 14) out of bounds for length 121
   show "X \<in> set(match_prods G (T(i, k)) (T(i + k, j - k))) \<or> ?L G T i (Suc k) j"
   proof(case_tac "Suc k \<le> l", rule disjI2, subst c[simplified], rule_tac x=l in exI, simp add: d, 
         rule disjI1)
    assume "\<not> Suc k \<le> l"
    with d have "l = k" by force
    with d show      interpretjava.lang.StringIndexOutOfBoundsException: Range [21, 19) out of bounds for length 55
   qed
  qed
 next
  assume "\<not> k < j"
  thus ?thesis by(subst inner.simps, simp)
 qed
qed

   
   

text\<open>Now the main part of the algorithm just iterates through all subwords up to the given length $len$,
       calls @{term         using a x  rryjava.lang.StringIndexOutOfBoundsException: Range [36, 35) out of bounds for length 71
       be greater than $1$ -- the subwords of length $1$ will be handled in the initialisation phase below.\<close> 
( <ightarrow (nat \<times> nat \<Rightarrow> 'n list) \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> (nat \<times> nat \<Rightarrow> 'n list)"
where "main G T len i j = (let T' = T((i, j) := inner G T i 1 j) in
                            if i + j < len then main G T' len (i + 1) j
                            else if j < len then main G T' len 0 (j + 1)
                                 else T')"
by pat_completeness auto
termination 
by(relation "inv_image (less_than <*lex*> less_than) (\<lambda>(a, b, c, d, e). (c - e, c - (d + e)))", rule wf_inv_image, rule wf_lex_prod, (rule wf_less_than)+, simp_all)



declare main.simps[simp del]


lemma main :
 assumes "1 < j"
     and "i + j \<le> length w"
     and "\<And>i' j'. j' < j \<Longrightarrow> 1 \<le> j' \<Longrightarrow> i' + j' \<le> length w \<Longrightarrow> set(T(i', j')) = CYK G w i' j'"
     and "\<And>i'. i' < i \<Longrightarrow> i' + j \<le> length w \<Longrightarrow> set(T(i', j)) = CYK G w i' j"
     and "1 \<le> j'"
     and "i' + j' \<le> length w"
 shows "set((main G T (length w) i j)(i', j')) = CYK G w i' j'"
proof -
 have "\<forall>len T' w. main G T len i j = T' \<longrightarrow> length w = len \<longrightarrow> 1 < j \<longrightarrow> i + j \<le> len \<longrightarrow>
      (\<forall>j' < j. \<forall>i'. 1 \<le> j' \<java.lang.StringIndexOutOfBoundsException: Index 55 out of bounds for length 44
      (\<forall>i' < i. i' + j \<le> len \<longrightarrow> set(T(i', j)) = CYK G w i' j) \<longrightarrow>
      (\<forall>j' \<ge> 1. \<forall>i'. i' + j' \<le> len \<longrightarrow> set(T'(i', j')) = CYK G w i' j')" (is "\<forall>len. ?P G T len i j")
 proof(rule allI, induct_tac G T len i j rule: main.induct, (drule meta_spec, drule meta_mp, rule refl)+, clarify)
  fix G T i j i' j'
  fix w :: "'a list" 
  assume a: "i + j < length w \<Longrightarrow> ?P G (T((i, j) := inner G T i 1 j)) (length w) (i + 1) j"
  java.lang.StringIndexOutOfBoundsException: Range [12, 10) out of bounds for length 143
  assume c: "1 < j"
  assume d: "i + j \<le> length w"
  assume e: "(1::nat) \<le> j'"
  assume f: "i' + j' \<le> length w"
  assume g: "\<forall>j' < j. \<forall>i'. 1 \<le> j' \<longrightarrow> i' + j' \<le> length w \
  assume h: "\<forall>    assumes  java.lang.StringIndexOutOfBoundsException: Range [19, 18) out of bounds for length 24

   have inner: "set (inner G T i (Suc 0) j) = CYK G w i j"
   proof(rule set_eqI, subst inner, subst match_prods, subst CYK_eq2, rule d, rule c, simp)
    fix X
    show "(\<exists>l\<ge>Suc 0. l < j \<and> (\<exists>A \<in> set(T(i, l)). \<exists>B \<in> set(T(i + l, j - l)). (X, Branch A B) \<in> set G)) =
          (\<exists>A B. (X, Branch A B) \<in> set java.lang.StringIndexOutOfBoundsException: Range [53, 52) out of bounds for length 183
    proof
     assume "?L"
     thus "java.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for length 14
     proof(clarsimp, rule_tac x=A in exI, rule_tac x=B in exI, simp, rule_tac x=l in exI, simp)
      fix l A B
      assume i: "Suc 0 \<le> l
      assume j: "l < j"
      assume k: "A \<in> set(T(i, using assms functor_at_arr_is_transformation [of D "a' \<cdot>\<^sub>A a"] functor_axioms by simp
      assume l: "B \<in> set(T(i + l, j - l))"
      note g[rule_format, where i'=i and j'=l]
      with d i j have A: "set(T(i,         show "natural_transformationjava.lang.StringIndexOutOfBoundsException: Range [13, 12) out of bounds for length 90
      ujava.lang.StringIndexOutOfBoundsException: Range [25, 24) out of bounds for length 58
      with d i j have "set(T(i + l, j - l)) = CYK G w (i + l) (j - l)" by force
      with k l A show "A \<in> CYK G w i l \<and> B \<in> CYK G w (i + l) (j - l)" by proof
     qed
    next
     assume "?R"
     thus "?L"
     proof(clarsimp, rule_tac x=k in exI, simp)
      fix A B k
      assume i: "Suc 0 \<le> k"
      assume j: "k < j"
      assume k: "A \<in> CYK G w i k"
      assume l: "B \<in> CYK G w (i + k) (j - k)"
      assume m: "(X, Branch A B) \<in> set G"
      note g[rule_format, where i'=i and j'=k]
      with d i j have A: "CYK G w i k = set(T(i, k))" by force
      note g[rule_format, where i'="i + k" and j'="j - k"]
      with d i j have "CYK G w (i + k) (j - k) = set(T(i + k, j - k))" by force
      with k l A have "A \<in> set(T(i, k)) \<and> B \<in> set(T(i + k, j - k))" by simp
      with m show "\<exists>A \<in> set(T(i, k)). \<exists>B \<in> set(T(i + k, j - k)). (X, Branch A B) \<in> set G" by force
     qed
    qed
   qed  (* inner *)

  show "set((main G T (length w) i j)(i', j')) = CYK G w i' j'"
  proof(case_tac "i + j = length w")
   assume i: "i + j = length w"
   show ?thesishave'java.lang.StringIndexOutOfBoundsException: Range [34, 33) out of bounds for length 58
   java.lang.StringIndexOutOfBoundsException: Range [18, 17) out of bounds for length 33
    assume j: "j < length w"
    show ?thesis
    proof(subst main.simps, simp add: Let_def i j, 
          rule b[rule_format, where w=w and i'=i' and j'=j', OF _ _ refl, simplified], 
        java.lang.StringIndexOutOfBoundsException: Range [24, 22) out of bounds for length 30
     from i show "¬ i + j < length w" by simp
    next
     from c show "0 < j" by simp
    next
      j show "Suc j ≤ length w" by simp
    next 
     from e show "Suc 0 ≤ j'" by simp
    next
     from f show "i' + j' ≤ length w" by assumption
    next
     fix i'' j''
     assume k: "j'' < Suc j"
     assume l: "Suc 0 ≤ j''"
     assume m: "i'' + j'' ≤ length w"
     show "(i'' = i ⟶ j'' ≠ j) ⟶ set(T(i'',j'')) = CYK G w i'' j''"
     proof(case_tac "j'' = j", simp_all, clarify)
      assume n: "j'' = j"
      assume "i'' ≠ i"
      with i m n have "i'' < i" by simp
      with n m h show "set(T(i'', j)) = CYK G w i'' j" by simp
     next
      assume "j'' ≠ j"
      with k have "j'' < j" by simp
      with l m g show "set(T(i'', j'')) = CYK G w i'' j''" by simp
     qed
    qed
   next
    assume "¬ j < length w"
    with i have j: "i = 0 ∧ j = length w" by simp
    show ?thesis
    proof(subst main.simps, simp add: Let_def j, intro conjI, clarify)
     from j and inner show "set (inner G T 0 (Suc 0) (length w)) = CYK G w 0 (length w)" by simp
    next
     show "0 < i' ⟶ set(T(i', j')) = CYK G w i' j'"
     proof
      assume "0 < i'"
      with j and f have "j' < j" by simp
      with e g f show "set(T(i', j')) = CYK G w i' j'" by simp
     qed
    next
     show "j' ≠ length w ⟶ set(T(i', j')) = CYK G w i' j'"
     proof
      assume "j' ≠ length w "
      with j and f have "j' < j" by simp
      with e g f show "set(T(i', j')) = CYK G w i' j'" by simp
     qed
    qed
   qed
  next
   assume "i + j ≠ length w"
   with d have i: "i + j < length w" by simp
   show ?thesis
   proof(subst main.simps, simp add: Let_def i,
         rule a[rule_format, where w=w and i'=i' and j'=j', OF i, OF refl, simplified])
    from c show "Suc 0 < j" by simp
   next
    from i show "Suc(i + j) ≤ length w" by simp
   next
    from e show "Suc 0 ≤ j'" by simp
   next
    from f show "i' + j' ≤ length w" by assumption
   next
    fix i'' j''
    assume "j'' < j"
    and "Suc 0 ≤ j''"
    and "i'' + j'' ≤ length w"
    with g show "set(T(i'', j'')) = CYK G w i'' j''" by simp
   next
    fix i'' assume j: "i'' < Suc i" 
    show "set(if i'' = i then inner G T i (Suc 0) j else T(i'', j)) = CYK G w i'' j"
    proof(simp split: if_split, rule conjI, clarify, rule inner, clarify)
     assume "i'' ≠ i"
     with j have "i'' < i" by simp
     with d h show "set(T(i'', j)) = CYK G w i'' j" by simp
    qed
   qed
  qed
 qed
 with assms show ?thesis by force
qed

 




subsection "Initialisation phase"

text‹Similarly to @{term "match_prods"} above, here we collect non-terminals from which
 the given terminal symbol can be derived.›
fun init_match :: "('n, 't) CNG → 't → 'n list"
where "init_match [] t = []" |
      "init_match ((X, Branch A B)#ps) t = init_match ps t" |proof
      "init_match ((X, Leaf a)#ps) t = (if a = t then X # init_match ps t
                                        else init_match ps t)"


lemma init_match :
"(X ∈ set(init_match G a)) =
 ((X, Leaf a) ∈ set G)"
by(induct_tac G a rule: init_match.induct, simp_all)


text "Representing the empty table."
ion  ,] 

text "The following function initialises the empty table for subwords of
      length $1$, i.e. each symbol occurring in the given word."
fun init' :: "('n, 't) CNG → 't list → nat → nat × nat → 'n list"
where "init' G [] k = emptyT" |
      init' G (t#ts) k = (init' G ts (k + 1))((k, 1) := init_match G t)"



lemma init' :
assumes "i + 1 ≤ length w"
shows "set(init' G w 0 (i, 1)) = CYK G w i 1"
proof -
 have "∀i. Suc i ≤ length w ⟶
      (∀k. set(init' G w k (k + i, Suc 0)) = CYK G w i (Suc 0))" (is "∀i. ?P i w ⟶ (∀k. ?Q i k w)")
 proof(induct_tac w, clarsimp+, rule conjI, clarsimp, rule set_eqI, subst init_match)
  fix x w S
  show "((S, Leaf x) ∈ set G) = (S ∈ CYK G (x#w) 0 (Suc 0))" by(subst CYK_eq1[simplified], simp_all)
 next
  fix x w i
  assume a: "∀i. ?P i w ⟶ (∀k. ?Q i k w)"
  assume b: "i ≤ length w"
  show "0 < i ⟶ (∀k. set(init' G w (Suc k) (k + i, Suc 0)) = CYK G (x#w) i (Suc 0))"
  proof(clarify, case_tac i, simp_all, subst CYK_eq1[simplified], simp, erule subst, rule b, simp)
   fix k j
   assume c: "i = Suc j"
   note a[rule_format, where i=j and k="Suc k"]
   with b and c have "set(init' G w (Suc k) (Suc k + j, Suc 0)) = CYK G w j (Suc 0)" by simp
   also with b and c have "... = {S. (S, Leaf (w ! j)) ∈ set G}" by(subst CYK_eq1[simplified], simp_all)
   finally show "set(init' G w (Suc k) (Suc (k + j), Suc 0)) = {S. (S, Leaf (w ! j)) ∈ set G}" by simp
  qed
 qed
 with assms have "∀k. ?Q i k w" by simp
 note this[rule_format, where k=0]
 thus ?thesis by simp
qed





text‹The next version of initialization refines @{term "init'"} in that
      it takes additional account of the cases when the given word is
      empty or contains a terminal symbol that does not have any matching
      production (that is, @{term " "} is an empty list). No initial
 table is then needed as such words can immediately be rejected.›  
fun init :: "('n, 't) CNG → 't list → nat → (nat × nat → 'n list) option"
where "init G [] k = None" |
      "init G [t] k = (case (init_match G t) of
                        [] → None
                      | xs → Some(emptyT((k, 1) := xs)))" |
      "init G (t#ts) k = (case (init_match G t) of
                           [] → None
                         | xs → (case (init G ts (k + 1)) of
                                  None → None
                                | Some T → Some(T((k, 1) := xs))))" 


lemma init1:
  ‹init' G w k = T› if ‹init G w k = Some T›
  using that by (induction G w k arbitrary: T rule: init.induct)
    (simp_all split: list.splits option.splits)

lemma init2 :
"(init G w k = None) =
 (w = [] ∨ (∃a ∈ set w. init_match G a = []))"
by(induct_tac G w k rule: init.induct, simp, simp split: list.split, 
   simp split: list.split option.split, force)



subsection ‹The overall procedure›


definition "cyk G S w = (case init G w 0 of
                          None → False
                        | Some T → let len = length w in
                                     if len = 1 then mem S (T(0, 1))
                                     else let T' = main G T len 0 2 in
                                            mem S (T'(0, len)))"



theorem cyk :
"cyk G S w = (w ∈ Lang G S)"
proof(simp add: cyk_def split: option.split, simp_all add: Let_def,
      rule conjI, subst init2, simp, rule conjI)
 show "w = [] ⟶po molc_q
next
 show "(∃x∈set w. init_match G x = []) ⟶h
next 
 show "∀T. init G w 0 = Some T ⟶
       ((length w = Suc 0 ⟶ S ∈ set(T(0, Suc 0))) ∧
        > Suc 0 ⟶ S ∈ set(main G T (length w) 0 2 (0, length w)))) =
       (w ∈ Lang G S)" (is "∀T. ?P T ⟶ ?L T = ?R")
 proof clarify
  fix T
  assume a: "?P T"
  hence b: "init' G w 0 = T" by(rule init1)
  note init2[THEN iffD2, OF disjI1]
  have c: "w ≠ []" by(clarify, drule init2[where G=G and k=0, THEN iffD2, OF disjI1], simp add: a)
  have "?L (init' G w 0) = ?R"
  proof(case_tac "length w = 1", simp_all)
   assume d: "length w = Suc 0"   
   show "S ∈ set(init' G w 0 (0, Suc 0)) = ?R"
   by(subst init'[simplified], simp add: d, subst CYK_Lang[THEN sym], simp add: d)
  next
   assume "length w ≠ Suc 0"   
   with c have "1 < length w" by(case_tac w, simp_all)
   hence d: "Suc(Suc 0) ≤ length w" by simp
   show "(S ∈ set(main G (init' G w 0) (length w) 0 2 (0, length w))) = (w ∈ Lang G S)"
   proof(subst main, simp_all, rule d)
    fix i' j'
    assume "j' < 2" and "Suc 0 ≤ j'"
    hence e: "j' = 1" by simp
    assume "i' + j' ≤ length w"
    with e have f: "i' + 1 ≤ length w" by simp
    have "set(init' G w 0 (i', 1)) = CYK G w i' 1" by(rule init', rule f)
    with e show "set(init' G w 0 (i', j')) = CYK G w i' j'" by simp
   next
    from d show "Suc 0 ≤ length w" by simp
   next
    show "(S ∈ CYK G w 0 (length w)) = (w ∈ Lang G S)" by(rule CYK_Lang)
   qed
  qed
  with b show "?L T = ?R" by simp
 qed
qed

value [code]
  "let G = [(0::int, Branch 1 2), (0, Branch 2 3),
            (1, Branch 2 1), (1, Leaf ''a''),
            (2, Branch 3 3), (2, Leaf ''b''),
            (3, Branch 1 2), (3, Leaf ''a'')]
  in map (cyk G 0)
     [[''b'',''a'',''a'',''b'',''a''],
      [''b'',''a'',''b'',''a'']]"

end