V današnji tehnološki dobi se je področje strojne in programske opreme izjemno razvilo. Eno glavnih področij razvoja je bilo vidno v metodah zasnove strojne opreme. Z rastoča tehnologija , je bilo mogoče uvesti koncept strojne opreme - sooblikovanje programske opreme. Razvite so različne metode, s katerimi z uporabo programske opreme v celoti lahko načrtujemo in simuliramo strojne sisteme. Ena izmed takih metod je teorija avtomatov. Teorija avtomatov je veja Računalništvo ki se ukvarja z oblikovanjem abstraktnega modela računalniških naprav, ki samodejno sledijo vnaprej določenemu zaporedju korakov. Ta članek obravnava kratke informacije o vajah za avtomate.
Kaj je teorija avtomatov?
Beseda Automata izhaja iz grščine, kar pomeni 'samoaktiven'. Automaton je matematični model stroja. Avtomat je sestavljen iz stanj in prehodov. Ko vhod dobimo v avtomatu, ta preide v naslednje stanje, odvisno od funkcije prehoda. Vhodi v funkcijo prehoda so trenutno stanje in nedavni simboli. Če ima Avtomat končno število stanj, je znan kot Končni avtomati oz Končni državni stroj . Končni avtomati so predstavljeni s 5 sklopi (Q, ∑, δ, qo, F)
Kje,
Q = Končni nabor stanj.
∑ = končni nabor simbolov, imenovan tudi abeceda avtomatov.
δ = prehodna funkcija.
qo = začetno stanje vnosa.
F = niz končnih stanj Q.
Osnovne terminologije teorije avtomatov
Nekatere osnovne terminologije teorije avtomatov so:
1. . Abeceda : Vsak končni nabor simbolov v teoriji avtomatov je znan kot abeceda. Predstavljen s črko∑, se množica {a, b, c, d, e,} imenuje abeceda, črke množice „a“, „b“, „c“, „d“, „e“ pa simboli.
dva . Vrvica : V avtomatih je niz končno zaporedje simbolov, vzeto iz abecednega niza ∑, na primer niz S = ‘adeaddadc’ velja za abecedni niz∑ = {a, b, c, d, e,}.
3. . Dolžina niza : Število simbolov v nizu je znano kot Dolžina niza. Za niz S = 'adaada' je dolžina niza | S | = 6. Če je dolžina niza 0, se imenuje prazen niz.
4. . Kleen Star : Unarni operator na naboru simbolov Σ daje neskončen niz vseh možnih nizov, vključno z λ, vseh možnih dolžin nad naborom Σ. Zastopal ga je. Na primer, za nabor Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5. . Zapiranje Kleen : To je neskončna množica vseh možnih nizov abecede brez λ. Označuje se z. Za množico Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6. . Jezik : Jezik je podnabor zvezde Kleene star * za nekatere abecedne sklope Σ. Jezik je lahko končen ali neskončen. Na primer, če jezik zavzame vse možne nize dolžine 2 nad naborom Σ = {a, d}, potem je L = {aa, ad, da, dd}.
Uradni jeziki in avtomati
V teoriji avtomatov je formalni jezik niz nizov, kjer je vsak niz sestavljen iz simbolov ki pripadajo končnemu abecednemu nizu Σ. Upoštevajmo mačji jezik, ki lahko vsebuje vse nize iz spodnjega neskončnega nabora ...
mija!
mej!
mewww !! ......
Za mačji jezik je nastavljena abeceda Σ = {m, e, w,!}. Naj se ta niz uporablja za model avtomata s končnim stanjem-m. Potem je formalni jezik, za katerega je značilen model m, označen z
L (m)
L (m) = {'mew!', 'Meww!', 'Mewww', ……}
Avtomat je koristen za določanje jezika, ker lahko izraža neskončno množico v zaprti obliki. Formalni jeziki niso enaki naravnim jezikom, ki jih govorimo v vsakdanjem življenju. Formalni jezik lahko označuje različna stanja stroja, za razliko od naših običajnih jezikov. Formalni jezik se uporablja za modeliranje dela naravnega jezika, kot je skladnja itd. Formalne jezike določajo avtomati s končnimi stanji. Obstajata dve glavni perspektivi končnih avtomatov - sprejemniki, ki lahko ugotovijo, ali je niz v jeziku, drugi pa je generator, ki proizvaja samo nize v jeziku.
Deterministični končni avtomati
V determinističnem tipu avtomatov lahko kadar damo vhod vedno določimo, v katero stanje bi bil prehod. Ker je to končni avtomat, se imenuje deterministični končni avtomat.
Grafični prikaz
Diagram stanja je digraf, ki se uporablja za grafični prikaz determinističnih končnih avtomatov. Razumimo s primerom. Naj bodo deterministični končni avtomati ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} in prehodna funkcija je
Tabelarična oblika grafičnega prikaza
Diagram stanja
Diagram stanja determinističnih končnih avtomatov
Iz diagrama stanja
- Države so predstavljene z oglišči.
- Prehodi so predstavljeni z lokom, označenim z vhodno abecedo.
- Prazen en dohodni lok predstavlja začetno stanje.
- Država z dvojnimi krogi je končno stanje.
Nedeterministični končni avtomati
Avtomati, pri katerih izhodnega stanja za dani vhod ni mogoče določiti, se imenujejo nedetermični avtomati. Imenujejo se tudi nedeterministični končni avtomati, saj ima končno število stanj. Nedeterministični končni avtomati so predstavljeni kot niz 5 -členov, kjer (Q, ∑, δ, qo, F)
Q = končni nabor držav.
∑ = Set abecede.
δ = prehodna funkcija
kje : 
qo = Začetno stanje.
Grafični prikaz
Nedeterministični končni avtomati so predstavljeni s pomočjo diagrama stanja. Naj bodo nedeterministični končni avtomati
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Prehodi so
Tabelarična oblika grafičnega prikaza
Diagram stanja
Diagram stanja nedeterminističnih končnih avtomatov
Aplikacije za teorijo avtomata
Uporabe teorija avtomatov vključujejo naslednje.
- Teorija avtomatov je zelo koristna na področjih teorije računanja, produkcije prevajalnikov, umetne inteligence itd.
- Pri prevajalnikih za obdelavo besedila in oblikovanju strojne opreme imajo končni avtomati glavno vlogo.
- Za aplikacije v AI in v programskih jezikov , Slovnica brez konteksta je zelo koristna.
- Na področju biologije so koristni celični avtomati.
- V teoriji končnih polj lahko najdemo tudi aplikacijo Automata.
V tem članku smo se naučili kratkega uvoda v teoretske jezike avtomatov in računanje. Avtomati obstajajo že od prazgodovine. Z izumom novih tehnologij je na tem področju vidno veliko novih dosežkov. Na katero vrsto avtomatov ste že naleteli?
