A l’era tecnològica actual, el camp del maquinari i el programari ha experimentat un desenvolupament enorme. Una de les principals àrees de desenvolupament es va veure en els mètodes de disseny de maquinari. Amb el tecnologia creixent , es va poder implementar el concepte de co-disseny de maquinari - programari. Es desenvolupen diferents mètodes mitjançant els quals, mitjançant programari es pot dissenyar i simular completament els sistemes de maquinari. Un d’aquests mètodes és la teoria dels autòmats. La teoria dels autòmats és la branca de Ciències de la Computació que tracta de dissenyar el model abstracte de dispositius informàtics que segueixen automàticament la seqüència de passos predeterminada. En aquest article es parla d'informació breu sobre el tutorial d'autòmats.
Què és la teoria dels autòmats?
La paraula Autòmats deriva del grec, que significa 'actuar per si mateix'. Un automata és un model matemàtic de la màquina. L’automat consisteix en estats i transicions. A mesura que l'entrada es dóna a l'autòmat, fa una transició al següent estat, depenent de la funció de transició. Les entrades per a la funció de transició són símbols d'estat actual i recents. Si un automata té un nombre finit d’estats, es coneix com a autòmats finits o Màquina d'estats finits . Els autòmats finits estan representats per una tuple de 5 (Q, ∑, δ, qo, F)
On,
Q = Conjunt d'estats finits.
∑ = conjunt finit de símbols també anomenat alfabet dels autòmats.
δ = la funció de transició.
qo = estat inicial de l'entrada.
F = conjunt d'estats finals de Q.
Terminologies bàsiques de la teoria dels autòmats
Algunes de les terminologies bàsiques de la teoria dels autòmats són:
1 . Alfabet : Qualsevol conjunt finit de símbols de la teoria dels autòmats es coneix com a alfabet. Representat per la lletra∑, el conjunt {a, b, c, d, e,} es diu conjunt alfabètic, mentre que les lletres del conjunt 'a', 'b', 'c', 'd', 'e' es diuen símbols.
2 . Corda : En els autòmats, una cadena és una seqüència finita de símbols extrets del conjunt alfabètic ∑, per exemple, la cadena S = ‘adeaddadc’ és vàlida en el conjunt alfabètic∑ = {a, b, c, d, e,}.
3 . Longitud de la cadena : El nombre de símbols presents a la cadena es coneix com a Longitud de la cadena. Per a la cadena S = ‘adaada’ la longitud de la cadena és | S | = 6. Si la longitud de la cadena és 0, s'anomena cadena buida.
4 . Kleen Star : És l'operador unari del conjunt de símbols Σ, que dóna el conjunt infinit de totes les cadenes possibles, inclosa λ, de totes les longituds possibles sobre el conjunt Σ. Representat per. Per exemple, per al conjunt Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ...…}.
5 . Kleen Closure : És el conjunt infinit de totes les cadenes possibles del conjunt de l'alfabet, excloent λ. Es denota amb. Per al conjunt Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Llenguatge : L'idioma és el subconjunt del conjunt d'estrelles de Kleene∑ * per a alguns conjunts d'alfabet Σ. El llenguatge pot ser finit o infinit. Per exemple, si un idioma pren totes les cadenes possibles de longitud 2 sobre el conjunt Σ = {a, d}, llavors L = {aa, ad, da, dd}.
Llenguatges formals i autòmats
En teoria d'autòmats, el llenguatge formal és un conjunt de cadenes, on hi ha cada cadena compost de símbols pertanyent al conjunt alfabètic finit Σ. Considerem un llenguatge de gats, que pot contenir qualsevol cadena del conjunt infinit següent ...
mew!
meww!
mewww !! ……
L'alfabet establert per al llenguatge del gat és Σ = {m, e, w,!}. Utilitzeu aquest conjunt per a un model d'autòmats d'estat finit-m. Llavors, el llenguatge formal caracteritzat pel model m es denota amb
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ...…}
L’automatisme és útil per definir un llenguatge perquè pot expressar un conjunt infinit de forma tancada. Les llengües formals no són les mateixes que les llengües naturals que parlem en el nostre dia a dia. Un llenguatge formal pot denotar els diferents estats de la màquina, a diferència dels nostres idiomes habituals. El llenguatge formal s'utilitza per modelar una part del llenguatge natural, com ara la sintaxi, etc. Els llenguatges formals es defineixen mitjançant autòmats d'estats finits. Hi ha dues perspectives principals dels autòmats d'estats finits: els acceptors que poden saber si una cadena està en l'idioma i la segona és el generador que només produeix les cadenes en l'idioma.
Autòmats finits deterministes
En tipus d’autòmats deterministes, quan es dóna una entrada, sempre podem determinar en quin estat es trobaria la transició. Com que es tracta d’un autòmat finit, s’anomena autòmat finit determinista.
Representació gràfica
El diagrama d’estats és el dígraf utilitzat per a la representació gràfica d’autòmats finits deterministes. Entenem-ho amb un exemple. Deixem que els autòmats finits deterministes siguin ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {A}
F = {d} i la funció de transició ser
Forma tabular de representació gràfica
Diagrama d’Estat
Diagrama d'estats d'autòmats d'estats finits deterministes
A partir del diagrama d'estats
- Els estats estan representats per vèrtexs.
- Les transicions es representen mitjançant l’arc etiquetat amb un alfabet d’entrada.
- L'arc entrant únic buit representa l'estat inicial.
- L’estat amb doble cercle és l’estat final.
Autòmats finits no deterministes
Els autòmats on no es pot determinar l’estat de sortida de l’entrada donada s’anomenen autòmats no deterministes. També s’anomena autòmats finits no deterministes, ja que té un nombre finit d’estats. Els autòmats finits no deterministes es representen com el conjunt de 5 –doble on (Q, ∑, δ, qo, F)
Q = conjunt finit d’estats.
Σ = Conjunt d’alfabet.
δ = la funció de transició
on : 
qo = Estat inicial.
Representació gràfica
Els autòmats finits no deterministes es representen amb l'ajut del diagrama d'estats. Deixem que els autòmats finits no deterministes siguin
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Les transicions són
Forma tabular de representació gràfica
Diagrama d’Estat
Diagrama d’estats d’autòmats finits no deterministes
Aplicacions de teoria d’autòmats
Les aplicacions de teoria d'autòmats inclou el següent.
- La teoria dels autòmats és molt útil en els camps de la teoria de la computació, produccions de compiladors, IA, etc.
- Per als compiladors de processament de text i els dissenys de maquinari, els autòmats finits tenen un paper important.
- Per a aplicacions en IA i en llenguatges de programació , La gramàtica lliure de context és molt útil.
- En el camp de la biologia, els autòmats cel·lulars són útils.
- En teoria de camps finits també podem trobar l'aplicació d'Autòmats.
En aquest article, hem après una breu introducció als llenguatges i càlculs de la teoria dels autòmats. Els autòmats existeixen des de la prehistòria. Amb l’invent de les noves tecnologies es veuen molts nous desenvolupaments en aquest camp. Amb quin tipus d’autòmats us heu trobat?
