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₀, 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),
• q₀ — sākuma stāvoklis, q₀ ∈ Q,
• F — beigu jeb akceptējošo stāvokļu kopa (iespējams, tukša), F ⊆ Q.

Ja M = (Q, Σ, δ, q₀, F) ir galīgs determinēts automāts un X = x₀x₁ ... x_n−1 ∈ Σⁿ 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₀, r₁, ..., r_n ∈ Qⁿ⁺¹ garumā n + 1, kas apmierina šādus nosacījumus:

1. r₀ = q₀ — virkne sākas ar automāta M sākuma stāvokli q₀,
2. 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 δ,
3. 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.

Automāta M stāvokļu diagramma

Apskatīsim automātu M = (Q, Σ, δ, q₀, F), kam

• Q = {S₁, S₂},
• Σ = {0, 1},
• q₀ = S₁,
• F = {S₁},
• pārejas funkcija δ definēta šādi:

	0	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ī S₁, bet ja nepāra — tad S₂. 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₁, 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₂ 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^{[nepieciešama atsauce]}, kas jebkuriem diviem dotiem galīgiem determinētiem automātiem M₁ un M₂ uzkonstruē automātu, kas atpazīst

• M₁ un M₂ atpazīto valodu apvienojumu (vārdus, kas ir kaut vienā no šīm valodām),
• M₁ un M₂ atpazīto valodu šķēlumu (vārdus, kas ir abās valodās),
• M₁ atpazītās valodas papildinājumu (vārdus, ko neakceptē M₁).

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^{[nepieciešama atsauce]}

• 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ⁿ 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ⁿbⁿ 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

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006), Introduction to Automata Theory, Languages, And Computation (3 izd.), Addison-Wesley, ISBN 9780321462251.
• Sipser, Michael (2005), Introduction to the Theory of Computation (2 izd.), Thomson Course Technology, ISBN 9780534950972.
• Брауэр, Вильфрид; Рудаков, К.В; Журавлев, Ю.И (1987), Введение в теорию конечных автоматов, Радио и связь, krievu tulkojums. Oriģināls: Brauer, Wilfried (1984), Automatentheorie: Eine Einführung in die Theorie endlicher Automaten, Teubner, ISBN 9783519022510.
• Кобринский, Натан Ефимович; Трахтенброт, Борис Авраамович (1962), Введение в теорию конечных автоматов, Физматгиз.

Ārējās saites

• Kārlis Čerāns, Abstraktās mašīnas un automāti, Automātu teorijas elementi^{[novecojusi saite]}, 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^{[novecojusi saite]}.
• Pēteris Daugulis, Algoritmi un skaitļošanas mašīnas, lekciju materiāli.
• Теория конечных автоматов^{[novecojusi saite]}.