Exercise 4 (Nested substitution) (20 Marks)Question 7 For the language variant featuring while, if-statement and functions (no recursion), showthe following statement.{E3/y} {E2/x} E1 = {({E3/y} E2)/x} {E3/y} E1where x and y are variable with x̸ = y, and E1, E2 and E3 expressions with x̸ ∈ fv(E3). Clearly state yourproof strategy and mark the places where the assumptions are used.

The statement is about the equality of two nested substitutions. The left-hand side is performing the substitution {E3/y} first and then {E2/x}, while the right-hand side is performing {E3/y} on both E2 and E1 and then substituting the result of {E3/y} E2 for x in {E3/y} E1.

To prove this statement, we can use structural induction on the expression E1. The base case is when E1 is a variable or a constant, and the inductive step is when E1 is a compound expression.

Base case:

• If E1 is a variable v, then there are three subcases:
  • If v = x, then both sides of the equation become E3.
  • If v = y, then both sides of the equation become {E2/x} E3.
  • If v ≠ x and v ≠ y, then both sides of the equation remain v.
• If E1 is a constant, then both sides of the equation remain the same, because substitution does not affect constants.

Inductive step:

• If E1 is a compound expression, then we apply the inductive hypothesis to its subexpressions. For example, if E1 is E4 + E5, then we have {E3/y} {E2/x} (E4 + E5) = {({E3/y} E2)/x} {E3/y} (E4 + E5), which simplifies to {E3/y} {E2/x} E4 + {E3/y} {E2/x} E5 = {({E3/y} E2)/x} {E3/y} E4 + {({E3/y} E2)/x} {E3/y} E5 by the inductive hypothesis.

The assumption that x ≠ y is used to ensure that the substitutions {E3/y} and {E2/x} do not interfere with each other. The assumption that x ∉ fv(E3) is used to ensure that the substitution {E2/x} does not affect E3.

Therefore, the statement {E3/y} {E2/x} E1 = {({E3/y} E2)/x} {E3/y} E1 holds for the language variant featuring while, if-statement, and functions (no recursion).