todos

AUTOMATAS FINITOS
La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”. Antes de que existieran las computadoras, en la década de los años treinta, A. Turing estudió una máquina abstracta que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían calcular.
Conceptos fundamentales de la teoría deautómatas
Alfabetos
Un alfabeto es un conjunto de símbolos finito y no vacío. Convencionalmente, utilizamos el símbolo ∑ para designar un alfabeto. Entre los alfabetos más comunes se incluyen los siguientes:
1. , el alfabeto binario.
2. , el conjunto de todas las letras minúsculas.
3. El conjunto de todos los caracteres ASCII o el conjunto de todos los caracteres ASCII imprimibles.
Cadenasde caracteres
Una cadena de caracteres (que también se denomina en ocasiones palabra) es una secuencia finita de símbolos seleccionados de algún alfabeto. Por ejemplo, 01101 es una cadena del alfabeto binario . La cadena 111 es otra cadena de dicho alfabeto.

La cadena vacía
La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. Esta cadena, designada por ε, es una cadenaque puede construirse en cualquier alfabeto.

Longitud de una cadena
Suele ser útil clasificar las cadenas por su longitud, es decir, el número de posiciones ocupadas por símbolos dentro de la cadena. Por ejemplo, 01101 tiene una longitud de 5. Es habitual decir que la longitud de una cadena es igual al “número de símbolos” que contiene; esta proposición está aceptada coloquialmente, sinembargo, no es estrictamente correcta. Así, en la cadena 01101 sólo hay dos símbolos, 0 y 1, aunque tiene cinco posiciones para los mismos y su longitud es igual a 5. Sin embargo, generalmente podremos utilizar la expresión “número de símbolos” cuando realmente a lo que se está haciendo referencia es al “número de posiciones”.
La notación estándar para indicar la longitud de una cadena Por ejemplo,Concatenación de cadenas
Sean x e y dos cadenas. Entonces, xy denota la concatenación de x e y, es decir, la cadena formada por una copia de seguida de una copia de y. Dicho de manera más precisa, si x es la cadena compuesta por i símbolos e y es la cadena compuesta por j símbolos , entonces xy es la cadena de longitud


Definición de lenguajes mediante descripciones de conjuntos
Eshabitual describir un lenguaje utilizando una “descripción de conjuntos”:

Esta expresión se lee “el conjunto de palabras w tal que (lo que se dice acerca de w a la derecha de la barra vertical)”. Algunos ejemplos son:




Autómatas finitos
Un autómata finito tiene un conjunto de estados y su “control” pasa de un estado a otro en respuesta a las “entradas” externas. Una de las diferenciasfundamentales entre las clases de autómatas finitos es si dicho control es “determinista”, lo que quiere decir que el autómata no puede encontrarse en más de un estado a un mismo tiempo, o “no determinista”, lo que significa que sí puede estar en varios estados a la vez.
Autómatas finitos deterministas
El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno ysólo un estado al que el autómata puede hacer la transición a partir de su estado actual.

Un autómata finito determinista consta de:
1. Un conjunto finito de estados, a menudo designado como Q.
2. Un conjunto finito de símbolos de entrada, a menudo designado como .
3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función detransición se designa habitualmente como . En nuestra representación gráfica informal del autómata, se ha representa mediante arcos entre los estados y las etiquetas sobre los arcos.
Si q es un estado y a es un símbolo de entrada, entonces es el estado p tal que existe un arco etiquetado a que va desde q hasta p
4. Un estado inicial, uno de los estados de Q.
5. Un conjunto de estados finales o de...