Teorija automata: Terminologije i primjene

Isprobajte Naš Instrument Za Uklanjanje Problema





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

Grafički prikaz Tablični oblik

Dijagram stanja

Dijagram stanja determinističkih automata konačnog 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

Grafički prikaz Tablični oblik

Dijagram stanja

Dijagram stanja nedeterminističkih konačnih automata

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?