La teoría de los autómatas es una rama teórica de la informática y las matemáticas. Es el estudio de las máquinas abstractas y los problemas de cálculo que se pueden resolver utilizando estas máquinas. La máquina abstracta se llama autómata. La principal motivación detrás del desarrollo de la teoría de los autómatas fue desarrollar métodos para describir y analizar el comportamiento dinámico de sistemas discretos.
Este autómata consta de estados y transiciones. El Estado está representado por círculos , y el Transiciones está representado por flechas .
Los autómatas son el tipo de máquina que toma una cadena como entrada y esta entrada pasa por un número finito de estados y puede ingresar al estado final.
Existen terminologías básicas que son importantes y se utilizan con frecuencia en los autómatas:
Símbolos:
Los símbolos son una entidad u objetos individuales, que pueden ser cualquier letra, alfabeto o cualquier imagen.
Ejemplo:
1, a, b, #
Alfabetos:
Los alfabetos son un conjunto finito de símbolos. Se denota por ∑.
Ejemplos:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Cadena:
Es una colección finita de símbolos del alfabeto. La cadena se denota por w.
Ejemplo 1:
Si ∑ = {a, b}, varias cadenas que se pueden generar a partir de ∑ son {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Una cadena con cero apariciones de símbolos se conoce como cadena vacía. Está representado por ε.
- El número de símbolos en una cadena w se llama longitud de una cadena. Se denota por |w|.
Ejemplo 2:
w = 010 Number of Sting |w| = 3
Idioma:
Un idioma es una colección de cadenas apropiadas. Un lenguaje que se forma sobre Σ puede ser Finito o Infinito .
Ejemplo 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Ejemplo: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>