Šiandienos technologijos epochoje tiek aparatinės, tiek programinės įrangos srityje įvyko didžiulė plėtra. Viena iš pagrindinių plėtros sričių buvo aparatinės įrangos projektavimo metodai. Su auganti technologija , buvo galima įgyvendinti aparatinės įrangos - programinės įrangos bendro dizaino koncepciją. Sukuriami skirtingi metodai, kuriais naudojant programinę įrangą galima visiškai suprojektuoti ir imituoti aparatinės įrangos sistemas. Vienas iš tokių metodų yra automatų teorija. Automatų teorija yra informatika kuris susijęs su abstraktaus skaičiavimo įrenginių modelio projektavimu, kuris automatiškai vykdo iš anksto nustatytą žingsnių seką. Šiame straipsnyje aptariama trumpa informacija apie automatų mokymo programą.
Kas yra automatų teorija?
Žodis „Automata“ yra kilęs iš graikų kalbos, o tai reiškia „savaime veikiantis“. „Automaton“ yra matematinis mašinos modelis. Automatas susideda iš būsenų ir perėjimų. Kadangi įvestis suteikiama automatui, jis pereina į kitą būseną, priklausomai nuo perėjimo funkcijos. Perėjimo funkcijos įvestys yra dabartinė būsena ir naujausi simboliai. Jei automatas turi ribotą būsenų skaičių, jis žinomas kaip baigtiniai automatai arba Galutinė valstybės mašina . Galutinius automatus vaizduoja 5 atkarpos (Q, ∑, δ, qo, F)
Kur,
Q = baigtinis būsenų rinkinys.
∑ = baigtinis simbolių rinkinys, dar vadinamas automatų abėcėle.
δ = perėjimo funkcija.
qo = pradinė įvesties būsena.
F = Q galutinių būsenų rinkinys.
Pagrindinės automatų teorijos terminijos
Kai kurios pagrindinės automatų teorijos terminologijos yra
1 . Abėcėlė : Bet koks baigtinis automatų teorijos simbolių rinkinys yra žinomas kaip Abėcėlė. Raidė∑ atstovaujama aibė {a, b, c, d, e,} vadinama Abėcėlės rinkiniu, o aibės „a“, „b“, „c“, „d“, „e“ raidės vadinamos abėcėlės rinkiniu. simboliai.
du . Stygos : Automatuose eilutė yra baigtinė simbolių seka, paimta iš abėcėlių rinkinio ∑. Pavyzdžiui, eilutė S = ‘adeaddadc’ galioja abėcėlių rinkinyje∑ = {a, b, c, d, e,}.
3 . Stygos ilgis : Simbolių skaičius eilutėje yra žinomas kaip eilutės ilgis. Stygai S = ‘adaada’ eilutės ilgis yra | S | = 6. Jei eilutės ilgis yra 0, tada ji vadinama tuščia eilute.
4 . Kleen Star : Tai unarinis simbolių rinkinio operator operatorius, kuris suteikia begalinį visų galimų eilučių rinkinį, įskaitant λ, visų galimų ilgių per rinkinį Σ. Ją atstovavo. Pavyzdžiui, aibei set = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen uždarymas : Tai begalinis visų galimų abėcėlės rinkinių eilučių rinkinys, išskyrus λ. Tai žymima. Aibei Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Kalba : Kalba yra kai kurių abėcėlių rinkinio le Kleene žvaigždžių rinkinio pogrupis set. Kalba gali būti baigtinė arba begalinė. Pvz., Jei kalba užima visas galimas 2 ilgio eiles per aibę Σ = {a, d}, tada L = {aa, ad, da, dd}.
Oficialios kalbos ir automatai
Automatų teorijoje oficiali kalba yra eilučių rinkinys, kuriame yra kiekviena eilutė susideda iš simbolių priklausantis baigtiniam Abėcėlės rinkiniui Σ. Panagrinėkime katės kalbą, kurioje gali būti bet kokios eilutės iš žemiau pateikto begalinio rinkinio ...
mew!
meww!
mewww !! ……
Kačių kalbos abėcėlė yra Σ = {m, e, w,!}. Tegul šis rinkinys naudojamas baigtinių būsenų automatų modeliui-m. Tada formali kalba, kuriai būdingas modelis m, žymima
L (m)
L (m) = {„mew!“, „Meww!“, „Mewww“, ……}
Automatinis įrankis yra naudingas apibrėžiant kalbą, nes jis gali išreikšti begalinį rinkinį uždara forma. Oficialios kalbos nėra tas pats, kas natūralios kalbos, kuriomis kalbame kasdieniame gyvenime. Formali kalba gali žymėti skirtingas mašinos būsenas, skirtingai nei mūsų įprastos kalbos. Formali kalba naudojama natūralios kalbos, pavyzdžiui, sintaksės ir pan., Modeliavimui. Formalias kalbas apibrėžia baigtiniai būsenos automatai. Yra dvi pagrindinės baigtinių būsenos automatų perspektyvos - priėmėjai, kurie gali pasakyti, ar eilutė yra kalboje, o antroji yra generatorius, kuris gamina tik kalbos eilutes.
Deterministiniai baigtiniai automatai
Deterministinio tipo automatuose, kai pateikiama įvestis, mes visada galime nustatyti, į kurią būseną būtų pereita. Kadangi tai yra baigtinis automatas, jis vadinamas deterministiniu baigtiniu automatu.
Grafinis vaizdavimas
Būklės diagrama yra digrafai, naudojami grafiniam deterministinių baigtinių automatų vaizdavimui. Leiskite mums suprasti pavyzdžiu. Tegul deterministiniai baigtiniai automatai yra ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} ir perėjimo funkcija būti
Grafinio pavaizdavimo lentelė
Valstybės schema
Deterministinių baigtinių būsenų automatų būsenos diagrama
Iš būsenos diagramos
- Būsenas vaizduoja viršūnės.
- Perėjimus vaizduoja lankas, pažymėtas įvesties abėcėle.
- Tuščias vienas įeinantis lankas reiškia pradinę būseną.
- Valstybė su dvigubais apskritimais yra galutinė būsena.
Nedeterministiniai baigtiniai automatai
Automatai, kurių nurodytos įvesties išvesties būsenos nustatyti negalima, vadinami nedeterministiniais automatais. Jis taip pat vadinamas nedeterministiniais baigtiniais automatais, nes turi ribotą būsenų skaičių. Nedeterminuoti baigtiniai automatai vaizduojami kaip 5 aibių aibė, kur (Q, ∑, δ, qo, F)
Q = baigtinis valstybių rinkinys.
∑ = Abėcėlės rinkinys.
δ = perėjimo funkcija
kur : 
qo = Pradinė būsena.
Grafinis vaizdavimas
Nedeterministiniai baigtiniai automatai vaizduojami būsenos diagramos pagalba. Tegul nenustatomi baigtiniai automatai
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Perėjimai yra
Grafinio pavaizdavimo lentelė
Valstybės schema
Nenustatytų baigtinių automatų būsenos diagrama
Automatų teorijos programos
Programos automatų teorija įtraukti šiuos dalykus.
- Automatų teorija yra labai naudinga skaičiavimo teorijos, kompiliatorių produkcijos, dirbtinio intelekto ir kt. Srityse.
- Kalbant apie teksto apdorojimo kompiliatorius ir aparatūros dizainą, svarbų vaidmenį vaidina baigtiniai automatai.
- Taikymui dirbtinio intelekto ir in programavimo kalbos , Gramatika be konteksto yra labai naudinga.
- Biologijos srityje naudingos korinio ryšio automatai.
- Ribotų laukų teorijoje taip pat galime rasti „Automata“ pritaikymą.
Šiame straipsnyje mes sužinojome trumpą automatų teorijos kalbų ir skaičiavimo įvadą. Automatai egzistuoja nuo priešistorinio laikotarpio. Išradus naujas technologijas, šioje srityje pastebima daugybė naujų pokyčių. Su kokio tipo automatais susidūrėte?
