Deterministisen äärellisen automaatin minimointi

Ahvonen, Veeti (2020)
 
Avaa tiedosto
Lataukset: 



Ahvonen, Veeti
2020

Matematiikan ja tilastotieteen kandidaattiohjelma - Bachelor's Degree Programme in Mathematics and Statistics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-02-25
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202002212276
Tiivistelmä
Tässä tutkielmassa tarkastellaan, miten voimme minimoida deterministisen äärellisen automaatin. Deterministinen äärellinen automaatti on minimaalinen, jos kaikilla saman kielen tunnistavilla deterministisillä äärellisillä automaateilla on vähintään yhtä paljon tiloja.
Huomaamme määrittelemällä tietyn relaation säännölliselle kielelle ja muodostamalla sen ekvivalenssiluokilla deterministisen äärellisen automaatin saamme halutun minimaalisen automaatin säännölliselle kielelle. Lisäksi konstruoimme algoritmin, jonka avulla voimme muokata suoraan deterministisen äärellisen automaatin minimaaliseksi.
Kokoelmat