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, Σ, δ, 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 katram stāvoklim un ieejas simbolam piekārto jaunu stāvokli (δ : Q × Σ → Q),
 q0 — sākuma stāvoklis, q0 ∈ Q,
 F — beigu jeb akceptējošo stāvokļu kopa (iespējams, tukša), F ⊆ Q.

Ja M = (Q, Σ, δ, q0, F) ir galīgs determinēts automāts un X = x0x1 ... xn−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 r0, r1, ..., rn ∈ Qn+1 garumā n + 1, kas apmierina šādus nosacījumus:
 r0 = q0 — virkne sākas ar automāta M sākuma stāvokli q0,
 ri+1 = δ(ri, xi), kur i = 0, ..., n−1 — nolasot kārtējo simbolu, automāta stāvoklis nomainās saskaņā ar pārejas funkciju δ,
 rn ∈ 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.


Apskatīsim automātu M = (Q, Σ, δ, q0, F), kam
 Q = {S1, S2},
 Σ = {0, 1},
 q0 = S1,
 F = {S1},
 pārejas funkcija δ definēta šādi:
{| class="wikitable" style="text-align: center"
! width="30px" |
! width="30px" | 0
! width="30px" | 1
|-
! S1
| S2 || S1
|-
! S2
| S1 || S2
|}

Š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ī S1, bet ja nepāra — tad S2. 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 S1, 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 S2 un vārds tiks noraidīts.

Automāta M atpazītā valoda ir regulāra un to var aprakstīt ar regulāru izteiksmi

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 M1 un M2 uzkonstruē automātu, kas atpazīst
 M1 un M2 atpazīto valodu apvienojumu (vārdus, kas ir kaut vienā no šīm valodām),
 M1 un M2 atpazīto valodu šķēlumu (vārdus, kas ir abās valodās),
 M1 atpazītās valodas papildinājumu (vārdus, ko neakceptē M1).

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 2n 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 anbn 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.
 Теория конечных автоматов.

Kategorija:Skaitļošanas modeļi
Kategorija:Automātu teorija
Kategorija:Automāti