Fra AndreasUkens bevis er en …

Fra Andreas

Ukens bevis er en beviskonkurranse der deltakerene hver uke får mulighet til å levere inn et bevis. Bevisene gis fra 0 til 2 poeng. Blant de som i løpet av et semester får flest poeng trekkes det ut en premie (TBA).

Besvarelser sendes inn til ukens-bevis-svar@ifi.uio.no innen utgangen av kalenderuken oppgaven er gitt. Poeng telles per UiO-brukernavn, så svar må alltid sendes fra samme UiO-adresse. Emne skal være ukenummer. Eventuelt vedlegg skal ha navn som innholder ukenummer og UiO-brukernavn.

Oppgave uke 5 (frist 2012-02-03T23:59):

Bevis at enhver NFA kan gjøres om til en ekvivalent NFA med kun én aksepterende tilstand. (Oppgave 1.11 i læreboka for INF2080.)

Merk: Det er ikke tilstrekkelig å gi en metode for omgjøring. En slik metode må i så fall bevises å være rett.