Conversion de Expresion Regular a Grafo

 xyz* + yxz*

Autómata finito no determinista

 ¿Qué es?

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.

Una transición puede llevar a múltiples estados.

Construcción

Un AFN se representa esencialmente como un AFD: 

A = (Q,Σ,δ,q0,F) 

donde:

 1. Q es un conjunto finito de estados. 

2. Σ es un conjunto finito de símbolos de entrada. 

3. q0, un elemento de Q, es el estado inicial. 

4. F, un subconjunto de Q, es el conjunto de estados finales (o de aceptación). 

5. δ, la función de transición, es una función que toma como argumentos un estado de Q y un símbolo de entrada de Σ y devuelve un subconjunto de Q. Observe que la única diferencia entre un AFN y un AFD se encuentra en el tipo de valor que devuelve δ: un conjunto de estados en el caso de un AFN y un único estado en el caso de un AFD. 

Lenguaje

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 no aceptación, o no lleven a ningún estado en absoluto (es decir, la secuencia de estados “muertos”), no impide que w sea aceptada por el AFN como un todo.

EJ.

Autómata finito determinista

 ¿Qué es?

Es aquel que sólo puede estar en un único estado después de leer cualquier secuencia de entradas. 

Construcción

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. 

4. Un estado inicial, uno de los estados de Q. 

5. Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.

Notación

Hay disponibles dos notaciones más cómodas para describir los autómatas:

1. Un diagrama de transiciones, que es un grafo 

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.

Diagramas 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) = p. Entonces, el diagrama de transiciones tiene un arco desde el nodo q hasta el nodo p, etiquetado como a. Si existen varios símbolos de entrada que dan lugar a transiciones desde q hasta p, entonces el diagrama de transiciones puede tener un único arco etiquetado con la lista de estos símbolos. 

c) Existe un flecha dirigida al estado inicial q0, etiquetada como Inicio. Esta flecha no tiene origen en ningún nodo. 

d) Los nodos correspondientes a los estados de aceptación (los que pertenecen a 

F) están marcados con un doble círculo. Los estados que no pertenecen a F tienen un círculo simple.

Lenguaje

Ahora podemos definir el lenguaje de un AFD A = (Q,Σ,δ,q0,F). Este lenguaje se designa por L(A) y se define como:

L(A) = {w | δ(q0,w) pertenece a F}

Es decir, el lenguaje de A es el conjunto de cadenas w que parten del estado inicial q0 y van hasta uno de los estados de aceptación. Si L es L(A) para un determinado AFD A, entonces decimos que L es un lenguaje regular.

El “lenguaje” del AFD es el conjunto de todas las cadenas que acepta

EJ.

Ejercicio de Expresión Regular o Autómata

 

3.1 conceptos: definición y clasificación de autómata finito (AF)

 

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.

3.1 Definición formal

Formalmente, un autómata finito es una tupla (Q, Σ, q0, δ, F) donde:

Q: es un conjunto finito de estados;

Σ: es un alfabeto finito;

q0 ∊ Q: es el estado inicial;

δ × Σ → Q: es una función de transición;

F ⊆ Q es un conjunto de estados finales o de aceptación.

En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo con lo determinado por la función de transición. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.

Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.

Clasificación de AF los autómatas se pueden clasificar en:

· Deterministas; Cada combinación (estado, símbolo de entrada) produce un solo estado.

· No Deterministas; Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

Representación:

TABLA	a	b
->p	q
*q	q3	r
q3		r
r	q3

Tablas de transición:
• Filas encabezadas por los estados(Q)
• Columnas encabezadas por los símbolos de entrada ( E )

 

 

Diagramas de transición:

• Nodos etiquetados por los estados(Q)
• Arcos entre nodos etiquetados con (E)
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo

 

Ejercicios

 

q₀ =0q₀ + 1q₁ λ

q₁ =1q₁ + 0q₂ λ

q₂ =1q₂ λ + 0q₀ λ

q₀ =0* + 1q₁

q₁ =1* + 0q₂

q₂ =1* + 0*

