Galīgs automāts

Vikipēdijas lapa

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[labot šo sadaļu | labot pirmkodu]

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 lentes 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.

Formāls apraksts[labot šo sadaļu | labot pirmkodu]

Akceptoru parasti var raksturot ar kortežu (Q, Σ, δ, q0, F), kur

  • Q — galīga netukša stāvokļu kopa,
  • Σ — ieejas alfabēts (galīga netukša simbolu kopa),
  • δ — stāvokļu pārejas funkcija, kas raksturo to, kā mainās automāta stāvoklis nolasot katru no ieejas alfabēta simboliem,
  • q0sākuma stāvoklis,
  • Fbeigu jeb akceptējošo stāvokļu kopa.

Šāds automāta uzdošanas veids ir kopīgs lielākajai daļai akceptoru. Precīzāks automāta apraksts un nosacījumi, kad tas akceptē ievadīto vārdu, ir atkarīgi no konkrētā automāta modeļa. Piemēram, varbūtiskiem automātiem pārejas funkciju δ uzdod ar stohastisku matricu, bet kvantu automātiem — ar unitāru matricu. Arī automāta sākuma stāvokļa uzdošanas veids ir atkarīgs no modeļa, piemēram, determinētam automātam ir tieši viens sākuma stāvoklis, taču nedeterminētam var būt vairāki.

Pārveidotāju parasti var raksturot ar kortežu (Q, Σ, Γ, δ, ω, q0), kur

  • Q, Σ, δ, q0 — tāpat kā akceptoram,
  • Γ — izejas alfabēts,
  • ωizejas funkcija, kas raksturo automāta izvadīto simbolu atkarība no ielasītā simbola un automāta pašreizējā stāvokļa.

Atšķirībā no akceptora pārveidotājam nav akceptējošo stāvokļu kopa F. Precīzāks pārveidotāja apraksts ir atkarīgs no konkrētā modeļa.

Piemērs (vienkāršota lifta darbības modelis)[labot šo sadaļu | labot pirmkodu]

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

Ieejas alfabēts[labot šo sadaļu | labot pirmkodu]

Pieņemsim, ka dotais lifts var izpildīts šādas četras komandas:

  • o — atvērt durvis,
  • c — aizvērt durvis,
  • U — uzbraukt otrajā stāvā,
  • D — nobraukt uz pirmo stāvu.

Lai modelētu lifta darbību, automāta ieejā tiks padotas šīs komandas. Tas nozīmē, ka automāta ieejas alfabēts ir Σ = {o, c, U, D}.

Stāvokļu kopa[labot šo sadaļu | labot pirmkodu]

Nav grūti ievērot, ka šāds lifts var atrasties četros stāvokļos:

  • oD — pirmajā stāvā, durvis atvērtas,
  • cD — pirmajā stāvā, durvis aizvērtas,
  • cU — otrajā stāvā, durvis aizvērtas,
  • oU — otrajā stāvā, durvis atvērtas.

Pieņemsim, ka sākotnēji lifts atrodas stāvoklī oD. Tas nozīmē, ka liftu modelējošā automāta stāvokļu kopa ir Q = {oDcDcUoU}, bet sākumstāvoklis ir q0 = oD.

Pārejas funkcija[labot šo sadaļu | labot pirmkodu]

Stāvokļu diagramma automātam, kas modelē lifta darbību

Automāta pārejas funkcija δ raksturo to, kā automāts reaģē uz ieejā padotajiem datiem. Automāta reakcija izpaužas kā tā stāvokļa maiņa un ir atkarīga no automāta pašreizējā stāvokļa.

Lifta gadījumā pārejas funkciju definēsim šādi:

δ(oD, c) = cD — aizvērt durvis (stāvot 1. stāvā),
δ(cD, o) = oD — atvērt durvis (stāvot 1. stāvā),
δ(cD, U) = cU — uzbraukt 2. stāvā (ar aizvērtām durvīm),
δ(cU, D) = cD — nobraukt 1. stāvā (ar aizvērtām durvīm),
δ(cU, o) = oU — atvērt durvis (stāvot 2. stāvā),
δ(oU, c) = cU — aizvērt durvis (stāvot 2. stāvā).

Stāvokļu diagramma[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

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, δ(oDo) = {}.

Pielietojums[labot šo sadaļu | labot pirmkodu]

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ā.[nepieciešama atsauce]

Galīgu automātu pētniecība Latvijā[labot šo sadaļu | labot pirmkodu]

Ievērojamākie Latvijas zinātnieki, kas ir veikuši pētījumus galīgo automātu teorijā ir profesori Juris Hartmanis,[1] Jānis Bārzdiņš[2] un Rūsiņš Mārtiņš Freivalds.[3] 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.[nepieciešama atsauce] 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ā.[nepieciešama atsauce]

Atsauces[labot šo sadaļu | labot pirmkodu]

  1. Skatīt publikācijas Kornela Universitātes bibliotēkas un DBLP Arhivēts 2009. gada 26. jūnijā, Wayback Machine vietnē. mājaslapās.
  2. Skatīt publikācijas LU Arhivēts 2009. gada 8. jūnijā, Wayback Machine vietnē. un LUMII Arhivēts 2008. gada 17. decembrī, Wayback Machine vietnē. mājaslapās.
  3. Skatīt publikācijas LZA Arhivēts 2009. gada 5. janvārī, Wayback Machine vietnē. un DBLP Arhivēts 2009. gada 11. martā, Wayback Machine vietnē. mājaslapās.

Skatīt arī[labot šo sadaļu | labot pirmkodu]