Quellcode-Bibliothek SmallStep.thy

(*
    Author:      Norbert Schirmer
    Maintainer:  Norbert Schirmer, norbert.schirmer at web de

Copyright (C) 2006-2008 Norbert Schirmer
*)

section ‹Small-Step Semantics and Infinite Computations›

theory SmallStep imports Termination
begin

text ‹The redex of a statement is the substatement, which is actually altered
  the next step in the small-step semantics.
 ›

primrec redex:: "('s,'p,'f)com ==> ('s,'p,'f)com"
where
"redex Skip = Skip" |
"redex (Basic f) = (Basic f)" |
"redex (Spec r) = (Spec r)" |
"redex (Seq c₁ c₂) = redex c₁" |
"redex (Cond b c₁ c₂) = (Cond b c₁ c₂)" |
"redex (While b c) = (While b c)" |
"redex (Call p) = (Call p)" |
"redex (DynCom d) = (DynCom d)" |
"redex (Guard f b c) = (Guard f b c)" |
"redex (Throw) = Throw" |
"redex (Catch c₁ c₂) = redex c₁"


subsection ‹Small-Step Computation: ‹Γ⊨(c, s) → (c', s')››

type_synonym ('s,'p,'f) config = "('s,'p,'f)com × ('s,'f) xstate"
inductive "step"::"[('s,'p,'f) body,('s,'p,'f) config,('s,'p,'f) config] ==> bool"
                                (‹_⊨ (_ →/ _)› [81,81,81] 100)
  for Γ::"('s,'p,'f) body"
where

  Basic: "Γ⊨(Basic f,Normal s) → (Skip,Normal (f s))"

| Spec: "(s,t) ∈ r ==> Γ⊨(Spec r,Normal s) → (Skip,Normal t)"
| SpecStuck: "∀t. (s,t) ∉ r ==> Γ⊨(Spec r,Normal s) → (Skip,Stuck)"

| Guard: "s∈g ==> Γ⊨(Guard f g c,Normal s) → (c,Normal s)"

| GuardFault: "s∉g ==> Γ⊨(Guard f g c,Normal s) → (Skip,Fault f)"


| Seq: "Γ⊨(c₁,s) → (c₁',s')
        ==>
        Γ⊨(Seq c₁ c₂,s) → (Seq c₁' c₂, s')"
| SeqSkip: "Γ⊨(Seq Skip c₂,s) → (c₂, s)"
| SeqThrow: "Γ⊨(Seq Throw c₂,Normal s) → (Throw, Normal s)"

| CondTrue: "s∈b ==> Γ⊨(Cond b c₁ c₂,Normal s) → (c₁,Normal s)"
java.lang.NullPointerException

| WhileTrue: "[s∈aeb e
              ==>
              Γ⊨C) 2006-2008 No-200 Norbert Sc Schirmer

| WhileFalse: "
               ==>
               <Gamma>\<>( (Skip,Normal s)"

|
         \<>\,N s)"

| CallUndefined: by the next step in the small-step semantics.
         Γ⊨(Call p,Normal s) → (Skip,Stuck)"

java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

java.lang.NullPointerException
          >
          Γ1 c (Catch c₂,s')"

| CatchThrow⊨ Throw c\<^>22,Normal s)"
| CatchSkip: "Γ⊨(Catch Skip ‹Γ⊨ (c', s')›

| FaultProp:java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
| StuckProp:  "[c≠Skip; redex c = c] ==> Γ⊨(c,Stuck) → (Skip,Stuck)"
| AbruptProp: "[c≠Skip; redex c = c] body,('s'p,') config,(s,'p,') con] <Rightarrbool"