q₂ =1* + 0*

q₁ =1* + 0(1* + 0*)

q₀ =0* + 1(1*+0(1*+0*))

Pasos para convertir autómatas a E.R.

1. Revisar autómata

2. Analizar estados  

3. Representar a cada estado como una expresión  

   3.1 los estados de aceptación se representa con épsilon 

ec1: q₀ = 1q₀+0q₁λ

ec2: q₁=1q₁λ+0q₀

4. Si se repite un estado se representa con la estrella de kleene

ec1: q₀ = 1*+0q₁                                                     

ec2: q₁=1*+0q₀

5. Teniendo las ecuaciones se resuelve de abajo hacia arriba 

ec2: q₁=1*+0q₀

-> ec1: q0=1*+0(1*+0q₀)

Expresiones Regulares - ER

Expresiones regulares: 

es un equivalente algebraico para un autómata

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. REPRESENTACION GRAFICA DE UN AUTOMATA FINITO 

Grafo

1.1 COMPILADORES

 

A grandes rasgos, un compilador es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y 10 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.

1.5 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. Es útil pensar en estas fases como piezas separadas dentro del compilador, y pueden en realidad escribirse como operaciones codificadas separadamente aunque en la práctica a menudo se integran.

• Análisis Léxico
• Análisis Sintáctico
• Análisis Semántico
• Generación y Optimización de código intermedio
• Generación de código objeto
• Tabla de símbolos
• Gestor de errores

• 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.

• 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.

• 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 de alto nivel del lenguaje.

•Análisis semántico: realiza las comprobaciones necesarias sobre el árbol sintáctico para determinar el correcto significado del programa.

• Generación y optimización de código intermedio: la optimización consiste en la calibración del árbol sintáctico donde ya no aparecen construcciones de alto nivel. Generando un código mejorado, ya no estructurado, más fácil de traducir directamente a código ensamblador o máquina, compuesto de un código de tres direcciones (cada instrucción tiene un operador, y la dirección de dos operándoos y un lugar donde guardar el resultado), también conocida como código intermedio.

• Generación de código objeto: toma como entrada la representación intermedia y genera el código objeto. La optimización depende de la máquina, es necesario conocer el conjunto de instrucciones, la representación de los datos (número de bytes), modos de direccionamiento, número y propósito de registros, jerarquía de memoria, encauzamientos, etc.

• Tabla de Símbolos: es una estructura tipo diccionario con operaciones de inserción, borrado y búsqueda, que almacena información sobre los símbolos que van apareciendo a lo largo del programa como son: – los identificadores (variables y funciones) – Etiquetas – tipos definidos por el usuario (arreglos, registros, etc.)

• Gestor de errores: detecta e informa de errores que se produzcan durante la fase de análisis. Debe generar mensajes significativos y reanudar la traducción.

1.4.- 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

Ensamblador.

El programa ensamblador es el programa que realiza la traducción de un programa escrito en ensamblador a lenguaje máquina. Esta traducción es directa e inmediata, ya que las instrucciones en ensamblador no son más que nemotécnicos de las instrucciones máquina que ejecuta directamente la CPU.

Tipos de ensambladores

Podemos distinguir entre tres tipos de ensambladores:

·         Ensambladores básicos. Son de muy bajo nivel, y su tarea consiste básicamente en ofrecer nombres simbólicos a las distintas instrucciones.

·         Ensambladores modulares, o macro ensambladores. Descendientes de los ensambladores básicos. Hacen todo lo que puede hacer un ensamblador, y además proporcionan una serie de directivas para definir e invocar macroinstrucciones.

·    Ensambladores modulares 32-bits o de alto nivel. Son ensambladores que aparecieron como respuesta a una nueva arquitectura de procesadores de 32 bits, realizan la misma tarea que los anteriores, permitiendo también el uso de macros, permiten utilizar estructuras de programación más complejas propias de los lenguajes de alto nivel.

Compilador

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 nivel inferior (lenguaje máquina). Generando un programa equivalente a capaz de interpretar.

Componentes en que se divide un compilador:

