U današnjoj tehnološkoj eri i hardversko i softversko područje doživjelo je strašan razvoj. Jedno od glavnih područja razvoja vidjelo se u metodama dizajna hardvera. Uz rastuća tehnologija , koncept Hardversko - softverskog ko-dizajna bilo je moguće implementirati. Razvijene su različite metode kojima se, pomoću softvera može se u potpunosti dizajnirati i simulirati hardverski sustav. Jedna od takvih metoda je teorija automata. Teorija automata grana je informatika koja se bavi dizajniranjem apstraktnog modela računarskih uređaja koji automatski slijede unaprijed određeni slijed koraka. Ovaj članak raspravlja o kratkim informacijama o vodiču za automate.
Što je teorija automata?
Riječ Automata izvedena je iz grčkog, što znači 'samo-djelujući'. Automat je matematički model stroja. Automat se sastoji od stanja i prijelaza. Kako se ulaz daje automatu, on prelazi u sljedeće stanje, ovisno o prijelaznoj funkciji. Ulazi u funkciju prijelaza su trenutno stanje i nedavni simboli. Ako Automat ima konačan broj stanja, poznat je kao Konačni automati ili Konačni državni stroj . Konačni automati predstavljeni su s 5 sklopova (Q, ∑, δ, qo, F)
Gdje,
Q = Konačni skup stanja.
∑ = konačni skup simbola koji se također naziva Abeceda automata.
δ = prijelazna funkcija.
qo = početno stanje ulaza.
F = skup konačnih stanja Q.
Osnovne terminologije teorije automata
Neke od osnovnih terminologija teorije automata su
1 . Abeceda : Bilo koji konačni skup simbola u teoriji automata poznat je kao abeceda. Predstavljen slovom∑ skup {a, b, c, d, e,} naziva se Abecedni skup, dok se slova skupa 'a', 'b', 'c', 'd', 'e' nazivaju simboli.
dva . Niz : U automatima je niz konačan slijed simbola preuzet iz abecednog skupa ∑, Na primjer, niz S = ‘adeaddadc’ vrijedi za abecedni skup∑ = {a, b, c, d, e,}.
3 . Duljina niza : Broj prisutnih simbola u nizu poznat je pod nazivom Duljina niza. Za niz S = ‘adaada’ duljina niza je | S | = 6. Ako je duljina niza 0, tada se naziva praznim nizom.
4 . Kleen Star : Unarni je operator na skupu simbola Σ koji daje beskonačni skup svih mogućih nizova, uključujući λ, svih mogućih duljina nad skupom Σ. Predstavljao je. Na primjer, za skup Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Zatvaranje Kleen : To je beskonačni skup svih mogućih nizova abecede, isključujući λ. Označava se sa. Za skup Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Jezik : Jezik je podskup Kleeneova zvjezdanog skupa∑ * za neki Abecedni skup Σ. Jezik može biti konačan ili beskonačan. Na primjer, ako jezik zauzme sve moguće nizove duljine 2 preko skupa Σ = {a, d}, tada je L = {aa, ad, da, dd}.
Formalni jezici i automati
U teoriji automata, formalni jezik je skup žica, gdje je svaki niz sastavljen od simbola koji pripada konačnom abecednom skupu Σ. Razmotrimo mačji jezik koji može sadržavati bilo koji niz iz donjeg beskonačnog skupa ...
mjau!
jao!
mewww !! ......
Abeceda postavljena za mačji jezik je Σ = {m, e, w,!}. Neka se ovaj skup koristi za model automata konačnog stanja-m. Tada se formalni jezik koji karakterizira model m označava sa
L (m)
L (m) = {‘jauuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu…’
Automat je koristan za definiranje jezika jer može izraziti beskonačni skup u zatvorenom obliku. Formalni jezici nisu isto što i prirodni jezici kojima govorimo u svakodnevnom životu. Formalni jezik može označavati različita stanja stroja, za razliku od naših redovnih jezika. Formalni jezik koristi se za modeliranje dijela prirodnog jezika kao što je sintaksa itd. Formalni jezici definirani su automatima konačnih stanja. Dvije su glavne perspektive automata konačnih stanja - akcepti koji mogu znati je li niz u jeziku, a drugi je generator koji proizvodi samo nizove u jeziku.
Deterministički konačni automati
U determinističkom tipu automata, kada se daje ulaz, uvijek možemo odrediti u koje bi stanje bio prijelaz. Kako je ovo konačni automat, naziva se determinističkim konačnim automatima.
Grafički prikaz
Dijagram stanja su digrafi koji se koriste za grafički prikaz determinističkih konačnih automata. Razumijemo na primjeru. Neka deterministički konačni automati budu ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} a prijelazna funkcija biti
Grafički prikaz Tablični oblik
Dijagram stanja
Dijagram stanja determinističkih automata konačnog stanja
Iz dijagrama stanja
- Države su predstavljene vrhovima.
- Prijelazi su predstavljeni lukom označenim ulaznom abecedom.
- Prazni pojedinačni dolazni luk predstavlja početno stanje.
- Država s dvostrukim krugovima je konačno stanje.
Nedeterministički konačni automati
Automati kod kojih se ne može odrediti stanje izlaza za zadani ulaz nazivaju se ne-deterministički automati. Zovu se i nedeterministički konačni automati, jer ima konačan broj stanja. Nedeterministički konačni automati predstavljeni su kao skup od 5 - parova gdje (Q, ∑, δ, qo, F)
Q = konačni skup stanja.
∑ = Abeceda postavljena.
δ = prijelazna funkcija
gdje : qo = Početno stanje.
Grafički prikaz
Nedeterministički konačni automati prikazani su uz pomoć dijagrama stanja. Neka budu nedeterministički konačni automati
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Prijelazi su
Grafički prikaz Tablični oblik
Dijagram stanja
Dijagram stanja nedeterminističkih konačnih automata
Primjene teorije automata
Primjene teorija automata uključuju sljedeće.
- Teorija automata vrlo je korisna u područjima Teorije računanja, izrade kompajlera, AI, itd.
- Za kompajlere za obradu teksta i dizajne hardvera, konačni automati igraju glavnu ulogu.
- Za programe u AI i na programski jezici , Gramatika bez konteksta vrlo je korisna.
- Na polju biologije korisni su stanični automati.
- U teoriji konačnih polja također možemo pronaći primjenu Automata.
U ovom smo članku naučili kratki uvod u jezike teorije automata i računanje. Automati postoje od pretpovijesnog razdoblja. Izumom novih tehnologija na ovom se polju vide mnogi novi razvoji. Na koju ste vrstu automata naišli?