Tänasel tehnoloogilisel ajastul on nii riistvara kui ka tarkvara valdkonnas toimunud tohutu areng. Riistvara kujundamise meetodites nähti üht peamist arenguvaldkonda. Koos kasvav tehnoloogia , riistvara - tarkvara kaasprojekteerimist oli võimalik rakendada. Välja töötatakse erinevad meetodid, mille abil tarkvara kasutamine riistvarasüsteeme saab täielikult kujundada ja simuleerida. Üks sellistest meetoditest on automaatteooria. Automaatteooria on filiaal arvutiteadus mis tegeleb etteantud sammude järjekorda automaatselt järgivate arvutiseadmete abstraktse mudeli kujundamisega. Selles artiklis käsitletakse lühiteavet automaatide õpetuse kohta.
Mis on automaatteooria?
Sõna Automata on tuletatud kreeka keelest, mis tähendab 'isetegevus'. Automaton on masina matemaatiline mudel. Automaat koosneb olekutest ja üleminekutest. Kuna sisend antakse automaadile, läheb see üle järgmisse olekusse, sõltuvalt üleminekufunktsioonist. Siirdefunktsiooni sisendid on praegune olek ja hiljutised sümbolid. Kui automaadil on piiratud arv olekuid, tuntakse seda kui piiratud automaate või Lõplik olekumasin . Lõplikud automaadid on tähistatud 5-kahega (Q, ∑, δ, qo, F)
Kus
Q = piiratud olekukomplekt.
∑ = piiratud sümbolite kogum, mida nimetatakse ka automaatide tähestikuks.
δ = siirdefunktsioon.
qo = sisendi algolek.
F = Q lõppseisundite kogum.
Automaatiteooria põhiterminid
Mõned automaatteooria põhiterminid on
1 . Tähestik : Automaatide teoorias tuntakse kõiki piiratud sümbolite kogumit tähestikuna. Tähte∑ tähistab kogumit {a, b, c, d, e,} tähestikukomplekt, seevastu hulga „a”, „b”, „c”, „d”, „e” tähte sümbolid.
kaks . String : Automaatides on string tähtede komplektist taken võetud sümbolite lõplik jada. Näiteks täht S = ‘adeaddadc’ kehtib tähestikukomplektil∑ = {a, b, c, d, e,}.
3 . Stringi pikkus : Stringis olevate sümbolite arvu nimetatakse stringi pikkuseks. Stringi S = ‘adaada’ jaoks on stringi pikkus | S | = 6. Kui stringi pikkus on 0, nimetatakse seda tühjaks stringiks.
4 . Kleen Star : See on unaaroperaator sümbolite hulgal which, mis annab lõpmatu hulga kõikidest võimalikest stringidest, kaasa arvatud λ, kogu komplekti võimalikest pikkustest Σ. Seda esindas. Näiteks hulga Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……} korral.
5 . Kleen Sulgemine : See tähestikukomplekti kõigi võimalike stringide lõpmatu hulk, välja arvatud λ. Seda tähistatakse. Hulga Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..} jaoks.
6 . Keel : Keel on osade tähestikukomplektide Kleene tähekomplekti∑ * alamhulk. Keel võib olla piiratud või lõpmatu. Näiteks kui keel võtab kõik võimalikud stringid pikkusega 2 üle hulga Σ = {a, d}, siis L = {aa, ad, da, dd}.
Ametlikud keeled ja automaadid
Automaatide teoorias on ametlik keel stringide komplekt, kus iga string on koosneb sümbolitest mis kuulub piiratud tähestiku komplekti Σ. Mõelgem kassi keelele, mis võib sisaldada mis tahes stringe allpool olevast lõpmatust komplektist ...
mew!
meww!
mewww !! ……
Kassikeele tähestik on Σ = {m, e, w,!}. Kasutage seda komplekti piiratud oleku automaatide mudeli m korral. Seejärel tähistatakse vormi keelt, mida iseloomustab mudel m, tähisega
L (m)
L (m) = {’mew!’, ‘Meww!’, ‘Mewww’, ……}
Automaat on keele määratlemiseks kasulik, kuna see võib väljendada lõpmatut kogumit suletud kujul. Ametlikud keeled ei ole samad kui loomulikud keeled, mida me igapäevases elus räägime. Ametlik keel võib erinevalt meie tavakeeltest tähistada masina erinevaid olekuid. Ametlikku keelt kasutatakse loomuliku keele osa, näiteks süntaks jne, modelleerimiseks. Ametlikud keeled on määratletud piiratud olekuautomaatidega. Piiratud olekuautomaatidel on kaks peamist vaatenurka: aktseptorid, kes oskavad öelda, kas string on keeles, ja teine on generaator, mis toodab ainult keeles olevaid stringe.
Deterministlikud lõplikud automaadid
Deterministlikus tüüpi automaatides võime sisendi andmisel alati kindlaks teha, millisesse olekusse üleminek oleks. Kuna see on piiratud automaat, nimetatakse seda Deterministic Finite Automata.
Graafiline esitus
Olekudiagramm on digrafaaž, mida kasutatakse deterministlike lõplike automaatide graafiliseks esitamiseks. Mõistkem ühe näitega. Olgu deterministlikud piiratud automaadid…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} ja üleminekufunktsioon olema
Graafilise esituse tabelivorm
Riigi skeem
Deterministlike lõplike olekuautomaatide olekudiagramm
Olekudiagrammilt
- Osariike esindavad tipud.
- Üleminekuid tähistab kaar, mis on tähistatud sisendtähestikuga.
- Tühi üks sissetulev kaar tähistab algolekut.
- Topeltringidega riik on lõplik riik.
Mittemääravad lõplikud automaadid
Automaatid, kus antud sisendi väljundi olekut pole võimalik kindlaks määrata, nimetatakse mitteterministlikeks automaatideks. Seda nimetatakse ka mitteterministlikuks lõplikuks automaadiks, kuna sellel on piiratud arv olekuid. Mitteterministlik lõplik automaat on esitatud 5-korruselisena, kus (Q, ∑, δ, qo, F)
Q = piiratud olekute kogum.
∑ = Tähestiku komplekt.
5 = üleminekufunktsioon
kus : 
qo = Esialgne olek.
Graafiline esitus
Mittemääravaid lõplikke automaate on kujutatud olekudiagrammi abil. Olgu mitteterministlikud lõplikud automaadid
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Üleminekud on
Graafilise esituse tabelivorm
Riigi skeem
Mittetermineerivate lõplike automaatide olekudiagramm
Automaatide teooria rakendused
Rakendused automaatide teooria sisaldama järgmist.
- Automaatteooriast on väga palju kasu arvutusteooria, kompilaatorite toodangu, tehisintellekti jms valdkonnas.
- Tekstitöötluse kompilaatorite ja riistvara kujunduste puhul mängivad suurt rolli piiratud automaadid.
- Tehisintellektis ja in programmeerimiskeeled , Kontekstivaba grammatika on väga kasulik.
- Bioloogia valdkonnas on kasulikud raku automaadid.
- Lõplike väljade teoorias leiame ka Automata rakenduse.
Selles artiklis oleme õppinud lühikese sissejuhatuse automaatteooria keeltesse ja arvutamisse. Automaatid on olnud juba eelajaloolisest ajast. Uute tehnoloogiate leiutamisel on selles valdkonnas näha palju uusi arenguid. Mis tüüpi automaatidega olete kokku puutunud?
