Chapter 6: Recursion and Induction

Question 1

Recursively define a list

Answer 1

base: []
step: s:l

Question 2

what is Lists_s

Answer 2

The set of all lists over set S

Question 3

How is an operation defined on a list

Answer 3

Define base case, Define step case

Question 4

Give the general structure of a proof by induction on lists

Answer 4

Base case: prove the statement for the case where all occurrences of l have been replaced with []

Ind Hypothesis: given statement holds for list l

Step case: prove the statement for the case where all occurrences of l have been replaced by s:l using the induction hypothesis

Question 5

What is a full binary tree

Answer 5

Full: 0 children or most
Binary: at most two children
Tree: recursive data type made from nodes and edges

Question 6

Give the recursive definition of a full binary tree

Answer 6

for every element s of S there is a tree s which is a node labelled s
For two given trees t, t’ labelled over S and an s in S there is a Tree_s(t, t’)

Question 7

How do we define operations on trees?

Answer 7

Define what happens to Tree s

Define what happens to Tree_s(t, t’)

Question 8

Describe a proof by induction on trees

Answer 8

Base: show the statement holds for Tree s
Ind hypothesis: The statement holds for Tree t and Tree t’
Step case: show the statement holds for Tree_s(t, t’)

Question 9

Give the recursive definition of an ordered binary tree

Answer 9

Base: Tree_s is ordered for all s in N
Step: Trees_s(t, t') is ordered if:
    for every m in Labels(t) m <= s
    for every m' in Labels(t')  s <= m'
    t and t' are ordered

Question 10

Give the recursive definition of a string

Answer 10

Base: elipson is a string
Step: if s is in S and w is a string, then ws is a string

Question 11

Give the recursive definition of logical propositions

Answer 11

Base: for every prop var Z, Z is a proposition
Step: if A and B are propositions:
not A, A and B, A or B, A implies B are propositions

Question 12

Describe a proof by induction for propositions

Answer 12

Base case: show the statement holds for every propositional variable
Ind Hypothesis: assume the statement holds for A and B
Step case: Show that given the Ind Hyp, the statement holds for not A, A and B, A or B, A implies B

Question 13

What are the base and step cases for regex?

Answer 13

Base: elipson, alphabet
Step: +, |, *

Question 14

What are the base and step cases for a grammar?

Answer 14

Base: provided by start symbol
Step: provided by each production rule

Question 15

What are the base and step cases of a parse tree?

Answer 15

Base: the tree corresponding to one node labelled S
Step: if R -> Y is a rule of the grammar and there is a leaf labelled R, add children to that leaf one for every symbol in Y

Question 16

Give the recursive definition of the Natural numbers

Answer 16

Base case: there is a natural number 0

Step case: for each natural number n there is a natural number Sn, the successor of n

Question 17

How do we define operations on natural numbers?

Answer 17

Base: what to do with 0
Step: what to do with Sn

Question 18

Proof by induction with natural numbers?

Answer 18

Base: Replace Sm with 0
Ind Hypothesis: The statement works for Sn
Step: show it works for SSn