Consider the following grammar (for symbolic arithmetic expressions): Expression

Question

Consider the following grammar (for symbolic arithmetic expressions): Expression: : = zero two Expression + Expression Expression * Expression where + is interpreted as addition and multiplication, as usual. The symbols zero and two stand for the corresponding integer values, that is, 0 and 2. We write e e Expression to mean an expression derived inductively from the grammar (here an inductive specification), whose value is an integer calculated in the standard way. For example, if e is an expression zero + two * two + two, then expression e represents the value 6. Use structural induction to show that if e elementof Expression (e is an expression generated by the grammar Expression), then e represents an even number. Do not count! Remember you need to consider each case in turn. You can picture the argument as a tree (root at the bottom), where the root is given by one of the possible four cases of e elementof Expression. The proof argument uses the "length of the derivation", which is equivalent to the concept of height of a tree. So, P(n) and P(n + 1) both refer to the length of the derivation, but recall that in the proof we will use the variable k

Explanation / Answer

Basic step:

If the expression ends after single step. Then we end up 0 or 2, we already know these two numbers are even.

Induction step:

Let us assume E is derived from E1 and E2. Assume that E1 and E2 are both even.

Case 1: Consider E = E1 + E2. As E1 and E2 are both even E is also even. As sum of two even numbers is always even.

Case 2: Consider E = E1 * E2. As E1 and E2 are both even E is also even. As product of two even numbers is always even.

So in both cases E is always even.

Conclusion: Based on these two steps, by structural induction we can conclude that for evey e Expression will always be even.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.