Symboliset äärelliset automaatit ja Brzozowskin lause

Abstract

Tässä tutkielmassa todistetaan Brzozowskin lause ja yleistetty Brzozowskin lause symbolisille äärellisille automaateille.

Luvussa 2 käydään läpi Boolen algebran perusteita, kuten Boolen renkaan ja Boolen algebran määritelmät. Esitellään Boolen algebran tärkeimmät identiteettilait ja todistetaan ne. Lisäksi havaitaan, että joukon A Boolen rengas on tulkittavissa joukon A Boolen algebraksi. Lopuksi esitellään ja todistetaan Stonen esityslause, joka on yksi Boolen algebran merkittävimmistä tuloksista.

Luvussa 3 tarkastellaan säännöllisen äärellisen lauseen ja kielen, sekä determinististen ja epädeterminististen äärellisien automaattien käsitteitä. Todistetaan, että epädeterministisestä äärellisestä automaatista on mahdollista konstruoida deterministinen äärellinen automaatti ja että epädeterministisestä äärellisestä automaatista konstruoitu deterministinen äärellinen automaatti tunnistaa saman kielen kuin alkuperäinen epädeterministinen äärellinen automaatti. Luvussa 4 esitellään symbolisen säännöllisen lauseen ja kielen määritelmät sekä symbolisten determinististen ja epädeterminististen automaattien käsitteet, niiden mintermit, sekä kieliin ja tiloihin liittyviä käsitteitä. Todennetaan epsilon-siirtymillä varustetun symbolisen epädeterministinen automaatin hyväksyvän jokaisen symbolisen säännöllisen kielen, Brzozowskin lauseen sekä symbolisten automaattien mintermeihin liittyviä väitteitä. Luvussa 5 tutkitaan peitteen ja atomipeitteen käsitteet, sekä atomipeitteen generoiman symbolisen epädeterministisen äärellisen automaatin, symbolisen atomaatin ja atomisen symbolisen epädeterministisen äärellisen automaatin käsitteet. Todistetaan apulauseita yleisen Brzozoskin lauseen todistusta varten.