Galīgs automāts

Automātu teorijā galīgs automāts ir diskrētas sistēmas abstrakts matemātisks modelis, kas apraksta sistēmas izmaiņas diskrētos laika momentos atkarībā no ieejas datiem un tās iepriekšējā stāvokļa. Šādu automātu sauc par galīgu tādēļ, ka tā ieejas, izejas un stāvokļu kopas ir galīgas. Galīgs automāts ir viens no abstrakta automāta veidiem, kā arī viena no Tjūringa mašīnas sastāvdaļām.

Iedalījums

Pēc automāta funkcijas galīgos automātus iedala akceptoros un pārveidotājos. Akceptors (angļu: acceptor) pēc ieejā padotās informācijas jeb vārda nolasīšanas izvada vienu no divām iespējamajām atbildēm — nolasītais vārds tiek vai nu akceptēts vai noraidīts. Visu akceptēto vārdu kopu sauc par akceptora pazīto valodu. Pārveidotājs jeb galīgs automāts ar izeju (angļu: transducer) pārveido ieejā padoto simbolu virkni par kādu citu virkni — parasti pēc katra simbola nolasīšanas pārveidotājs nomaina savu iekšējo stāvokli un izvada vienu vai vairākus simbolus izvadā. Pārveidotāju intuitīvi var uztvert kā tulku, kas "pārtulko" vienu valodu par citu.
Pēc darbības veida galīgos automātus iedala determinētos, nedeterminētos, varbūtiskos un kvantu automātos. Determinēta automāta nākamo stāvokli viennozīmīgi nosaka tā pašreizējais stāvoklis un ieejā padotais simbols. Nedeterminēta automāta darbību var interpretēt divējādi — var uzskatīt, ka tas vienlaicīgi atrodas vairākos stāvokļos vai arī no daudziem atļautajiem stāvokļiem "izvēlas" to, kas novedīs pie pareizā risinājuma. Varbūtiska automāta stāvokli var raksturot ar varbūtību sadalījumu pār stāvokļu kopu, bet kvantu automāta — ar viļņu funkciju. Atkarībā no ieejas datiem, varbūtisks automāts nākamo stāvokli "izvēlas" nejauši jeb pāriet uz katru no atļautajiem stāvokļiem ar noteiktu varbūtību. Kvantu automāts darbojas pēc kvantu mehānikas likumiem un tā stāvokļa maiņu apraksta ar unitāras matricas palīdzību.
Bieži vien apskata galīgu automātu modeļus, kam ir pievienotas dažādas palīgierīces, piemēram, viena vai vairākas lentas vai magazīnas. Šādā veidā uzlaboti automātu modeļi parasti ir spējīgi atrisināt problēmas, kas sākotnējiem modeļiem nav pa spēkam.

Piemērs (vienkāršota lifta darbības modelis)

Kā galīga automāta piemēru apskatīsim automātu, kas apraksta vienkāršota lifta darbību.

Stāvokļu diagramma

Automāta stāvokļus pieņemts attēlot ar aplīšiem un katrā aplītī ierakstīt attiecīgā stāvokļa nosaukumu. Aplīšus savieno ar bultiņām un uz katras no tām uzraksta kādu no ieejas alfabēta simboliem. Sākuma stāvokli atzīmē ar bultiņu, uz kuras nekas nav rakstīts. Iegūto attēlu sauc par automāta stāvokļu diagrammu (skatīt attēlu).

Automāta darbība

Apskatīsim kā izveidotais automāts reaģē uz virknes cUo ievadīšanu (šī virkne atbilst programmai "aizvērt durvis, uzbraukt uz otro stāvu un atvērt durvis"). Sekojot līdzi bultiņām, no automāta stāvokļu diagrammas ir viegli nolasīt, ka automāts secīgi izies caur stāvokļiem oD, cD, cU, oU. Līdzīgi, izpildot programmu cUocDo, automāts atgriezīsies sākuma stāvoklī oD.
Ne visas komandu virknes atbilst korektām "lifta programmām". Piemēram, programma o nav korekta, jo sākuma stāvoklim oD nav pārejas ar simbolu o (lifta durvis sākumā jau ir atvērtas). Līdzīgi arī U nav korekta programma (nav paredzēts ar atvērtām durvīm braukt augšā). Atkarībā no konteksta, šādas programmas var interpretēt vairākos veidos. Var pieņemt, ka tās ir aizliegtas, tāpēc automāta uzvedība tām nav definēta. Var arī pieņemt, ka automāts pārtrauc darboties un paziņo, ka ievadītā programma nav korekta. Visbeidzot, ja automātu uzskata par nedeterminētu, tad tā stāvokli apraksta tukšā kopa {}.

Automāta tips

Augstāk aprakstītā automāta mērķis ir simulēt lifta darbību nevis akceptēt vai pārveidot vārdus. Formāli to var uzskatīt gan par akceptoru, kura akceptējošo stāvokļu kopa F ir tukša, gan par pārveidotāju, kura izejas alfabēts Γ ir tukšs un izejas funkcija ω vienmēr izvada tukšo vārdu ε (simbolu virkni, kas nesastāv ne no viena simbola).
Apskatītais automāts nav determinēts, jo tam ir stāvokļi, kuriem nav pārejas ar visiem ieejas alfabēta simboliem. Toties to var uzskatīt par galīgu nedeterminētu automātu. Tas nozīmē, ka visos pārējos gadījumos, kas nav uzskaitīti augstāk, pārejas funkcija δ atgriež tukšo kopu {}, piemēram, δ(oD, o) = {}.

Pielietojums

Galīgos automātus izmanto ciparu elektronikā, programmējamās loģiskās ierīcēs. Plašs pielietojums ir programmatūrā, piemēram, sintaktisko analizatoru, regulāro izteiksmju realizācijā.

Galīgu automātu pētniecība Latvijā

Ievērojamākie Latvijas zinātnieki, kas ir veikuši pētījumus galīgo automātu teorijā ir profesori Juris Hartmanis, Jānis Bārzdiņš un Rūsiņš Mārtiņš Freivalds. Profesora Freivalda vadībā Latvijas Universitātē ir izstrādātas vairākas doktora disertācija par tēmām, kas saistītas ar galīgiem automātiem. Viņa bijušie doktoranti Andris Ambainis, Juris Smotrovs, Marats Golovkins, Maksims Kravcevs, Arnolds Ķikusts un Vasilijs Kravcevs turpina veikt pētījumus automātu teorijā.