Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
      • Avaldispuu läbimine
      • Eksami alusosa!
      • Regulaaravaldiste analüüs
      • Kodutöö
        • Minimeerimine*
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Süvendus
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

DFA minimeerimine

Kodutöös implementeerime regulaaravaldise teisenduse NFA-ks ja NFA teisenduse DFA-ks, aga üks loengus käsitletud samm on veel implementeerimata! Lisaülesandeks on realiseerida ka see viimane puuduolev DFA minimeerimise samm.

Klassis DfaMinimizer tuleb realiseerida meetod minimize, mis just seda teeks. Võib eeldada, et argumendina antud automaat on alati DFA, aga mitte ilmtingimata minimaalne. Seda saab teha erinevate algoritmidega (nt õpikust või loengust).

Oma lahenduse kontrollimiseks on ka vastavad testid, mis muuhulgas sisaldavad õpiku ja loengu näiteid. Minimeerituse kontrolliks kasutavad testid minimeerimise algoritme dk.brics.automaton teegist ja võrdlevad olekute arve. Automaatide teooria muuhulgas garanteerib, et minimeeritud DFA on üheselt määratud.

Lahenduse saab esitada Moodle'isse.

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo