Automātu teorija, galīgie automāti
Dažādu mašīnu uzbūvi, dizainu, darbības principu lielā mērā nosaka to funkcionālais mērķis. Atšķirt tehnoloģiskās, transporta, skaitļošanas, militārās un citas mašīnas. Dažādās nozarēs plaši tiek ieviesti veseli automātiskie kompleksi, kas paredzēti sarežģītu tehnoloģisko procesu veikšanai. Tiek projektēti un būvēti automāti, kas veic dažādas loģiskās funkcijas (loģiskās mašīnas).
Automātu teorija — kibernētikas sadaļa, kas radās digitālo datoru un vadības mašīnu tehnoloģiju prasību ietekmē. Automātu teorijā pētītie diskrētie automāti ir abstrakti reālu sistēmu (gan tehnisko, gan bioloģisko) modeļi, kas apstrādā diskrētu (digitālu) informāciju diskrētos laika posmos.
Automātu teorija balstās uz precīzām matemātiskām koncepcijām, kas formalizē intuitīvus priekšstatus par automāta darbību (uzvedību) un par tā struktūru (iekšējo struktūru).
Šajā gadījumā informācijas transformācija vienmēr tiek saprasta kā darbība, kas pārveido ievades secības, kas sastāv no burtiem no ievades alfabēta, izvades secībās, kas sastāv no burtiem no izvades alfabēta.
Plaši tiek izmantots matemātiskās loģikas, algebras, varbūtību teorijas, kombinatorikas un grafu teorijas aparāts.
Problēma ar automātu teoriju atsevišķās tās daļās (automātu strukturālā teorija) pieauga no releju-kontaktu ķēžu teorijas, kas sāka veidoties 30. gadu beigās. ieskaitot loģiskās algebras metodes.
Automātu strukturālajā teorijā tiek pētītas dažāda veida shēmas, kas paredzētas, lai aprakstītu, kā tiek izveidots sarežģīts automāts no vienkāršākiem komponentiem (elementiem), kas pareizi savienoti sistēmā.
Cits virziens, ko sauc par automātu abstrakto teoriju, pēta automātu uzvedību (tas ir, to veiktās informācijas transformācijas raksturu), vienlaikus abstrahējoties no to iekšējās struktūras specifikas, un radās 1950. gados.
Abstraktās automātu teorijas ietvaros jēdzienu "automāts" un "mašīna" saturs būtībā ir izsmelts standarta aprakstā par informācijas pārveidošanu, ko veic automāts. Šāda transformācija var būt deterministiska, taču tai var būt arī varbūtības raksturs.
Visvairāk pētītas ir deterministiskās mašīnas (automāti), kas ietver galīgos automātus — galveno automātu teorijas izpētes objektu.
Galīgo stāvokļu mašīnu raksturo ierobežots atmiņas apjoms (iekšējo stāvokļu skaits), un to nosaka, izmantojot pārejas funkciju.Ar zināmu saprātīgu idealizāciju visas mūsdienu matemātiskās mašīnas un pat smadzenes no to darbības viedokļa var uzskatīt par galīgiem automātiem.
Termini "secīgā mašīna", "Milija automāts", "Mūra automāts" tiek lietoti literatūrā (un ne visi autori vienādi) kā sinonīmi terminam "galīgs automāts" vai lai uzsvērtu noteiktas iezīmes ierobežota pārejas funkcijās. automāts.
Automāti ar neierobežotu atmiņu ir Tjūringa mašīna, kas spēj veikt (potenciāli) jebkuru efektīvu informācijas transformāciju. Jēdziens "Tjūringa mašīna" radās agrāk nekā jēdziens "galīgā stāvokļa mašīna" un galvenokārt tiek pētīts algoritmu teorijā.
Abstraktā automātu teorija ir cieši saistīta ar labi zināmām algebriskām teorijām, piemēram, pusgrupu teoriju. No lietišķā viedokļa interesanti ir rezultāti, kas raksturo informācijas transformāciju automātā atmiņas lieluma izteiksmē.
Tā tas ir, piemēram, problēmās ar eksperimentiem ar automātiem (E.F. Mūra darbi u.c.), kur tāda vai cita informācija par automāta pārejas funkcijām vai par tā atmiņas ietilpību tiek iegūta no automātiskās iekārtas rezultātiem. eksperimentiem.
Cits uzdevums ir aprēķināt izvades secību periodus, pamatojoties uz pieejamo informāciju par automāta atmiņas apjomu un ievades secību periodiem.
Liela nozīme ir metožu izstrādei galīgo stāvokļu mašīnu atmiņas samazināšanai un to uzvedības izpētei nejaušās vidēs.
Abstraktajā automātu teorijā sintēzes problēma ir šāda.Runājot par kādu skaidri formalizētu valodu, tiek rakstīti nosacījumi projektētā automāta uzvedībai (automātā attēlotajam notikumam). Šajā gadījumā ir jāizstrādā metodes, kas atbilstoši katram rakstiskajam nosacījumam:
1) noskaidrot, vai pastāv tāda stāvokļa mašīna, ka tās pārveidotā informācija atbilst šim nosacījumam;
2) ja jā, tad tiek konstruētas šādas galīgo stāvokļu mašīnas pārejas funkcijas vai novērtēts tās atmiņas apjoms.
Sintēzes uzdevuma risinājums šādā formulējumā paredz iepriekš izveidot ērtu valodu automāta darbības apstākļu ierakstīšanai ar ērtiem algoritmiem pārejai no ierakstīšanas uz pārejas funkcijām.
Automātu strukturālajā teorijā sintēzes problēma sastāv no noteikta veida elementu ķēdes konstruēšanas, kas realizē ierobežotu automātu, ko nosaka tā pārejas funkcijas. Šajā gadījumā viņi parasti nosaka kādu optimāluma kritēriju (piemēram, minimālo elementu skaitu) un cenšas iegūt optimālu shēmu.
Kā izrādījās vēlāk, tas nozīmē, ka dažas metodes un koncepcijas, kas iepriekš izstrādātas saistībā ar releju kontaktu shēmām, ir piemērojamas cita veida shēmām.
Saistībā ar elektronisko tehnoloģiju attīstību visizplatītākās ir shēmas funkcionālie elementi (loģiskie tīkli). Īpašs loģisko tīklu gadījums ir abstrakti neironu tīkli, kuru elementus sauc par neironiem.
Ir izstrādātas daudzas sintēzes metodes atkarībā no ķēžu veida un informācijas transformācijas, kurai tās paredzētas (Releja ierīču sintēze).
Skaties -Kombinēto ķēžu minimizēšana, Karno kartes, ķēžu sintēze
Galīgā stāvokļa mašīna — vadības sistēmas matemātiskais modelis ar fiksētu (darba laikā nevar palielināties) atmiņas lielumu.
Galīgo stāvokļu mašīnas jēdziens ir matemātiska abstrakcija, kas raksturo vadības sistēmu kopas vispārīgos raksturlielumus (piemēram, vairāku cilpu releja ierīce). Visām šādām sistēmām ir kopīgas iezīmes, kuras ir dabiski pieņemt kā ierobežota automāta definīciju.
Katram pabeigtam automātam ir ieeja, kas pakļauta ārējām ietekmēm un iekšējiem elementiem. Gan ievades, gan iekšējiem elementiem ir noteikts skaits diskrētu stāvokļu, ko tie var uzņemt.
Ievades un iekšējo elementu stāvokļu izmaiņas notiek atsevišķos laika momentos, kuru intervālus sauc par ērcēm. Iekšējo stāvokli (iekšējo stāvokli) lentes beigās pilnībā nosaka iekšējais stāvoklis un ieejas stāvoklis lentes sākumā.
Visas pārējās ierobežotā automāta definīcijas var reducēt līdz šim raksturlielumam, jo īpaši definīcijas, kas pieņem, ka ierobežotam automātam ir izvade, kas ir atkarīga no automāta iekšējā stāvokļa noteiktā laikā.
Runājot par šādu raksturlielumu, tā ievades un iekšējo stāvokļu raksturam nav nozīmes pilnīga automāta aprakstam. Ievades un stāvokļu vietā varat vienkārši apskatīt to numurus nejaušā numerācijā.
Stāvokļa mašīna tiks iestatīta, ja ir norādīta tās iekšējā stāvokļa numura atkarība no iepriekšējā iekšējā stāvokļa numura un iepriekšējā ievades stāvokļa numura. Šāds uzdevums var būt fināla galda formā.
Vēl viens izplatīts veids, kā definēt pilnīgu automātu, ir tā sauktā konstrukcija pāreju diagrammas. Ievades stāvokļi bieži tiek saukti vienkārši par ievadi, un iekšējie stāvokļi ir vienkārši stāvokļi.
Galīgā stāvokļa mašīna var būt gan tehnisko ierīču, gan dažu bioloģisko sistēmu modelis. Pirmā tipa automāti ir, piemēram, releja ierīces un dažādi elektroniskie datori, t.sk. programmējami loģiskie kontrolleri.
Releja ierīces gadījumā ievades stāvokļu lomu spēlē releja ierīces jutīgo elementu stāvokļu kombinācijas (katra šādu stāvokļu kombinācija ir "sarežģīts stāvoklis", ko raksturo visu jutīgo elementu norāde). šie diskrētie stāvokļi, kas viņiem ir noteiktā brīdī). Līdzīgi kā iekšējie stāvokļi darbojas releja ierīces starpelementu stāvokļu kombinācijas.
Programmējams loģiskais kontrolleris (PLC) ir releja darbības ierīces piemērs, ko var saukt par atsevišķu stāvokļa mašīnu.
Faktiski, kad programma ir ievadīta PLC un kontrolieris ir sācis aprēķināt, tā netiek pakļauta ārējai ietekmei un katru nākamo stāvokli pilnībā nosaka tās iepriekšējais stāvoklis. Var pieņemt, ka ieejai ir vienāds stāvoklis katrā pulksteņa ciklā.
Un otrādi, jebkura ierobežota stāvokļa mašīna, kurai ir vienīgais iespējamais ievades stāvoklis, dabiski tiek saukta par autonomu, jo šajā gadījumā ārējā vide nesatur informāciju, kas kontrolētu tās uzvedību.
Skatīt arī:
Mikroprocesoru sistēmu izmantošana elektrotehnikā uz PLC izmantošanas piemēra