Galīgs determinēts automāts

Automātu teorijā **galīgs determinēts automāts** jeb **akceptors** ir galīgs automāts, kura katram stāvoklim ir tieši viena pāreja katram ieejas simbolam. Galīga determinēta automāta atpazīto valodu kopa precīzi sakrīt ar visu regulāro valodu kopu.

## Neformāls darbības apraksts

Galīgs determinēts automāts darbu sāk kādā noteiktā stāvoklī. Tā ieejā padod simbolu virkni jeb vārdu, kuru automāts nolasa secīgi pa vienam simbolam. Ielasot katru jaunu simbolu, automāta stāvoklis nomainās atbilstoši iepriekš definētai pārejas funkcijai. Pēc pēdējā simbola nolasīšanas automāts ievadīto virkni vai nu akceptē vai noraida atkarībā no tā, kādā stāvoklī tas atrodas. Saka, ka automāts akceptē vārdu kopu jeb valodu *L*, ja tas akceptē visus vārdus, kas pieder kopai *L*, bet pārējos vārdus noraida.

## Formāla definīcija

Galīgu determinētu automātu raksturo kortežs (*Q*, Σ, *δ*, *q*0, *F*), kur
* *Q* — galīga netukša *stāvokļu kopa*,
* Σ — *ieejas [[alfabēts (datorzinātnes)|alfabēts]]* (galīga netukša simbolu kopa),
* *δ* — stāvokļu *pārejas funkcija*, kas katram stāvoklim un ieejas simbolam piekārto jaunu stāvokli (*δ* : *Q* × Σ → *Q*),
* *q*0 — *sākuma stāvoklis*, *q*0 ∈ *Q*,
* *F* — *beigu* jeb *akceptējošo stāvokļu kopa* (iespējams, tukša), *F* ⊆ *Q*.

Ja *M* = (*Q*, Σ, *δ*, *q*0, *F*) ir galīgs determinēts automāts un *X* = *x*0*x*1 ... *x**n*−1 ∈ Σ*n* ir ieejas virkne no simboliem alfabētā Σ, kuras garums ir *n*, tad saka, ka *M* *akceptē vārdu* *X*, ja eksistē tāda stāvokļu virkne *r*0, *r*1, ..., *r**n* ∈ *Q**n*+1 garumā *n*&nbsp;+&nbsp;1, kas apmierina šādus nosacījumus:
# *r*0 = *q*0 — virkne sākas ar automāta *M* sākuma stāvokli *q*0,
# *r**i*+1 = *δ*(*r**i*, *x**i*), kur *i* = 0, ..., *n*−1 — nolasot kārtējo simbolu, automāta stāvoklis nomainās saskaņā ar pārejas funkciju *δ*,
# *r**n* ∈ *F* — automāts beidz darbu stāvoklī, kas pieder akceptējošo stāvokļu kopai *F*.

Tā kā automāts *M* ir determinēts, tad eksistē tieši viena virkne, kurai izpildās pirmie divi nosacījumi. Šī virkne pilnībā raksturo automāta darbības vēsturi jeb kādā stāvoklī automāts nokļūst pēc katra simbola ielasīšanas. Ja šai virknei izpildās arī trešais nosacījums, tad automāts vārdu *X* akceptē. Pretējā gadījumā tas vārdu *X* *noraida* jeb *neakceptē*. Automāta visu akceptēto vārdu kopa ir *valoda*, kuru automāts *M* *atpazīst*.

## Piemērs

Apskatīsim galīgu determinētu automātu *M*, kura ieejā padod nulles un vieniniekus un kas ievadīto vārdu akceptē tad un tikai tad, ja tajā ir pāra skaits nuļļu.

[right|thumb|250px|Automāta ''M'' [stāvokļu diagramma]]

Apskatīsim automātu *M* = (*Q*, Σ, *δ*, *q*0, *F*), kam
* *Q* = {*S*1, *S*2},
* Σ = {0, 1},
* *q*0 = *S*1,
* *F* = {*S*1},
* pārejas funkcija *δ* definēta šādi:
:

