Galīgs determinēts automāts

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt

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

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

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),
  • q0sākuma stāvoklis, q0Q,
  • Fbeigu jeb akceptējošo stāvokļu kopa (iespējams, tukša), FQ.

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, ..., rnQn+1 garumā n + 1, kas apmierina šādus nosacījumus:

  1. r0 = q0 — virkne sākas ar automāta M sākuma stāvokli q0,
  2. 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 δ,
  3. rnF — 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[izmainīt šo sadaļu | labot pirmkodu]

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:
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ī 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

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

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

Literatūra[izmainīt šo sadaļu | labot pirmkodu]

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