Lenguajes y Autómatas I

 

 

  xyz* + yxz* Autómata:

  Definición de autómata finito no determinista Es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un s í mbolo a ∈ Σ del alfabeto, existe más de una transición δ (q,a) posible. Todo AFND puede ser convertido en un AFD equivalente. Autómatas finitos no deterministas Un autómata finito “no determinista” (AFN) 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. Punto de vista informal de los autómatas finitos no deterministas El lenguaje de un AFN Como hemos sugerido, un AFN acepta una cadena w si es posible elegir cualquier secuencia de opciones   del estado siguiente, a medida que se leen los caracteres de w, y se pasa del estado inicial a cualquier estado  de aceptación. El hecho de que otras opciones que empleen los símbolos de entrada de w lleven a un estado de...

  Autómata  finito determinista (AFD) Es aquel que sólo puede estar en un único estado después de leer cualquier secuencia de entradas. 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. El término “autómata finito” hace referencia a la variedad determinista. lenguaje que utiliza El lenguaje de un AFD es el conjunto de todas las cadenas w que  el AFD acepta. Hay disponibles dos notaciones más cómodas para describir los autómatas: 1. Un diagrama de transiciones. 2. Una tabla de transiciones, que es una ordenación tabular de la función δ , la cual especifica el conjunto  de estados y el alfabeto de entrada. Diagrama de transiciones Un diagrama de transiciones de un AFD A = (Q, Σ , δ ,q0,F) es un grafo definido como sigue: a) Para cada estado de Q, existe un nodo. b) Para cada estado q de Q y cada símbolo de entrada a de Σ , sea δ (q,...

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

 Definición de autómata finito Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.   La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky. Definición formal:   E: alfabeto de entrada. Q: conjunto de estados; es conjunto finito no vacío. f: función de transición. f(p,a)=q q0 : (pertenecien...

 Ejercicio 3 q0 =mq1 + hq2λ q1 = aq2λ + hq3λ q2= mq1 q3= aq3λ  q0 =mq1 + hq2 q1 = aq2λ + hq3 q2= mq1 q3= a* q3= a* q2= mq1 q1= a(mq1) + h(a*) q0= m[a(mq1) + h(a*)] + h(mq1) q3= a* q2= mq1 q1= a(m*) + h(a*) q0= m[a(m)* + h(a*)] + h(mq1)     →     E. R

  Ejercicio 2 q0 = aq1 q1 = aq3λ | bq2 q2 = cq2 | bq3λ q3 = cq4 | λ q4 = bq4 | aq3λ       q0 = aq1 q1 = aq3 + bq2 q2 = c* + bq3        ↑ q3 = cq4 q4 = b* + aq3   q4 = b* + aq3 q3 = c(b* + aq3)     →   c (b* + a)* q2 = c* + b(c(b* + a)*) q1 = a (c(b* + a)*) + b (c* +b (c(b* + a)*)) q0 = a (c(b* + a)*) + b (c* + b(c(b* + a)*)) q0 = b (c* + (b + a)(c(b*+a)*))   →     E. R

  Ejercicio 1 q0= 0qo | 1q1                                                       q1= 1q1 | 0q2λ q2=1q2λ | 0q2λ   q0= 0* + 1q1 q1= 1* +0q2             ↑ q2=1* + 0*     q2 = 1* +0* q1= 1* + 0(1* + 0*) q0 = 0* + 1 (1*+0(1* +0*))    →    E. R

Algoritmo 1. Se observa el autómata y se analiza estado por estado 2.Convertir cada estado en una ecuación siguiendo los pasosos siguientes. 3. Escribir el estado inicial  ej. Si se toma el estado q0 : q0  ej. Si se toma el estado q1 : q1  4. Igualar ej. Si se toma el estado q0 : q0 =  ej. Si se toma el estado q1 : q1 = 5. Observar las palabras que tiene  Σ={0,1} 6. Dependiendo del estado que va a tomar se escribe la palabra y el nombre del estado, si el estado se repite se utiliza la estrella de Kleene.    Nota: se le agrega el símbolo landa  λ cuando llega al estado de aceptación para representar que puede tomar el alfabeto vacío. Al representar la ecuación con la estrella de Kleene ya no se utiliza el símbolo de Landa. ej. Si se toma el estado q0 : q0 =1q0      ó        q0=1*   ej. Si se toma el estado q1 : q1=1q1 λ      ó      q1=1* 7. Luego se concatena utilizando  | ó...

Expresiones regulares Es una descripción compacta y fácil de leer de un lenguaje regular.  Ejemplos:    -RFC     -CURP: Los primeros 4 dígitos empiezan con letras. PREGUNTAS DEL CRUCIGRAMA 1.  Sinónimo de autómata finito r. Maquina estado finito 2. Es el estado final r. Aceptación 3. Función en la que se basa un autómata. r. Transición 4. Finalidad del AF 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.Puntos donde se desplazara el autómata. r. Estado 9. Representación simbólica de un estado finito. r. Grafo  Link: https://es.educaplay.com/recursos-educativos/3231109-automatas_finitos.html

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 lenguaje, 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 programa 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 virtualmente 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. Durante la Compilación de un Programa se realizan las siguientes fases:  Preprocesamiento: Transformaciones al Archivo Fuente, previas a la Compilación.  Análisis Léxico: Reconocimiento de los Elementos del Lenguaje. Análisis Sintáctico: Reconocimiento de la Estructura del Lenguaje....

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     Compiladores Un compilador es un programa informático que traduce un programa escrito en un lenguaje de programación a otro lenguaje de programación, es decir programa que permite traducir el código fuente de un programa en lenguaje de alto nivel, a otro lenguaje de ...

  Lenguajes Un lenguaje es un conjunto de cadenas, todas ellas seleccionadas de un subconjunto finito donde el conjunto es un determinado alfabeto. Es una forma de representar información basada en un conjunto finito de signos o símbolos.   Tipos  Lenguajes de bajo nivel: Son lenguajes totalmente dependientes de la máquina, es decir que el programa que se realiza con este tipo de lenguajes no se puede migrar o utilizar en otras máquinas. Al estar prácticamente diseñados a medida del hardware, aprovechan al máximo las características del mismo. Dentro de este grupo se encuentran:   El lenguaje maquina: este lenguaje ordena a la máquina las operaciones fundamentales para su funcionamiento.  Su desventaja es que son bastantes difíciles de manejar y usar, además de tener códigos fuente enormes donde encontrar un fallo es casi imposible.   El lenguaje ensamblador: es un derivado del lenguaje máquina y está formado por abreviaturas de letras y números llamadas mn...

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

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