Análisis Léxico. En esta fase se lee los caracteres del programa fuente y se agrupan en cadenas que representan los componentes léxicos. A la secuencia de caracteres que representa un componente léxico se le llama lexema (o con su nombre en inglés token).

Análisis Sintáctico. Los componentes léxicos se agrupan en frases gramaticales que el compilador utiliza para sintetizar la salida.

Análisis Semántico. Intenta detectar instrucciones que tengan la estructura sintáctica correcta, pero que no tengan significado para la operación implicada.

Generación de código Intermedio. Se puede considerar esta operación intermedia como un subprograma para una máquina abstracta, a esta representación debe tener dos propiedades importantes: debe ser fácil de producir y fácil de traducir al programa objeto.

Optimización de Código. Se trata de mejorar el código intermedio, de modo que resulte un código de máquina más rápido de ejecutar.

Generación de Código. Esta constituye la fase final de un compilador.
Administrador de la tabla de símbolos. Se encarga de manejar los accesos a la tabla de símbolos, en cada una de las etapas de compilación de un programa.

Manejador de errores. Es posible encontrar errores. De esta forma podrán controlarse más eficientemente los errores encontrados en cada una de las fases de la compilación de un programa.

1.3 Lenguajes, tipos y herramientas

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 DE LENGUAJES

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 mnemotécnicos. Las desventajas de este lenguaje siguen siendo prácticamente las mismas que las del lenguaje ensamblador, añadiendo la dificultad de tener que aprender un nuevo lenguaje difícil de probar y mantener.

 Lenguajes de alto nivel Son aquellos que se encuentran más cercanos al lenguaje natural que al lenguaje máquina. Están dirigidos a solucionar problemas mediante el uso de EDD's (Estructuras Dinámicas de Datos).

Son estructuras que pueden cambiar de tamaño durante la ejecución del programa. Nos permiten crear estructuras de datos que se adapten a las necesidades reales de un programa. Se tratan de lenguajes independientes de la arquitectura del ordenador. 

Lenguajes de Medio nivel Estos lenguajes se encuentran en un punto medio entre los dos anteriores. Dentro de estos lenguajes podría situarse C ya que puede acceder a los registros del sistema, trabajar con direcciones de memoria, todas ellas características de lenguajes de bajo nivel y a la vez realizar operaciones de alto nivel.

HERRAMIENTAS

Editores de estructuras: Un editor de estructuras toma como entrada una secuencia de órdenes para construir un programa fuente. El editor de estructuras no solo realiza las fuentes de creación y modificación de textos de un editor de textos ordinarios, sino que también analiza el texto del programa, imponiendo al programa fuente una estructura jerárquica apropiada. Ejemplos:

·       Impresoras estéticas: Una impresora estética analiza un programa y lo imprime de forma que la estructura del programa resulte claramente visible. Por ejemplo, los comentarios pueden aparecer con un tipo de letra especial, y las proposiciones pueden aparecer con una identificación proporcional a la profundidad de su anidamiento en la organización jerárquica de las proposiciones. EJEMPLOS: Word, Excel, Power Point, Photoshop, etc.

·       Verificadores estáticos: Un verificador estático lee un programa, lo analiza e intenta descubrir errores potenciales sin ejecutar el programa. Ejemplos: Editores de C y Pascal. Verificadores estáticos de sintaxis (como lint) permiten detectar muchos errores antes de la compilación. (Algo parecido a lo que se obtiene con la opción -fsyntax- only del compilador de GNU).

·       Intérpretes: Un intérprete realiza las operaciones que implica el programa fuente. Para una proposición de asignación, por ejemplo, un intérprete podría construir un árbol y después efectuar las operaciones de los nodos con forme “recorre” el árbol. Ejemplos: Los intérpretes (para lenguajes como Lisp o Basic, o para programas con sus propios lenguajes interpretados como Derive o Mathematica) Shells de sistemas operativos o de alguna aplicación como un SMBD. 

 

 

Autómata que me acepta par de 1

 

Autómata que me acepta 101