Mūsdienu tehnoloģiskajā laikmetā gan aparatūras, gan programmatūras jomā ir notikusi milzīga attīstība. Viena no galvenajām attīstības jomām bija aparatūras dizaina metodes. Ar augoša tehnoloģija , bija iespējams ieviest aparatūras - programmatūras līdzdizaina koncepciju. Tiek izstrādātas dažādas metodes, ar kurām izmantojot programmatūru var pilnībā projektēt un simulēt aparatūras sistēmas. Viena no šādām metodēm ir automātu teorija. Automātu teorija ir filiāle datorzinātne kas nodarbojas ar skaitļošanas ierīču abstrakta modeļa projektēšanu, kas automātiski seko iepriekš noteiktajai darbību secībai. Šajā rakstā ir aplūkota īsa informācija par automātu apmācību.
Kas ir automātu teorija?
Vārds Automata ir atvasināts no grieķu valodas, kas nozīmē “pašdarbība”. Automāts ir mašīnas matemātiskais modelis. Automāts sastāv no stāvokļiem un pārejām. Tā kā ievade tiek dota automātam, tā pāriet uz nākamo stāvokli atkarībā no pārejas funkcijas. Pārejas funkcijas ievadi ir pašreizējais stāvoklis un jaunākie simboli. Ja automātam ir ierobežots stāvokļu skaits, to sauc par ierobežoto automātu vai Galīgā stāvokļa mašīna . Ierobežotos automātus attēlo piecu kopu skaits (Q, ∑, δ, qo, F)
Kur,
Q = ierobežots stāvokļu kopums.
∑ = ierobežota simbolu kopa, ko sauc arī par automātu alfabētu.
δ = pārejas funkcija.
qo = ievades sākotnējais stāvoklis.
F = Q galīgo stāvokļu kopa.
Automātu teorijas pamatterminoloģijas
Daži no automātu teorijas pamatterminiem ir:
1 . Alfabēts : Jebkurš ierobežots simbolu kopums automātu teorijā ir pazīstams kā Alfabēts. Ar burtu∑ kopu {a, b, c, d, e,} sauc par alfabēta kopu, bet kopas “a”, “b”, “c”, “d”, “e” burtus sauc par alfabēta kopu. simboli.
divi . Stīgas : Automātos virkne ir ierobežota simbolu secība, kas ņemta no alfabētu kopas ∑. Piemēram, virkne S = ‘adeaddadc’ ir derīga alfabētu kopai∑ = {a, b, c, d, e,}.
3 . Stīgu garums : Virknē esošo simbolu skaitu sauc par virknes garumu. Virknei S = ‘adaada’ virknes garums ir | S | = 6. Ja virknes garums ir 0, tad to sauc par tukšu virkni.
4 . Kleina zvaigzne : Simbolu kopas Σ vienotais operators dod visu iespējamo virkņu, ieskaitot λ, visu iespējamo garumu kopas Σ bezgalīgo kopu. To pārstāv. Piemēram, kopai Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleina slēgšana : Tas ir visu iespējamo alfabēta kopu virkņu bezgalīgais kopums, izņemot λ. To apzīmē ar. Kopai Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Valoda : Valoda ir Kleene zvaigžņu kopas apakškopa∑ * dažām alfabētu kopām Σ. Valoda var būt ierobežota vai bezgalīga. Piemēram, ja valoda pārņem visas iespējamās virknes 2 garumā virs kopas Σ = {a, d}, tad L = {aa, ad, da, dd}.
Oficiālās valodas un automāti
Automātu teorijā formālā valoda ir virkņu kopa, kur katra virkne atrodas sastāv no simboliem kas pieder pie ierobežotā Alfabēta kopas Σ. Padomāsim par kaķu valodu, kurā var būt visas virknes no zemāk redzamā bezgalīgā komplekta ...
mew!
meww!
mewww !! ……
Kaķu valodas alfabēts ir Σ = {m, e, w,!}. Ļaujiet šo kopu izmantot galīgo stāvokļu automātu modelim-m. Tad formālo valodu, ko raksturo modelis m, apzīmē ar
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ……}
Automāts ir noderīgs valodas definēšanai, jo tas var izteikt bezgalīgu kopu slēgtā formā. Oficiālās valodas nav tas pats, kas dabiskās valodas, kuras mēs runājam ikdienas dzīvē. Formālā valoda var apzīmēt dažādos mašīnas stāvokļus, atšķirībā no mūsu parastajām valodām. Formālo valodu izmanto, lai modelētu dabiskās valodas daļu, piemēram, sintaksi utt. Oficiālās valodas nosaka ierobežoti stāvokļa automāti. Pastāv divas galvenās ierobežoto stāvokļu automātikas perspektīvas - akceptori, kas var pateikt, vai virkne ir valodā, bet otrais ir ģenerators, kas ražo tikai valodas virknes.
Deterministiski ierobežoti automāti
Deterministiskā tipa automātos, kad tiek ievadīts ievads, mēs vienmēr varam noteikt, kurā stāvoklī būtu pāreja. Tā kā tas ir ierobežots automāts, to sauc par Deterministic Finite Automata.
Grafiskais attēlojums
Stāvokļa diagramma ir digrafi, ko izmanto deterministisko galīgo automātu grafiskam attēlojumam. Ļaujiet mums saprast ar piemēru. Lai deterministiski ierobežoti automāti būtu…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} un pārejas funkcija ir
Grafiskā attēlojuma tabulas forma
Valsts diagramma
Deterministisko galīgo stāvokļu automātu stāvokļu diagramma
No stāvokļa diagrammas
- Stāvokļus attēlo virsotnes.
- Pārejas attēlo loka apzīmējums ar ievades alfabētu.
- Tukšā viena ienākošā loka apzīmē sākotnējo stāvokli.
- Valsts ar dubultiem apļiem ir galīgais stāvoklis.
Nedeterministiski ierobežoti automāti
Automātus, kur konkrētās ievades izejas stāvokli nevar noteikt, sauc par nedeterministiskiem automātiem. To sauc arī par nedeterministiskiem galīgiem automātiem, jo tam ir ierobežots stāvokļu skaits. Nedeterministiski galīgie automāti tiek attēloti kā 5 kopu kopa, kur (Q, ∑, δ, qo, F)
Q = ierobežots stāvokļu kopums.
∑ = Alfabēta komplekts.
δ = pārejas funkcija
kur : 
qo = Sākotnējais stāvoklis.
Grafiskais attēlojums
Ar stāvokļa diagrammu tiek attēloti nedeterministiski galīgi automāti. Ļaujiet nedeterministiskiem galīgajiem automātiem būt
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Pārejas ir
Grafiskā attēlojuma tabulas forma
Valsts diagramma
Nenoteiktu galīgo automātu stāvokļa diagramma
Automātu teorijas lietojumi
Lietojumprogrammas automātu teorija iekļaujiet sekojošo.
- Automātu teorija ir ļoti noderīga skaitļošanas teorijas, kompilatoru produkcijas, AI uc jomās.
- Teksta apstrādes kompilatoros un aparatūras projektos liela nozīme ir ierobežotiem automatiem.
- Pielietojumam AI un IN programmēšanas valodas , Ļoti noderīga ir gramatika bez konteksta.
- Bioloģijas jomā noder mobilie automāti.
- Arī ierobežoto lauku teorijā mēs varam atrast Automata pielietojumu.
Šajā rakstā mēs esam iemācījušies īsu ievadu par automātu teorijas valodām un aprēķiniem. Automāti ir bijuši kopš aizvēsturiskā perioda. Izgudrojot jaunas tehnoloģijas, šajā jomā ir redzami daudzi jaunumi. Ar kāda veida automātiem esat saskāries?
