Springen naar inhoud

Bewijs van taal m.b.v. inductie


  • Log in om te kunnen reageren

#1

kubbazoob

    kubbazoob


  • >25 berichten
  • 51 berichten
  • Ervaren gebruiker

Geplaatst op 01 oktober 2006 - 14:55

Ik moet een bewijs leveren met behulp van inductie dat in de hieronder (recursief) gespecificeerde taal iedere string uit een even aantal elementen bestaat.

i) Basis: LaTeX
ii) Recursieve stap: Als LaTeX , dan LaTeX

Hoe bewijs ik zoiets? Kan iemand mij hier mee helpen?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

qrnlk

    qrnlk


  • >5k berichten
  • 5079 berichten
  • Lorentziaan

Geplaatst op 01 oktober 2006 - 15:49

Stel dat string LaTeX een even lengte heeft dan volgt uit (ii) dat alle strings die je kunt maken van LaTeX ook even moeten zijn, elke productie regel voegt immers steeds twee elementen toe. De enige manier om een string te maken met oneven lengte is als LaTeX oneven is.

Vervolgens kun je (i) gebruiken om aan te tonen elke LaTeX even moet zijn: Er zitten alleen even strings in de basis.

Ik hoop dat je dit op weg helpt.
Any sufficiently analyzed magic is indistinguishable from science.
Any sufficiently advanced technology is indistinguishable from magic.

There is no theory of protecting content other than keeping secrets Ė Steve Jobs

#3

kubbazoob

    kubbazoob


  • >25 berichten
  • 51 berichten
  • Ervaren gebruiker

Geplaatst op 01 oktober 2006 - 17:02

bedankt voor je antwoord, maar ik kan er niet veel mee. Ik had reeds begrepen dat dit uit de definitie van de taal volgde, alleen kan ik het niet bewijzen m.b.v. inductie. Kan iemand mij hier een stap in de goede richting in geven?

#4

*_gast_PeterPan_*

  • Gast

Geplaatst op 01 oktober 2006 - 17:33

Inductie naar het aantal recursieve stappen.

Na 0 stappen hebben we slechts de strings aa en ab. Deze hebben een even lengte.

Stel dat alle strings die na n recursieve stappen gevormd kunnen worden een even lengte hebben.
Bekijk nu alle strings die op de n+1-ste stap gevormd kunnen worden.
Die worden dan (volgens de inductiehypothese) gevormd uitgaande van een string van even lengte m.b.v. regel 2.
enz.

Overigens: Dit is informatica en past beter in de rubriek wiskunde.

#5

kubbazoob

    kubbazoob


  • >25 berichten
  • 51 berichten
  • Ervaren gebruiker

Geplaatst op 01 oktober 2006 - 17:38

PeterPan, bedankt voor je antwoord. Is jouw antwoord een geldige bewijsvoering of is het niet formeel genoeg. Ik zat namelijk te denken om stringlengte van n aantal recursies gelijk te stellen aan 2k, en dan n+1 gelijk stellen aan 2k+1 maar ik kwam er zo namelijk niet uit.

#6

*_gast_PeterPan_*

  • Gast

Geplaatst op 01 oktober 2006 - 19:12

Je kunt het nog formeler formuleren m.b.v. proposities.
Voor elke n :) {0, 1, 2, ... } definieren we propositie Pn.
Pn : Alle strings in deze taal die na n recursieve stappen gevormd kunnen worden hebben een even lengte.
We tonen met volledige inductie aan dat (:) n: n :) {0, 1, 2, ... }: Pn).
m.a.w. Alle strings in deze taal (die na een eindig aantal recursieve stappen gevormd kunnen worden) hebben een even lengte.

Er geldt P0, want ...
Stel n [rr] {0, 1, 2, ... } ťn Pn, dan ...
en dus geldt Pn+1.
Hieruit volgt volgens het principe van volledige inductie dat (:) n: n :) {0, 1, 2, ... }: Pn). En dat was te bewijzen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures