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.