La teoría de los autómatas (también conocida como teoría de la computación ) es una rama teórica de las ciencias de la computación y las matemáticas, que se ocupa principalmente de la lógica de la computación con respecto a las máquinas simples, denominadas autómatas.
Automata* permite a los científicos comprender cómo las máquinas calculan las funciones y resuelven problemas. La principal motivación detrás del desarrollo de la Teoría de Autómatas fue desarrollar métodos para describir y analizar el comportamiento dinámico de sistemas discretos.
Los autómatas se originaron de la palabra «Autómata», que está estrechamente relacionada con «Automatización».
Terminologías básicas de la teoría de la computación:
Ahora, comprendamos las terminologías básicas, que son importantes y se usan con frecuencia en la teoría de la computación.
Símbolo:
Un símbolo (a menudo también llamado carácter ) es el bloque de construcción más pequeño, que puede ser cualquier alfabeto, letra o imagen.
Alfabetos (Σ):
Los alfabetos son un conjunto de símbolos, que siempre son finitos .
Cuerda:
Una string es una secuencia finita de símbolos de algún alfabeto. Una string generalmente se denota como w y la longitud de una string se denota como |w| .
Empty string is the string with zero occurrence of symbols, represented as ε.
Number of Strings (of length 2)
that can be generated over the alphabet {a, b}:
- -
a a
a b
b a
b b
Length of String |w| = 2
Number of Strings = 4
Conclusion:
For alphabet {a, b} with length n, number of
strings can be generated = 2n.
Nota: Si el número de símbolos en el alfabeto Σ está representado por |Σ|, entonces un número de strings de longitud n, posible sobre Σ es |Σ| norte _
Representación de cierre en TOC:
L + : Es un cierre positivo que representa un conjunto de todas las strings excepto strings nulas o ε.
L * : Es » Kleene Closure «, que representa la ocurrencia de ciertos alfabetos para alfabetos de idiomas dados desde cero hasta un número infinito de veces. En el que también se incluye la string ε.
De las dos afirmaciones anteriores, se puede concluir que:
L* = εL+
Example:
(a) Regular expression for language accepting all combination of g's over Σ={g}:
R = g*
R={ε,g,gg,ggg,gggg,ggggg,...}
(b) Regular Expression for language accepting all combination of g's over Σ={g} :
R = g+
R={g,gg,ggg,gggg,ggggg,gggggg,...}
Nota: Σ* es un conjunto de todas las strings posibles (a menudo conjunto de potencia (no es necesario que sea único aquí o podemos decir multiconjunto) de string) Por lo tanto, esto implica que el lenguaje es un subconjunto de Σ*. Esto también se denomina «Kleene Star ” .
Kleene Star también se denomina «Operador de Kleene» o «Cierre de Kleene» . Los ingenieros y los profesionales de TI utilizan Kleene Star para lograr todo el conjunto de strings que se incluirán a partir de un conjunto determinado de caracteres o símbolos. Es un tipo de operador unario. En la metodología Kleene Star, todos los elementos individuales de una string determinada deben estar presentes, pero se pueden incluir elementos adicionales o combinaciones de estos alfabetos en cualquier medida.
Example:
Input String: "GFG".
Σ* = { ε,"GFG","GGFG","GGFG","GFGGGGGGGG","GGGGGGGGFFFFFFFFFGGGGGGGG",...}
(Kleene Star is an infinite set but if we provide any grammar rules then it can work as a finite set.
Please note that we can include ε string also in given Kleene star representation.)
Idioma:
Un idioma es un conjunto de strings , elegido de algún Σ* o podemos decir: ‘ Un idioma es un subconjunto de Σ* ‘ . Un lenguaje que se puede formar sobre ‘Σ’ puede ser Finito o Infinito .
Example of Finite Language:
L1 = { set of string of 2 }
L1 = { xy, yx, xx, yy }
Example of Infinite Language:
L1 = { set of all strings starts with 'b' }
L1 = { babb, baa, ba, bbb, baab, ....... }