Hei! Jeg sliter med å skjønne hvordan jeg skal løse disse oppgavene. Har ikke helt forstått meg på induksjon enda, så sliter spesielt med det... Håper noen snille kan hjelpe meg på veien
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.
Strukturell induksjon
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Grothendieck
- Innlegg: 826
- Registrert: 09/02-2015 23:28
- Sted: Oslo
Noe er feil. Vi er gitt at $\wedge\in B$, men dette ordet består av kun ett tegn, altså lar ikke oppgave (b) seg løse.