Šis automāts uzglabā tikai nuļļu skaita paritāti, tāpēc tam ir nepieciešami tikai divi stāvokļi: ja ielasītajā vārda daļā nuļļu skaits ir pāra, tad automāts atrodas stāvoklī *S*1, bet ja nepāra — tad *S*2. Ja automāts ielasa simbolu "1", tā stāvoklis nemainās, bet ja tas ielasa simbolu "0", tā stāvoklis nomainās uz pretējo (neatkarīgi no tā, kādā stāvoklī automāts atradās pirms šo simbolu nolasīšanas). Redzams, ka automāta beigu stāvoklis būs *S*1, ja ielasītais vārds saturēja pāra skaitu nuļļu, un tas tiks akceptēts. Pretējā gadījumā automāta beigu stāvoklis būs *S*2 un vārds tiks noraidīts.

Automāta *M* atpazītā valoda ir regulāra un to var aprakstīt ar regulāru izteiksmi
: 1^* \bigl( 0 (1^*) 0 (1^*) \bigr)^*, \,
kur 1* apzīmē patvaļīgu daudzumu (nulle vai vairāk) simbolu "1".

## Priekšrocības un trūkumi

Galīgs determinēts automāts ir visvienkāršākais formālais skaitļošanas modelis, tas ir daudzu citu skaitļošanas modeļu pamatā. Šī modeļa iespējas ir salīdzinoši vājas, piemēram, salīdzinot ar Tjūringa mašīnu. Galīgus determinētus automātus var simulēt ar daudzu citu modeļu palīdzību.

Eksistē efektīvi algoritmi, kas jebkuriem diviem dotiem galīgiem determinētiem automātiem *M*1 un *M*2 uzkonstruē automātu, kas atpazīst
* *M*1 un *M*2 atpazīto valodu apvienojumu (vārdus, kas ir kaut vienā no šīm valodām),
* *M*1 un *M*2 atpazīto valodu šķēlumu (vārdus, kas ir abās valodās),
* *M*1 atpazītās valodas papildinājumu (vārdus, ko neakceptē *M*1).

Katram galīgam determinētam automātam eksistē *kanoniskā normālforma* jeb *minimālais automāts*, kas atpazīst to pašu valodu. Izmantojot šo normālformu, var efektīvi
* pārbaudīt, vai dotais automāts neakceptē nevienu vārdu,
* pārbaudīt, vai dotais automāts akceptē visus vārdus,
* pārbaudīt, vai divi dotie automāti atpazīst vienu un to pašu valodu,
* uzkonstruēt automātu ar minimālu stāvokļu skaitu, kas atpazīst doto regulāro valodu.

Viens no automātu teorijas pamatrezultātiem ir pierādījums tam, ka galīgu determinētu un nedeterminētu automātu atpazīto valodu saimes sakrīt. Neskatoties uz to, atbilstošo automātu stāvokļu skaits var būtiski atšķirties, piemēram, eksistē valodas, kuras var atpazīt nedeterminēts automāts ar *n* stāvokļiem, taču jebkuram determinētam automātam to atpazīšanai ir nepieciešami vismaz 2*n* stāvokļi.

Tanī pat laikā galīgi determinēti automāti ir ļoti ierobežoti, jo tie nevar atpazīt daudzas pavisam vienkāršas valodas — patiesībā jebkuru valodu, kuras atpazīšanai nepietiek ar konstantu atmiņas daudzumu. Visvienkāršākais piemērs ir valoda *a<sup>n</sup>b<sup>n</sup>* jeb virkne no simboliem "*a*", kurai seko tikpat gara virkne no simboliem "*b*". Līdzīgi ir ar "iekavu valodu" jeb visām simbolu "(" un ")" virknēm, kurās iekavas ir pareizi sapārotas, piemēram, (), (()), ((())()), utt.

## Skatīt arī

* Galīgs nedeterminēts automāts
* Galīgs alternējošs automāts
* Galīgs varbūtisks automāts
* Galīgs kvantu automāts
* Galīgs automāts
* Tjūringa mašīna

## Literatūra

* .
* .
* , krievu tulkojums. Oriģināls: .
* .

## Ārējās saites

* Kārlis Čerāns, Abstraktās mašīnas un automāti, Automātu teorijas elementi , lekciju materiāli.
* Andžāns Agnis, Ramāna Līga, Čakste Jānis, Larfelds Tomass, Mārīte Seile, "Vidējās vērtības metode", 7.3.1. Galīgo automātu piemēri un vispārīgais jēdziens.
* Pēteris Daugulis, Algoritmi un skaitļošanas mašīnas, lekciju materiāli.
* Теория конечных автоматов.