Expresiones Regulares

-

Las expresiones regulares pueden definir de forma exacta los mismos lenguajes que describen los distintos tipos de autómatas: los lenguajes regulares. Sin embargo, las expresiones regulares ofrecen algo que los autómatas no proporcionan: una forma declarativa para expresar las cadenas que deseamos aceptar.

Por tanto, las expresiones regulares sirven como lenguaje de entrada de muchos sistemas que procesan cadenas.

Algunos ejemplos son los siguientes:

1. Comandos de búsqueda tales como el comando grep de UNIX o comandos equivalentes para localizar cadenas en los exploradores web o en los sistemas de formateo de texto. Estos sistemas emplean una notación de tipo expresión regular para describir los patrones que el usuario desea localizar en un archivo. Los distintos sistemas de búsqueda convierten la expresión regular bien en unAFDo en unAFNy simulan dicho autómata sobre el archivo en que se va a realizar la búsqueda.

2. Generadores de analizadores léxicos, como Lex o Flex. Recuerde que un analizador léxico es el componente de un compilador que divide el programa fuente en unidades lógicas o sintácticas formadas por uno o más caracteres que tienen un significado. Entre las unidades lógicas o sintácticas se incluyen las palabras clave (por ejemplo, while), identificadores (por ejemplo, cualquier letra seguida de cero o más letras y/o dígitos) y signos como + o <=. Un generador de analizadores léxicos acepta descripciones de las formas de las unidades lógicas, que son principalmente expresiones regulares, y produce un AFD que reconoce qué unidad lógica aparece a continuación en la entrada.








Comentarios

Publicar un comentario

Entradas populares de este blog

1.3. Lenguajes, tipos y herramientas

-
Imagen
Lenguajes, tipos y herramientas Lenguaje: Subconjunto del universo del discurso. Conjunto de palabras de un determinado alfabeto. "El alfabeto Σ es también un lenguaje sobre Σ." Lenguaje vació: Es aquel que no contiene la cadena vacía ni ninguna otra cadena.     Cardinal ( { Ø } ) = 0     Cardinal ( { λ } ) = 1 Clausula (cierre) positiva de un lenguaje: El lenguaje obtenido uniendo el lenguaje L con todas sus potencias posibles, excepto L0. Obviamente, ninguna clausura positiva contiene la palabra vacía, a menos que dicha palabra esté en L. Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que: L+ = L1 U L2 U L3.... W(∑) = Lenguaje universal de ∑. ∑+ = W(∑) - { λ } Estrella de kleene: Es la unión de todas las potencias de un lenguaje incluso L0. Obviamente, todas las clausuras contienen la palabra vacía. Son evidentes las siguientes identidades: L0 = λ L* = L+ U { λ } L* =L0 U L1 U L2 U L3..... Puest...
Leer más

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

-
Imagen
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 Formalmente: 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 : (perteneciente a Q) estado inicial. F : (perteneciente a Q) conjunt...
Leer más