lemmas step_induct = step.induct [of _ "(c,s)" "(c',s')", split_format (complete), case_names
Basic Spec SpecStuck Guard GuardFault Seq SeqSkip SeqThrow CondTrue CondFalse
WhileTrue WhileFalse Call CallUndefined DynCom Catch CatchThrow CatchSkip
FaultProp(‹


  step_elim_cases [cases set]:
 "Γ⊨(Skip,s) → u"
 "Γ⊨(Guard f g c,s) → u"
 "Γ⊨(Basic f,s) → u"
 "Γ⊨(Spec r,s) → u"
 "Γ⊨(Seq c1 c2,s) → u"
 "Γ⊨(Cond b c1 c2,s) →
 tile>(Wh b c,s) →
 "Γ⊨(Call p,s) → u"
 "Γ⊨st) ∈ t)
 "Γ⊨(Throw,s) → u"
 "Γ⊨(Catch c1 c2,s) → u"

  step_Normal_elim_cases [cases set]:
 "Γ⊨(Skip,Normal s) → u"
 "Γ⊨>t. (s,) \notin r ==> s →
 "Γ⊨(Basic f,Normal s) → u"
 "Γ⊨(Spec r,Normal s) → u"
 "Γ⊨(Seq c1 c2,Normal s) → u"
 "Γ⊨(Cond b c1 c2,Normal s) → u"
 "\<><
 "Γ⊨(Call p,Normal s) → u"
 "Γ⊨(DynCom c,Normal s) → u"
 "Γ⊨(Throw,Normal s) →
 "G>⊨


  ‹The final configuration is either of the form ‹(Skip,_)› for normal
 ,, or @{term "(Throw,Norm s)"} cas t programwas started in
  @{term "Normal"} state and terminated abruptly. The @{const "Abrupt"} state is not used to
  abrupt termination, in contrast to the big-step semantics. Only if the
  starts in an @{const "Abrupt"} states it ends in the same @{term "Abrupt"}
 .›

  final:: "('s,'p,'f) config ==> bool" where
 ip \> cfg=Throw∧


 
 "step_rtrancl" :: "[('s,'p,'f) body,('s,'p,'f) config,('s,'p,'f) config] ==> bool"
java.lang.NullPointerException
 where
 "Γ⊨cf0 →^* cf1 ≡ (CONST step Γ)^** cf0 cf1"
 
 "step_trancl" :: "[('s,'p,'f) body,('s,'p,'f) config,('s,'p,'f) config] ==> bool"
 (‹
 where
 "Γ⊨cf0 →⁺ cf1 ≡ (CONST step Γ)⁺⁺ cf0 cf1"








(* ************************************************************************ *)
subsection Small
(* ************************************************************************ *)

lemma redex_not_Seq: "redex c = Seq c1 c2 ==> P"
  apply (induct c)
  apply auto
  done:  ""<>b <Longrightarrow<> 

lemma no_step_final:
  assumes step: "Γ⊨(c,s) → (c',s')"
  shows "final (c,s) ==> P"
using step
by induct (auto simp add: final_def)

lemma no_step_final':
  assumes step: "Γ⊨cfg → cfg'"
  shows "final cfg ==> P"
using step
  by (cases cfg, cases cfg') (auto intro: no_step_final)

lemma step_Abrupt:
  assumes step: "Γ⊨ (c, s) →L> Γ<>2,No s) \rightarrow(c\^>,No s)
  shows "∧x. s=Abrupt x ==> s'=Abrupt x"
using step
by (induct) auto

lemma step_Fault:
  assumes step: "Γ⊨ (c, s) → (c', s')"
  shows "∧f. s=Fault f ==> s'=Fault f"
using step
by (induct) auto

lemma step_Stuck:
  assumes step: "Γ⊨ (c, s) → (c', s')"
  shows "∧f. s=Stuck ==> s'=Stuck"
using step
by (induct) auto

lemma SeqSteps:
  assumes steps: "Γ⊨cfg₁→^* cfg₂"
  shows "∧ c₁ s cjava.lang.NullPointerException
          <ongrightarrow<><(Seq^sub c<subs)\rightarrowsup<^ub>,s'"
using steps
proof (induct rule: converse_rtranclp_induct [case_names Refl Trans])
  case Refl
  thus ?case
    by simp
next
  case (Trans cfg₁ cfg'')
  have step: "Γ⊨ cfg₁ → cfg''" by fact
  have steps: "Γ⊨ cfg'' →^* cfg₂" by fact
  have cfg₁: "cfg₁ = (c₁, s)" and cfg₂: "cfg₂ = (c₁', s')" by fact+
  obtain c₁'' s'' where cfg'': "cfg''=(c₁'',s'')"
    by (cases cfg'') auto
  from step cfg₁ cfg''
  have "Γ
    by WhileFalselbrakk><rbrakk
  hence java.lang.NullPointerException
    Γ \rightarrow> Skip,Nor s)"
  also from Trans.hyps (3) [OF cfg'' cfg₂]
  have java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null

qed


lemma tchSeps:
  assumes s:s "Γ
  shows "∧ c₁' s'. [cfg = (c\^1,s); cfg_c2,s)) <> u"
          ==> Γ⊨(Catch c u"
using steps
proof (induct rule: converse_"🚫1 c\<^>)Small-Step Computation: ‹(c, s) →›
  case Refl
  thus ?case
    
next
  case
  have step: "Γ
  have steps: "Γ⊨>u
  have<n>g ==> Γ(Guard f g c,Normal s) →
  obtain c<sub>1's' erecfg': "ffg''=c_'
    by (
  from step cfg🚫2,s) →2, s)"
  have s: "Γ (c₁'',s'')"
    by simp
henceGamma>turstle> ac c\subc\^>2s)\ightarrowCac<ub>' c\^>2,'')
    by (rule step.Catch)
 3) [OF cfg'' cfg_\<turnstile>(While b c,Nor \rightarrow (Seq c (While b c),Normal s)"
   "\\G>tu> Catch c\\<su1'' c<^sub>2,s'' \<<ightarrow
  finally show ?case .
qed: "\Gamma p=ome bdy ==>⊨ (bdy,Normal s

lemma Γ(Call p,Normal s) → (Skip,Stuck)
proof (inductt c)
  case eq c\sub1c\^>2)
  have steps_c_Normal) \ igh> u
  have steps_c₂: "Γ⊨ (c₂, Fault f) →>⊨
java.lang.NullPointerException
  have "Γ (Seq c₂, Fault f) →<^up>* (q ki c\sub, Fulf).
  also
  have "Γ (Seq Skip c_>, Fault f)" by (rule SeqSkip)
java.lang.NullPointerException
  finally show ?ca CatchSk: "\Gamma<turnstile>(Catch Skip c₂,s) → FFautPro: "[Skip; redex c = c] Γ(c,Fault f) →
next
  case (Catch c_Skip; redex c = c] Γ(c,Abrupt f) →p,bruptf"
  have steps_c_\r>gh> u"
  from CatchSteps [OF ste
  <Gamma>⊨1 c c2,or s \rightarrow"
  also
java.lang.NullPointerException
  finally shot‹
qed (fastforce intro: step.intros)+

lemma steps_Stuck: "Γ⊨ (c, Stuck) →^* (Skip, Stuck)"
proof (induct c)
  case ( c\^>1 \^>2)
  have steps_c₁: "Γ⊨ teabrupt. h @co"A"} s is useto
java.lang.NullPointerException
  from SeqSteps [OF steps_c₁ refl refl]
java.lang.NullPointerException
  also
  have "Γ⊨ (Seq Skip c₂, Stuck) → (c₂, Stuck)" by (rule SeqSkip)
e \^u>2
  finally show ?case by simp
next
case(Ca c\^>1\^2)
java.lang.NullPointerException
java.lang.NullPointerException
  have "Γsteprtra" : "[',','f)bod,('s'p,'f,'f co,(s,p'f) config] ==>
  also
  have "Γ⊨ (Catch Skip c₂, Stuck) →\turnstile_ <r>\^>/ )c> 81,8,81]10)
  finally show ?case by simp
qed (fastforce intro: step.intros)+

java.lang.NullPointerException
proof (induct c)
java.lang.NullPointerException
  have steps_c₁: "Γ⊨ (c₁, Abrupt s) →^: "[s'p,') b,(s,p,f) onf(','p'f) co \Rightarrowbo
  have steps_c₂: "Γ⊨ (c₍→
  from SeqSteps [OF steps_c₁ refl refl]
  have "Γ⊨ (Seq c₁ c₂, Abrupt s) →^* (Seq Skip c₂, Abrupt s)".
java.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 6
  have "Γ⊨ (Seq Skip c₂, Abrupt s) → (c₂, Abrupt s)" by (rule SeqSkip)
java.lang.NullPointerException
  finally show ?case by simp
next
  case (Catch c "rre c = Seq c1 c2 \Longrightarrow P"
java.lang.NullPointerException
java.lang.NullPointerException
 have "Γ
 also
 have "Γ⊨ (Catch Skip c₂, Abrupt s) → (Skip, Abrupt s)" by (rule CatchSkip)
 finally show ?case by simp
  (fastforce intro: step.intros)+

  step_Fault_prop:
 assumes step: "Γ⊨ (c, s) → (c', s')"
 shows "∧f. s=Fault f ==> s'=Fault f"
  step
  (induct) auto

  step_Abrupt_prop:
 lemma no_ste:
 shows "∧x. s=Abrupt x ==> s'=Abrupt x"
  step
 (ndu) auto

 ep_Stuck_prop:
 assumes step: G>🚫
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
  step
  (induct) auto

  steps_Fault_prop:
 assumes step: "Γ⊨ (c, s) →\<  shows
 shows "s=Fault f ==>
  step
  (ind⊨
 case Refl thus ?case by simp
 
 case (Trans c s c'' s'')
 thus ?case
 by (auto intro: step_Fault_prop)
 

  steps_Abrupt_prop:
 assumes step: "Γ⊨es [casest]:
  "s=Abrupt t ==>
  step
  (induct rule: converse_rtanclp_induct2 [cas
 case Refl thus ?case by simp
 
  (Trans c s '' s''
  "Γ(Seq c1 c2,Normal s) →⊨ (c', s')"
 by (auto intro: step_Abrupt_prop)
 

  steps_Stuck_prop:
 assumes ste: "Γ step
 shows "s=Stuck ==>\< (ck:
  step
  (induct rule: converse_r[case_names Refl Trans])
 case Refl thus ?case y sip
 
 case (Trans c s c'' s'')
 thus ?case
 by (auto intro: step_Stuck_prop)
 

(* ************************************************************************ *)
subsection)
(* ************************************************************************ *)

theorem  :{termNormalconsttstateo
  assumes exec: java.lang.NullPointerException
  shows "∃⊨* (c',t') ∧
               (case
                 Abrupt if s=t then cip t'=t else c'=Throw ∧
                | _ ==> c'=Skip ∧
using exec
proof (induct
  case thus
    by simp
next
  case husstrdtrans
next
  case\urnstilecf0 →⁺ cf1 ≡ (CONST step Γ)⁺ cf0 cf1"
next
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
next
  case Basic thus ?case by (fastforce intro: step.Basic rtranclp_trans)
next
  case Spec thus ?case by (fastforce intro: step.Spec rtranclp_tra (fastforce intro: step.intr+
next
  case Sp thus ?case by (fastforce intro: step.SpecStuck rtr)
next
   (Seq c₁ s s' c₂ t)
  have exec_c₁: "Γ>⟨
  have exec_c "∧<ongrig> s'=Fault f"
  showusing step
  proof (cases\existsx.brupt
    case False
    fromFalse.hyps ()
    have "Γ ste: "<Gamma⊨ Skip^sub,)\rightarrow(,)
      by (cases s') auto
    hence seq_c_\<> (Seq
      y rule) auto
    from Seq.hyps (4) obtain c' t' where
      steps_c_\<turnstileStuckProp  "\\<lb>≠<Longrightarrow> Γ> Skip,St)"
      t: (tf
           Abrupt x \by (induct
                       step_Stuck_prop
           | _ ==> t' = t)"
      by autoAbruptProp\lbrakk<>Ski; sho "===>
    note seq_c
    also have "Γ
java.lang.NullPointerException
    finally a"\amma>< ( "s=Fault f==> f"
    with step
      bycases 
  next
    case True
    then obtain x where s': "s'=Abrupt x"
      byblast
    from   thus ?
    have\Gamma><turnstile<WhileFalse CallUndefinedCatchCatchThrow
      by auto
    hence seq_cjava.lang.NullPointerException
      by (rule SeqSteps) auto
    also java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
      by (rule
     veGamma⊨1 cjava.lang.NullPointerException
    
    from
      by (autointro: Abrupt_end
    ultimately showthesis
      by auto
  qed
next
  case CondTrue thus ?case by (blast intro: step.CondTrue rtranclp_trans)
next
  case CondFalse thus ?case by (blast intro: step.CondFalse rtranclp_trans)
next
  case (WhileTrue s b c s' t)
  have exec_c: "Γ ⟨ s⟩ s'" by fact
  haveexec_w: "Γ⊨: "Γturnstile \ "\<\< thus case b sim
  have b: "s ∈?case"\<amma\
  hence step: "<⊨ )<rightarrow<\turnstile<rightarrow 
    by (rule exec_impl_steps
  showcase
  proof (cases "∃x."Gamma(DynCom<>"
    case False
    from False WhileTrue.hyps (3)
    have "Γ
      by (cases s') auto
    hence><turnstileCatch,)<ightarrow  c'=Skip<>t'=t)"
     by rul SeqSteps) auto
    from WhileTrue.hyps (5) (induct)
      steps_c_"<Gamma>\turnstile>(uard frdf c,N ) →
      t: "(case t of 
           Abrupt x \caseGuard ?caseby(blast intro step.Guard  <\<
                       hrow t' = Normal x
           | _ ==>
      by auto case astforcejava.lang.StringIndexOutOfBoundsException: Index 71 out of bounds for length 71
    note step also note seq_c
    alsoGamma>  c1 s) <>u
      by uleip
    also tesub
    finally have "Γ⊨🚫 ⟨
    withFale show ow ?tesisjava.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for length 29
       by t) a
  next
    case True
    then obtain x where s': "s'=Abrupt x"
      by blast
    note step
    also
    from s While.hyps (3
    have "Γ⊨
      by auto
    hence
      seq_c<>turnstile(Seq c (While b c), Normal s) →^ted in
      by (rule SeqSteps
amma>(SeqThrowWhile c), Normal <> (Throw Normal
       (ulejava.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
    finally have "Γ
    moreover
    from exec have \ammat (Seq Skip c₂, s')" by (rule step.SeqSkip)
      alsonotec^sub2
    ultimately
      by auto
  qed
next
  case WhileFalsethus ?caseby( intro.WhileFalsemodel terminationinto big semantics if  havehaveteps_c1 \Gamma\turnstile>(c<sub1,Abrupt<rightarrowup*(, Abrupt"
next
  case Call thus ?case by a
next
  case CallUndefined thus ?case by (fastforce intro: step.CallUndefined rtranclp_trans)
next
  case StuckProp thus ?case by (fastforce intro: steps_Stuck)
next
  case DynCom thus ?case by (blast in(fast intro: step.)+
next
   case Throw thus ?case by simp
next
  rop thus ?case by (fastintro: steps_)
next
  case CatchMatch c_finally hav "\>turnstile
  from CatchMatch'p  <bool" f<Longrightarrowt "
  have "Γ⊨
    by simp
  hence ()to
    by rule) auto
  also haveultimatelyshow thesis
    by (rule stepjava.lang.StringIndexOutOfBoundsException: Index 5 out of bounds for length 5
  also
  from CatchMatch.hyps (4) byblast: step rtranclp_trans
      steps_c s cs')
      t: "(case t of
java.lang.NullPointerException
                       else c' = Throw ∧
row c' Skip \<and< t' = t)"
      by auto
  notehencestep Γ (While b c,Normal s) →ljava.lang.StringIndexOutOfBoundsException: Index 96 out of bounds for length 6
  ally?case
    using t
    by 
next
  caseiss
  have t: "\<notlemma
  with Catch.hyps (2)
  have "Γ⊨ (c_s
    by (cases t) auto
  ence<Gamma⊨^ub,Normal \ightarrow^>*(  c<sub t)
    by (rule CatchSteps) auto
  o
  have "Γ
    by (rule step.Catcl steps_Faul_rp:
  finally show ?case
    using t
    by (fastforce split: xstate.splits)
qed

corollary exec_impl_steps_Normal:
  assumes exec: "Γ⊨
  showsrtranclp_induct2
using exec_impl_steps [OF exec]
by auto

corollary exec_impl_steps_Normal_Abrupt:
  assumes exec:
  shows "Γ
using exec_impl_steps [OF exec]
by a

corollary exec_impl_steps_Abrupt_Abrupt:
  assumes exec: "Γ
  shows teps_Abrupt_prop
using exec_impl_steps⊨
by autoshows=upt> s'=brupt

corollary exec_impl_steps_Fault step
  ssumes🪙 [case_names Refl Trans])
  shows><turnstile>(c,s) →* (Skip, Faultf)java.lang.StringIndexOutOfBoundsException: Index 73 out of bounds for length 73
using exec_impl_steps [OF exec]
by autodone

corollary :
  assumes exec: "\<Gammaassumes (c,s) \Longrightarrow"
  shows "Γ⊨
usingmpl_stepsxu n_st':
by auto


lemma step_Abrupt_end:
  assumes s "\Gamma>⊨
  shows "s'=Abrupt x ==>
using step
by induct auto 

lemma step_Stuck_end: step
  assumes step: "Γ *
  shows "s'=Stuck ==>
          k <r>
          (∃
          (∃
using step
by induct auto

lemma step_Fault_end "∧s'=Fault f"
  assumes step: "Γ⊨
  shows "s'=Fault f ==>
          s=Fault f ∨⊨(case tt
          (∃shows "<nd sStuck s'=Stuck"
using step
by induct auto

lemmaexec_redex_Stuck:
"Γ⊨
proof (induct c)
  case Seq
  thus ?case
    by (cases s) (auto intro: exec.intros elim:exec_elim_cases)
next
  case Catch
  thus ?case
    by(cases s) (autointro exec.intros:exec_elim_cases
qed simp_all

lemma exec_redex_Fault:    have "<>\<urnstile 
"< 
proof (induct c)
 Seq
  thus ?case
    by (cases s) (auto intro: exec.thus
next
  case Catch
  thus ?case
    ycasesntroslimes
qed simp_allfromileTrue()btain where

lemmatep_extend
  assumes tof
  shows havecfg: "cfg₁ = (c_^>2= (c₊
using step
proof else c' = Thr oc<1'' ' wh g' cfg=(c\^>1'',s')"
  (scfg
    ep1 cfg''
next
  case Spec thus ?case
    by (fastforce step seq_c
next
  case SpecStuck thus ?case
    by (fastforce intro simp
next
  case Guard thus ?case
    by (fastforce: exec elim)
next _<finally haveΓ<><^supc' 'java.lang.StringIndexOutOfBoundsException: Index 93 out of bounds for length 93
  casese
    by (fastforce intro: exec.intros elim tfinallyy show
next
  case (Seq
  have step: "Γ
java.lang.NullPointerException
  show ?case
  proof (cases s)
    case (Normal x)
    note s_Normal = this
    show ?thesis
    proof (cases s')
      case (Normal x')
      from exec' [simplified Normal] obtain s'' where
java.lang.NullPointerException
         (Transcfg\^sub>1cfg'''
        cases
from Seq.h(2 Normal execcb
 "Γcjava.lang.NullPointerException
        by simp
      from.SeqOF  exec_c<sub2] s_Normal
      show ?thesis by simp
t
      case (Abrupt x')
       exec "t==Abr x₁'',s'')"
        by (auto intro)
      moreover
          ultimatelyhesis
      have "s=Abrq
        by (auto intr int step_nd))
      ultimately
      show ?thesis
        by (auto intro: exec.intros)
    ext
      case (Fault f)
      from step_Fault
      obtain g c where
        redex_c\<<^ c)
        fail: x \next
        by auto
      hence "\Gamma><> 
        by (autohavejava.lang.NullPointerException
      from exec_redex_Fault [OF this]
       sFsteps_c> lefl
      moreover from Fault
        by (auto: Fault_end)
      ultimately
      show ?thesis
        usingNormal
        by (autoo.introsmp
    next
      case Stuck
      from step_Stuck_end [OF  also have"\Gamma\turnstile> (
      have ""∃cr ∧>t. (x, t) ∉
            (∃p. redex c_from Catchyps (4) ob c' t' where
        by auto
      moreover
     
        fix r
        sume"edex1 = Spec r" and "(∀  <>r)"
        hence "Γ⊨ ∧
          .)
        from exec_redex_Stuck [OF this]
        have java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
        moreover from Stuck exec' have "t=Stuck"
          by (rul CatchSt) auto
        also
        have ?thesis
          using s_Normal
          by (auto intro: exec.intros)
      }
      moreover
      {
        fix p
        assume "redex c\1corollaryrmal
        hence java.lang.NullPointerException
          by (auto into: excintrs
        from exec_redex_Stuck [OF this]
        have "Γ⊨
        moreover from Stuck [ steps_c1  refl
          bytojava.lang.NullPointerException
        ultimatelyjava.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 6
        have ?thesis
          using s_Normal
          by (auto intro: exe.intros)
      }
      ultimately show ?thesis
        by auto
    qed
  next
    case (Abrupt x)
     int c)
    have "s'=Abrupt>2java.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32
    with'
    have "t=Abrupt x"
      by(autoo:
    with Abrupt
    show ?thesis
      by (auto intro: exec.intros)
  next
    case (have "<>⊨
    from step_Fault [OF step this]
    have"s'=Fault f".shows🚫 sho ?case by si
    with exec'
    have "t=Faultend(induct
      by   Skip
    with "s'= x ==>
    show ?thesis
      by (auto intro: exec.intros)
java.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 6
    sek
    from step_Stuck [OF step this]
  have ss==Stu"
    with'
    have "t=Stuck"
      by (auto
    ith
    show ?thesis
      by (auto intro: exec
  qedjava.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 10
next
   step_Abrupt_prop
    by (cases:<amma<(, s) → (c', s')"
next
  case (SeqThrow c₍g c x. redex c s=Normal x ∧ g)"
    by (fastforce intro: exec.intros
next
  case CondTrueedex_Stuck
    by><><langle>redex c,s⟩
next  thus ?Seq
  case CondFalse
    by (fastforce intro: exec.intros elimnduct(Seq
next
  case WhileTrue thus ?case
     imp_all
next
  caseWhileFalse ?case
    by (fastforce: execrosjava.lang.StringIndexOutOfBoundsException: Index 66 out of bounds for length 66
nextbycasestros:elim_cases
  case Call thus ?case
    by (fastforceintroim_cases
next
  case CallUndefined thus ?case
    by (fastforce intro "s=Fau f ==>
next
  case DynCom thus ?case
    by (fastforce intro: exec.intros elim: exec_Normal_elim_cases)
next(Trs cc'' s
  case Cath c\< s
  have step: "Γ
  have exec': "Γ⊨
  show ?case
  proof (cases s)
    case (Normal x)
    note s_Normal =
    show ?thesis
    proof (cases s')
java.lang.StringIndexOutOfBoundsException: Index 57 out of bounds for length 22
      exec mifdrmal]
      show ?thesis
      proof (cases)
        fix s''
java.lang.NullPointerException
        assume exec_c_\<langle>c₂,Normal s''⟩
        from Catch.hyps (2) Normal exec_c s=Stuck"
        have "Γ⊨ i(induct rul: conve [case_names Refl Trans)
          by si
java.lang.NullPointerException
        show ?thesis by simp
      next
java.lang.NullPointerException
        assume t: "¬Equivalence between Small-Stepeq
        from Catch.hyps2)Normal
        have\turnstile theoremjava.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
          by simp
        from exec.CatchMiss [OF this t] s_Normal
        show ?thesis by simp
      qed
    next
      case (Abrupt
                       Abruptghtarrowthencand else t'=Normal x
        by (auto intro:Abrupt_end)
      moreover
      from step Abrupt
      have "s y (o ase
        by (auto
      ultimately
      show ?thesis
        by (auto intro: exec.intros)
    next
      case e (Fault
      from step_Fault_end [OF step this] s_Normal
      obtain g c where
        redex_c
        x ∉
        by auto
      hence "Γ
        by (auto intro: exec:"Gamma>⊨ (c', s')"
      from exec_redex_Fault [OFjava.lang.StringIndexOutOfBoundsException: Index 37 out of bounds for length 37
      have><turnstile> ⟨1,Normal x⟩ Fault
      moreoverFault
        by (auto intro:bystforceasic?case(fastforce: step anclp_transssjava.lang.StringIndexOutOfBoundsException: Index 71 out of bounds for length 71
      ultimately
      show ?thesiscasestforceard
        using
        by (autofastforcec elimrmal_elim_cases
    next
      case Stuck
      from step_Stuck_endtep>turnstile> (c< ) execjava.lang.StringIndexOutOfBoundsException: Index 12 out of bounds for length 12
show
            (∃1': "\<>\
        by auto
      moreover
      {
        fix r
        ssume "c\^1  r" and "(\forall> (  \notin "
        hence "Γ
          by (autove⊨by(utobrupt_end
        from exec_redex_Stuck thisave⊨
        have auto java.lang.StringIndexOutOfBoundsException: Index 39 out of bounds for length 23
        moreoverlast
          by (auto intro [OF<<urnstile1, Normal s) →
            ^>" c_x< g"
        hesis
          using s_Normal⊨* (Throw x)
          by (auto _^> s' have 
      }
      moreover
      {
        fix p
        assume "redex c\      
        hence "Γ.intros⊨
          by (autoromOF
        fromedex_Stuck
        "< ce ep: "Gamma⊨(Seq c (While b c),Normal s)"
        moreover from Sby auto
          by (auto intro: Stuck_end)
        
        have ?thes "redex1 = Spec r" and "(∀
          using s_Normal
           ( intro
      
       show
        by auto
    qed
  next
    case (Abrupt x)
    from step_Abrupt [OF step this]
    have "s'=A
    with exec'
    " 
       auto: )
    withexec_redex_Stuck]
    show ?thesis
      by (auto introxec="
  next
    case (Fault f)
    from step_Fault [OF step this]
    have "s'=Fault f".
    with exec'
    have "t=Fault "
      by (auto intro: Faul)
    with Fault
    show ?thesis
      by auto intro: : exec.intros)
  next
    case Stuck
    from step_Stuck [OF step this]
    have "s'=Stuck".
    with exec'
    have "t=Stuck"
      by (auto intro: Stuck_end)
    with Stuck
    show ?thesis
      by (auto intro: e: exec.intros)
  qed
next
  case CatchThrow thus ?case
    by (fastforce intro: exec.intros elim: exec_Normal_elim_cases)
next
  case step also note seq_c
    by (fastforce intro: exec.intros elim: exec_elim_cases)
next
  case Fathus ?case
    by (fastforce ntro: exec.i elim: exec
next
  case StuckProp thus ?case
    by (fastforce intro: exec.intros elim: exec_elim_cases)
next
  case AbruptProp thus ?case
    by (fastforce intro: exec.intros elim: exec_elim_cases
java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 3

theorem steps_Skip_impl_exec:
  assumes steps: "Γ
 \Gamma><>\
usingjava.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 27
proofrulecase_namesTrans
  case Refl thus ?case
    by (cases t) (auto intro: exec.intros)
next
  case (Trans c s c' s')
  have " Cao have "\rnstile hrow c)Normal<> (, Normal
  thus ?case
    uleep_extendxtend
qed

theorem steps_Throw_impl_exec
  assumes steps: "Γ<rightarro>^sup>>* (Trow,Norml tt)"
  shows "Γ⊨case
using steps
proof (induct rule: converse_rtranclp_induct s_No = this
  case Refl thus ?case
    by (acase (Normal x')
next
  case (T s c' s')
  have "<>\
  thus ?case
    by (rule step_extendjava.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
qed

(* ************************************************************************ *)
subsection ‹
(* ************************************************************************ *)

definition inf:: "('s,'p,'f) body \Rightarrow's,'p,'f) config ==>by (fastforce itro: ro:o:: ssteps_Abrupt)
 (‹1><turnstile>case(CathMatcch cc\\ssu1 s c_t
" 🚫 ⟨1,Normal x⟩

  not_infI: "[∧f. [
 ==>
 imp inef)

(* ************************************************************************ *)
ubsectionopen betweenTermination
(* ************************************************************************ *)


lemmaFault
ssumes
showsauto
using
proof java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
  case Basic thus ?case by
next
  caseSpec (stforceates showcaseuptProp y forceintro steps_Abruptupt
next
  casecase(tch>  step_Faults]
next
  case GuardMatch
    by (fastforcebyautoault_end
next
  next
next
   \sub\^>with
    apply (  shows=withck
      byuto
    pply
                    
    apply (also
      step_Fault_propintrosim_caseses
    done^>2: "shows=Stuc intrxec.i.inintroe exec_elimcaaeaes
next
java.lang.NullPointerException
  thus else c' = h=ow \row\<ndd1Call p🪙
    apply (cases s)
    apply (fastforce intro: terminates.intros exec.intros
            elim: terminates_Normal_elim_cae )
using
nextby(ost st.ls
java.lang.NullPointerException
  thuscasRefl?case
    by (fastforce intro: terminates.intros exec.intros
            elim: terminates_Normal_elim_cases )
next
  case CondTrue
  thus ?case
    yfastfreino te.irs ac',s)ad\Gamma\urnstile ⟨ ==>
            elim: terminates_Normal_elim_cases )
next
  case CondFalse
  thus ?case
    by (fastforce intro: terminates.intros
            elim:terminaNormal_elies )
next
  case WhileTrue
  thus ?case
    by (fastfby (fast spit sat.slits)
            elim: terminates_Normal_elim_cases )
next
  case WhileFalse
  thus ?case
    by (fastforce intro: terminates.intros
            elim: te * ************************************************************************ (
next
  case Call
  thus ?case
    by (fastforce intro: terminates.intros
            elim: terminates_Normal_elim_cases )
next
  case CallUndefid
   by (auto simp add: inf_def)
    by (fastforce intro: terminates.intros
            elim: terminates_Normal_elim_cases )
next
  case DynCom
  thus ?case
    by (fastforce intro:: term.it)
            elim: terminates_Normal_elim_cases )shows "<>c,s) →
next
  case (Catch cjava.lang.NullPointerException
    apply corollaryex_Fault:
    apply     (cases s')
    apply         fastforcerorminatesesstep_extend
                    elim: terminates_Normal_elim_cases <<proofuardFault
     fastforce intro: terminates.intros dest: step_Abrupt_prop
      step_Fault_prop step_Stuck_propcases s  introintroselimxec_elim_casesases
    done
next
  case CatchThrow
  thus ?case
   by (fastforce intro: terminates.intros execpjava.lang.NullPointerException
            elim: term step
next
  case (CatchSkip c<^sub>2 s)
  thus ?case
    (caseases ) (fastforce intr
next
  case FaultProp thus ?case by (cases s)
next
   r hu ca b(atoc inro:teriates.nros
next
  case AbruptProp thus ?case by (fastforce intro: terminates.intros)
qed

lemma steps_preserves_termination:
  assumes steps: "<using 
  shows "Γ
using
proof (induct rule: rtranclp_induct2 [consumes 1, case_names Refl Trans])
  case Refl thus ?case .
next
  case Trans
  thus ?case
    by (blast dest: step_preserves_termithus ?case
qed

pen
  ML_Thmsbind_th("tranclp_induct2plit_Ruleext
     (
      [((("a", 0), Position.none),"(aa,ab)"), ((thus?ase
      @{thm tranclp_induct
›

lemma 
  showthesis
  howsGamma⊨
using steps
proof (induct rule⊨dex ==> Γ⟨
  case Step ?case
next
  case Trans
  thus ?case
    exec_cdefined
qed



definition         by 
where
"head_com c =
            : terminates_Normal_elim_case )
     Seq c_\<turnstile> ⟨> sc\<^ub1sub2] s_Normal
   | Catch c_: termina)
   | _ ==> c)"


definitiond: sp'fconfigep_Fault_propk_prop
  where "head cfg = (head_com (fst cfg), snd cfg)"

lemma 
  clarify
  apply (case_tac "i=k")
  apply
  done

lemma redex_Seq_False: "∧
  by (induct c) auto

lemma repaes s
  by (induct c) auto


lemma i ase Noal ')
  assumes inf_comp: "∀
exec_c⊨<>(c,) \rightarrow^sup'
  assumes not_fin "<forall>i<k. ¬1' s_Normal
  shows "∀Gamma⊨downs ==>c'↓
               Γ⊨ consumesefl
        <i<k. ?P i")
using not_fin
proof (induct k)
  case 0
  show ?case by simp
next
  case (Suc k)
  have not_fin_Suc:
    "\moreover
  from this[rule_format] have not_fin_k:
    "foralli<.¬
     clarify
    apply subgoal "i < Sucjava.lang.StringIndexOutOfBoundsException: Index 35 out of bounds for length 35
    apply blast
    apply simp
    done

  from Suc.hyps [OF this]
  have \foralli(<s  eq,s')\and
                   \Gamma<> head i) →)".
show
  proof (rule le_Suc_cases)
    fix i
    assume "i < k"
    then show "?P i"
      by (rule hyp [rule_format])
  next
    show "?P k"
    proof -
      hypre_fmt, k 1f0
      obtain c' fs' L' s' where f_k: "f k = (Seq c' c₂,
        by (cases:exec
      from inf_comple_format,f ] f_k
           ve<<turnstile
        byhave<>r. redex (∀ r)) ∨
      moreover
            \existsp dex1 = 
      have "¬
        by y (simp add: final_def head_def hehead_co)
      ultimately
      
         "hence⊨
         "f " _{c_redex_Stuck}
        by cases
      with
       ??esis
        by (simp add: head_def head_com_def)
    qed
  qed
qed

lemma infinite_computation_extract_head_Catch inf_comp<>:at⊨
  assumes inf_comp^ub1 = Callfromexec_redex_StuckOF
  assumes not_fin: "\foralli<. \<> \rangle> \RightarrowStuck"
  assumes not_fin: "∀i<k. ¬ final (head (f i))"
  showsforalli<k. (\exists>c' s'. f ((i+1)(Catch^ub2,, s')) 🪙
               Γhead (fi)<> 
        (is "\foralli<k. ?P i")
using not_fin
proof (inducts_Normalultimately
  case 0
     
next
  ase
  have not_fin_Suc
     "redexc\        
  from this[rule_orma] havenot_fin_k:
    "∀
    apply clarify
    apply (subgoal_tac by auto exec.intros
    apply blast
    apply 
    done

  from Suc.hyps [OF this]
  have hyp: "∀i<k. (∃
                   Γ
  show ?case
  eeSu_)
    fix i
    assume "i < k"
    then show "?P     ?esis
          
  next
    show "?P k"
    proof -
      from hyp [rule_format, of "k - 1"] f_0
      obtain'fs L'  wherejava.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for length 32
        by (cases k) auto
      from inf_comp [rule_format, of k] f_k
      have "Γ⊨ec_elim_cases
        by simp
      moreover
      from not_fin_Suc [rule_format, of k] f_k
      have "¬nselm ec_m_m_ss)
        have "t=Abrupt x"
      ultimately
      obtain c'' s'' where
         "Γ⊨
         java.lang.NullPointerException
        by cases (auto simp add: redex_Catch_False by (ffre tr:oecntremllm:xec_oe
      with f)
      w s cse
        by (
    qed eallUthuscse
  qed
qed

lemma no_inf_(aintr
proof
  assume "\><> Throwcase<^ub<>' s' cjava.lang.NullPointerException
  then obtain f where
    stepexec⊨
    f_0 f  =Throw
    by (auto "Γ
  from step [of 0, simplified f_0] step [of 1]
  showf not_fin_Suc [rule_format, of k] f_k
    byvt=Stu"
qed

lemma split_inf_Seq:
  assumes inf_comp: "Γ><>(c', s') →
  shows "Γ⊨1,s) →
         (>s'. Γ
proof -
  from inf_comp obtain f where
    step:<>inat⊨ f (i+1"and
    f_0: "by
    by (autojava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
  avesub,s)"
    by (simp add: head_def head_com_def)
  show ?thesis
  proof (cases "<existsi
    case True
    fineereEAST(f)
    haveshows "∀
      apply (intro allI impI)
      apply (unfold k by (fa i: o:ex.ino limeec_)
      apply (drule not_less_Least)
usingfin
      done
    from infi
    obtain step_head: "∀
           conf: "∀      
      by blast
    from True
    have final_f_k: "finali<k. ¬
      ply
      apply (erule        redex_csub: " c₎
      ulea)
      apply (simp add: k_def)
java.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 10
    moreover
    from f_0 conf [rule_format, of "k - 1"]
    obtain c' s' where f_k: "f k = java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 16
      by (cases k) autoby(tro
    moreover
    from step_head have steps_head: "Γ
    proof (induct k)
      case th ?cse by m
    next
      case (Suc m)
       step: "\forall<Suc<Gammaturnstile head (f i) →
      hence "∀ Γ head (f (i + 1))"
        byuto
    "\amma<tu>head (f 0) →"
        bycjava.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
     ( java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20
      haveultimately
      finally show ?case by simp
    qed
    {
      assumefeq>, s')"
      steps_head
      have "      {
        using head_f_0
        by (simp add_ head_com_defsjava.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
      moreover
      from le_format
      obtain "Γ
        f_Suc_k: "f (k + 1) = (c_turnstile> ⟨qed
        by (fastforce elim: step.cases intro: steplemma no_inf_Throw> Γ⊨        moreover fromexect"
      define g where" = f i
      from f_Suc_k
      haveg_0 0 = (\^          using Normal
        by (simp add: g_def)
      from step
      have "∀ elim: step_elim_cases)
        by (simp add: g_def)
       have "=tx
        by (auto simp add: inf_def)
      ultimately
      have?java.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 18
        by auto
java.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 5
    
    
      fixwith
         me= byutond
      from step [rule_format, of k] f_k"not> iiby (o itro:o: e.ints
      obtain "Γ(Seq Throw cjava.lang.NullPointerException
        f_Suc_k: "f (k + 1) = (Throw,s')"
        by (fastforce ( k_def)
      define " i (i))" i
      from 
      have g_0:
        bysimp
      from step
      have " "forall>O th t] _N
        by (simp add: g_def)
       g_0 h "<<turnstile,s') <>show
        by (auto -
      with
      have ?thesis
        by auto
    
     c 'where: f =Seqsub,s')"
    show ?thesis case Catch thus case
      by (auto simp add: final_def head_def head_com_def)
  ext
    case False
    then have not_fin: "∀simpntroses
      by 
    have "∀
    proof
      fix k
       not_fin
      have "∀i<assumes  steprule_format]
        bymp

      infinite_computation_extract_head_Seq
      show "Γ
    qed
    with head_f_0 havet steps_head
      by (auto simp add: inf_def)
    thus ?thesis
      by simp
  d
qed

emmat_inf_Catch:
  assumes inf_comp: "Γ(\Gammaturnstile\langlec,s⟩Abrupt
  shows " (ind e cvesran_dt [aenmeflp r _u_k
         (∃s'. Γ⊨haveg_0 g 0r exec.in)
proof
  from inf_comp obtain f where
    step: "∀f_def
    ?
    by (auto ‹
  java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    by (simp add: head_def head_com_def)
  thesis
  proof (cases "\<exists>i. final (head (f
    case rue
    define kwhere:f_deff)
    have  f_Suc_k
      apply (intro allI impI)
      apply (unfold         byjava.lang.StringIndexOutOfBoundsException: Index 78 out of bounds for length 78
       drulenot_less_Least)
      apply auto
      done
    omnfinite_computation_extract_head_Catchcomputation_extract_head_Catchmputation_extract_head_Catch[ pf_0 java.lang.StringIndexOutOfBoundsException: Index 67 out of bounds for length 67
    obtainstep_head\<>i<k. \<Gamma><turnstile> head (f i)\rightarrow> head (f (i + )nd
           \<have:"\forall>i. \not> final(head (f i"
      by blast
    fromrue
    have java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
       -
       
      apply (drule LeastI)
      apply (simp add: k_def)
              from exec_redex_Stuck OF ]
    moreover
    from f_0 conf [rule_format, of "k - 1"]
    obtain c' s' where f_k: "f k = (Catch c' c\<^sub>2,s')"step_Fault_prop step_Stuck_prop)
      (kauto
    shows "<>turnstile(c\<^sub>1,s) \<rightarrow> \<dots>(\<infinity>) \<or>
    from step_head have steps_head: "\<Gamma>\<turnstile>head (f 0) \<rightarrow>\<^sup>* head (f kelim: terminates_Normal_elim_cases
    proof (induct k)
      case 0 thus ?case by simp
    next
      case (Suc m)
      have step: "\<forall>i<Suc m. \<Gamma>\<turnstile> head (f ielim  )
      hence"\<forall>im. <Gamma\<turnstile> head (f i) \<rightarrowapply        "<amma\turnstile \<angle>c\<>,Normal \<><Rightarrow>Stuck"
        by auto
      hence\Gamma>\turnstile0<>\^up*ad 
        by (rule         
soromstep        by utointro  tuck_endjava.lang.StringIndexOutOfBoundsException: Index 36 out of bounds for length 36
rightarrow> (f m  1)" by simp
      finally show ?case by simp
    qed
    
      assumef_k "         intro: terminates.intros
      with steps_head
      have "\<Gamma>\<turnstile>(c\<^sub       DynCom
        using head_f_0
        by (impadd head_def head_com_def)
      moreovercase (Catch c\<^sub>1  c\^sub1' s c\<sub>2) thus ?java.lang.StringIndexOutOfBoundsException: Index 61 out of bounds for length 61
      apply(astforceintro: terminates.introsdest step_Abrupt_prop
      obtain "\<Gamma>\<turnstile>(Catch Skip c\<^       fromep le_formatormat java.lang.StringIndexOutOfBoundsException: Index 8 out of bounds for length 8
        f_Suc_k: "f (k + 1) = (Skip,s')
        by (fastforce elim: step.casesthus ?case
      from step [rule_format, of "k+1", simplified f_Suc_k]
      have
        by ruleno_step_final') (auto simp add: final_def)
    
    moreover
    {
      fix x
      s': "s'=Normal x" and f_k: "f       
      with steps_head
       "\<urnstile(<sub>s) \<rightarrow>\<^sup>* (Throw,s"java.lang.StringIndexOutOfBoundsException: Index 79 out of bounds for length 79
        using head_f_0
        by (simp add: head_def head_com_def)
      moreover
      from step [rule_format, of k]f_k s'
      obtain "\<Gamma>\<turnstile>(Catch Throw c\<^sub
        f_Suc_k: "f (k + 1) = (c\<^sub2,s')"
        by (fastforce elim:[((,),osition ,)(",)onone)
      define g where "g i = f (i + (k + 1))" for i
      from f_Suc_k
      have g_0: "g 0= (c\<subs"
        by (simp add: g_def)
      from step
      have "\<forall>i. \<Gamma>\<turnstile>g i \<rightarrow> g (i + 1)"
        by (simp add: g_def)
      with g_0 have "\<Gamma>\<turnstile>(c\<^sub>2,sjava.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
   add inf_def
      ultimately
      have ?thesiswhere
        usings'
        by auto
    }
    ultimately
    show ?thesis
      by (auto simp add:java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
  next
    case java.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for length 14
    then havenot_fin:"\foralli..\not>final(head(fi)
      by blast
    have "\<forall>i. \<Gamma>\<turnstile>head (f i) \<rightarrow> head shows"<><turnstile>\< \<turnstileapplyapplylarify
    proof
      fix k
      from not_fin
      havei<(Suc k). \<not> final (head (f i))"
        by simp

       infinite_computation_extract_head_Catch [OF step f_0 this ]
      show "\<
    qed
    with head_f_0 have "\<Gamma>\<turnstile>(c\<^sub>1,s) \<rightarrow> \<dotsassume : "f 0 ==(Skip, Stuck)"
      by (auto    "<iSuc k notfinalal(headd    teps
    thus ?thesis
      
  qed
qed

lemma Skip_no_step: "\<Gamma>\<turnstile>(Skip,s) \<rightarrow> cfg \<Longrightarrow> P"
  apply (erule no_step_final')
  apply (simpfrom le_formatk - 1" f_0
  done

lemma not_inf_Stuck: "\<not> \<Gamma>\<turnstile>(cStuck<rightarrow \<dots>(\<infinity>)"
proof inductc
  case Skip
  show ?case
         c''s'' where
     f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assumef_0"f"f  "
    from f_step [of 0] f_0
    show False
      by (auto elim: Skip_no_step)
qedqed
next
  case (Basic g)
  thus ?case
  proofrulenot_infI)
    fix f
java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
    assume f_0: "f 0 = (Basic g, Stuck)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Spec r)
  thus ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>by(fastforcetroerminatesros                   Gamma\<turnstile>> head (f i) \<rightarrow> head (f ( +1)).
    assume f_0: "f 0 = (Spec r, Stuck)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Seq c\<^sub>1
  show ?case
  proof
    assume "\<Gamma>\<turnstile> (Seq c\<^sub>1 c\<^sub>2, Stuck) \<rightarrow> \then show?Pi"
    from split_inf_Seq [OF this] Seq.hyps
    show False
      by (auto dest: steps_Stuck_prop)
  qed
next
  case (Cond b c\<^sub>1 c\<^sub>2)
  show ?case
  proof (rule not_infI)
    fix f
    ssume f_step_stepp:<And      by uto elim kip_no_step_no_step
    ume0f 0  case( g)
    from f_stepof 0]f_0f_step[of 1]1]
    show False
      by (fastforce elim: Skip_no_step(simp add: head_def head_com_def)
  qed
next
  case (While b c)
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (While b c, Stuck)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Call p)
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<shows "\<Gamma>\<turnstile>(c\^sub1s)\<ightarrow> \<dots(<nfinity>) \<java.lang.StringIndexOutOfBoundsException: Index 82 out of bounds for length 42
    ume f 0 =Callp,Stuck)
    fromf_step [of ] _0 f_stepep ofjava.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 40
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (DynCom d)
  show ?case
   (rulenot_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>assume<Gamma>urnstileSeq\sub <sub> t)ightarrowarrowdots(\infinity)
    assume \<ubc<b2java.lang.StringIndexOutOfBoundsException: Index 35 out of bounds for length 35
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Guard m g c)
  show ?case
  proof (rule not_infI)

    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (Guard m g c, Stuck)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
   Throw
   ??case
  proof (rule not_infI)
    fix f
f_step:i <>\urnstilef i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (Throw, Stuck)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by(fastforce elim Skip_no_stepstep_elim_cases)
  qed
next
  case (Catch c\<^sub>1 c\<^sub>2     True
  show ?case
  proof
<Gamma\<urnstile less_k:   ?case
    from split_inf_Catchapply (unfold k_def)
java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 14
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
  java.lang.StringIndexOutOfBoundsException: Index 5 out of bounds for length 5
qed  husseeimp

lemma not_inf_Fault: "\<not> \<Gamma>\<turnstile>(c,Fault x) \<rightarrow> \<dots(\infinity)"
proof (induct c)
  case Skip
  show ?case
  proof (rule not_infI)
    fix f
    ssume_tep:assumef  q ip\<sub  arify
    assume f_0: "f 0 = (Skip, Fault x)"
     [of] f_0
    show False
      by (auto elim: Skip_no_step)
  qed
next
  case (Basic g)
   ?case
  (t_infI
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>   inf_comp \<>i::nat. \<qed
    assume f_0: "f 0
    from f_step [    
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Spec r)
  thus ?case
  proof (rule not_infI)
      show ?case bysimp
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (Spec r Faultx"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim:  step_elim_cases)
  qed
next
  caseSeq c\<^sub>1 c\<^sub2)
  show ?case
  proof
    assume "\<Gamma>\<turnstile> (Seq c\<^sub>1 c\<^sub>2, Fault x) \<rightarrow> \<dots>(\<infinity>)"
    from split_inf_Seq [OF this] Seq.hyps
    show False
       ( dest: steps_Fault_prop)
  qed
next
  case (Cond b c\<^sub>1 c\<^sub>2)
  show ?case
  proof (rule not_infI)
by(rule hyp [rule_format])
    assume f_step: "\<And>i. \<Gamma>\<turnstilef <rightarrow f (Suc i)"
    assume f_0: "f 0 = (Cond b c\<^subqed
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (While b c)
  show ?case
  proof (rule)
    fix f
    assume f_step: "\<And>i. \<Gammaassumes: "\<mma<c \<down> s"
assume: "f 0  ( ,ltx)
    from f_stepp[f_0f_step1java.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 40
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Call p)
  show ?case
  proof (rule not_infI)
    fix f
    assumef_step: "\<And>i. \<Gamma><turnstile>f i \<rightarrow f(Suc i)"
    assume f_0: "f 0 = (Call p, Fault x)"
    from  f
    show False
      by (fastforceelim:kip_no_stepstep_elim_cases
  qed
next
  case (DynCom d)
  using not_fin
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (DynCom
    from f_step [of 0] f_0 f_step [of 1]
    show 
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  
  show ?case
  proof (proof
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)" split_inf_Seq [OF this] Seq.hyps
    assumef_0: f 0= Guard m g c Fault x)"
    from f_step [of 0] f_0 f_step [of 1]
    False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
     i
 caseThrow
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And    with hyp_c1showFalsebysimp
    assume f_0: "f 0 = (Throw, Fault x)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
          by simp
  show ?case
java.lang.StringIndexOutOfBoundsException: Index 41 out of bounds for length 7
    assume "\<Gamma>\<turnstile> (Catch c\<^sub>1 c<sub>2, Fault ) <rightarrow>\<dots(\<infinity>)"
    from split_inf_Catch [OF this] Catch.hyps
    show False
      by (utodest: steps_Fault_prop)
  qed
qed

lemmajava.lang.StringIndexOutOfBoundsException: Index 12 out of bounds for length 12
proof (induct c)
  case Skip
  show f_step [of 0f_0b
  from step
    fix f
ilef iwith  >rnstileThrow,<> \<ots><infinity>java.lang.StringIndexOutOfBoundsException: Index 87 out of bounds for length 87
    assume f_0: "f 0by simp
    from  [ 0]f_0
    show False
       (uto elim: Skip_no_step)
  qed
next
  case from  f_step 0f_step1
  thus ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>next
    assume_ "0sicgAbruptruptsjava.lang.StringIndexOutOfBoundsException: Index 43 out of bounds for length 43
    from f_step [of 0] f_0 f_step  f
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  
next
  case (Spec r)
  thus ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (Spec r, Abrupt s)"
    from f_step [of 0  f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Seq c\<^sub>1 c\<^sub>2)
  show ?case
  proof
    assume "\<Gamma>\<turnstile> (Seq c\<>1c^2, Abrupt s) \<rightarrow> \<dots>(\<infinity>)      apply( exE)
    from split_inf_Seq [OF this] Seq.hyps
    show False
      by (auto dest: steps_Abrupt_prop)
  java.lang.StringIndexOutOfBoundsException: Index 5 out of bounds for length 5
next
  case (Cond b c\<^sub>1 c\<^sub>2)
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. <Gamma><turnstile> i\rightarrow>  Suci"
    assume f_0: "f 0 = (Cond b c\<^sub>1 c\<^sub>2, Abrupt s)"
    from f_step [of 0] f_0 f_step [of  case Abruptc
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (While b c)
  show ?case
   ( not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume:"f0 =Whilebby elim step.casesintrostep)
    mf_stepf ]_0_tepof
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Call p)
  ?ase

     java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
 f_step\<And>. \<><urnstile>f \<>f Sucjava.lang.StringIndexOutOfBoundsException: Index 77 out of bounds for length 77
    assume f_0: "f 0 = (Call p, Abrupt s)"
    from f_step [of 0] f_0 f_step [of 1]
     False
      by (fastforce    {
qed
next
  case (DynCom d)
  show  ?case
  proof(rulenot_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\ "\<Gamma>\<>(r,s)<rightarrow> ('s' \Longrightarrow <Gamma>\turnstile>(obtain "<Gammaturnstile( Throw c\<^sub>2,s') \rightarrow>(tainstep_head \<forall< turnstile> head (f i) \<rightarrow> head (f (i + 1))" and
    assume f_0: "f 0 = (DynCom d, Abrupt s)"
    from f_step [of 0] f_0 f_step [of 1]
            byauto
      by (fastforce elimmately
  qed
next
  case (Guard m g c)
  show ?case
  proofule infI))
    fix
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc"\\Gamma\turnstile>c\sub>1,s) \<rightarrow>\<^>* (  java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
    assume f_0: "tep_,f"k1" implifiediedSuc_kc_k
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case Throw
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = Throw, s)
    from f_step [of 0] f_0 f_step [of 1]
    show False
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Catch c\<^sub>1 c\<^sub>2)
  show ?case
  proof
    assume "\<Gamma>\<turnstile> (Catch c\<^sub>1 c\<^sub>2, Abrupt s) \<rightarrow> \<dots>(\<infinity>)"
    from split_inf_Catch [OF this] Catch.hyps
    show False
      by (auto dest: steps_Abrupt_prop)
  qed
qed


theorem terminates_impl_no_infinite_computation:
  assumes termi: "\<Gamma>\<turnstile>c \<down> s"
  shows "\<not> \<Gamma>\<turnstile>(c,s) \<rightarrow> \<dots>(\<infinity>)"
using termi
proof (induct)
  case s)hus?java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
  proof (rule not_infI)
    fix f
> i\rightarrow f( i)"
    assume f_0: "f 0 = (Skip, Normal s)"
    from f_step[of 0]f_0
    show False
      by (auto elim: Skip_no_step)
qed
next
  case (Basic g s)
  thus?case
  proof (rule not_infI)
    fix nce "<forallim \Gamma\<> head(f i)\rightarrow  (f(i+1)"
    assume f_step: "       "\<>\<urnstile  (f0)\rightarrow\^sup>   (f)
    assume f_0: "f 0 = (Basic g, Normal s)"
    from f_step [of 0] f_0 f_step [of 1]
    show False
       fastforceelim:Skip_no_step   qed
  qed
next
  case (Spec r s)
  thus ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc    show False
    assume f_0: "f 0 = (Spec r, Normal s)"
    assume f_step: "\<Andi. \<Gamma>\turnstilefi\rightarrow f Suci)java.lang.StringIndexOutOfBoundsException: Index 77 out of bounds for length 77
showFalse
      by (fastforce elim: Skip_no_step step_elim_cases)
  qed
next
  case (Guard s show False
  have g: "s
  have hyp: "\<not> \<Gamma>\<turnstile> (c, Normal s) \<rightarrow> \<dots>(\<infinity>)" by fact
  show ?case
(not_infI

    assume f_step: "\<And>i. \<Gamma>\<turnstile  qed
    assume f_0: "f 0 = (Guard m g c, Normal s)"
    from f_step [of 0] f_0  g
    have "f 1 = (c,Normal s)"
      by (fastforce elim: step_elim_cases)
    with f_step
    have "\<Gamma     f_0: "f0      Faultx
      apply (simp add: inf_def)
      apply (rule_tac x="\<lambda>i. f (Suc i)" in exI)
      by simp
    with hyp show False ..
  qed
next
    show?case
  have g:     "\<>\<turnstile (Catch c<sub1c\^sub> Fault x)\<ightarrow>\<ots>\<>)java.lang.StringIndexOutOfBoundsException: Index 105 out of bounds for length 105
  show ?case
  proof (rule not_infI)     f_step: "\<>i <><> i\rightarrow f( "
    fix f
    assumef_step "And>.\Gamma\turnstile>f  <> f(Suc )
showFalse
java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
    showassume f_0 " 0= (pec , brupts)"
      by (fastforce elim: Skip_no_step step_elim_cases)

next
  case (Fault c m)
java.lang.StringIndexOutOfBoundsException: Index 12 out of bounds for length 12
    by (rule not_inf_Fault    show False
next
  case (Seq c\<^sub>1 s c\<java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
  show ?case
  proof
    assume "\<Gamma>\<turnstile> (proof rulenot_infIjava.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23
    from split_inf_Seq  
    show False
      by (auto intro: steps_Skip_impl_exec)
  qed
next
  case (CondTrue s b c1 c2)
   f_step [of 0 f_0 f_step[ 1]
  havehyp_c1: \not \<\<turnstile( s\<>\<dots(<nfinity)byfact
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (Cond b c1 c2, Normal s)"
    from b f_step [of 0] f_0
    have "f 1 = (c1,Normal s)"
by( elim step_Normal_elim_cases)
    with f_step
    have "\<Gamma>\<turnstile> (c1, Normal s) \<rightarrow> \<dots>(\<infinity>)"
      apply (simp add: inf_def)
      apply (rule_tac x="\<lambda>i. f (Suc i)" in exI)
      by simp
    with hyp_c1 show False by simp
d
next
  case (CondFalse s b c2 c1)
  have b: "s \<notin> b" bycase(Skip s)thus ?case
  have hyp_c2: "\<not> \<Gamma>\<turnstile> (c2, Normal s) \<rightarrow> \<dots>(\<infinity>)" by fact
  show ?case
  proof (rule not_infI)
    fix f
    assume f_step: "\<And>i. \<           proof(rule )
    assume f_0 "  =(Cond  c1c2             uc)f i\>y,)amma>\>cs \rightarrow>\sup> xand\Gamma>\<> rightarrow\^>+}
    from bjava.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 4
    have "f 1 = (c2,Normal s)"
      by (auto elim: step_Normal_elim_cases)
    with f_step
    have "\<Gamma>\<turnstile> (c2, Normal s) \<rightarrow> \<dots>(\<infinity>)"
apply( add: inf_def)
 java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
      by simp
    with hyp_c2 show False by simp
  qed
next
  case (WhileTrue s b c)
  have b: "s \<in> b" by fact
  have hyp_c: "\<not> \<Gamma>\<turnstile> (c, Normal s) \<rightarrow> \<dots>(\<      apply (rule_tac x"\<lambdai.  ( i) inexI)
  have hyp_w: "  have g: "s \otin g" by 
     f_step: "<Andi.
  have not_inf_Seq: "\<not> \<Gamma>\<turnstile> (Seq c (While b c), Normal s) \<rightarrow> \<dots>(\<infinity>)"
  proof
    assume "\     rule not_inf_Fault
    from split_inf_Seq [F this] hyp_chyp_w  False

  qed
  show ?case
  proof
 ">\turnstile Whilec  s)\ghtarrow>\dots\infinity>"
    thenobtainf where
      f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)" and
f_0"(  p0) Call p "
      by (auto simp add: inf_def)
    from f_step [of 0] f_0 b
    have "f 1 = (Seq c (While b c),Normal s)"
      by (auto elim: step_Normal_elim_cases)
    with f_step
    have "\<Gamma>\<turnstile> (Seq c (While b c), Normal s) \<rightarrow> \<dots>(\<infinity>)"
     apply simp add:inf_def)
      apply                     ><>While  <>  <>\><>turnstile( cs)<> <dots>\infinity>)  
      by simp
    with not_inf_Seq   case ( c\<sub>1c<sub>)
  qed
next
  case (WhileFalse s b c)
  have b: "s \<notin> b" by fact
  show ?case

    fix f
    assume f_step: "\<And>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)"
    assume f_0: "f 0 = (While b c, Normal s)"
    from b f_step [of 0] f_0 f_step [of 1]
     False
      by (fastforce elim: Skip_no_step step_elim_cases
  qed
next
  case (Call p bdy s)
  "Gamma p  Somebdy by fact
  have hyp: "\<not> \<Gamma>\case(Specjava.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
  show ?case
  proof (rule not_infI)
    fix fby(induct       (fastforce elim Skip_no_step )
    assume f_step: "\<  case (eqc<sub> c<sub>2
 f0 = ( p,  s)"
    from bdy f_step [of 0] f_0
    have "f 1 = (bdy,Normal s)"
      by (auto elim: step_Normal_elim_cases)
    with f_step
    have "\<Gamma>\<turnstile> (bdy, Normal s) \<rightarrow> \<dots>(\java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
      apply (simp add: inf_def)
      apply (rule_tac x="\<lambda>i. f (Suc i)" in exI)
      bycase(Whilebc)
    with hyp show False by simp
  
next
  case (CallUndefined p s)
  have no_bdy: "\<Gamma> p = None" by fact
  show ?case
  proof (rule not_infI)
    fix f
 :"\Andi<><turnstile>fi  uardfg java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20
    assume f_0: "f 0 = (Call p, Normal s)"
    from no_bdy f_step [of 0] f_0 f_step [of 1]
    show java.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for length 14
      by fastforceelim: Skip_no_step step_elim_cases)
  qed
next
  case (Stuck c)
  show ?case
    by (rule not_inf_Stuck)
next
  case (DynCom c s)
  havesteps not_final java.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 27
  show ?case
   ( not_infI)
    fix f
    assumes hypjava.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
    assume f_0: "f  (induct c)
    from f_step [of 0] f_0
    have "f (Suc 0) = (c s, Normal s)"
java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
    with f_step have "<><>(c ,Normals \rightarrow>\<>\infinity)
      apply (simp add: inf_def)
      apply (rule_tac x="\<lambda>i. f (Suc i)" in exI)
by
    with hyp
    show False by simp
  qed
next
  case (Throw s) thus ?case
  ( not_infIjava.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23
    fix f
    assume f_step: "\show "<>frulenot_infI
    assume f_0: "f 0 = (Throw, Normal s)"
    from f_step [of 0] f_0
 False
byautoelim step_elim_cases
  qed
next
 (bruptc
  show ?case
    by (rule not_inf_Abrupt)
next
  case (Catch c\<^sub>1 s c\<^sub>2)
  show ?case
  proof
    assume "\<Gamma>\<turnstile> (Catch c\<^sub>1 c\<^sub>2, Normal s) \<rightarrow> \<dots>(\<infinity>)"
    from split_inf_Catch [OF this] Catch.hyps
    show False
      by (auto intro: steps_Throw_impl_exec)
  qed
qed


definition
  (s,pf Rightarrow(stimes p)case( java.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
f f_step[f0 f_0f_step of1
"termi_call_stepsby( :Skip_no_stepstep_elim_cases
 {((t,q),(s,p)). \<Gamma>\<turnstile>Call p\<down>Normal s \<and>
(existsc.Gammaturnstile>( pNormal)<>\<+ cNormal t)\nd c=)


::
where
"subst_redex Skipsteps_Throw_impl_exec [OF rest [simplifiedthis]]Normal
"subst_redex (Basic f) c = c" |
"subst_redex (Spec r) c = c" |
"subst_redex (Seq c\<^sub>1 c\<^sub>2) c  = Seq (subst_redex c\<^sub>1 c) c\<^sub>2" |
" Cond  c\<>1 \^sub>2)c ==c" f_0:f0= (d,Abrupt s"
"subst_redex (While b c') c = c" |
"subst_redex (Call p) c = c" |
" ( dd)c =  c" java.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32
"step"\<i \<>turnstilefi \rightarrow (uci"
"subst_redex (Throw) c = c" |
"subst_redex (Catch c\     by ( elim:  step_elim_cases

lemma subst_redex_redex:
  "subst_redex c (redex c) = c"
  by (induct c) auto

a redex_subst_redex "redex (subst_redex c r)  redexr"
  by (induct c) auto

lemma step_redex':
 \<amma><( c,)\< 's <>\>\(c)< subst_redex c''java.lang.StringIndexOutOfBoundsException: Index 143 out of bounds for length 143
by (induct c) (auto intro: step.Seq step.Catch)


lemma step_redex:
 <Gamma\<turnstile>(theorem:
by(nductc ( intro: stepSeqstepCatch)

lemma steps_redex:
  assumes steps: "\<Gamma>\<turnstile> (
row\^>*subst_redex c's'
using steps
proof  [of 0]java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
  case Refl
  show "\<Gamma>\<turnstile> (subst_redex c r', s') \<rightarrow>\<^sup>* (subst_redex c r', s')"
    by simp
next
  case (Trans r s r'' s'')
  have "\<Gamma>\<turnstile> (r, s) \<rightarrow> (r'', s'')" by fact
  from step_redex [OF this]
  have "\<Gamma>\<turnstile> (subst_redex c r, s) \<rightarrow> (subst_redex c r'', s'')".
  also
  have "\<Gamma>\<turnstile> (subst_redex c r'', s'') \<rightarrow>\<showFalse
  finally show ?case .
qed

  show by( stepDynCom)
  ML_Thms.bind_thm ("trancl_induct2", Split_Rule.split_rule @{context}
    (Rule_Instsjava.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
     [((a ) .none (a,ab", (("b,0,Positionproof cases"s\g"
      @{thm trancl_induct}));
\(rule_tac=<>.(Suci"inexIjava.lang.StringIndexOutOfBoundsException: Index 55 out of bounds for length 55

lemma steps_redex':
  assumes steps: "\<Gamma>\<turnstile> (r, s) \<rightarrow>\<^sup>+ (r', s')"
  shows "\<And>c. \<Gamma>\<turnstile>(subst_redex c r,s) \<rightarrow>\<^sup>+ (subst_redex c r',s')"
usingsteps
proof (induct rule: tranclp_induct2 [consumes 1,case_names Step Trans])
  case (Step r' s')
  have "\<Gamma>\<turnstile> (r, s) \<rightarrow> (r', s')" by fact
then  \<Gamma<turnstile(subst_redexc ,s <>  c r's)
    by (rule step_redex)
  then show "\<Gamma>\<turnstile> (subst_redex c r, s) \<rightarrow>\<^sup>+ (subst_redex c r', s')"..
next
  case (Trans r' s' r'' s'')
  have "\<Gamma>\<turnstile> (subst_redex c r, s) \<rightarrow>\<^sup>+ (subst_redex c r', s')" by fact
  also
  have "\<Gamma>\<turnstile> (rjava.lang.StringIndexOutOfBoundsException: Index 31 out of bounds for length 17
  hence "\<Gamma>\<turnstile> (subst_redex c r', s') \<rightarrow> (subst_redex c r'', s'')"
by (elim: )
  finally     "\<>\
qed

primrec          steps_c\<^sub>1"<amma\turnstile>  case(CondFalsesbc2 java.lang.StringIndexOutOfBoundsException: Index 28 out of bounds for length 28
where
"seq c by(uto simp add final_def)
         <Gamma\turnstile Catch\^> \^>,Normal ) <rightarrow> ( c'\^>   f_step: \nd>> i\rightarrow> (uc"


lemma renumber':
  assumes f: "\<forall>i.          show?thesis
  assumes a_b: "(a,b) \<in> r\<^sup>*"
  shows "b = f 0 \<Longrightarrow> (\<exists>f. f 0 = a \<and> (\<forall>i. (f i, f(Suc i)) \<in> rjava.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
using
proof (induct rule: converse_rtrancl_induct [consumes 1])
  assume "b = f 0"
  with f show "\<exists>f. f 0 = b \<and> (\<forall>i. (f i, f (Suc i)) \<in> r)"
    by blast
next
  fix a      f_0:"f0 (hilec, s)
  assume a_z:fromf_step of0]f_0 java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
  assume "b = f 0 \<Longrightarrow> \<exists>    show ?thesis
         "b = f 0"
  then obtain f where f0: "f 0 = z" and seq: "\<forall>i. (f i, f (Suc i)) \<in> r"
    by iprover
  {
    fix i have "((\<lambda>i. case i of 0 \<Rightarrow> a | Suc i \<Rightarrow> f i) i, f i) \<in> r"
      using seq a_z f0
      by (cases i) auto
  }
  then
(************************havehyp\>\<>turnstile(,Normals \<ightarrow\>\)  fact
    by - (rule exI [where x="\<lambda>i. case i of 0 \<Rightarrow> a | Suc i \<Rightarrow> f i"],simp)
qed

lemma renumber:
 \forall.fi\in> \sup>\>f,(uc)\injava.lang.StringIndexOutOfBoundsException: Index 67 out of bounds for length 67
 \<Longrightarrow> \<exists>f. f 0 = a \<and> (\<forall>i. (f i, f(Suc i)) \<in> r)"
  by (blast dest:renumber')

  f_0f_step [ ]
  "\<forall>y. r\<^sup>+\<^sup>+ a y \<longrightarrow> P a \<longrightarrow> P y
ongrightarrow ((,a) \in> {(,x. P  <and rxy\^sup>+)  ((ba)<in {(,) P \and \<sup+<sup> xy}"
apply(rule iffI)
 apply clarify
 apply(erule trancl_induct)
  apply blast
 apply(blast intro:tranclp_trans)
 
apply(erule tranclp_induct)
 apply blast
apply(blast intro:trancl_trans)
done

corollary terminates_impl_no_infinite_trans_computation:
 assumes terminates: "\<Gamma>\<turnstile>c\<down>s"
 shows "\<not>(\<exists>f. f 0 = (c,s) \<and> (\<forall>i. \<Gamma   Transhyps () [OFr']
proof -
  have "wf({(y,x). \<Gamma>\<turnstile>(c,s) \<rightarrow>\<^sup>* x \<and> \<Gamma>\<turnstile>x \<rightarrow> y}\<^sup>+)"
  proof (rule wf_trancl)
    show "wf {(y, x). \<Gamma>\<turnstile>(c,s) \<rightarrow>\<^sup>* x \<and> \      apply: \>\turnstile(,)<<up r sjava.lang.StringIndexOutOfBoundsException: Index 77 out of bounds for length 77
    proof    by simp
      fix f
assume"<forall>.      by(: )
      hence "\<exists>f. f (0::nat) = (c,s) \<and> (\<forall>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i))"
        by (rule renumber [to_pred])
      moreover from terminates_impl_no_infinite_computation split_inf_Catch [OF this Catch.hyps
      have "\<not> (\<exists>f. f (0::nat) = (c, s) \<and> (\<forall>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)))"
        > \Gamma\turnstile( pNormal ) \rightarrow>\<sup>+ (c, t) <{thm trancl_induct};
      ultimately show False
        by simp
    qed
  
  hence "\<not> (\<exists>f. \<forall>i. (f (Suc i), f i)
                 \<in> {(y, x). \<Gamma>\<turnstile>(c, s) \<rightarrow>\<^sup>* x \<and> \<Gamma>    by (rule step_redex)
    by (simp add: wf_iff_no_infinite_down_chain)
  thus ?thesis
  proof (rule contrapos_nn)
    assume "\<exists>f. f (0::nat) = (c, s)  "\<amma>< (subst_redex r,)<rightarrow> (subst_redex  '', s'')"
    thenobtainf where
      f0: "f 0 = (c, s)" and
      seq: "\<forall>i. \<Gamma>\lemma steps_redex:
       iprover
    
        show "\<Gamma><turnstile> (subst_redex cr', s)\rightarrow>\^>* (subst_redex  r,'"
proof(ule exI [wherexf], allI)
      fix i
      show "(f (Suc i), f i) \<in> {(y, x). \<Gamma>\<turnstile>(c, s) \<rightarrow>\<^sup>* x \<and> \<Gamma>\<turnstile>x \<rightarrow> y}\<^sup>+"
      proof -
        {
          fixjava.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
          proof (induct i)
             0show  then
              by (simp add: f0)
          next
            case (Suc n)
             rule
            with seq show "\<Gamma>\<turnstile>(c, s) \<rightarrow>\<^sup>* f (Suc n)"
              by(blast intro:tranclp_into_rtranclp rtranclp_trans)
          qed
        }
        hence "\<Gamma>\<turnstile>(c,s) \<rightarrow>\<^sup>* f i"
          by iprover
        with seq have
          "(f (Suc i), f i) \<in> {(y, x). \<Gamma>\<turnstile>(c, s) \<rightarrow>\<^sup>* x \<and>\Gamma><> \rightarrow><>y"
          by clarsimp
        moreover
        have terminates_impl_no_infinite_trans_computation
          by (blast intro: tranclp_into_rtranclp rtranclp_trans)
        ultimately
        show ?thesis
          by (subst lem )
      qed
    qed
  qed


theorem wf_termi_call_steps: "wf (termi_call_steps \<Gamma>)"
proof (simp only: termi_call_steps_def wf_iff_no_infinite_down_chain,
       clarify,simp)
  fix: "Gamma\<>c<owns"
  assume inf: "\<forall>i. (\<lambda>(t, q) (s, p).
                \<Gamma>\<turnstile>Call p \<down> Normal s \<and>
(exists.\Gamma><>Call,Normal     simp :wf_iff_no_infinite_down_chain
(f fixf
  define s where "s i = fst (f i)" for i :: nat
    i =snd(f:)for i:nat
 inf
have':forall.\Gamma\>allpi <downNormal ((s) \<>
               (\<exists>c. \<Gamma>\<turnstile> (Call (p i), Normal (s i)) \<rightarrow>\<^sup>+ (c, Normal (s (i+1  hence<not>(<exists>. <forall>i.(    (uleexI [ f]rule)
                    redex c = Call show
    apply -
    apply (rule allI)
    apply (erule_tac x=i in             java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 13
    apply 
    done

  proof -
    from inf'
    have "\<exists>c. \<forall>i. \<Gamma>\<turnstile>Call (p i) \<down> Normal (s i          by iprover
               \<Gamma>\<turnstile> (Call (p i), Normal (s i)) \<rightarrowhave"<forall>y \><turnstile>  <rightarrow><sup>+y\longrightarrow\Gamma>turnstile(c s)\          subst  
                    redex (c i) = Call (p (i+1))"
      apply -
      apply (rule choice)
      by blast
    then obtain c where
      termi_c: "\<forall>i. \<Gamma>\<turnstile>Call (p i)             f ( i))(fi)java.lang.StringIndexOutOfBoundsException: Index 31 out of bounds for length 31
      steps_c: "\<forall>i. \  define s where "s   fst (f i)" for i :: nat
      red_c:   "\<forall>i. redex (c i) = Call (p (i+1))"
      by auto
    define g where "g i = (seq c (p 0) i,Normal (s i)::('a,'c) xstate)" for i
    from red_c [rule_format, of 0]
    have "g 0 = (Call (p 0), Normal (s 0))"
      by (simp add: g_def)
    moreover
    {
      fix i
      have "redex (seq c (p 0) i) = Call (p i)"
        by (induct i) (auto simp add: redex_subst_redex red_c)
      from this [symmetric]
      have "subst_redex (seq c (p 0      termi_c "\<forall>.<Gamma>> (pi <>Normalfix i
        by (simp add:
    } note subst_redex_seq = this
      "Gamma>\>( i) \rightarrow\<sup+g(i1))
    proof
fixi
      from steps_c[rule_format,  ijava.lang.StringIndexOutOfBoundsException: Index 38 out of bounds for length 38
      have "\<Gamma>\<turnstile> (Call (p i), Normal (s i)) \<rightarrow>\<^sup>+ (c i, Normal (s (i + 1)))".
      from        "<>< subst_redexc p) )Calli)Normals) <>\sup>
      have "\<Gamma>\<turnstile> (subst_redex (seq c (p 0) i) (Call (p i)), Normal (s i)) \<rightarrow>\<^by( : inf_defjava.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
                (subst_redex (seq c (p 0) i) (c i), Normal (s (i + 1)))" .
      hence "\<Gamma>\<turnstile> (seq c (p 0) i, Normal (s i)) \<rightarrow>\<^sup>+
                 (seq c (p 0) (i+1> <exists>c s'java.lang.StringIndexOutOfBoundsException: Index 120 out of bounds for length 120
bysimp add:subst_redex_seq)
      thus "\<Gamma>\<turnstile> (g i) \<rightarrow>\<^sup>+ (g (i+1))"
        by (simp add: g_def)
        by (cases "final(c\^sub>1,Normal s)) (fastforceintro step.ntrossimp:final_def+
moreover
    from terminates_impl_no_infinite_trans_computation [OF termi_c [rule_format, of 0]]
    have "\<not> (\<exists>f. f 0 = (Call (p 0), Normal (s 0)) \<and> (\<forall>i. \<Gammajava.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 18
    ultimately show False
      by auto
  qed
qed


lemma no_infinite_computation_implies_wf:
  assumesal_termi:
  shows "wf {(c2,c1). \<Gamma> \<turnstile> (c,s) \<rightarrow>\<^sup>* c1 \<and> \<Gamma> \<turnstile> c1 \<rightarrow> c2}"
proof (simp only: wf_iff_no_infinite_down_chain,clarify, simp)
  fix by cases "<>.  induct converse_rtranclp_induct2 [case_names Transjava.lang.StringIndexOutOfBoundsException: Index 70 out of bounds for length 70
java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
  hence "\<exists>f. f 0 = (c, s) \<and> (\<forall>i. \<Gamma
  [to_pred]java.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32
  moreover from not_inf
  have "\<not> (\<exists>f. f 0 = (c, s) \<and> (\<forall>i. \<Gamma>\<turnstile>f i \<rightarrow> f (Suc i)))"
     simp add inf_def)
  ultimately show False
     
qed

lemma not_final_Stuck_step: "\<not> final (c,Stuck) \<Longrightarrow> \<exists>c' s'. \<Gamma>\<turnstile> (c, Stuck) \<rightarrow>by    
bylemma         java.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 10

lemmasplit_computation
  "\<not> final (c,Abrupt s) \<Longrightarrow> \<exists>c' s'. \
by c (fastforce :step.intros simpaddassumes Gamma\<r ightarrow ,'java.lang.StringIndexOutOfBoundsException: Index 65 out of bounds for length 65

lemma not_final_Fault_step:
  "\<not> final (c,Fault f) \<Longrightarrow> \<exists>c' s'. \<Gamma>\<turnstile> (c, Fault f) \<rightarrow> (c',s')"
by (induct c) (fastforce intro: step.intros simp add: final_def)+

lemma not_final_Normal_step:
          thus "\<Gamma>\<turnstilec'<> ss'
proof (induct c)
  case Skip thus ?case by (fastforce intro: step.intros simp add: final_def)
next
   Basic thus ?case by fastforceintro: step.intros)
next
  case (Spec r)
  thus ?case
    by (cases "\<exists>t. (,t) \inr") (fastforce intro: step.intros)+
next
  case (Seq c\<^sub>1 c\<^sub>2)
  thus?case
    by (cases "final (c\<^sub>1,Normal s)") (fastforce intro: step.intros simp add: final_def)+
next
  case (Cond b c1 c2)
  
     "s<>) fastforceintro stepintros+
next
  case (While b c)
  show ?case
    by (cases "s \<in> b") (fastforce intro: step.intros)+
java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
  case (Call p)
  show ?case
  by (cases "\<Gamma>p" (fastforce intro: step.intros)+
next
     (ynComcjava.lang.StringIndexOutOfBoundsException: Index 17 out of bounds for length 17
next
  case (Guard f g c)
  show ?case
    by (cases "s \<in> g") (fastforce  case (Guard f g c)
next
  lemma wf_implies_termi_reach
   ?case by fastforceintro: step.intros simp add final_def)
next
  case (Catch c\<^sub> c<^sub>2
  thus ?case
    by hypp:<>c2 s2. \<Gamma>\<turnstile> (c1, s1) < (c2, s2) \<Longrightarrow> \<Gamma>\<turnstile>c2 \<down> s2"
qed

lemma final_termi:
"final (c,s) \<Longrightarrow> \<Gamma>\<turnstile>c\<down>s"
  by (cases s) (auto simp add: final_def terminates.intros)


lemma split_computation
assumes steps: "\<Gamma>\<turnstile> (c, s) \<rightarrow>\<^sup>* (c\<^sub>f, s\<^sub>f)"
assumes not_final "<>finalalc,"
assumes final: "final (c\<^sub>f,s\<^sub>f)c\<^sub>2<down> '.
shows "\<exists>c' s'. \<Gamma>\<turnstile> (c, s) \<rightarrow> (c',s') \<and> \<Gamma>\<turnstile> (c', s') \<rightarrow>\<^sup>* (c\<^sub>f, s\<^sub>f)"
using steps not_final final
proof (induct rule: converse_rtranclp_induct2 [case_names Refl Trans])
  case Refl thus ?case by simp
ext
  case (Trans c      "<Gamma>turnstile>c\<^sub>2 \<down> Normal s'"
  thus ?case by auto
qed

lemma wf_implies_termi_reach_step_case:
assumes hyp: "\<And>c' s'. \<Gamma>\<turnstile> (c, Normal s) \<rightarrow> (c', s') \<Longrightarrow> \<Gamma>\<turnstile>c' \<down> s'"
shows "\<Gamma>\<turnstile>c \<down> Normal s"
using hyp
proof (induct c)
  case Skip show ?case by (fastforce intro: terminates.intros)
next
  sesicow? (tforceeroatesros)
next
  case (Spec r)
  show?case
    by (cases "\<exists>t. (s,t)\<in>r") (fastforce intro: terminates.intros)+
next
  case (Seq c\<^sub>1 c\<^sub>2)
  have hyp: "\<And>c' s'. \<Gamma>\<turnstile> (Seq c^sub>1 c\<^sub>2, Normal s) \<rightarrow> ( hyp [OF this]
  show ?case
  proof (rule terminates.Seq)
    {
      fix c' s'
      assume step_c\<^sub>    yps)[ step_r_is
      have "\<Gamma>\<turnstile>c' \<down> s'"
      proof -
        from step_c\<^sub>1
        have "\<Gamma>\<turnstile> (Seq c\<^sub>1 c\<^sub>2, Normal s) \<rightarrow> (Seq c' c\<^sub>2, s')"
          by (rule step.Seq)
        from hyp [OF thiscaseall sase
        have "\<Gamma>\<turnstile>Seq c' c\<^sub>2 \<down> s'".
        thus "\<Gamma>\<turnstile>c'\<down> s'"
          by cases auto
      qed
    }
    from Seq.hyps (1) [OF this]
    show "\<Gamma>\<turnstile>java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
  next
    show "\<forall>s'. \<Gamma>\<turnstile> \<langle>c\<^sub>1,Normal s\<rangle> Rightarrow s' \<longrightarrow> \<Gamma>\<turnstile>c\<^sub>2 \<down> s'"
     (intro allI impI)
      fix s'
      assume exec_c\<^sub>1: "\java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
      show "\<Gamma>\<turnstile>c\<sub>2 \down> '"
      proof (cases "final (c\<^sub>1,Normal s)")
        case True
        hence "\^sub1Skip \<or> c\<^sub>1=Throw
          by (simp add: final_def)
        thus ?thesis
        proof
          assume Skip: "c\<^sub>1 ?case
          have "\<Gamma>\<turnstile>(Seq Skip c\<^sub>2,Normal s) \<rightarrow> (c\<^sub>2,Normal s)"
            by (rule step.SeqSkip)
          from hyp [simplified Skip, OF this]
          have "\<Gamma>\<turnstile>c\<sub>2 <own Normals" .
          moreover from exec_c\<^sub>1 Skip
          have "s'=Normal s"
            by (auto elim: exec_Normal_elim_cases)
          ultimately show ?thesis by simp
        next
          assume Throw: "c\<^sub>1=Throw"
          with exec_c\<^sub>1 have "s'=Abrupt s"
            by (auto elim: exec_Normal_elim_cases)
          thus ?thesis
            by auto
        qed
      next
        case False
        from exec_impl_steps [OF exec_c\<^sub>1]
        obtain c\<^sub>java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
         \^sub1: "Gamma>\<turnstile\^sub1Normalmall) ightarrow^*(\^f) and
          fin:"(case s' of
                 Abrupt x \<Rightarrow> c\<^sub>f = Throw \<and> t = Normal x
                | _ \<Rightarrow> c\<^sub>f = Skip \<and> t = s')"
          by (fastforce split: xstatelemmaredex_redexes \<And>c'.  steps
        with fin have final: "final (c\<^sub>f,t)"
          by (cases s') (auto simp add: final_def)
        from split_computation [OF steps_c\<^sub>1 java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
        obtain c'' s'' where
          first: "\<Gamma>\<turnstile> (c\<^sub>1, Normal s) \<rightarrow> (c'', s'')" and
          rest: "\<Gamma>\<turnstile> (c'', s'') \<rightarrow>\<^sup>* (c Seq: "  <^sub <in xesc
          by blast
        from step.Seq [OF first]
        have "\<\turnstile> (Seq c\<^sub>1 c\<^sub>2, Normal s) \<rightarrow> (Seq c'' c\<^sub>2, s'')".
        from hyp [OF this]
        have termi_s'': "\<Gamma>\<turnstile>Seq c'' c\<^sub>2hence r: "r= Seq c\<^sub>1 c\<^sub>2 \<or> r \<in> redexes1"
        show ?thesis
        f(ses java.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
          case (Normal x)
          from termi_s'' [simplified Normal]
          have termi_c\^sub2"<forall>t<Gamma\<nstilele>langleormalalrangle\<Rightarrow> t \<longrightarrow> \<Gamma>\<turnstile>c\<^sub>2 \<down> t"
            by cases
          show ?thesis
           cases<xs'uptx)
            case False
            with fin obtain "c\<^sub>f=Skip" "t=s'"
              by (cases s') auto
            from steps_Skip_impl_exec [OF rest [simplified this]] Normal
            have "\<Gamma>\<turnstile> \<langle>c'',Normal x\<rangle> \<Rightarrow> s'"
              by (induct rule: tranclp_induct2 [ 1, case_names Step Trans])
            from termi_c\<^sub>2 [rule_format, OF this]
             "\<Gamma>\<turnstile>c\<^java.lang.StringIndexOutOfBoundsException: Index 61 out of bounds for length 61
          next
            case True
            with fin obtain x' where s': "s'=Abrupt x'" and "c\<^sub>f=Throw" "t=Normal x'"
              by auto
                    from steps_Throw_impl_exec [OF rest [simplified this]] Normal
            have "\<Gamma>\<turnstile> \<langle>c'',Normal x\<rangle> \<Rightarrow> Abrupt x'"
              by simp
            from termi_c\<^sub>2 [rule_format, OF this] s'
            show "\<Gamma>\<turnstile>c\<^sub>2 \<down> s'" by simp
          qed
        next
          case (Abrupt x)
          from steps_Abrupt_prop [OF rest this]
          have "t=Abrupt x" by simp
          with fin have "s'=Abrupt x"
            
          thus "\<Gamma>\<turnstile>c\<^sub>2 \<down> s'"
            by auto
        next
          case (Fault f)
          from steps_Fault_prop [OF rest this]
          have "t=Fault f" by simp
          with fin have "s'=Fault f"
            by (cases s') auto
          thus "\<Gamma>\<turnstile>c\<^sub>2 \<down> s'"
            
        next
          case Stuck
          from steps_Stuck_prop [OF rest 
          have "t=Stuck" by simp
          with fin have "s'=Stuck"
            by (cases s') auto
          thus "\<Gamma>\<turnstile>c\<^sub>2 \<down> s'"
            by auto
        qed
      qed
    qed
  qed
next
  case (Cond b c\<^sub>1 \^sub>2)
  have hyp: "\<And>c'\Gamma\<turnstile> (Cond bcsub1 c\<^sub>2, Normal s) \<rightarrow> (c', )\Longrightarrow \<Gamma>\<turnstile>c' \<down>' fact
  show ?
  s<inb")
    case True
    then have "\<Gamma>\<turnstile> (Cond b c\<^sub>1 c\<^sub>2rmal  \rightarrow (c\<^sub>1, Normal
      by (rule step.CondTrue)
    from hyp [OF this] have "\<Gamma>\<turnstile>c\<^sub>1 \<down> Normal s".
    with True show ?thesis
      by (auto intro: terminates.intros)
  next
    case False
    then have "<Gamma><turnstile> (Cond b<^ub>1 c\<^sub>2, Normal s) \<rightarrow> (c\<^sub>2, Normal s)"
      by (rule step.CondFalse)
    from hyp [OF this] have "\<Gamma>\<turnstile>c\<^sub>2 \<down> Normal s".
    with False show ?thesis
      by (auto intro: terminates.intros)
  qed
next
  case (While b c)
  have hyp: "\<And>c' s'. \<Gamma>\<turnstile> (While b c, Normal s) \<rightarrow> (c', s') \<Longrightarrow> \<Gamma>\<turnstile>c' \<down> s'" by fact
ow?e
  proofntroteproslimtep_elim_casesdoot_in_redexesedexes
    case True
    then have "\<Gamma>\<turnstile> (While b c, Normal s) \<rightarrow> (Seq c (While b c, 
      by (rule step.WhileTrue)
    fromyp[Fis]e\<>\<>(Seq c ( b ) <>Normals.
    with True show ?thesis
      by (auto elim: terminates_Normal_elim_cases intro: terminates.intros)
  next
    case False
    thus ?thesis
      by (auto intro: terminates.intros)
  qed
next
  case (Call p)
  have hyp: "\<And>c' s'. \<Gamma>\<turnstile> (Call p, Normal s) \<rightarrow> (c', s') \<Longrightarrow> \<Gamma>\<turnstile>c' \<down> s'" by fact
  show ?case
  proof (cases "\<Gamma> p")
    case None
    thus ?thesis
      by (auto intro: terminates.intros)
  next
    case (Some bdy)
    then have "\<Gamma>\<turnstile> (Call p, Normal s) \<rightarrow> (bdy, Normal s)"
      by (rule step.Call)
    from hyp [OF this] have "\<Gamma>\<turnstile>bdy \<down> Normal s".
   sis
      by (auto intro: terminates.intros)
  qed
next
  case (DynCom c)
  have hyp: "\<And>c' s'. \<Gamma>\<turnstile> (DynCom c, Normal s) \<rightarrow> (c', s') \<Longrightarrow> \<Gamma>\<turnstile>c' \<down> s'" by fact
  have "\<Gamma>\<turnstile> (DynCom c, Normal s) proofinduct rulenclp_induct2p_induct2consumesnsumes ase_namestep ans]
    by (rule step.DynCom)
  from hyp [OF this] have "\<Gamma>\<turnstile>c sbylasttro _nto_trancl
  then show ?case
    by (auto intro: terminates.intros)
next
  case (Guard f g c)
  have hyp: "\<And>c' s'. \<Gamma>\<turnstile> (Guard f   Normal s) \<rightarrow> (c', s')\Longrightarrow <\<turnstile>c' \<down> s" fact
  show ?case
  proof (cases "s\<in>g")
    case True
    then have "\<Gamma>\<turnstile> (Guard f g c, Normal s) \<rightarrow> (c, Normal s)"
      by (rule step.Guard)
    from hyp [OF this] have "\<Gamma>\<turnstile>c\<down> Normal s".
    with True showhesiss
      by (auto intro: terminates.intros)
  next
    case False
    thus ?thesis
      by (auto intro: terminates.intros)
  qed
next
  case Throw show ?case by (auto intro: terminates.intros)
next
  case (Catch c\<^sub>1 c\<^sub>2)
  have hyp: "\<And>c' s'. \<Gamma>\<turnstile> (Catch c\<^sub>1 c\<^sub>2, Normal s) \<rightarrow> (c', s') \<Longrightarrow> \<Gamma>\<turnstile>c' \<down> s'" by fact
  show ?case
  proof (rule terminates.Catch)
    {
      fix c' s'
      assume step_c\<^sub>1: "\<Gamma>\<turnstile> (c\<^sub>1, Normal s) \<rightarrow> (c', s')"
      have "\<Gamma>\<turnstile>c' \<down> s'"
      proof -
        from step_c\<^sub>1
        have "\<Gamma>\<turnstile> (Catch c\<^sub>1 c\<^sub>2, Normal s) \<rightarrow> (Catch c' c\<^sub>2, s')"
          by (rule step.Catch)
        from hyp [OF  this]
        have "\<Gamma>\<turnstile>Catch c' c\<^sub>2 \<down> s'".
        thus "\<Gamma>\<turnstile>c'\<down> s'"
          by cases auto
      qed
    }
    from Catch.hyps (1) [OF this]
    show "\<Gamma>\<turnstile>c\<^sub>1 \<down> Normal s".
  next
    show "\<forall>s'. \<Gamma>\<turnstile> \<langle>c\<^sub>1,Normal s\<rangle> \<Rightarrow> Abrupt s' \<longrightarrow> \<Gamma>\<turnstile>c\<^sub>2 \<down> Normal s'"
    proof (intro allI impI)
      fix s'
      assume exec_c\<^sub>1: "\<Gamma>\<turnstile> \<langle>c\<^sub>1,Normal s\<rangle> \<Rightarrow> Abrupt s'"
      show "\<Gamma>\<turnstile>c\<^sub>2 \<down> Normal s'"
      proof (cases "final (c\<^sub>1,Normal s)")
        case True
        with exec_c\<^sub>1
        have Throw: "c\<^sub>1=Throw"
          by (auto simpsimpadd: final_def elim:exec_Normal_elim_cases)
        have "\<Gamma>\<turnstile>(Catch Throw c\<^sub>2,Normal s) \<rightarrow> (c\<^sub>2,Normal s)"
          rulep.atchThrowThrowrow
        from hyp [simplified Throw, OF this]
        have "\<Gamma>\<turnstile>c\<^sub>2 \<down> Normal s".
        moreover from exec_c\<^sub>1 Throw
        have "s'=s"
          by (auto elim: exec_Normal_elim_cases)
        ultimately show ?thesis by simp
      next
        case False
        from exec_impl_steps [OF exec_c\<^sub>1]
        obtain c\<^sub>f t where
          steps_c\<^sub>1: "\<Gamma>\<turnstile> (c\<^sub>1, Normal s) \<rightarrow>\<^sup>* (Throw, Normal s')"
          by (fastforce split: xstate.splits)
        from split_computation [OF steps_c\<^sub>1 False]
        obtain c'' s'' where
          first: "\<Gamma>\<turnstile> (c\<^sub>1, Normal s) \<rightarrow> (c'', s'')" and
          rest: "\<Gamma>\<turnstile> (c'', s'') \<rightarrow>\<^sup>* (Throw, Normal s')"
          by (auto simp add: final_def)
        from step.Catch [OF first]
        have"<Gamma>\<turnstile(Catch\^sub1 c\sub2Normal s) <rightarrow> (Catchc c\<sub>,s')".
        from hyp [OF this]
        have "\<Gamma>\<turnstile>Catch c'' c\<^sub>2 \<down> s''".
        
        from steps_Throw_impl_exec [OF rest]
        have "\<Gamma>\<turnstile> \<langle  note steps
        moreover
        from rest obtain x where "s''=Normal x"
          by (cases s'')
             (auto dest: steps_Fault_prop steps_Abrupt_prop steps_Stuck_prop)
        ultimately show ?thesis
          by (fastforce elim: terminates_elim_cases)
      qed
qed
  qed
qed

lemma wf_implies_termi_reach:
assumes wf: "wf {(cfg2,cfg1). \<Gamma> \<turnstile> (c,s) \<rightarrow>\<^sup>* cfg1 \<and> \<Gamma> \<turnstile> cfg1 \<rightarrow> cfg2}"
shows "\<And>c1 s1. \<lbrakk>\<Gamma> \<turnstile> (c,s) \<rightarrow>\<^sup>* cfg1;  cfg1=(c1,s1)\<rbrakk>\<Longrightarrow> \<Gamma>\<turnstile>c1\<down>s1"
using wf
proof (induct cfg1, simp)
  fix c1 s1
  assume reach: "\<Gamma>\<turnstile> (c, s) \<rightarrow>\<^sup>* (c1, s1)"
  assume hyp_raw: "\<And>y c2 s2.
           \<lbrakk>\<Gamma>\<turnstile> (c1, s1) \<rightarrow> (c2, s2); \<Gamma>\<turnstile> (c, s) \<rightarrow>\<^sup>* (c2, s2); y = (c2, s2)\<rbrakk>
           \<Longrightarrow> \<Gamma>\<turnstile>c2 \<down> s2"
  have hyp: "\<And>c2 s2. \<Gamma>\<turnstile> (c1, s1) \<rightarrow> (c2, s2) \<Longrightarrow> \<Gamma>\<turnstile>c2 \<down> s2"
    apply -
    apply (rule hyp_raw)
    apply   assumption
    using reach
    apply  simp
    apply (rule refl)
    done

  show "\<Gamma>\<turnstile>c1 \<down> s1"
  proof (cases s1)
    case (Normal s1')
    with wf_implies_termi_reach_step_case [OF hyp [simplified Normal]]
    show ?thesis
      by auto
  qed (auto intro: terminates.intros)
qed

theorem no_infinite_computation_impl_terminates:
  assumes not_inf: "\<not> \<Gamma>\<turnstile> (c, s) \<rightarrow> \<dots>(\<infinity>)"
  shows "\<Gamma>\<turnstile>c\<down>s"
proof -
  from no_infinite_computation_implies_wf [OF not_inf]
  have wf: "wf {(c2, c1). \<Gamma>\<turnstile>(c, s) \<rightarrow>\<^sup>* c1 \<and> \<Gamma>\<turnstile>c1 \<rightarrow> c2}".
  show ?thesis
    by (rule wf_implies_termi_reach [OF wf]) auto
qed

corollary terminates_iff_no_infinite_computation:
  "\<Gamma>\<turnstile>c\<down>s = (\<not> \<Gamma>\<turnstile> (c, s) \<rightarrow> \<dots>(\<infinity>))"
  apply (rule)
  apply  (erule terminates_impl_no_infinite_computation)
  apply (erule no_infinite_computation_impl_terminates)
  done

(* ************************************************************************* *)
subsection ‹Generalised Redexes›
(* ************************************************************************* *)

text ‹
  an important lemma for the completeness proof of the Hoare-logic for
  correctness we need a generalisation of @{const "redex"} that not only
  the redex itself but all the enclosing statements as well.
 ›

primrec redexes:: "('s,'p,'f)com ==> ('s,'p,'f)com set"
where
"redexes Skip = {Skip}" |
"redexes (Basic f) = {Basic f}" |
"redexes (Spec r) = {Spec r}" |
"redexes (Seq c₁ c₂) = {Seq c₁ c₂} ∪ redexes c₁" |
"redexes (Cond b c₁ c₂) = {Cond b c₁ c₂}" |
"redexes (While b c) = {While b c}" |
"redexes (Call p) = {Call p}" |
"redexes (DynCom d) = {DynCom d}" |
"redexes (Guard f b c) = {Guard f b c}" |
"redexes (Throw) = {Throw}" |
"redexes (Catch c₁ c₂) = {Catch c₁ c₂} ∪ redexes c₁"

lemma root_in_redexes: "c ∈ redexes c"
  apply (induct c)
  apply auto
  done

lemma redex_in_redexes: "redex c ∈ redexes c"
  apply (induct c)
  apply auto
  done

lemma redex_redexes: "∧c'. [c' ∈ redexes c; redex c' = c'] ==> redex c = c'"
  apply (induct c)
  apply auto
  done

lemma step_redexes:
  shows "∧r r'. [Γ⊨(r,s) → (r',s'); r ∈ redexes c]
  ==> ∃c'. Γ⊨(c,s) → (c',s') ∧ r' ∈ redexes c'"
proof (induct c)
  case Skip thus ?case by (fastforce intro: step.intros elim: step_elim_cases)
next
  case Basic thus ?case by (fastforce intro: step.intros elim: step_elim_cases)
next
  case Spec thus ?case by (fastforce intro: step.intros elim: step_elim_cases)
next
  case (Seq c₁ c₂)
  have "r ∈ redexes (Seq c₁ c₂)" by fact
  hence r: "r = Seq c₁ c₂ ∨ r ∈ redexes c₁"
    by simp
  have step_r: "Γ⊨ (r, s) → (r', s')" by fact
  from r show ?case
  proof
    assume "r = Seq c₁ c₂"
    with step_r
    show ?case
      by (auto simp add: root_in_redexes)
  next
    assume r: "r ∈ redexes c₁"
    from Seq.hyps (1) [OF step_r this]
    obtain c' where
      step_c₁: "Γ⊨ (c₁, s) → (c', s')" and
      r': "r' ∈ redexes c'"
      by blast
    from step.Seq [OF step_c₁]
    have "Γ⊨ (Seq c₁ c₂, s) → (Seq c' c₂, s')".
    with r'
    show ?case
      by auto
  qed
next
  case Cond
  thus ?case
    by (fastforce intro: step.intros elim: step_elim_cases simp add: root_in_redexes)
next
  case While
  thus ?case
    by (fastforce intro: step.intros elim: step_elim_cases simp add: root_in_redexes)
next
  case Call thus ?case
    by (fastforce intro: step.intros elim: step_elim_cases simp add: root_in_redexes)
next
  case DynCom thus ?case
    by (fastforce intro: step.intros elim: step_elim_cases simp add: root_in_redexes)
next
  case Guard thus ?case
    by (fastforce intro: step.intros elim: step_elim_cases simp add: root_in_redexes)
next
  case Throw thus ?case
    by (fastforce intro: step.intros elim: step_elim_cases simp add: root_in_redexes)
next
  case (Catch c₁ c₂)
  have "r ∈ redexes (Catch c₁ c₂)" by fact
  hence r: "r = Catch c₁ c₂ ∨ r ∈ redexes c₁"
    by simp
  have step_r: "Γ⊨ (r, s) → (r', s')" by fact
  from r show ?case
  proof
    assume "r = Catch c₁ c₂"
    with step_r
    show ?case
      by (auto simp add: root_in_redexes)
  next
    assume r: "r ∈ redexes c₁"
    from Catch.hyps (1) [OF step_r this]
    obtain c' where
      step_c₁: "Γ⊨ (c₁, s) → (c', s')" and
      r': "r' ∈ redexes c'"
      by blast
    from step.Catch [OF step_c₁]
    have "Γ⊨ (Catch c₁ c₂, s) → (Catch c' c₂, s')".
    with r'
    show ?case
      by auto
  qed
qed

lemma steps_redexes:
  assumes steps: "Γ⊨ (r, s) →^* (r', s')"
  shows "∧c. r ∈ redexes c ==> ∃c'. Γ⊨(c,s) →^* (c',s') ∧ r' ∈ redexes c'"
using steps
proof (induct rule: converse_rtranclp_induct2 [case_names Refl Trans])
  case Refl
  then
  show "∃c'. Γ⊨ (c, s') →^* (c', s') ∧ r' ∈ redexes c'"
    by auto
next
  case (Trans r s r'' s'')
  have "Γ⊨ (r, s) → (r'', s'')" "r ∈ redexes c" by fact+
  from step_redexes [OF this]
  obtain c' where
    step: "Γ⊨ (c, s) → (c', s'')" and
    r'': "r'' ∈ redexes c'"
    by blast
  note step
  also
  from Trans.hyps (3) [OF r'']
  obtain c'' where
    steps: "Γ⊨ (c', s'') →^* (c'', s')" and
    r': "r' ∈ redexes c''"
    by blast
  note steps
  finally
  show ?case
    using r'
    by blast
qed



lemma steps_redexes':
  assumes steps: "Γ⊨ (r, s) →⁺ (r', s')"
  shows "∧c. r ∈ redexes c ==> ∃c'. Γ⊨(c,s) →⁺ (c',s') ∧ r' ∈ redexes c'"
using steps
proof (induct rule: tranclp_induct2 [consumes 1, case_names Step Trans])
  case (Step r' s' c')
  have "Γ⊨ (r, s) → (r', s')" "r ∈ redexes c'" by fact+
  from step_redexes [OF this]
  show ?case
    by (blast intro: r_into_trancl)
next
  case (Trans r' s' r'' s'')
  from Trans obtain c' where
    steps: "Γ⊨ (c, s) →⁺ (c', s')" and
    r': "r' ∈ redexes c'"
    by blast
  note steps
  moreover
  have "Γ⊨ (r', s') → (r'', s'')" by fact
  from step_redexes [OF this r'] obtain c'' where
    step: "Γ⊨ (c', s') → (c'', s'')" and
    r'': "r'' ∈ redexes c''"
    by blast
  note step
  finally show ?case
    using r'' by blast
qed

lemma step_redexes_Seq:
  assumes step: "Γ⊨(r,s) → (r',s')"
  assumes Seq: "Seq r c₂ ∈ redexes c"
  shows "∃c'. Γ⊨(c,s) → (c',s') ∧ Seq r' c₂ ∈ redexes c'"
proof -
  from step.Seq [OF step]
  have "Γ⊨ (Seq r c₂, s) → (Seq r' c₂, s')".
  from step_redexes [OF this Seq]
  show ?thesis .
qed

lemma steps_redexes_Seq:
  assumes steps: "Γ⊨ (r, s) →^* (r', s')"
  shows "∧c. Seq r c₂ ∈ redexes c ==>
              ∃c'. Γ⊨(c,s) →^* (c',s') ∧ Seq r' c₂ ∈ redexes c'"
using steps
proof (induct rule: converse_rtranclp_induct2 [case_names Refl Trans])
  case Refl
  then show ?case
    by (auto)

next
  case (Trans r s r'' s'')
  have "Γ⊨ (r, s) → (r'', s'')" "Seq r c₂ ∈ redexes c" by fact+
  from step_redexes_Seq [OF this]
  obtain c' where
    step: "Γ⊨ (c, s) → (c', s'')" and
    r'': "Seq r'' c₂ ∈ redexes c'"
    by blast
  note step
  also
  from Trans.hyps (3) [OF r'']
  obtain c'' where
    steps: "Γ⊨ (c', s'') →^* (c'', s')" and
    r': "Seq r' c₂ ∈ redexes c''"
    by blast
  note steps
  finally
  show ?case
    using r'
    by blast
qed

lemma steps_redexes_Seq':
  assumes steps: "Γ⊨ (r, s) →⁺ (r', s')"
  shows "∧c. Seq r c₂ ∈ redexes c
             ==> ∃c'. Γ⊨(c,s) →⁺ (c',s') ∧ Seq r' c₂ ∈ redexes c'"
using steps
proof (induct rule: tranclp_induct2 [consumes 1, case_names Step Trans])
  case (Step r' s' c')
  have "Γ⊨ (r, s) → (r', s')" "Seq r c₂ ∈ redexes c'" by fact+
  from step_redexes_Seq [OF this]
  show ?case
    by (blast intro: r_into_trancl)
next
  case (Trans r' s' r'' s'')
  from Trans obtain c' where
    steps: "Γ⊨ (c, s) →⁺ (c', s')" and
    r': "Seq r' c₂ ∈ redexes c'"
    by blast
  note steps
  moreover
  have "Γ⊨ (r', s') → (r'', s'')" by fact
  from step_redexes_Seq [OF this r'] obtain c'' where
    step: "Γ⊨ (c', s') → (c'', s'')" and
    r'': "Seq r'' c₂ ∈ redexes c''"
    by blast
  note step
  finally show ?case
    using r'' by blast
qed

lemma step_redexes_Catch:
  assumes step: "Γ⊨(r,s) → (r',s')"
  assumes Catch: "Catch r c₂ ∈ redexes c"
  shows "∃c'. Γ⊨(c,s) → (c',s') ∧ Catch r' c₂ ∈ redexes c'"
proof -
  from step.Catch [OF step]
  have "Γ⊨ (Catch r c₂, s) → (Catch r' c₂, s')".
  from step_redexes [OF this Catch]
  show ?thesis .
qed

lemma steps_redexes_Catch:
  assumes steps: "Γ⊨ (r, s) →^* (r', s')"
  shows "∧c. Catch r c₂ ∈ redexes c ==>
              ∃c'. Γ⊨(c,s) →^* (c',s') ∧ Catch r' c₂ ∈ redexes c'"
using steps
proof (induct rule: converse_rtranclp_induct2 [case_names Refl Trans])
  case Refl
  then show ?case
    by (auto)

next
  case (Trans r s r'' s'')
  have "Γ⊨ (r, s) → (r'', s'')" "Catch r c₂ ∈ redexes c" by fact+
  from step_redexes_Catch [OF this]
  obtain c' where
    step: "Γ⊨ (c, s) → (c', s'')" and
    r'': "Catch r'' c₂ ∈
    by blast
  note step
  o
   ranssh() [O ']
  btain'' wheere
    steps:"<⊨* (c'', s')" and
    bolol | wsymbol s
    ers,,[membe]),
  tes
java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
  show ?case
    usingarcter0C)]),
    by (CH xF9)]),
qed

lemma steps_redexes_Catch':
  assumes steps: "Γ+ (r', s')"
  shows "size_binsL JSON_cfg JSON_inp2)<comment33720›
             tjava.lang.StringIndexOutOfBoundsException: Index 12 out of bounds for length 12
usingjava.lang.StringIndexOutOfBoundsException: Index 11 out of bounds for length 11
proof etranclp_induct2 se_names Step
  "PagesRefresh"
row2 ∈
  from step_redexes_CatchFhis
  show rce
    by (blast intror_into_trancl
next
  case (Trans r' s' r'' s'')
  from Trans obtain c' where
    steps: "Γ⊨ (c, s) →⁺ (c', s')" and
    r': "Catch r' c₂ ∈ redexes c'"
    by blast
  note steps
  moreover
  have "Γ⊨ (r', s') → (r'', s'')" by fact
  from step_redexes_Catch [OF this r'] obtain c'' where
    step: "Γ⊨ (c', s') → (c'', s'')" and
    r'': "Catch r'' c₂ ∈ redexes c''"
    by blast
  note step
  finally show ?case
    using r'' by blast
qed

lemma redexes_subset:"∧c'. c' ∈ redexes c ==> redexes c' ⊆ redexes c"
  by (induct c) auto

lemma redexes_preserves_termination:
  assumes termi: "Γ⊨c↓s"
  shows "∧c'. c' ∈ redexes c ==> Γ⊨c'↓s"
using termi
by induct (auto intro: terminates.intros)


end