Lenguajes y Autómatas 1

 

Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino, es decir, es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado , tal que para un símbolo  del alfabeto, existe más de una transición  posible. La definición formal de AFND se basa en la consideración de que a menudo según los algoritmos de transformación de expresiones y gramáticas regulares a AF terminan obteniéndose autómatas con transiciones múltiples para un mismo símbolo o transiciones vacías. Independientemente que sean indeseables, sobre todo para la implementación material, fundamentalmente mecánica, de los autómatas finitos, son imprescindibles durante la modelación de analizadores lexicográficos de los elementos gramaticales de los lenguajes de programación, llamados tókens, como literales numéricos, identificadores, cadenas de texto, operadores, etc. Los AFND sondefiniciones no tan deseable...

Un autómata finito determinista (abreviado AFD) es un caso especial  de un autómata finito  no determinista  en el cual. Ningún estado  tiene una transición Є es decir, una transición con la entrada Є, Para cada  estado   s   y cada símbolo  de entrada a, hay  a lo sumo  un arista  etiquetada  a   que sale  de   s . Un autómata finito tiene a lo sumo una transición  desde cada  estado con cualquier entrada. Si se esta usando una tabla de transiciones para representar  la función  de transición de un AFD, entonces cada entrada en la tabla de transiciones es solo un solo estado. Como consecuencia, es muy fácil determinar si un autómata finito determinista acepta o no  una cadena de entrada, puesto que hay a lo sumo un camino desde el estado de inicio etiquetado con esa cadena.  El siguiente  algoritmo  muestra  como simular el comportamiento de un AFD con una cadena de e...

 

Conceptos: Definición y calsificación del automata finito (AF) Los autómatas finitos son reconocedores; sólo dicen “sí” o “no” en relación con cada posible cadena de entrada. Los autómatas finitos pueden ser de dos tipos: Los autómatas finitos no deterministas (AFN) no 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.   Tanto los autómatas finitos deterministas como los no deterministas son capaces de reconocer los mismos lenguajes. De hecho, estos lenguajes son exactamente los mismos lenguajes, conocidos como lenguajes regulares, que pueden describir las expresiones regulares. Autómata Finito No Determinista (AFND) para una expresión regular Intuitivamente...

  q0 = 0q0+1q1 q1 = 1q1+0q1λ q2 = 1q2λ+0q2λ   q0 = 0*+1q1 q1 = 1*+0qλ q2 = 1*+0   q2 = 1*+0* q1 = 1*+0(1*+0*) q = 0*+1(1*+0(1*+0*))  q0= aq1                                                           q4=b*+aq3 q1=bq2+aq3e                                                   q3=c(b*+a*) q2=cq2+bq3e                                                  q2= c*+b(c(b*aq3)) q3=cq4+e                                                    ...

Pasos para convertir un autómata a una expresión regular expresión regular  representación automática de un autómata. Concatenación: La concatenación es la acción y el efecto de encadenar conceptos, ideas, números, códigos o átomos para crear una secuencia o conjunto interconectado. La palabra concatenación deriva del latín concatenatio, compuesta por el prefijo con-, que se refiere a una unión, catena, que significa “cadena”, y el sufijo -ción, que indica “acción y efecto de”. De esta manera, concatenación es etimológicamente la acción y efecto de juntar elementos para formar una cadena.  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 x seguida de una copia de y. paso: -se toma cada uno de los estados y ver a hacia dónde y representar matemáticamente. -tomamos el primer estado inicial que sería q0, tomando el valor de 1 regresa a mismo estado. -representamos con el alfabeto vacío ya ...

Una expresión regular es una cadena de caracteres que es utilizada para describir o encontrar patrones dentro de otros strings, en base al uso de delimitadores y ciertas reglas de sintaxis. La mayoría de los programadores no se dan el tiempo de aprender a aplicar las expresiones regulares, lo cual es una lástima ya que son de gran utilidad. Cuando aprendas a aplicar las expresiones regulares, te darás cuenta de lo poderosas que son, la gran cantidad de problemas que pueden resolver, y lo mucho que aumentará tu productividad al programar. 1. SINONIMO DE AUTOMATA FINITO Maquina estado finito  2. FUNCION EN LA QUE SE BASA UN AUTOMATA Transición  3. ES EL ESTADO FINAL Aceptación  4. FINALIDAD DEL AF EN EL TEXTO DE RECONOCER LENGUAJES DE ESTE TIPO Regulares  5. SE REPRESENTA CON LA LETRA SIGMA Alfabeto  6. LOS LENGUAJES REGULARES PERTENECEN A ESTOS LENGUAJES Formales  7. PUNTOS DONDE SE DESPLAZARA EL AUTOMATA Estados  8. ES EL PRIMER ESTADO Inicial 9. REPRE...

  FASES DE UN COMPILADOR: Los compiladores son programas de computadora que traducen de un lenguaje a otro. Un compilador toma como su entrada un programa escrito en lenguaje fuente y produce un programa equivalente escrito en lenguaje objeto. • Un compilador se compone internamente de varias etapas, o fases, que realizan operaciones lógicas.       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, identificadores, operadores, constantes numéricas, signos de puntuación como separadores de sentencias, llaves, paréntesis, etc. , son diversas clasificaciones de componentes léxicos. 2.-Análisis sintáctico: Determina si la secuencia de componentes léxicos sigue la sintaxis del lenguaje y obtiene la estructura jerárquica del programa en forma de árbol, donde los nodos son las construcciones d...

  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. 1. Ejemplos de traductores son los ensambladores y los compiladores. 2. En el proceso de traducción se identifican dos fases principales:

  Es un conjunto de cadenas, de todas las seleccionadas de un Σ*. donde Σ determinado el alfabeto se denomina lenguaje. Si Σ es un alfabeto y L Σ*, entonces L es un lenguaje de Σ. Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos esta que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un súper conjunto de Σ. La elección del termino "lenguaje" puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el Ingles, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C.

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

 

 Lo  que me gusta de la clase es que aprendemos un nuevo lenguaje de los autómatas es como conocer un nuevo lenguaje y aprender del aparte de que las clases son muy interactivas.