En la era tecnológica actual, tanto el campo del hardware como del software ha experimentado un tremendo desarrollo. Una de las principales áreas de desarrollo se vio en los métodos de diseño de hardware. Con el tecnología en crecimiento , fue posible implementar el concepto de codiseño de hardware y software. Se desarrollan diferentes métodos mediante los cuales, usando software uno puede diseñar y simular completamente los sistemas de hardware. Uno de esos métodos es la teoría de los autómatas. La teoría de los autómatas es la rama de Ciencias de la Computación que se ocupa de diseñar el modelo abstracto de dispositivos informáticos que siguen automáticamente la secuencia predeterminada de pasos. Este artículo analiza información breve sobre el tutorial de autómatas.
¿Qué es la teoría de los autómatas?
La palabra Automata se deriva del griego, que significa 'autoactiva'. Un autómata es un modelo matemático de la máquina. Autómata consta de estados y transiciones. A medida que se le da la entrada al autómata, éste hace una transición al siguiente estado, dependiendo de la función de transición. Las entradas a la función de transición son el estado actual y los símbolos recientes. Si un autómata tiene un número finito de estados, se conoce como autómatas finitos o Máquina de estados finitos . Los autómatas finitos están representados por una tupla de 5 (Q, ∑, δ, qo, F)
Dónde,
Q = Conjunto finito de estados.
∑ = conjunto finito de símbolos también llamado Alfabeto de los autómatas.
δ = la función de transición.
qo = estado inicial de la entrada.
F = conjunto de estados finales de Q.
Terminologías básicas de la teoría de los autómatas
Algunas de las terminologías básicas de la teoría de los autómatas son:
1 . Alfabeto : Cualquier conjunto finito de símbolos en la teoría de autómatas se conoce como Alfabeto. Representado por la letra∑, el conjunto {a, b, c, d, e,} se llama Conjunto alfabético, mientras que las letras del conjunto 'a', 'b', 'c', 'd', 'e' se llaman símbolos
2 . Cuerda : En los autómatas, una cadena es una secuencia finita de símbolos tomados del conjunto alfabético ∑. Por ejemplo, la cadena S = 'adeaddadc' es válida sobre el conjunto alfabético∑ = {a, b, c, d, e,}.
3 . Longitud de la cadena : El número de símbolos presentes en la cadena se conoce como Longitud de cadena. Para la cadena S = 'adaada', la longitud de la cadena es | S | = 6. Si la longitud de la cadena es 0, entonces se llama cadena vacía.
4 . Estrella Kleen : Es el operador unario del conjunto de símbolos Σ, que da el conjunto infinito de todas las cadenas posibles, incluida λ, de todas las longitudes posibles sobre el conjunto Σ. Representado por. Por ejemplo, para el conjunto Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Cierre Kleen : Es el conjunto infinito de todas las cadenas posibles del conjunto alfabético excluyendo λ. Se denota por. Para el conjunto Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Idioma : El idioma es el subconjunto del conjunto de estrellas de Kleene∑ * para algunos conjuntos de alfabeto Σ. El lenguaje puede ser finito o infinito. Por ejemplo, si un idioma toma todas las cadenas posibles de longitud 2 sobre el conjunto Σ = {a, d}, entonces L = {aa, ad, da, dd}.
Lenguajes formales y autómatas
En la teoría de los autómatas, el lenguaje formal es un conjunto de cadenas, donde cada cadena es compuesto de símbolos perteneciente al conjunto de Alfabeto finito Σ. Consideremos un lenguaje de gatos, que puede contener cualquier cadena del siguiente conjunto infinito ...
¡maullar!
meww!
mewww !! ……
El alfabeto establecido para el lenguaje de los gatos es Σ = {m, e, w,!}. Deje que este conjunto se utilice para un modelo-m de autómatas de estado finito. Entonces, el lenguaje formal caracterizado por el modelo m se denota por
L (m)
L (m) = {'¡miau!', '¡Miau!', 'Mewww', ……}
Autómata es útil para definir un lenguaje porque puede expresar un conjunto infinito en forma cerrada. Los lenguajes formales no son los mismos que los lenguajes naturales que hablamos en nuestro día a día. Un lenguaje formal puede denotar los diferentes estados de la máquina, a diferencia de nuestros lenguajes regulares. El lenguaje formal se utiliza para modelar una parte del lenguaje natural como la sintaxis, etc. Los lenguajes formales se definen mediante autómatas de estado finito. Hay dos perspectivas principales de los autómatas de estado finito: los aceptadores que pueden decir si una cadena está en el idioma y la segunda es el generador que produce solo las cadenas en el idioma.
Autómatas finitos deterministas
En el tipo determinista de autómatas, cuando se da una entrada, siempre podemos determinar en qué estado sería la transición. Como se trata de un autómata finito, se le llama autómata finito determinista.
Representación grafica
State Diagram son los dígrafos utilizados para la representación gráfica de los autómatas finitos deterministas. Entendamos con un ejemplo. Dejemos que los autómatas finitos deterministas sean ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} y la función de transición sea
Forma tabular de representación gráfica
Diagrama de estado
Diagrama de estado de los autómatas deterministas de estado finito
Del diagrama de estado
- Los estados están representados por vértices.
- Las transiciones están representadas por el arco etiquetado con un alfabeto de entrada.
- El arco entrante único vacío representa el estado inicial.
- El estado con círculos dobles es el estado final.
Autómatas finitos no deterministas
Los autómatas en los que no se puede determinar el estado de salida de la entrada dada se denominan autómatas no deterministas. También se le llama autómatas finitos no deterministas, ya que tiene un número finito de estados. Autómatas finitos no deterministas se representa como el conjunto de 5 - tupla donde (Q, ∑, δ, qo, F)
Q = conjunto finito de estados.
∑= Conjunto de alfabeto.
δ = la función de transición
dónde : 
qo = Estado inicial.
Representación grafica
Los autómatas finitos no deterministas se representan con la ayuda del diagrama de estados. Dejemos que los autómatas finitos no deterministas sean
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Las transiciones son
Forma tabular de representación gráfica
Diagrama de estado
Diagrama de estado de autómatas finitos no deterministas
Aplicaciones de la teoría de autómatas
Las aplicaciones de teoría de autómatas Incluya lo siguiente.
- La teoría de los autómatas es muy útil en los campos de la teoría de la computación, producciones de compiladores, IA, etc.
- Para los compiladores de procesamiento de texto y los diseños de hardware, los autómatas finitos juegan un papel importante.
- Para aplicaciones en IA y en lenguajes de programación , La gramática libre de contexto es muy útil.
- En el campo de la biología, los autómatas celulares son útiles.
- En teoría de campos finitos también podemos encontrar la aplicación de Automata.
En este artículo, hemos aprendido una breve introducción a los lenguajes y computación de la teoría de autómatas. Los autómatas han existido desde el período prehistórico. Con el invento de nuevas tecnologías se ven muchos nuevos desarrollos en este campo. ¿Con qué tipo de autómatas te has encontrado?
