Lenguajes y Autómatas I

  Σ= {x,y,z} xyz *+yxz *

Definicion. Este tipo de autómatas tiene la capacidad de estar en varios estados a la vez. Esta capacidad a menudo se expresa como la posibilidad de que el autómata “conjeture” algo acerca de su entrada. Por ejemplo, cuando el autómata se utiliza para buscar determinadas secuencias de caracteres (por ejemplo, palabras clave) dentro de una cadena de texto larga, resulta útil “conjeturar” que estamos al principio de una de estas cadenas  y utilizar una secuencia de estados únicamente para comprobar la aparición de la cadena, carácter por carácter. Los AFN son definiciones no tan deseables dentro de los Lenguajes Regulares (LR) porque dificultan su implementación tanto mecánica como informática; aunque en la mayoría de las transformaciones a lo interno de los LR (expresiones regulares a Autómatas Finitos (AF), y gramáticas regulares a AF) conducen a AFN. Los AFN, por tanto, son imprescindibles en el análisis lexicográfico y el diseño de los lenguajes de programación. Punto de vista in...

Definición.  Los automatas finitos deterministas ( AFD) son ideales dentro de los lenguajes regulares por su cercanía formal hacia la creación de máquinas de reconocimiento fundamentalmente , en tanto sus transiciones son únicas por símbolo, pudiendo a la hora de su implementación en software, matemática y física realizarse con mayor facilidad. Un AFD tiene un conjunto finito de estados y un conjunto finito de símbolos de entrada. El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado al que el autómata puede hacer la transición a partir de su estado actual. Un estado se diseña para que sea el estado inicial, y cero o más estados para que sean estados de aceptación. Una función de transición determina cómo cambia el estado cada vez que se procesa un símbolo de entrada. Cómo procesa cadenas un AFD. Lo primero que tenemos que entender sobre un AFD es cómo decide si “aceptar” o no una secuencia de símbolos  de entrada. El “len...

  Σ = {a,b} a *ba+aba *

Automata Finito.  Definición.  Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final.  Clasificacion. Los autómatas finitos no deterministas (AFN): N o tienen restricciones en cuanto a las etiquetas de sus líneas. Un símbolo puede etiquetar a varias líneas que surgen del mismo estado, y ϵ, la cadena vacía, es una posible etiqueta. Los autómatas finitos deterministas (AFD): Tienen, para cada estado, y para cada símbolo de su alfabeto de entrada, exactamente una línea con ese símbolo que sale de ese estado.

 

