Oppgave 1:
La B være språket over alfabetet {(,)} som er induktivt definert slik:
∧ ∈ B
Hvis X ∈ B og Y ∈ B, så XY ∈ B.
Hvis X ∈ B, så (X) ∈ B.
a) Forklar med egne ord hvordan elementene i mengden B ser ut.
b) Bevis ved strukturell induksjon at for alle X ∈ B, er det slik at antall tegn I X er et partall.
c) Definer to funksjoner, v og h, rekursivt slik at for alle X ∈ B, er v(X) antall venstreparenteser I X og h(X) antall høyreparenteser i X.
Oppgave 2:
Definer en rekursiv funksjon SUM på lister over tall som summerer alle tallene i listen. For eksempel vil SUM((2, 3)) = 5 og SUM((2, 3, 4)) = 9. Bevis ved strukturell induksjon at SUM(L + M) = SUM(L) + SUM(M) for alle lister L og M.
((