Theorem: ContextFreeGrammar.derivation_preserves_prefix (FormalSystems/Chomsky/ContextFree/ContextFreeGrammar.lean)

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
⊢ w = a :: List.tail w
Tactic:
match d with
| .same h =>
  rw [<- h, h_lhs] at h_rhs
  cases w
  simp [List.map_nil] at h_rhs
  simp [List.map_cons] at h_rhs
  rw [List.cons_eq_cons] at h_rhs
  have _ := (Sum.inr_injective h_rhs.left).symm
  simp; rw [List.cons_eq_cons]
  simp; assumption
| .step s d r =>
  unfold Grammar.DerivationStep.result at r
  rw [ContextFreeGrammar.derivation_step_prefix s h_lhs] at r
  simp_rw [HMul.hMul, Mul.mul] at r
  simp at r
  let h_lhs' := r.symm
  exact ContextFreeGrammar.derivation_preserves_prefix d h_lhs' h_rhs
State after:
no goals

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
h : lhs = rhs
⊢ w = a :: List.tail w
Tactic:
rw [<- h, h_lhs] at h_rhs
State after:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : Sum.inr a :: xs = Sum.inr <$> w
h : lhs = rhs
⊢ w = a :: List.tail w

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : Sum.inr a :: xs = Sum.inr <$> w
h : lhs = rhs
⊢ w = a :: List.tail w
Tactic:
cases w
State after:
case nil
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
h_rhs : Sum.inr a :: xs = Sum.inr <$> []
⊢ [] = a :: List.tail []

case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a :: xs = Sum.inr <$> (head✝ :: tail✝)
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)

State before:
case nil
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
h_rhs : Sum.inr a :: xs = Sum.inr <$> []
⊢ [] = a :: List.tail []

case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a :: xs = Sum.inr <$> (head✝ :: tail✝)
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)
Tactic:
simp [List.map_nil] at h_rhs
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a :: xs = Sum.inr <$> (head✝ :: tail✝)
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a :: xs = Sum.inr <$> (head✝ :: tail✝)
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)
Tactic:
simp [List.map_cons] at h_rhs
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a :: xs = Sum.inr head✝ :: List.map Sum.inr tail✝
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a :: xs = Sum.inr head✝ :: List.map Sum.inr tail✝
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)
Tactic:
rw [List.cons_eq_cons] at h_rhs
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)
Tactic:
have _ := (Sum.inr_injective h_rhs.left).symm
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ :: tail✝ = a :: List.tail (head✝ :: tail✝)
Tactic:
simp
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ :: tail✝ = a :: tail✝

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ :: tail✝ = a :: tail✝
Tactic:
rw [List.cons_eq_cons]
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ = a ∧ tail✝ = tail✝

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ = a ∧ tail✝ = tail✝
Tactic:
simp
State after:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ = a

State before:
case cons
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h : lhs = rhs
head✝ : { x // x ∈ G.Z }
tail✝ : List { x // x ∈ G.Z }
h_rhs : Sum.inr a = Sum.inr head✝ ∧ xs = List.map Sum.inr tail✝
x✝ : head✝ = a
⊢ head✝ = a
Tactic:
assumption
State after:
no goals

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : Grammar.DerivationStep.result s = u'✝
⊢ w = a :: List.tail w
Tactic:
unfold Grammar.DerivationStep.result at r
State after:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : s.pre * Production.rhs ↑s.prod * s.suf = u'✝
⊢ w = a :: List.tail w

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : s.pre * Production.rhs ↑s.prod * s.suf = u'✝
⊢ w = a :: List.tail w
Tactic:
rw [ContextFreeGrammar.derivation_step_prefix s h_lhs] at r
State after:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : (Sum.inr a :: List.tail s.pre) * Production.rhs ↑s.prod * s.suf = u'✝
⊢ w = a :: List.tail w

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : (Sum.inr a :: List.tail s.pre) * Production.rhs ↑s.prod * s.suf = u'✝
⊢ w = a :: List.tail w
Tactic:
simp_rw [HMul.hMul, Mul.mul] at r
State after:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : List.append (List.append (Sum.inr a :: List.tail s.pre) (Production.rhs ↑s.prod)) s.suf = u'✝
⊢ w = a :: List.tail w

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : List.append (List.append (Sum.inr a :: List.tail s.pre) (Production.rhs ↑s.prod)) s.suf = u'✝
⊢ w = a :: List.tail w
Tactic:
simp at r
State after:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : Sum.inr a :: (List.tail s.pre ++ (Production.rhs ↑s.prod ++ s.suf)) = u'✝
⊢ w = a :: List.tail w

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : Sum.inr a :: (List.tail s.pre ++ (Production.rhs ↑s.prod ++ s.suf)) = u'✝
⊢ w = a :: List.tail w
Tactic:
let h_lhs' := r.symm
State after:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : Sum.inr a :: (List.tail s.pre ++ (Production.rhs ↑s.prod ++ s.suf)) = u'✝
h_lhs' : u'✝ = Sum.inr a :: (List.tail s.pre ++ (Production.rhs ↑s.prod ++ s.suf)) := r.symm
⊢ w = a :: List.tail w

State before:
α nt : Type
P : Finset α → Finset nt → Type
i : Production.ContextFree α nt P
G : Grammar P
lhs rhs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
w : Word { x // x ∈ G.Z }
xs : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
a : { x // x ∈ G.Z }
d✝ : Grammar.Derivation G lhs rhs
h_lhs : lhs = Sum.inr a :: xs
h_rhs : rhs = Sum.inr <$> w
u'✝ : Word ({ x // x ∈ G.V } ⊕ { x // x ∈ G.Z })
s : Grammar.DerivationStep G lhs
d : Grammar.Derivation G u'✝ rhs
r : Sum.inr a :: (List.tail s.pre ++ (Production.rhs ↑s.prod ++ s.suf)) = u'✝
h_lhs' : u'✝ = Sum.inr a :: (List.tail s.pre ++ (Production.rhs ↑s.prod ++ s.suf)) := r.symm
⊢ w = a :: List.tail w
Tactic:
exact ContextFreeGrammar.derivation_preserves_prefix d h_lhs' h_rhs
State after:
no goals