matematikk.net

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.

Er det noe her som gikk tapt da du copy/paste'a oppgaven? Enkelte deler ser litt uforventet ut.

alfabetet {(,)}

∧ ∈ B

Takk for svar! Det er faktisk nøyaktig det som står i oppgaven...

Da er det bare jeg som har glemt notasjonen for formelle språk.

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.

Tegnet i oppgaven er ikke konjunkt, men Lambda. Lambda konjunkt XY = XY.

Stemmer at tegnet er Lambda, ja!:-)

Noen som kan hjelpe med oppgave b, sitter veldig veldig fast ((