CONCEPTOS BASICOS DE AUTOMATA

 Que es un automata?

La teoria de automatas es el estudio de dispositivos de calculos 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. El objetivo de Turing era describir de forma precisa los límites entre lo que una máquina de cálculo podía y no podía hacer.

1.introduccion a los automatas finitos

 Los autómatas finitosconstituyenunmodeloútilparamuchostiposdehardwareysoftware. ApartirdelCapítulo 2 veremos ejemplos de cómo se emplean estos conceptos. Por el momento, sólo enumeraremos algunos de los tipos más importantes: 

 1. Software para diseñar y probar el comportamiento de circuitos digitales.

 2. El “analizadorléxico” de uncompiladortípico,esdecir,el componentedelcompiladorqueseparaeltexto de entrada en unidades lógicas, tal como identificadores, palabras clave y signos de puntuación. 

 3. Software para explorar cuerpos de texto largos, como colecciones de páginas web, o para determinar el número de apariciones de palabras, frases u otros patrones.

 4. Software para verificar sistemas de todo tipo que tengan un número finito de estados diferentes, tales como protocolos de comunicaciones o protocolos para el intercambio seguro de información.

ejemplo: 

 Modelo de un autómata finito de un interruptor de apagado/encendido(on/off)

 En la Figura anterior se muestra el modelo de autómata finito para el interruptor. Como en todos los autómatas f initos, los estados están representados mediante círculos; en este ejemplo, hemos denominado a los estados on y off. L

que  es una cadena de carecteres?

una cadena de caracteres es una secuencia finita de simbolos seleccionados de algun alfabeto. Por ejemplo, 01101 es una cadena de alfabeto binario p={0,1}. La cadena 111 es una cadena de dicho alfabeto

que es la cadena vacia?

la cadena vacia es aquella cadena que presenta cero apariciones de simbolos. Esta cadena, designada por E, es una cadena que puede construirse en cualquier alfabeto

potencias de un alfabeto?

si p es un alfabeto, podemos expresar el conjunto de todas las cadenas de una determinada longitud de dicho alfabeto utilizando una notacion exponencial

Un alfabeto, es un conjunto de símbolos finitos no vacíos que se representan con el símbolo sigma