Σ   = q 0=  a q 1 q 1=  b  q 2  + a  q 3    λ q 2=    c  q 2  + b  q 3    λ q 3=  c  q 4  +     λ q 4=  b  q 4  + a  q 3    λ __________________ q3= c (b *  +a * ) q2= c *   + b [c (b *  +a *   )] q1= b {c *  +b[c(b *  +a *   )] } + a [c(b *  +a * )] q0= a(b{c *  +b[c(b *+a * )] } + a[c(b *  +a * )] _______________________________ q4= b *  +a q3 q3= c(b * + a ) *   q2= c *  +b (c(b *  +a ) * ) q1= b  (c * (b+a)(c(b *+a * )) ) q0=a (b(c * +(b+a) (c(b *+a * )) ))

  q 0= 0  q 0 + 1  q 1 q 1= 1  q 1+ 0  q 2  λ q 2= 1   q 2  λ +   1   q 2  λ q 0= 0 * + 1  q 1 q 1= 1 * + 0   q 2   λ q 2=  1 * + 0 * q 2=  1 * + 0 * q 1=  1 *+ 0 (1 * + 0 *) q 0 =  0 * + 1 (1 *+0 (1 *+0 *))

Algoritmo. Observar el automata.  Se analiza estado estado por estado  convertir cada estado en una ecuacion  Revisar cada movimiento del estado  Concatenar  Tomo estado por estado  Colocar la estrella de Kleene  Teniendo la ecuaciones se resuelve de abajo hacia arriba Sustituir valores Ejemplo:  q0= 1 q0 + 0 q1 λ q1 = 1 q1 λ  + 0 q0 q0=1 * + 0 q1 q1=1 * + 0 q0 q1= 1 *+0 q0 q0= 1 *+0(1 *+0q0 )

 Expresiones Regulares: es una descripcion Son faciles y compactas al leer. Sinonimo de automata.  Formato de programación.  Los primeros digitos son letras poer ejemplo el CURP   1. S INONIMO DE AUTOMATA FINITO. R: Maquina Estado Finito 2. ES EL ESTADO FINAL R:Aceptacion.  3.  FUNCION EN LA QUE SE BASA UN AUTOMATA R:Transicion  4.  FINALIDAD AL RECONOCER LENGUAJES DE ESTE TIPO R:Regulares 5.  LOS LENGUAJES REGULARES PERTENECEN A ESTOS LENGUAJES FORMALES R:Formales 6.  SE REPRESENTA CON LA LETRA SIGMA R:Alfabeto 7. ES EL PRIMER ESTADO R:Inicial 8.F UNTOS DONDE SE DESPLAZARA EL AUTOMATA R:Estado 9.  REPRESENTACION SIMBOLICA DE UN ESTADO FINITO R:Grafo

 Fases de un compilador. A grandes rasgos, un compilador es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y lo traduce a un programa equivalente en otro len guaje, el lenguaje objeto. Como parte importante de este proceso de traducción, el compilador informa a su usuario de la presencia de errores en el pro grama fuente, A primera vista, la diversidad de compiladores puede parecer abrumadora. Hay miles de lenguajes fuente, desde los lenguajes de programación tradicionales, como FORTRAN o Pascal, hasta los lenguajes especializados que han surgido virtual mente en todas las áreas de aplicación de la informática. Los lenguajes objeto son igualmente variados; un lenguaje objeto puede ser otro lenguaje de programación. 1.-Analizador léxico: Lee la secuencia de caracteres de izquierda a derecha del programa fuente y agrupa las secuencias de caracteres en unidades con significado propio (componentes léxicos o “tokens” en ingles). • Las palabras clave, identif...

Estructura de  un Traductor.  Un traductor es un programa que tiene como entrada un texto escrito en un lenguaje (lenguaje fuente) y como salida produce un texto escrito en un lenguaje (lenguaje objeto) que preserva el significado de origen. Ejemplos de traductores son los  ensambladores y los compiladores. En el proceso de traducción se identifican dos fases principales: * Fase de análisis * Fase de Síntesis Ensambladores El programa ensamblador es el programa que realiza la traducción de un programa escrito en ensamblador a lenguaje máquina. Tipos de ensambladores: *Ensambladores básicos. *Ensambladores modulares, o macro ensambladores *Ensambladores modulares 32-bits o de alto nivel 1. Ejemplos de traductores son los ensambladores y los compiladores. 2.En el proceso de traducción se identifican dos fases principales:

 Lenguajes.  El lenguaje es un sistema de signos a través del cual los individuos se comunican entre sí. Por extensión, se usa también la palabra lenguaje para referir a todo tipo de sistema de señales que permiten comprender un determinado asunto o transmitir un mensaje. Por ejemplo, el lenguaje musical, el cual tiene un sistema de escritura propio. Aunque normalmente la palabra lenguaje se usa para referir la capacidad de la comunicación entre los humanos, investigaciones recientes apuntan que algunas especies también poseen códigos de comunicación mediante signos sonoros y corporales. Tipos.  Lenguaje natural Este nivel se refiere a las  lenguas que hablamos para comunicarnos  entre nosotros, las que utilizamos  de manera habitual día a día  (castellano, valenciano, catalan, vasco, inglés, francés, etc). Sería el código de comunicación que utilizamos porque nos lo han enseñado desde pequeños y lo hemos ido aprendiendo a medida que nos desarrollamos....

   L={x|x 101}  Σ={0,1}

 L={w|w sea par de unos}  Σ={0,1}