Abstrakto automātu teorijas pamatjēdzieni. Automātu teorija Vadības sistēmas Lietišķā automātu teorija

Veidlapā uzrādītas skaitļošanas mašīnas matemātiskie modeļi- un uzdevumi, ko viņi var atrisināt.

Automātu teorija ir visciešāk saistīta ar algoritmu teoriju: automāts pārvērš diskrēto informāciju soļos diskrētos laika momentos un ģenerē rezultātu ar dotā algoritma soļiem.

Enciklopēdisks YouTube

    1 / 3

    ✪ 12. nodarbība. Automātu teorijas pamati. Matemātiskā loģika. Datorzinātņu nodarbības

    ✪ Kā valdīt pār pasauli, apgūstot tikai vienu vienkāršs modelis!

    ✪ 15. nodarbība. Lietišķo uzdevumu risināšana automātu teorijā. Matemātiskā loģika. Datorzinātņu nodarbības

    Subtitri

Terminoloģija

Simbols- jebkurš datu atomu bloks, kas var ietekmēt iekārtu. Visbiežāk simbols ir burts parastajā valodā, bet tas var būt, piemēram, diagrammas grafiskais elements.

  • Vārds- rakstzīmju virkne, kas izveidota, izmantojot savienošanu (savienojumu).
  • Alfabēts- ierobežots dažādu rakstzīmju kopums (daudz rakstzīmju)
  • Valoda- vārdu kopums, ko veido dotā alfabēta simboli. Var būt ierobežots vai bezgalīgs.
Automāti Deterministiskais galīgais automāts (DFA)- piecu elementu secība (kopā). (Q , Σ , δ , S 0 , F) (\displaystyle (Q,\Sigma,\delta,S_(0),F)), kur: Nedeterministiska galīgā stāvokļa mašīna (NFA)- piecu elementu secība (kopā). (Q , Σ , Δ , S , F) (\displaystyle (Q,\Sigma,\Delta,S,F)), kur: Word Automaton nolasa beigu rakstzīmju virkni a 1 ,a 2 ,…., a n , kur a i ∈ Σ, ko sauc ievades vārds.Visu vārdu kopu raksta kā Σ*. Saņemtais vārds Vārdu w ∈ Σ* automāts pieņem, ja q n ∈ F.

Tiek teikts, ka valoda ir L lasīt (saņemts) automāts M, ja tas sastāv no vārdiem w, pamatojoties uz alfabētu Σ (\displaystyle \Sigma ) tā, ka, ja šie vārdi tiek ievadīti M, apstrādes beigās nonāk vienā no pieņemšanas stāvokļiem F:

L = ( w ∈ Σ ⋆ | δ ^ (S 0 , w) ∈ F ) (\displaystyle L=\(w\in \Sigma ^(\star )|(\cepure (\delta ))(S_(0) ,w)\in F\))

Parasti automāts pārvietojas no stāvokļa uz stāvokli, izmantojot pārejas funkciju δ (\displaystyle \delta ), lasot vienu rakstzīmi no ievades. Ir automāti, kas var pāriet uz jaunu stāvokli, neizlasot rakstzīmi. Tiek izsaukta lēciena funkcija, nelasot rakstzīmi ϵ (\displaystyle \epsilon )- pāreja(epsilona pāreja).Uzdevumu sarežģītība.

Tipiski uzdevumi

  • Automātu uzbūve un minimizēšana- abstrakta automāta konstruēšana no noteiktas klases, kas atrisina doto problēmu (pieņemot doto valodu), iespējams, ar sekojošu minimizēšanu stāvokļu skaita vai pāreju skaita ziņā.
  • Automātu sintēze- doto "elementāru automātu" sistēmas izveidošana, kas līdzvērtīga noteiktam automātam. Tādu automātu sauc strukturāli. To izmanto, piemēram, digitālo elektrisko ķēžu sintēzē uz noteikta elementa bāzes.
