A mai technológiai korszakban mind a hardver, mind a szoftver területén óriási fejlődés tapasztalható. A fejlesztés egyik fő területét a hardvertervezési módszerek látták. A ... val növekvő technológia , a Hardver - Szoftver társtervezés koncepciója megvalósítható volt. Különböző módszereket fejlesztenek ki, amelyek szoftverek segítségével teljesen lehet tervezni és szimulálni a hardver rendszereket. Az egyik ilyen módszer az Automata elmélet. Az automaták elmélete a Számítástechnika amely az előre meghatározott lépéssorokat automatikusan követő számítási eszközök absztrakt modelljének megtervezésével foglalkozik. Ez a cikk az automaták bemutatójával kapcsolatos rövid információkat tárgyalja.
Mi az az automata elmélet?
Az Automata szó a görögből származik, ami azt jelenti, hogy „önműködő”. Az Automaton a gép matematikai modellje. Az Automat állapotokból és átmenetekből áll. Mivel a bemenet az automatának adódik, az átmeneti függvénytől függően áttér a következő állapotra. Az átmeneti függvény bemenetei a jelenlegi állapot és a legutóbbi szimbólumok. Ha egy automatának véges számú állapota van, akkor véges automatának vagy Véges állapotú gép . A véges automatákat egy 5 páros képviseli (Q, ∑, δ, qo, F)
Hol,
Q = Véges állapothalmaz.
∑ = véges szimbólumkészlet, más néven az automaták ábécéje.
δ = az átmeneti függvény.
qo = a bemenet kezdeti állapota.
F = Q végállapotainak halmaza
Az automata-elmélet alapvető terminológiái
Az Automata Theory néhány alapvető terminológiája
1 . Ábécé : Az automatikaelmélet bármely véges szimbólumkészlete ábécé néven ismert. Az the betű képviseli az {a, b, c, d, e,} halmaz ábécé halmazát, míg az „a”, „b”, „c”, „d”, „e” halmaz betűit szimbólumok.
két . Húr : Az automatákban a karakterlánc a symbols ábécéhalmazból vett szimbólumok véges sorozata. Például az S = ‘adeaddadc’ karakterlánc érvényes az ∑ = {a, b, c, d, e,} ábécéhalmazra.
3 . A húr hossza : A karakterláncban lévő szimbólumok száma a Húr hossza néven ismert. Az S = ‘adaada’ húr esetében a húr hossza | S | = 6. Ha a karakterlánc hossza 0, akkor üres karakterláncnak hívjuk.
4 . Kleen Star : A symbols szimbólumkészlet unárista operátora adja meg az összes lehetséges húr végtelen halmazát, beleértve a λ-t is, a halmaz összes lehetséges hosszúságával. Képviseli. Például a Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……} halmazhoz.
5. . Kleen bezárása : Ez az ábécéhalmaz összes lehetséges karakterláncának végtelen halmaza, a λ kivételével. Jelöli. A Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..} halmazhoz.
6. . Nyelv : A nyelv a Kleene csillaghalmaz set * részhalmaza egyes ábécéhalmazokhoz Σ. A nyelv lehet véges vagy végtelen. Például, ha egy nyelv az összes lehetséges 2 hosszúságú karakterláncot átveszi a Σ = {a, d} halmaz felett, akkor L = {aa, ad, da, dd}.
Hivatalos nyelvek és automaták
Az automata elméletben a formális nyelv egy húrkészlet, ahol az egyes húrok vannak szimbólumokból áll a véges ábécéhalmazhoz tartozó Σ. Vegyünk egy macskanyelvet, amely tartalmazhat bármilyen karakterláncot az alábbi végtelen halmazból ...
elzár!
meww!
mewww !! ……
A macska nyelvének ábécéje: Σ = {m, e, w,!}. Használja ezt a halmazt egy Véges állapotú automata-m modellhez. Ezután az m modellel jellemzett formális nyelvet jelöljük
L (m)
L (m) = {’nyám!’, ’Meww!’, ’Mewww’, ……}
Az Automaton azért hasznos egy nyelv meghatározásához, mert egy végtelen halmazt képes kifejezni zárt formában. A hivatalos nyelvek nem azonosak a mindennapi életben beszélt természetes nyelvekkel. Egy hivatalos nyelv a gép különböző állapotait jelölheti, ellentétben a szokásos nyelveinkkel. A formális nyelvet a természetes nyelv egy részének, például a szintaxis stb. Modellezésére használják. A formális nyelveket véges állapotú automaták határozzák meg. A véges állapotú automatáknak két fő perspektívája van, amelyek meg tudják mondani, hogy egy karakterlánc van-e a nyelvben, a második pedig az a generátor, amely csak a nyelvet állítja elő.
Determinisztikus véges automaták
A determinisztikus típusú automatáknál, amikor bemenetet adunk, mindig meghatározhatjuk, melyik állapotba kerülne az átmenet. Mivel ez egy véges automata, Deterministic Finite Automata-nak hívják.
Grafikus ábrázolás
Az Állapotdiagram a determinisztikus véges automaták grafikus ábrázolásához használt ábrák. Értsünk meg egy példával. Legyen a determinisztikus véges automaták…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} és az átmeneti függvény legyen
Grafikus ábrázolás táblázatos forma
Államdiagram
Determinisztikus véges állapotú automaták állapotdiagramja
Az állapotdiagramból
- Az állapotokat csúcsok képviselik.
- Az átmeneteket a bemeneti ábécével jelölt ív képviseli.
- Az üres egyetlen bejövő ív a kezdeti állapotot jelenti.
- A kettős körökkel rendelkező állam a végső állapot.
Nem determinisztikus véges automaták
Azokat az automatákat, ahol az adott bemenet kimeneti állapota nem határozható meg, nemdeterminista automatáknak nevezzük. Nem-determinisztikus véges automatáknak is hívják, mivel véges számú állapota van. A nem-determinisztikus véges automaták az 5 –tábla halmazaként vannak ábrázolva, ahol (Q, ∑, δ, qo, F)
Q = véges állapothalmaz.
∑ = Ábécé készlet.
δ = az átmeneti függvény
hol : 
qo = Kezdeti állapot.
Grafikus ábrázolás
A nem determinisztikus véges automatákat az állapotdiagram segítségével ábrázoljuk. Legyen a nem-determinisztikus véges automaták
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Az átmenetek vannak
Grafikus ábrázolás táblázatos forma
Államdiagram
A nem determinisztikus véges automaták állapotdiagramja
Automataelméleti alkalmazások
A automaták elmélete a következőket tartalmazzák.
- Az automaták elmélete nagyon hasznos a számítási elmélet, a fordítói produkciók, az AI stb. Területén.
- A szövegfeldolgozó fordítóknál és a hardverterveknél a véges automatáknak van nagy szerepük.
- AI és IN alkalmazásokhoz programozási nyelvek , A kontextus nélküli nyelvtan nagyon hasznos.
- A biológia területén hasznosak a sejtautomaták.
- A véges mezők elméletében is megtalálhatjuk az Automata alkalmazását.
Ebben a cikkben megtanultunk egy rövid bevezetést az automata elméleti nyelvekre és a számításra. Az automaták már az őskor óta léteznek. Az új technológiák feltalálásával számos új fejlesztés látható ezen a területen. Milyen típusú automatákkal találkozott?
