Darbā analizēta automāta reprezentācija ar daļēji definētām transformācijām - automāta transformāciju kopa. Konstruēts piemērs, kas parāda, ka attiecībā pret modelēšanu nesalīdzināmiem automātiem transformāciju kopas var sakrist. Vēl vairāk - šis rezultāts ir spēkā arī īpaši reducētiem automātiem.
Citāds stāvoklis ir autonomu automātu klasē, kas pētīta sīkāk. Pamatrezultāts:
Līdzīgas transformāciju kopas ar precizitāti līdz izomorfismam nosaka vienu vienīgu īpaši reducētu autonomu automātu.
Automātu teorija pārstāv vadības sistēmas teorijas nodaļu, kas pēta matemātiskus modeļus, kuri pārveido diskrētu informāciju. Šos matemātiskos modeļus sauc par automātiem. No zināma redzes viedokļa šādi pārveidotāji ir gan reālas ierīces (skaitļošanas mašīnas, automāti, dzīvie organismi un tml.), gan abstraktas sistēmas (matemātiskās mašīnas, aksiomātiskās teorijas un tml.). Raksturīga šo pārveidotāju īpašība ir funkcionēšanas diskrētums un to aprakstošo parametru vērtību galīgums.
Automātu teorija radās divdesmitā gadsimta vidū, sakarā ar galīgu automātu īpašību pētīšanu. Ar laiku šīs teorijas pētījuma priekšmets paplašinājās, aplūkojot dažādus galīgu automātu vispārinājumus. Galīgu automātu var raksturot kā ierīci, ar ieejas un izejas kanāliem, kura katrā no diskrētiem laika momentiem (takts momentiem), atrodas vienā no galīga skaita stāvokļiem. Katrā takts momentā pa ieejas kanālu ierīcē ienāk ieejas signāli (no kādas galīgas signālu kopas); tiek norādīts sāvokļu maiņas likums nākošajā takts momentā, ņemot vērā ieejas signālu un ierīces stāvokli iepriekšējā momentā, kā arī izejas signāla vērtība (no kādas galīgas signālu kopas) tekošajā takts momentā kā funkcija no stāvokļa un ieejas signāla tajā pat momentā.
Eksistē dažādas pieejas galīga automāta jēdziena definēšanā, kuras varētu sadalīt grupās: makropieeja un mikropieeja. Makropieejā interesējas par ierīces ārējo uzvedību, par to, kā tā veic ieejas informācijas pārveidi izejas informācijā un par stāvokļu secību, bet neinteresējas par tā iekšējo uzbūvi. Šādā ceļā nonāk pie abstrakta galīga automāta jēdziena. Tātad galīgu automātu var uzdot ar attēlojumu palīdzību, kas apraksta tā "ārējo" funkcionēšanu. Mikropieejā tiek ņemta vērā ierīces struktūra, funkcionēšana un saistība starp tā daļām. Šādā ceļā nonāk pie strukturāla galīga automāta jēdziena, ko sauc arī par automāta shēmu vai loģisko tīklu. Strukturāls galīgs automāts tiek uzdots ar galīga skaita abstraktu automātu, to savienojumu galīgu shēmu, norādot kā shēmas daļas ietekmē viena otru. Galīga abstrakta un galīga strukturāla automātu jēdzienus var uzskatīt par galīga automāta jēdziena sastāvdaļām.
Galīga automāta jēdziena vispārinājumu iegūst vispārinot galīga abstrakta un strukturāla automātu jēdzienus.
Abstraktu automātu iegūst, ja pēc izvēles aplūko (ne obligāti galīgas) ieejas un izejas signālu kopas, sāvokļu kopas, kā arī, pie jēdziena vispārinājuma, stāvokļa un izejas signāla atkarību no ieejas signāla un stāvokļa. Strukturālu automātu iegūst aplūkojot brīvi izvēlētās automātu kopas un to savienošanas shēmas.
Ņemot vērā šo divejādo pieeju automāta jēdzienam visa automātu teorija var tikt sadalīta abstrakto automātu teorijā un strukturālo automātu teorijā. Ar automātiem saista dažādas attiecības starp ieejas un izejas informāciju un stāvokļiem, kurus sauc par automāta uzvedību. Galvenā automātu teorijas problemātika ir saistīta ar šīs uzvedības pētīšanu. Var izdalīt dažus svarīgākos uzvedību veidus, t.i. , kā pārveidotāji un akceptori, kā arī dažas to modifikācijas. Pētot automātus kā pārveidotājus interesējas par ieejas signālu virknes attēlojumu izejas signālu virknē, ko veic automāts. Pētot automātus kā akceptorus interesējas, kādas ieejas signālu galīgas virkņu kopas var atšķirt vienu no otras ar automāta izejas signālu palīdzību. Par strukturālo automātu teorijas galveno saturu var uzskatīt attēlojumu īpašību pētīšanu, kuras realizē automāti, automātu kompozīciju attiecībā pret uzdoto operāciju klasi, kā arī automātu algebru. Pie svarīgākajiem šeit var uzskaitīt automātisko shēmu analīzes sintēzes uzdevumus, t.i., automātu shēmu attēlojumu īpašību aprakstīšana pēc attiecīgajiem attēlojumiem; uzdevumi par vienu automātu izteikšanu ar citiem izmantojot dažādas operācijas u.c.
Automātu teorijai ir plašs pielietojums gan pašā matemātikā un dažādās tās nozarēs (algebrā, matemātiskajā loģikā u.c.), gan arī praktisku uzdevumu risināšanā (ESM analīzē un sintēzē utml.).
Viens no automātu teorijas virzieniem - automātu algebriskā teorija. Tai raksturīga algebras līdzekļu izmantošana automātu pētīšanā. Šī teorija pamatota ar to, ka automātus var aplūkot kā dažas speciālas algebras vai algebriskas sistēmas. Algebriskā pieeja ļauj tieši izmantot algebras rezultātus automātu teorijā, kā arī dažos gadījumos palīdz saistīt automātu teoriju ar citām matemātikas nozarēm.
Šajā darbā izmantosim galīga abstrakta automāta jēdzienu un apskatīsim šādu automātu aprakstīšanu ar to atbilstošajām pusgrupām. Parastā nostādne šajā gadījumā ir tāda, ka automātam piekārto pusgrupu pēc šāda likuma .
Šajā nodaļā aplūkosim jēdzienus un apzīmējumus, kuri turpmāk tiks izmantoti darbā.
Par alfabētu sauksim grafisku simbolu (burtu) galīgu virkni, kuras locekļi ir cits no cita atšķirami. Piemēram, grafisku zīmju virkne A, kur A={a,b,c}, atskaitot simbolus "{" un "}" , uzskatāma par alfabētu. Par vārdiem dotajā alfabētā A sauksim galīgas simbolu virknes, kuru locekļi ir A burti. Piemēram, alfabētā {a,b,c} par vārdiem uzskatāmas simbolu virknes ab,c,bb,acb u.c. Tukšā vārda apzīmēšanai izmantosim simbolu e. Lai apzīmētu visu iespējamo fiksēta alfabēta A vārdu kopu, lietosim simbolu A*.
Divi dotā alfabēta A vārdi ir vienādi, ja:
1) tie abi ir tukšie vārdi,
2) tos abus veido alfabēta A burtu virknes, kurām ir
vienāds locekļu skaits un vienādi attiecīgie locekļi.
Piemēram, ja apskatam alfabētu A, A={a,b,c}, un tajā definētus vārdus a, bc, ab, bc, cc, tad otrais un ceturtais vārds šajā virknē ir uzskatāmi par vienādiem.
Ja u=a1....an ir dotā alfabēta A vārds, kur “j ajĻA ,tad par tā garumu sauksim u veidojošās burtu virknes locekļu skaitu n un apzīmēsim to ar l(u). Piemēram, ja dots alfabēts {a,b,c} un tajā vārds u=ccaba, tad l(u)=5. Tukšā vārda e garums, pēc definīcijas, ir 0, t.i., l(e)=0.
Terminu kopa lietosim matemātikā vispārpieņemtajā nozīmē. Ja A- kopa, tad ½A½-šīs kopas apjoms.
Ja A,B- kopas, tad pieraksts AĮB nozīmē, ka A ir kopas B apakškopa.
Kopu A un B Dekarta reizinājumu apzīmēsim ar A ´ B.
Ar simbolu := aizvietosim vārdisku apgalvojumu " ir pēc definīcijas ".
Ar j: A®B apzīmēsim kopas A attēlojumu kopā B.
Pieņemsim, ka j: A®B ir attēlojums. Mēs teiksim, ka :
1) j ir injekcija, ja no a1 ¹ a2 seko j(a1) ¹ j(a2);
2) j ir sirjekcija, ja “bĻB eksistē tāds aĻA, ka j(a)=b;
3) j ir bijekcija, ja tas vienlaicīgi ir gan sirjekcija, gan injekcija.
Ja j ir injekcija, tad ar j-1 apzīmēsim j inverso attēlojumu.
Ar j(A¢) apzīmēsim apakškopu kopā B, kura sastāv no visiem b Ļ B, kuriem atradīsies a Ļ A¢, ka j(A) = b, t.i. , j(A¢) = {b , $ a Ļ A¢ j(a) = b }.
Pieņemsim, ka j:A®B ir attēlojums un B¢- apakškopa kopā B. Ar j-1(B) apzīmēsim apakškopu kopā A, kura sastāv no visiem tiem a Ļ A, kuriem
j(A)ĻB¢ ,t.i., j-1(B¢) := { a , j(a)ĻB¢ }.
Pieraksts i= 1 n nozīmē, ka indeksi i mainās robežās no 1 līdz n pa visiem naturāliem skaitļiem.…