mijiedarbojošo procesu sistēmu pārbaude;
  • Dokumentu un objektu orientētu programmu aprakstu valodas;
  • Loģisko programmu optimizācija utt.

    • Par to var spriest pēc zinātnieku un speciālistu prezentācijām seminārā "Programmatūra 2000 ...".

    Dags Ross: "...80 vai pat 90% datorzinātņu (Computer Science) nākotnē balstīsies uz galīgo automātu teoriju..."

    Hervers Gallērs: "Es pazīstu Boeing cilvēkus, kas strādā pie lidmašīnu stabilizācijas sistēmām, izmantojot tīru automātu teoriju. Grūti iedomāties, ko viņi ir paveikuši ar šo teoriju."

    Braiens Rendels: "Liela daļa automātu teorijas ir veiksmīgi izmantota sistēmas programmas un teksta filtri operētājsistēmā UNIX OS. Tas ļauj daudziem cilvēkiem strādāt augstā līmenī un izstrādāt ļoti efektīvas programmas."

    1.1. Pamatjēdzieni un definīcijas.

    Vienkāršākais informācijas pārveidotājs (1.1. att., a) kartē noteiktu informācijas elementu kopu Xincoming uz ieeju uz noteiktu kopu izejā Y. Ja kopas X un Y ir ierobežotas un diskrētas, tas ir, transformācija tiek veikta diskrētos laikos, tad šādus informācijas pārveidotājus sauc par galīgajiem pārveidotājiem. Iestatiet elementus X un Y šajā gadījumā ir iepriekš kodēti ar binārajiem kodiem, un tiek veidota vienas kopas transformācija uz citu.

    Transformācijas rezultāts bieži vien ir atkarīgs ne tikai no tā, kāda informācija ir parādījusies ievadē dotajā brīdī, bet arī no tā, kas noticis iepriekš, tas ir, no transformācijas vēstures. Piemēram, tas pats ievads – atvainošanās no kaimiņa pēc tam, kad viņš uzkāpa tev uz kājas pārpildītā autobusā – pirmajā reizē radīs vienu reakciju, bet piektajā – pavisam citu.


    Rīsi. 1.1.

    Līdz ar to ir sarežģītāki informācijas transformatori (IT), kuru reakcija ir atkarīga ne tikai no ieejas signāliem konkrētajā brīdī, bet arī no iepriekš notikušā, no ievades vēstures. Šādus PI sauc par automātiem (atmiņas ķēdēm). Šajā gadījumā runā par automātisku informācijas transformāciju (1.1. att., b). Automāts var atšķirīgi reaģēt uz vienu un to pašu ieejas signālu atkarībā no stāvokļa, kurā tas bija. Automāts maina savu stāvokli ar katru ieejas signālu.

    Apskatīsim dažus piemērus.

    1. piemērs 1 Karpovs Yu.G. Automātu teorija-Sanktpēterburga: Sanktpēterburga, 2003.g. Automāts, kas apraksta "gudra" tēva uzvedību.

    Aprakstīsim tāda tēva uzvedību, kura dēls iet uz skolu un nes divniekus un pieciniekus. Tēvs nevēlas katru reizi ķerties pie jostas, tiklīdz dēls saņem divnieku, un izvēlas smalkāku audzināšanas taktiku. Mēs definējam šādu automātu ar grafiku, kurā virsotnes atbilst stāvokļiem, un loka no stāvokļa s uz stāvokli q, kas apzīmēts ar x/y , tiek novilkts, kad automāts no stāvokļa s ieejas signāla x ietekmē pāriet stāvoklī. q ar izejas reakciju y . Vecāka viedo uzvedību simulējošā automāta grafiks parādīts 1.2. attēlā. Šim automātam ir četri stāvokļi , divi ieejas signāli - novērtējumi un izejas signāli , kurus mēs interpretēsim kā vecāku darbības šādi:

    Paņemiet jostu;

    aizrādīt dēlu;

    Nomierinies dēls;

    Cerība;

    priecājies;

    Priecājieties.


    Rīsi. 1.2.

    Dēls, kurš saņēmis vienādu atzīmi – divnieku, mājās no tēva sagaida pavisam citu reakciju atkarībā no mācību fona. Piemēram, pēc trešā divnieka vēsturē dēls tiks sveikts ar jostu, un vēsturē viņi tiks nomierināti utt.

    Stāvokļa mašīnu var realizēt gan programmatūrā, gan aparatūrā. Programmatūras ieviešana var izdarīt uz jebkura augsta līmeņa valoda Dažādi ceļi. 1.3. attēlā parādīta programmas blokshēma, kas realizē 1. piemēra automāta uzvedību. Ir viegli redzēt, ka programmas blokshēmas topoloģija atkārto automāta pārejas grafika topoloģiju. Katrs stāvoklis ir saistīts ar darbību NEXT , kas pilda funkciju gaidīt nākamo jauna ievades signāla ienākšanas notikumu un nolasīt to kādā standarta buferī x , kā arī pēc tam analizēt, kāda veida signāls tas ir. Atkarībā no tā, kāds signāls nāca uz ieeju, tiek izpildīta šī vai cita funkcija un notiek pāreja uz jaunu stāvokli.


    Rīsi. 1.3.

    Automāta aparatūras ieviešana tiks aplūkota šīs sadaļas otrajā daļā.

    2. piemērs. "Students"

    Automāts , kura modelis parādīts 1.4. attēlā, raksturo skolēna un skolotāju uzvedību.


    Rīsi. 1.4.

    valstis;

    - ieejas signāli: "n", "2" un "5".

    Izejas reakcijas:

    3 . piemērs 1 . Elektroniskais pulkstenis (1.5. att.).

    Dažādu funkcionalitāti elektroniskie pulksteņi ir viena no ikdienā visplašāk izmantotajām elektroniskajām ierīcēm, kuras vadība ir būvēta uz galīga automāta modeļa bāzes. Tie parasti parāda: laiku, datumu; tiem ir tādas funkcijas kā "laika un datuma iestatīšana", "hronometrs", "modinātājs" utt. Vienkāršots strukturālā shēma elektroniskais pulkstenis parādīts 1.5.att


    Rīsi. 1.5.

    Reģistri parāda vai nu laiku, vai datumu, vai hronometru atkarībā no "Vadības". Vadības ierīce būvēts uz galīgā automāta modeļa bāzes. Stāvokļa mašīna reaģē uz pogas "a" nospiešanu uz korpusa, pārejot uz "Iestatīt minūtes" stāvokli, kurā pogas "b" nospiešanas gadījumā skaitlis palielināsies.

    Automāta teorija

    Automāta teorija- diskrētās matemātikas sadaļa, kurā tiek pētīti abstraktie automāti - matemātisko modeļu veidā attēloti datori - un problēmas, kuras tie var atrisināt.

    Automātu teorija ir visciešāk saistīta ar algoritmu teoriju: automāts pa soļiem pārveido diskrēto informāciju diskrētos laika momentos un rezultātu veido dotā algoritma soļos.

    Terminoloģija

    Simbols- jebkurš datu atomu bloks, kas var ietekmēt iekārtu. Visbiežāk simbols ir burts parastajā valodā, bet tas var būt, piemēram, diagrammas grafiskais elements.

    • Vārds- rakstzīmju virkne, kas izveidota, izmantojot savienošanu (savienojumu).
    • Alfabēts- ierobežots dažādu rakstzīmju kopums (daudz rakstzīmju)
    • Valoda- vārdu kopums, ko veido dotā alfabēta simboli. Var būt ierobežots vai bezgalīgs.
    Mašīna Mašīna- piecu elementu virkne, kur: Vārds Automaton nolasa beigu rakstzīmju virkni a 1 ,a 2 ,…., a n , kur a i ∈ Σ, un tiek saukts vārdu.Visu vārdu kopu raksta kā Σ*. Saņemtais vārds Vārdu w ∈ Σ* automāts pieņem, ja q n ∈ F.

    Tiek teikts, ka valoda ir L lasīt (saņemts) ar automātu M, ja tas sastāv no vārdiem w, kuru pamatā ir alfabēts tā, ka, ievadot šos vārdus M, apstrādes beigās tas nonāk vienā no pieņemšanas stāvokļiem F:

    Parasti automāts pāriet no stāvokļa uz stāvokli, izmantojot pārejas funkciju, nolasot vienu rakstzīmi no ievades. Ir arī automāti, kas var pāriet uz jaunu stāvokli, nelasot rakstzīmi. Tiek izsaukta lēciena funkcija, nelasot rakstzīmi - pāreja(epsilona pāreja).

    Pieteikums

    Praksē automātu teorija tiek izmantota formālo valodu (ieskaitot programmēšanas valodas) lekseru un parsētāju izstrādē, kā arī kompilatoru konstruēšanā un pašu programmēšanas valodu izstrādē.

    Vēl viens svarīgs automātu teorijas pielietojums ir matemātiski stingra problēmu atrisināmības un sarežģītības noteikšana.

    Tipiski uzdevumi

    • Automātu uzbūve un minimizēšana- abstrakta automāta konstruēšana no noteiktas klases, kas atrisina doto problēmu (pieņemot doto valodu), iespējams, ar sekojošu minimizēšanu stāvokļu skaita vai pāreju skaita ziņā.
    • Automātu sintēze- sistēmas izveidošana no dotajiem "elementārajiem automātiem", kas ir līdzvērtīgi noteiktam automātam. Tādu automātu sauc strukturāli. To izmanto, piemēram, digitālo elektrisko ķēžu sintēzē uz noteikta elementa bāzes.

    Skatīt arī

    Literatūra

    • Džons Hopkrofts, Rajjevs Motvani, Džefrijs Ulmens Ievads automātu teorijā, valodās un aprēķinos. - M .: Williams, 2002. - S. 528. - ISBN 0-201-44124-1
    • Kasjanovs V.N. Lekcijas par formālo valodu teoriju, automātiem un skaitļošanas sarežģītību. - Novosibirska: NSU, 1995. - C. 112.

    Saites


    Wikimedia fonds. 2010 .

    Skatiet, kas ir "Automātiskā teorija" citās vārdnīcās:

      Automāta teorija

      Automāta teorija- teorētiskās kibernētikas sadaļa, kas pēta matemātiskos modeļus (šeit tiek saukti par automātiem vai mašīnām) reālām vai iespējamām ierīcēm, kas diskrētos ciklos apstrādā diskrētu informāciju. Galvenais ... ... Ekonomikas un matemātikas vārdnīca

      automātu teorija- Teorētiskās kibernētikas nozare, kas pēta reālu vai iespējamu ierīču matemātiskos modeļus (šeit tiek saukti par automātiem vai mašīnām), kas diskrētos ciklos apstrādā diskrētu informāciju. Šīs teorijas galvenie jēdzieni ...... Tehniskā tulkotāja rokasgrāmata

      Eksist., Sinonīmu skaits: 1 tavt (1) ASIS Sinonīmu vārdnīca. V.N. Trišins. 2013... Sinonīmu vārdnīca

      automātu teorija- automatų teorija statusas T joma automatika atitikmenys: angl. automātu teorija vok. Automatenteorija, f rus. automātu teorija, f pranc. theorie des automates, f … Automatikos terminų žodynas

      Šim terminam ir citas nozīmes, skatiet stāvokļa diagrammu. Stāvokļa diagramma ir virzīts grafiks ierobežotam automātam, kurā virsotnes norāda loka stāvokļus, parāda pārejas starp diviem stāvokļiem Praksē ... ... Wikipedia

      Mašīnu un mehānismu teorija (TMM) ir zinātniskā disciplīna par mehānismu un mašīnu vispārīgajām izpētes metodēm, uzbūvi, kinemātiku un dinamiku un to projektēšanas zinātniskajiem pamatiem. Saturs 1 Disciplīnas attīstības vēsture 2 Pamatjēdzieni ... Wikipedia

      TEORIJA- (1) zinātnisko ideju un principu sistēma, kas apkopo praktisko pieredzi un atspoguļo mērķi dabiski modeļi un noteikumi, kas veido (skat.) vai jebkuras zinātnes sadaļu, kā arī noteikumu kopums jebkuru zināšanu jomā miljonu ... ... Lielā Politehniskā enciklopēdija

      Algoritmu teorija Ekonomikas un matemātikas vārdnīca

      Algoritmu teorija- matemātikas nozare, kas pēta algoritmu vispārīgās īpašības. Algoritma ar noteiktām īpašībām konstruēšanas problēmu sauc par algoritmisko problēmu, tās neatrisināmība nozīmē atbilstoša algoritma neesamību; ja…… Ekonomikas un matemātikas vārdnīca

    Grāmatas

    • Automātu teorija. Mācību grāmata bakalaura un maģistrantūras studijām, Kudrjavcevs V.B. Mācību grāmatā ir plašs materiāls par automātu teoriju. Tas iepazīstina ar automāta jēdzienu, sniedz teorijas ...
    automātu teorija
    Automāta teorija- diskrētās matemātikas sadaļa, kas pēta abstraktos automātus - matemātisko modeļu veidā attēlotus datorus - un uzdevumus, ko tie var atrisināt.

    Automātu teorija ir visciešāk saistīta ar algoritmu teoriju: automāts pārvērš diskrēto informāciju soļos diskrētos laika momentos un ģenerē rezultātu ar dotā algoritma soļiem.

    • 1 Terminoloģija
    • 2 Pieteikums
      • 2.1. Tipiski uzdevumi
    • 3 Skatīt arī
    • 4 Literatūra
    • 5 Saites

    Terminoloģija

    Simbols- jebkurš datu atomu bloks, kas var ietekmēt iekārtu. Visbiežāk simbols ir burts parastajā valodā, bet tas var būt, piemēram, diagrammas grafiskais elements.

    • Vārds- rakstzīmju virkne, kas izveidota, izmantojot savienošanu (savienojumu).
    • Alfabēts- ierobežots dažādu rakstzīmju kopums (daudz rakstzīmju)
    • Valoda- vārdu kopums, ko veido dotā alfabēta simboli. Var būt ierobežots vai bezgalīgs.


    Automāti

    Automāti var būt deterministiski vai nedeterministiski.

    Deterministiskais galīgais automāts (DFA)
    • ir tāda pārejas funkcija, ka
    • - sākotnējais stāvoklis
    Nedeterministisks galīgais automāts (NFA)- piecu elementu secība (kopā), kur:
    • - automāta stāvokļu kopums
    • - valodas alfabēts, ko automāts saprot
    • ir pārejas attiecība, kur ir tukšs vārds. Tas nozīmē, ka NFA var pāriet no stāvokļa q uz stāvokli p, atšķirībā no DFA, izmantojot tukšu vārdu, kā arī pāriet no q uz vairākiem stāvokļiem (kas atkal nav iespējams DFA).
    • - sākuma stāvokļu kopums
    • - gala stāvokļu kopums.
    Vārds Automāts nolasa ierobežotu rakstzīmju virkni a1,a2,…., an , kur ai ∈ Σ, ko sauc par ievadvārdu.Visu vārdu kopu raksta kā Σ*. Saņemtais vārds Vārdu w ∈ Σ* automāts pieņem, ja qn ∈ F.

    Tiek uzskatīts, ka valodu L nolasa (akceptē) automāts M, ja tā sastāv no vārdiem w, kuru pamatā ir alfabēts tā, ka, ievadot šos vārdus M, apstrādes beigās tā nonāk vienā no pieņemšanas stāvokļiem F:

    Parasti automāts pāriet no stāvokļa uz stāvokli, izmantojot pārejas funkciju, vienlaikus nolasot vienu rakstzīmi no ievades. Ir automāti, kas var pāriet uz jaunu stāvokli, neizlasot rakstzīmi. Pārejas funkciju bez rakstzīmes nolasīšanas sauc -jump (epsilon-jump).

    Pieteikums

    Automātiskā teorija ir visu digitālo tehnoloģiju pamatā un programmatūra, tāpēc, piemēram, dators ir īpašs gadījums praktiska īstenošana ierobežots automāts.

    Daļa no automātu teorijas matemātiskā aparāta tiek tieši izmantota formālo valodu, tostarp programmēšanas valodu, lekseru un parsētāju izstrādē, kā arī kompilatoru konstruēšanā un pašu programmēšanas valodu izstrādē.

    Vēl viens svarīgs automātu teorijas pielietojums ir matemātiski stingra problēmu atrisināmības un sarežģītības noteikšana.

    Tipiski uzdevumi

    • Automātu uzbūve un minimizēšana- abstrakta automāta konstruēšana no noteiktas klases, kas atrisina doto problēmu (pieņemot doto valodu), iespējams, ar sekojošu minimizēšanu stāvokļu skaita vai pāreju skaita ziņā.
    • Automātu sintēze- doto "elementāru automātu" sistēmas izveidošana, kas līdzvērtīga noteiktam automātam. Šādu automātu sauc par strukturālu. To izmanto, piemēram, digitālo elektrisko ķēžu sintēzē uz noteikta elementa bāzes.

    Skatīt arī

    • Sūknis Lemma
    • Abstrakts automāts
    • Spēle "Dzīve"
    • Automāta minimālā forma
    • Šenona-Lupanova teorēma

    Literatūra

    • Džons Hopkrofts, Rajjevs Motvani, Džefrijs Ulmens. Ievads automātu teorijā, valodās un aprēķinos. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
    • Kasjanovs V. N. Lekcijas par formālo valodu teoriju, automātiem un skaitļošanas sarežģītību. - Novosibirska: NSU, 1995. - C. 112.

    Saites

    • Automātu teorijas pielietojums

    automātu teorija